Efficient Malloc

So say you have some flat memory space and you're making a memory manager for it. It's not involved in page tables. This is something in the same vein as the "buddy block" system, only better.

Have an array of doubly-linked lists, the indexes to the array being steps of minimum amounts of memory to allocate. For example, the first linked list pointed to could be for chunks of at least 4 bytes, the second could be for chunks of at least 8, the third for chunks of at least 16, etc. Perhaps after a certain point we would stop doubling it, though, for example, 1024, 2048, 3072, 4096.., although we may still increase our granularity at certain points (while still making it possible to, via a formula, look directly to the right index without a search).

Each linked list is a linked list of available chunks of memory of a size in between its minimum size and the next-highest minimum size in the array. The end of the linked list simply runs off to the beginning of the next linked list, so that if all memory is taken for that chunk size then it automatically resorts to the next higher chunk size.

Of course, when a chunk is allocated it's removed from the linked list. When the chunk is freed it's inserted into the linked list. We can keep a hashtable of memory locations that remembers their sizes and locations of their list elements, or we can just return a memory object that contains more than just a pointer to the free memory.

Now, here's the method for consolidating otherwise adjacent blocks of free memory: when memory is freed, the addresses just before the beginning and just after the end of the chunk can be looked up in the hashtable. If the hashtable says that the memory chunk whose last byte is pointed to by the former is a free one, then the one we've just freed is conjoined with it (the exact location of the linked list item for the other block being stored within the hashtable value), and the same goes for if the memory chunk whose first memory location is pointed to by the latter is recorded as being free. Obviously we update the hashtable whenever we conjoin or split up some free memory, with both the chunk's first and last memory locations.

Oh, I forgot to mention: there is never any searching of these linked lists, because you always pop an item from the beginning of one to allocate a chunk, and insert one somewhere (for example, at the beginning of the appropriate linked list) to free one. (Obviously collisions can and will occur within the hashtable, but that only requires searching 2 or 3 elements now and then, by comparing ints.)