Latest Uploads
Super Shap ... ration Kit

Andy_A

Platdude Spotting

Jayenkai

Nom nom nom

Jayenkai

Rainbow Trout

Pakz

King Salmon

Pakz

Snooker

Jayenkai

Articles + Tutorials > Advanced Techniques ( Created 21 January 2012 | Last Edited 27 January 2012)

Obstacks for low memory and high performance by HoboBen | No Votes
Written in
Monkey
This article applies to C. In garbage collected languages, this is probably what NOT to do

When implementing a low-level data structure, e.g. linked list, hashmaps, it's common that individual elements are less than the smallest size malloc can allocate, (16 bytes on a 32 bit platform, 24 on a 64 bit platform).

For example a singly linked list of one pointer & one integer would use only 8 bytes per node, representing 100% wastage.

To a lesser extent, even medium-sized elements can also suffer some wasted space due to malloc's memory overhead for bookkeeping.

Additionally, multiple calls to malloc for small objects is extremely inefficient because system calls are slow.

Often it is better to allocate an entire chunk of memory in one go, and also free it in one chunk. This is only easy when the memory can be treated as a stack (i.e. LIFO/FILO). When the stack is exhausted, a new chunk of memory is added.

So not only does this reduce memory requirements, it reduces memory fragmentation, increases locality of reference, and decreases the average time to "allocate" a new structure.

malloc internally can only request blocks of a certain size from the OS (usually about 4kb), so in cases where you are treating large chunks of memory as a stack, growing the stack should be no more expensive than the worst case under malloc.

The GNU C Library provides such functionality with Obstacks. If you want to be more portable then you may like to write your own (it wouldn't be very complicated -- if you don't care about growing the stack you can do this in three lines of code).

For the purpose of demonstration, Obstacks will do fine.

As an example, here's a benchmark of a linked list implementation that uses malloc to allocate 12-bytes nodes in the first instance, and sources from obstack_alloc in the second instance.

The benchmark shows how long it took to apply merge sort to a lists of different sizes.





Obstacks can complete some of the tests in about half the time. That's a big win!

This is due to better memory locality.

I'm surprised Obstacks are barely mentioned online. Probably because they rely on the GNU C Library.

This was just a quick write up; I might do a more thorough job later.

When implementing your own, care must be taken to respect memory alignment.

Latest Comments

Posted : Saturday, 21 January 2012, 00:44
HoboBen


Important note, as this only works when memory can be treated as a stack (i.e. you can't free in the middle of it, only at the end), it is sometimes unsuitable and you have to fall back to malloc, which to be fair is incredibly clever about how to reuse memory and attempts to reduce fragmentation.

In the linked list example, the linked list is backed by an inactive list, which *is* treated like a stack. This has an important limitation in that the list cannot shrink unless you empty the entire list first (or "defrag" it).

If you're only growing, mostly only growing, or using a set of near-constant size, obstacks are a big advantage.

However if you are growing and shrinking a set, then this means you will always be holding the maximum size of the set inactive in memory. This is still probably a good trade off.

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 732|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Latest Posts
Steve's Car Buying Disaster
steve_ancell Wed 14:32
New Pound Coin
Jayenkai Tue 14:45
Homefries
steve_ancell Tue 01:47
Jeremy Bloody Kyle
steve_ancell Mon 09:45
GamerBlock
Jayenkai Mon 09:06
Laptop Aaargh...
Jayenkai Mon 07:06
Changing Thumbnail Sizes
Jayenkai Mon 05:27
Technology on Planes
therevillsgames Sat 17:00
London Car/Stab Incident
steve_ancell Sat 12:10
A New Korg Gadget!
Jayenkai Sat 04:53
More

Latest Items
Dev-Diary : Sensitive - Arduboy!
Jayenkai Thu 05:03
Link : Super Shapes Exploration Kit
Andy_A Tue 16:56
Snippet : Skylines
steve_ancell Tue 14:25
Blog : My Arduino experience.
steve_ancell Fri 13:45
Showcase : Infinitron
rychan Tue 03:02
Dev-Diary : PS2 to N64 Adapter
spinal Sun 10:49
Link : Vector Tutorials/Help page.
Pakz Thu 23:00
Blog : mini project
spinal Sun 10:13
Showcase : Blockman Returns
Jayenkai Fri 03:04
Snippet : Wall Tracing on Random Maps (rpg)
rskgames Wed 22:48
Snippet : Path Following
Pakz Mon 16:25
Snippet : Flowers (Jan 2017)
Kuron Thu 01:13
Showcase : Clusters of Hex
therevillsgames Mon 15:01
Article : Maths 101 - Episode 1: Basic Trigonometry
shroom_monk Sun 14:07
Article : Maths 101 - Episode 5: Line Intersection
shroom_monk Sun 14:02
More

Who's Online
Pakz
Thu, at 12:33
Jayenkai
Thu, at 12:32
spinal
Thu, at 12:20
Andy_A
Thu, at 09:58
rychan
Thu, at 09:56
rockford
Thu, at 07:45
steve_ancell
Thu, at 03:36
rskgames
Thu, at 03:09
Evil Roy Ferguson
Wed, at 19:54
9572AD
Wed, at 17:27
Link to this page
Site : Jayenkai 2006-Infinity | MudChat's origins, BBCode's former life, Image Scaler.