All About Libpas, Phil's Super Fast Malloc

A better rule is to be suspicious of anything with “fast” or synonyms in the name. It either won’t be fast or it’ll be insecure.

Its very easy to beat the general purpose ones if you know your exact use case.

Ex: 16-bit pointers is a 65536-sized heap. Assume 8-bytes per element, that's 512KB of space. A bit small, but large enough to so a lot of things.

65536 elements can be represented as a bitmask. The bitmask only takes up 8192-bytes (8KB), which fits inside of 16 AVX512 registers (Intel offers 32x AVX512/ZMM registers btw). Or it fits inside of GPU __shared__ memory.

If you need multithreaded, you perform atomic AND and atomic OR to clear, and set, the bitmask as appropriate.

-------

Do you know the exact size of your heap? The size of the pointer? The amount of parallelism involved? What about the size of the elements? Access pattern? (Bump-alloc'd Linked Lists are a sequential traversal over RAM btw, so that's very efficient), etc. etc.

The 64-bit pointer is overkill for most people's purposes. 32-bits represents 4-billion objects, and if each object is 16-bytes long that's 64GBs of RAM. Right here right now, a 32-bit pointer / custom allocator already offers many benefits over the 64-bit pointer. (half-sized pointers, more data in cache, etc. etc.)

Are there any projects that surgically augment the memory APIs to be more cooperative? Sure `malloc` implementations will make various tradeoffs, but what if the malloc/free APIs were expanded to expose more programmer-intent or cooperative defrag, etc?

- Perhaps `malloc` could ask for an intended lifecycle (think GC generation) that could swap arenas or other algo internals. This opens us up to meta-allocators.

- Perhaps program lifecycle hooks that give allocators more context into how already-allocated memory intends to be accessed. ("Done bootstrapping the server, so now new memory will be accessed by single threads and only live for one request", etc)

- Perhaps the programmer could periodically call `remalloc` to allow objects to be moved or promoted between arenas/generations.

- Perhaps mallocs/frees could be more intelligently batched (where explicit structs/arrays don't normally make sense) for surprise-free defrag or OS allocation.

- Intelligent pairing of malloc/free with explicit notions of intended re-use; some indication of "I will free this and ask for the same memory again in the same call" or auto-struct-ing mallocs which know that we tend stack malloc(foo);malloc(bar);free(bar);free(foo). Avoid any actual OS/memory involvement whatsoever.

- Perhaps `identmalloc` could handle common flyweight patterns of instantiate-unless-exists; e.g. intelligently turn shared state into offsets into a contiguous arenas. This may be more useful in C++ with existing conventions around copy-by-value constructs.

Some of these are indeed components of existing mallocs/allocators (e.g. libpas is type-aware), but my point is that allocators have to jump through hoops to derive heuristics, and these heuristics often amount to "the programmer often intends to use memory like X." Performance engineers then pattern-match for X rather than cooperating with the compiler to expose X intrinsically from the beginning. The above ideas impose slightly different programming paradigms, so there's still the white wale of a perfect drop-in heuristic, but it seems less subject to temporary or local maxima.

So: Are there compelling (albeit slightly less general-purpose) alternatives where the allocator and programmer communicate additional hints or other API contracts that allow the allocator to move away from heuristics and into proven patterns? Or is this basically akin to "use c++/smart pointers or just get a gc"?

I can neither confirm nor deny this awesome conjecture.

Premature optimization is not bad form when it's re-framed as good architecture. So it's not 'usually bad form' to architect something from the outset, using your experience, and that's something everyone understands. This pervasive disdain for premature optimization leads to bad architecture that often leads to expensive rewrites. So because the word optimization is so overloaded and treated with disdain it feels like we need a new language to talk about what's really meant by 'premature optimization' ( the bad kind)