Latest Uploads
Invasion V ... prototype

rychan

Invasion V ... Prototype

rychan

Shields 64x64

Pakz

Ffs_Spam

Jayenkai

Hives Screen shot

rychan

Rpg Potion Sprites

Pakz

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 581|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Latest Posts
Manchester Arena Explosion
Jayenkai Wed 04:17
Family
Jayenkai Wed 04:06
RIP - Sir Roger Moore
rockford Tue 15:56
CSS-Me-Do - SoCoder2
Jayenkai Tue 09:41
Any Feature Requests?
spinal Mon 12:02
Switch - Mini Dock
Jayenkai Mon 06:26
AGameAWeek : 2017 - Part One
rychan Mon 05:17
ArdWiiNo?
spinal Sun 12:42
Great Big Youtube thread
Jayenkai Sun 11:13
Time for a new Android Test Doohickey
Jayenkai Sun 07:00
More

Latest Items
Dev-Diary : My Journey into NES Development
rychan Tue 01:53
Showcase : Flappadiddle
Jayenkai Sun 14:39
Snippet : QFind
Jayenkai Sun 13:02
Showcase : Tiny Blocks
Jayenkai Sun 04:08
Showcase : Read Error A
rychan Fri 05:13
Blog : All my makes!
Jayenkai Tue 05:48
Showcase : Infinitron
rychan Mon 18:03
Showcase : Hives
rockford Wed 12:53
Showcase : Quadoban
rskgames Fri 10:11
Blog : My Arduino experience.
steve_ancell Wed 17:02
Showcase : Roguelike Explorer
Pakz Fri 06:59
News : Newsletter #311
Jayenkai Thu 17:27
Link : Super Shapes Exploration Kit
Andy_A Thu 11:09
Dev-Diary : Sensitive - Arduboy!
rychan Thu 17:27
Snippet : Skylines
steve_ancell Tue 14:25
More

Who's Online
Jayenkai
Wed, at 05:34
Socoder
Wed, at 05:30
HoboBen
Wed, at 04:23
rskgames
Wed, at 03:31
therevillsgames
Wed, at 03:26
steve_ancell
Wed, at 03:22
Pakz
Wed, at 03:21
rockford
Wed, at 02:15
spinal
Wed, at 01:19
Dabz
Tue, at 22:58
Link to this page
Site : Jayenkai 2006-Infinity | MudChat's origins, BBCode's former life, Image Scaler.