views:

62

answers:

1

I have heard that 'better-fit' is pretty commonly used, but I don't seem to read much about it online. What are the most commonly used / thought to be the most efficient policies used by heap allocators.

(I admit my vocabulary may be flawed; when I say 'policy' i mean things such as 'best fit,' 'first fit,' 'next fit,' etc)

Edit: I am also particularly interested in how the heap policies of 'better fit' and doug lea's strategy (http://gee.cs.oswego.edu/dl/html/malloc.html) compare. Doug uses a type of best fit, but his approach uses index bins, whereas better fit uses a Cartesian tree.

+2  A: 

C programming environments use the malloc implementation provided by the standard C library that comes with the operating system The concepts in Doug Lea's memory allocator (called dlmalloc) are most widely used in most of the memory allocators in one form or another on UNIX systems. dlmalloc uses bins of different sizes to accommodate objects - the bin closest to the object size is used to allocate the object.

FreeBSD uses a new multi-threaded memory-allocator called jemalloc designed to be concurrent and thread-safe, which provides good performance characteristics when used in multi-core systems of today. A comparison of the old malloc and the new multithreaded one can be found here. Even though it's multi-threaded it still uses the concepts of chunks of different sizes to accommodate objects according to their size (chunk(s) closest to the size of the object are used to allocate the object).

Inside the UNIX kernels the most popular memory allocator is the slab allocator, which was introduced by Sun Microsystems. The slab allocator uses large chunks of memory called slabs. These slabs are divided among caches of objects (or pools) of different sizes. Each object is allocated from the cache which contains objects closest to its size.

As you'd notice the above bin/chunks/slab caches are just forms of the best fit algorithm. So, you can easily assume that the "best fit" algorithm is one of the most widely used malloc algorithm (although memory allocators differ in other important ways).

Sudhanshu
+1 awesome links..
Jack