4 ms·

I've seen a few opensource projects archive their custom allocators because they were not beating the system's one or jemalloc. So if you have the skill and tim

I've seen a few opensource projects archive their custom allocators because they were not beating the system's one or jemalloc. So if you have the skill and time then yeah go for it, else stick with general purpose ones.

dragontamer 4y ago
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.)
- thesz 4y ago
  512 in AVX512 is the number of bits per register. You are off by factor of 8.
  - dragontamer 4y ago
    Agreed. Thanks for pointing out the mistake.
mananaysiempre 4y ago
There are a couple of approaches that might legitimately be simpler than using a general-purpose allocator: in a single-pass batch process, just throw things on the floor and let the OS sort it out on exit[1] (I think the D compiler does this); in a multiple-pass batch process, make each pass litter its own room (arena, obstack, etc.) then demolish said room when done (GCC does this or at least did in the past). On the other hand, these may require rearranging the logic somewhat to fit them, so the question of how much rearrangement to tolerate still remains. And, well[4], /* * We divy out chunks of memory rather than call malloc each time so * we don't have to worry about leaking memory. It's probably * not a big deal if all this memory was wasted but if this ever * goes into a library that would probably not be a good idea. * * XXX - this *is* in a library.... */ [1] I am rather dismayed by how Raymond Chen advocates for this for memory[2] but insists it could not possibly be a good idea for Windows GDI handles, no, you stupid sloppy programmer[3]. Maybe because he was involved in GDI from the other side? (Of course, for file descriptors on Unix it’s still the standard practice.) [2] http://bytepointer.com/resources/old_new_thing/20120105_006_when_dll_process_detach_tells_you_that_the_process_is_exiting_your_best_bet_is_j.htm http://bytepointer.com/resources/old_new_thing/20120105_006_... [3] http://bytepointer.com/resources/old_new_thing/20051014_305_thread_affinity_of_user_interface_objects_part_5_object_clean_up.htm http://bytepointer.com/resources/old_new_thing/20051014_305_... [4] https://github.com/the-tcpdump-group/libpcap/blob/4c1e516dd2971810918babcd871e428db53383e4/gencode.c#L221 https://github.com/the-tcpdump-group/libpcap/blob/4c1e516dd2...
- jstimpfle 4y ago
  This "[2] vs [3]" is a good find. I have several possible explanations. It could be the difference of 7 years between those posts. It could also be that Windows Handles can't be cleaned up in userspace. Not how malloc chunks up the "handles" (i.e. pages / regions) that it got from Windows. This is, AFAIK, different than HANDLE's that have to be requested from the system one-by-one and can't be chunked up. (Or am I wrong? I actually don't know a lot about how this works under the hood).

dragontamer 4y ago

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.)

thesz 4y ago
512 in AVX512 is the number of bits per register. You are off by factor of 8.
- dragontamer 4y ago
  Agreed. Thanks for pointing out the mistake.

mananaysiempre 4y ago

There are a couple of approaches that might legitimately be simpler than using a general-purpose allocator: in a single-pass batch process, just throw things on the floor and let the OS sort it out on exit[1] (I think the D compiler does this); in a multiple-pass batch process, make each pass litter its own room (arena, obstack, etc.) then demolish said room when done (GCC does this or at least did in the past). On the other hand, these may require rearranging the logic somewhat to fit them, so the question of how much rearrangement to tolerate still remains. And, well[4], /* * We divy out chunks of memory rather than call malloc each time so * we don't have to worry about leaking memory. It's probably * not a big deal if all this memory was wasted but if this ever * goes into a library that would probably not be a good idea. * * XXX - this *is* in a library.... */ [1] I am rather dismayed by how Raymond Chen advocates for this for memory[2] but insists it could not possibly be a good idea for Windows GDI handles, no, you stupid sloppy programmer[3]. Maybe because he was involved in GDI from the other side? (Of course, for file descriptors on Unix it’s still the standard practice.) [2] http://bytepointer.com/resources/old_new_thing/20120105_006_when_dll_process_detach_tells_you_that_the_process_is_exiting_your_best_bet_is_j.htm http://bytepointer.com/resources/old_new_thing/20120105_006_... [3] http://bytepointer.com/resources/old_new_thing/20051014_305_thread_affinity_of_user_interface_objects_part_5_object_clean_up.htm http://bytepointer.com/resources/old_new_thing/20051014_305_... [4] https://github.com/the-tcpdump-group/libpcap/blob/4c1e516dd2971810918babcd871e428db53383e4/gencode.c#L221 https://github.com/the-tcpdump-group/libpcap/blob/4c1e516dd2...

jstimpfle 4y ago
This "[2] vs [3]" is a good find. I have several possible explanations. It could be the difference of 7 years between those posts. It could also be that Windows Handles can't be cleaned up in userspace. Not how malloc chunks up the "handles" (i.e. pages / regions) that it got from Windows. This is, AFAIK, different than HANDLE's that have to be requested from the system one-by-one and can't be chunked up. (Or am I wrong? I actually don't know a lot about how this works under the hood).