Hacker News Reader

Comment by dragontamer | Hacker News Reader

General purpose memory-allocation is a lie. Everything has use cases where they're faster than other libraries.

I think that's why we keep seeing newer malloc schemes pop up, because the performance of the heap 100% depends on the use-case, and different people have different use cases.

Still, studying everyone else's heaps (and garbage collectors, a closely related discussion) is probably good for high-performance programmers.

View on HN

Yeah, you're totally right.

Libpas beats other mallocs in WebKit. I also had benchmarks involving non-WebKit workloads and the results were all over the place (sometimes slower than other mallocs by a lot, sometimes faster by a lot - same thing with memory, sometimes more efficient, sometimes less). This didn't surprise me; I've seen this before when writing memory management code.

I think it makes sense for large software projects that use malloc a lot and care about perf to eventually either write their own malloc or to take an existing one and then tune it a lot.

We should have libmetamalloc that tracks a history of program invocations using the actual workload on the actual machine. Cycle through different malloc implementations for each execve(). After gathering enough statistical data select the optimal implementation. The next step would be a basic ML model that looked at a few variables like time of day, args, etc to determine when to switch allocators.

If an OS used such a thing by default it would figure out that it should use libpas on the programs that were faster in your tests. Since most programs have zero effort put into optimizing allocators (or much of anything else) it would likely be a win even given the complexity. Many things are branch predictors if you squint!

Note: Not even I can tell if I'm joking or serious with this comment.

100%, and also I think there's a tendency among people who compare 'higher up the stack' in GC'd languages to manual heap allocation in C/C++ etc. in a way that implies the the latter is almost "free" from a performance POV when in fact underneath the covers in these allocators there's still a lot of the same kind of walking of datastructures that also happens inside a tracing GC.

You can get unpredictable pauses from malloc/free, too.

I think in either case, GC or not, you write something intuitively and then when it becomes an actual problem, you study the patterns and improve them, but most of the time you can leave it alone and the general purpose thing is good enough.

Or if you are in a niche like audio/video or something, you avoid allocations all together during the bulk of the code.

Oh for sure. Premature optimizing is usually bad form.

What is tricky about performance issues in allocation is that they can be hard to profile. There are tools for analyzing GC performance in GC'd languages, but sometimes malloc/free can just be a big black box.

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)

That's one reason I point out a few comments above that certain niches will need to take it into account ahead of time. Eg. An a/v application will typically allocate all buffers up front and re-use them frequently rather than return them to the allocator. A lot of server applications will want to keep per-client memory usage low. For general purposes, there's the general purpose allocator.

Very true. Also video games, and particularly rendering.

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.

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

512 in AVX512 is the number of bits per register. You are off by factor of 8.

Agreed. Thanks for pointing out the mistake.

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

[3] http://bytepointer.com/resources/old_new_thing/20051014_305_...

[4] https://github.com/the-tcpdump-group/libpcap/blob/4c1e516dd2...

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

This is a pretty well-known CS truism, isn't it? One of the first papers I ever fell in love with covers it in detail: https://users.cs.northwestern.edu/~pdinda/ics-s05/doc/dsa.pd...

Reply on news.ycombinator.com