Glibc malloc inefficiency (2016) | Hacker News Reader

Glibc malloc inefficiency (2016)

notes.secretsauce.net

72 pointsibobev51 comments

> but it suggests strongly that the heuristics in malloc either have a bug, or the parameters aren't set aggressively enough

I think the author might be being a bit naive about the role of the allocator. Sure, it could aggressively madvise()/munmap() unused pages to return them to the kernel but as soon as memory is needed again there's a significant overhead to bring it back again. For desktop apps it might be fine to run with few spare pages (and save the RAM) but doing so on a busy server would likely result in different inefficiencies.

jemalloc used to have an option (opt.lg_dirty_mult: https://linux.die.net/man/3/jemalloc) to control how many dirty pages it'd allow to build up before calling madvise(.., MADV_FREE) to give them back to the OS. This allowed one to choose between saving CPU by maintaining free pages or saving RAM by giving them back. Later jemallocs switched to decay-based purging of dirty pages (via a dedicated thread) to get the best of both worlds.

I've heard this as an argument for GC being faster/using less memory in some cases than manual memory management. You can asynchronously return memory to the OS in a separate thread. Boehm GC in particular is really easy to link into an app and use instead of malloc and friends.

GCs by and large are tuned to have a very high amount of spare free memory that they don't return to the OS because GC'd languages by & large churn through memory allocations at a much higher rate.

There are arguments that GCs can be faster, yes, but that speed almost always comes with an increase in memory usage not a reduction. After all asynchronous periodic collection must necessarily increase the transient working set of memory used over immediate synchronous collection.

The advantages of a GC here in typical contexts are that GC'd languages usually allow for compaction which can reduce fragmentation. But this isn't an inherent benefit of a GC. You can have a GC'd language where you don't get this benefit, though, it's not an inherent property of the GC itself.

For example D is a GC'd language, but because D's allocations are allowed to interop with C libraries you can no longer do compaction. There's thoughts on how you could do it with automatic pining but it's not done currently. But either way it's really the lack of raw pointers that make compaction possible, not whether or not you have a GC.

About Boehm GC, somebody told me a story about using it at his job for a highly technical simulation program that they sell... it worked unless the customer had data that fooled the GC into thinking it was seeing pointers in data that wasn't pointers, so it never freed memory. I guess it was in 32 bits with much smaller address space. They ended up switching to manual memory management, which wasn't significantly more complicated (in C++).

Such are the tradeoffs with a conservative garbage collector.

I would avoid Boehm GC (and other conservative GCs) in almost all situations.

Have been writing in D that has conservative GC for years.

Yes, on 32-bit platform false pointers are a problem esp as you get closer to 1g for instance.

On the other hand on 64-bit I’ve never seen it at all. The chance of arbitrary long/double to point to some object in the heap area is 1/2^32 smaller and that turns the problem from common nuisance to purely theoretical problem.

I agree. @camgunz' post is very naive. I never use a tool unless I understand it, and having read up on various GCs, conservative GCs are not something I could ever trust in production. False pointers cause leaks, and if the pointer graph is highly interconnected as happens with functional programs, then boom. In non-FP programs there's less risk but it's just not worth it I feel.

Memory allocators for manual memory management could return memory asynchronously in a separate thread as well. The call to free() is only required to update some internal bookkeeping in the memory allocator's internal data structures. A separate thread could easily monitor when the data structures that hold raw pages from the OS are completely free, and return them to the OS.

That's what tcmalloc does, at least if you set TCMALLOC_RELEASE_RATE.

I don't think that's completely true. The value TCMALLOC_RELEASE_RATE controls how often tcmalloc returns memory back to the OS, but I don't believe it uses a separate thread for that task.

Hrmm, you’re right. This seems to be among the gratuitous differences between internal and open source tcmalloc.

Have you seen the recently updated GitHub project: https://github.com/google/tcmalloc

It’s the fact that automatic memory memory management can defragment through moving that is key. But there are also some manual memory managers that can defragment through moving as well - even some compatible with the malloc interface.

If I remember correctly you couldn't do this by just re-linking with another manual memory manager though because the application could hold pointers to things in ways you don't understand and then you can't move them, so there has to be some additional indirection on every pointer access that resolves the real location of data in memory.

So I would think this requires some compiler support or some sort of runtime.

If you know more about this or know any cool implementations of it please elaborate!

> so there has to be some additional indirection on every pointer access

We already have this - almost all modern computers have something called virtual memory, that allows you to de-couple your memory addresses from where the memory actually is. This allows you to 'move' memory without changing the addresses that you use to refer to it. You can then defragment memory by mapping two sets of addresses to the same memory physical memory, as long as the holes in the two sets overlap.

In order words, if you have two pages, one with only the first half used, the other with only the second half used, you can copy the used part of the second page into the gap in the first page, and map the old addresses of the second page to the location of the first, now shared, page. You are using twice the address space (which costs just a few bytes in bookkeeping) but have defragmented so you're only using half the physical memory.

You can then completely return the second page, now un-used, to the kernel.

Double-mapping memory is almost always the wrong choice, since TLB entries are a critical resource for software performance. The only time it makes sense to double-map is when your are trying to make the CPU blind to what you are sharing, as seen in some high-performance ring buffer implementations. But this is double-black-diamond stuff, not something that has wide applicability.

But it's only using as many mappings in total as the memory would be if it had not been compacted.

Are there implementations that actually do this?

I would think the page level granularity of virtual memory makes it not that useful for this purpose, since the used and unused parts of the two pages would have to line up nicely and larger objects tend to cause less fragmentation.

I first saw this done in 2009 in the Hound memory allocator. I think it's been tried in or implemented in recent Glibc, but wouldn't swear to that. I think it's been shown to be useful in practice in real applications in a couple of papers.

Fragmentation is often just one pesky object holding onto a whole page. If you have many such pages all with one object it's likely you can map them all together and release most of them.

There are, for example: https://www.youtube.com/watch?v=VMP2w5o4Yco

Their algorithm also addresses your concern of how to make pages “line up”.

This method’s likely subject to the criticisms around this post.

I fully agree that moving is key.

Just to further clarify the terms if someone is looking for more info on this:

In the context of system memory people mostly refer to this as compaction and not defragmentation.

How does this work? Is the application required to call realloc() on its object in order to let the defragmentation happen (and the the application has to update all of its references manually)?

As described on the other side of this thread, it’s done through virtual memory - the virtual address of the object doesn’t need to change, so no need to realloc.

Oh yeah, I mean anything you can do automatically you can do manually.

A core benefit of GC is you can have pretty complex memory management techniques that run more or less totally transparently. You can leverage generations (or defragmentation) to keep allocation latency low, etc.

This assumes glibc can actually shuffle memory locations around, which it can’t. Except for some special cases you can’t return memory to the kernel, you can only stop using it and hope it’s swapped out. Perhaps you could zero it so it compresses well.

Umm.. that's not really true.

Most userspace memory allocators are based on mmap(). Using sbrk() is legacy. The slab allocator (Bonwick, 1994) is the dominant algorithm (both in userspace and the UNIX-like kernels), although there are various flavours and somewhat different implementations of it. Since it uses fixed-sized allocations under the hood, they are nicely packed in pages. Those pages can be released with munmap() once there are no used blocks. Sure, depending on the application and workload, allocations can be become quite distributed amongst the pages over the time, but that is a separate problem.

Also, as another comment states: madvise() is also an option, but it doesn't reclaim the virtual address space. On 32-bit systems VA space exhaustion can be a problem, especially with "modern" applications.

Both glibc and musl libc still uses brk for most allocations. You can see it when strace'ing simple programs. After the linker--which uses mmap for some allocations as it can't use malloc--has finished you'll see brk calls to satisfy application allocations.

Also you can verify in the code, e.g. https://git.musl-libc.org/cgit/musl/tree/src/malloc/expand_h...

I believe OpenBSD's malloc only uses mmap and also aggressively munmap's memory--to better catch application bugs and to keep addresses randomized.

Answers like this is the reason I came back to HN.

Facts and to the point.

    madvise( start, size, MADV_DONTNEED );

start must be page-aligned. size is in bytes, but if you take one byte of a page, you take the whole thing, so clip as appropriate.

this informs the kernel you're done with some part of the memory. mapped things will be re-read and others will act as if zero'd when later accessed. both can be safely dropped without taking space in the swap, instead being newly created when next needed.

Although this is true on Linux, it's worth noting that this behavior doesn't match the specified behavior of posix_madvise.[1] It was also a subject of Bryan Cantril's hilarious "A crime against common sense" Surge 2015 talk (at ~1:06:50).[2]

[1]: https://pubs.opengroup.org/onlinepubs/9699919799/functions/p...

[2]: https://youtu.be/bg6-LVCHmGM?t=3518

it clearly can if malloc_trim works?

I guess I didn't see how long that operation takes though, but it could certainly be useful for long-running processes like web browsers to call it every once in a while...

No, it definately can't. In C one would usually store pointers into memory blocks, which it is impossible to "fix up".

What you can do is search through all allocated memory for full 4K pages which are unused, which can be "given back" to the OS.

However, it's unclear how much benefit there is from doing this. If you give back memory too eagerly, and then need to request more later, you end up thrashing the kernel. Assuming you have some swap space, this unused memory gets swapped out.

It could be (hard to tell, but I do this in my own memory managers) that the memory is technically still assigned to the program, but the pages are marked as unused, in which point there is no "memory" there at all, just address space which you can start using again later. However, it can still look like my program is using something crazy like 1TB of memory.

> No, it definately can't.

Glibc malloc can return memory to the OS. This is what the trim that people are talking about does.

I got tripped up on that statement, too. The problem is that tinus_hn's parent comment started with a false premise: that the only way to return memory to the OS is by moving memory around, which is not the case. I think CJefferson was saying that manual memory allocators can't move memory around (which in the general case is true, but you point out in a different thread there are cases when it can), because the rest of their comment is explaining how they can return memory.

Sorry, I should have been clear I was specifically replying to suggestion that glibc (or any malloc, by which I mean C standard library memory manager) could move memory allocations.

> specifically replying to suggestion that glibc (or any malloc, by which I mean C standard library memory manager) could move memory allocations

But I think malloc can move memory allocations - it can move objects out of a page and return it to the kernel by copying objects into an existing page with a gap and then remapping the old addresses onto the copied page. Then the memory has moved but retains the same address and the old page is returned. See for example the Mesh allocator which does this and still manages to expose a conventional malloc interface.

https://github.com/plasma-umass/Mesh

OK, mesh is doing something very cool and unusual. I've never seen that before (in my defense, it is a 2019 academic paper). It still has its limits, as it can only merge allocations which don't overlap modulo 4096.

Ah, so that's where we are now. It used to be that we didn't clear the memory for performance reasons. Now, we clear the memory for performance reasons. Very entropy. I think I like it.

I mean you can munmap a page if it's not being used…

You can unmap memory.

If you care a lot about this stuff use tcmalloc, and its very helpful tc_malloc_stats()

I agree, and the arena movement in tcmalloc solves the over assignations in ptmalloc when one thread allocates and other frees.

Nevertheless I prefer jemalloc because I find the stats and memory profiling awesome to find leaks or structural over assignation.

I wonder if some particular M_TRIM_THRESHOLD value does better than the default. The author spent some time measuring before and after forcing a trim by attaching a debugger, but it may be more generally useful to tweak the default.

Another option is to use jemalloc[1] instead. Better performance with threads.

It'z possible to use via .so injection with ld_preload.

Limit Memory Allocation (if not necessary)

Multithreaded programs often do not scale because the heap is a bottleneck.

When multiple threads simultaneously allocate or deallocate memory from the allocator, the allocator will serialize them. Programs making intensive use of the allocator actually slow down as the number of processors increases.

Malloc (libc) is the worse memory allocation API to use.

Programs should avoid, if possible, allocating/deallocations memory too often and in particular whenever a packet is received.

In the Linux kernel there are available kernel/driver patches for recycling skbuff (kernel memory used to store incoming/outgoing packets).

Using PF_RING (into the driver) for copying packets from the NIC to the circular buffer without any memory allocation increases the capture performance (around 10%) and reduces congestion issues.

Design Evolution

Basic design of malloc() is to dynamically pre-allocate a pool of memory from the OS in which applications can then take smaller pieces from. malloc() is a standard API having a choice of different allocation algorithms and to mitigate the expensive OS system calls (typically done at program initialization time) during allocation of its system memory. The first memory allocation scheme started with a stack-based memory allocation.

Next came the dynamic-based memory allocation scheme where linked-list and bucket-heap mechanism are used to divide the private-heap using size class approach.

Soon, garbage collection algorithm introduced the initial backend of the memory allocation scheme. Frontend covers the usual malloc() API, et. al.

In 2006, a third pool was introduced (after operating system memory pool and library-based memory pool) called the “arena”. Arena is a jemalloc-term and is intended to deal with different memory types such as different-speed memory bank or NUMA-architecture, as well as memory tied to specific to each of the multiple CPU core or even CPU infinity.

Frontend Evolution Frontend manages the memory being given to the application.

Within the frontend of the memory allocation system, the evolution went in the following order:

- link-list free space - heap-bucket size classes (eliminating an object header) - (Process) Owner encoding - single core local allocation buffers (CLABs) - Epoch encoding - Large-size class memory block by direct mmap() Hazard pointers (safe memory reclamation for lock-free objects) (M.M. Michael, 2004) - Arena memory pool - thread-specific local allocation buffers (TLABs) - constant-time modulo synchronization (early return to OS pool, or FreeBSD madvise call)

Backend Evolution

Backend of the memory allocation system manages the empty, straggling, fragmented or no-longer used memory blocks back to the OS (thereby reducing RSS).

- Pool semantic: Remote f-list encoding, using Treiber stack), (R.K. Treiber, 1986) - buddy algorithm - binary buddy algorithm - BIPOP Table (span-based allocator)(S. Schneider, 2006) aka local free list and - remote free list - segment queue (Quasi-linearizability, Y. Afek, 2010) - multi-core distributed queue (A. Haas, 2013) - k-FIFO queue (T.A. Henzinger, 2013)

> When multiple threads simultaneously allocate or deallocate memory from the allocator, the allocator will serialize them.

Memory allocators designed for multithreaded use will not serialize allocations and frees. Such allocators use thread-local data structures and try to avoid touching non-thread-local structures that require synchronization. I am "S. Schneider, 2006" and that was one of the main points of that paper. Modern memory allocators (tcmalloc, jemalloc, even I believe modern glibc) follow similar designs.

Aye, such evolution tracking we must do for the history of malloc; Thanks, Scott.

Evolution doesn’t always means most efficient or better. :-)

100% agree. You answer shall be read by every engineer trying to improve performance in intensive memory multithread code.

Giving memory back to the OS is usually a pessimization; especially so, if the program runs more than one thread, on more than one core. Therefore, not giving it all back is not a failing, but an optimization.

Is that always true? If a long-living process (like Emacs in that blog post) at some point temporarily uses a lot of more, is it a good idea it keeps hold of that amount of memory forever, even if they don't have any use for it anymore?

It could be, but it's counter-intuitive to me that processes keeping unused memory in use is better for the system.

No, it's total nonsense of course. If you imagine a web browser with lots of tabs open, if someone closes lots of tabs they might be doing it specifically to free up memory.

Even going over physical memory is not a death sentence anymore because of fast SSDs being used for virtual memory. Because that is slower however, freeing up memory will still speed everything up, even if the maximum memory used needs to go over physical memory.

The OS also caches memory mapped pages of files, so memory used means more disk IO from that standpoint as well.

Even disregarding all of that, heaps get fragmented, and if many virtual memory allocations can be given back to the OS, the next time more memory is needed it will be allocated in large, 'virtually contiguous' chunks that start out without fragmentation.

> Is that always true?

"Usually" has a well-defined meaning, readily available from your nearest English dictionary, that is rather opposite to "always".

If a pause in execution of other threads is tolerable, then taking it could be the right choice. But taking it every time is usually (that word again) the wrong choice. So, identify times where it is warranted, and do it just at those times.

Reply on news.ycombinator.com