Log in

No account? Create an account
brad's life [entries|archive|friends|userinfo]
Brad Fitzpatrick

[ website | bradfitz.com ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Relocating memory allocator [May. 26th, 2003|01:53 pm]
Brad Fitzpatrick
So, it turns out the memcached takes up no CPU and makes the site blazing fast (even though we're only caching a few object types so far!).

Unfortunately, it did what we suspected: died hard when its address space got fragmented. (In the meantime I restarted the daemons with much smaller sizes, accounting for the bloat which accumulates over a few hours....)

I jotted out notes for an arena allocation scheme where we only malloc large, fixed-size pages and handle our own placement and and recompaction within those pages. However, I can't believe this hasn't been done before.

I want a memory allocator that lets you register a hook when it wants to move allocations around to defragment, so you can update pointers and whatnot. Anybody know of one?

[User Picture]From: brad
2003-05-28 01:14 pm (UTC)
Whoa, yes... this all makes a lot of sense.

I still don't understand why coalescings needs to be O(n). If you keep a mapping of free regions' start and end points, whenever you free a new region, you could check to see if the freed region has free regions on either side of it and combine them. With something like Judy (judy.sf.net), that mapping is pretty cheap, I'd think. Definitely better than O(n).

In any case, powers-of-two slab allocation seems like the best bet here.

(Reply) (Parent) (Thread)
[User Picture]From: taral
2003-05-28 05:59 pm (UTC)
Coalescing can be made O(1) very easily. And slab allocators don't have to be power-of-two. In fact, they're usually not used for that. Slab allocators are used when you have a large number of objects that are _not_ power-of-two sized. The slab allocator is substantially better at reducing fragmentation and minimizing memory usage.
(Reply) (Parent) (Thread)