Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Malloc Challenge

vicsydev.blogspot.com

Post reply on HN
Print view View original

41–50 of 109 posts

Re: Malloc Challenge

#41

Post by EdSharkey »

I recall reading in the last year or two a recount of how a game developer got their PS3 engine to run at 30 or 60Hz framerate by aggressive triple-buffering of their scenes.

One of the interesting bits about the article was their memory allocation scheme. Each game frame they'd allocate a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool. I think this is what you describe as a slab allocator, because they never free()'d their allocations, they just recycled the pool after each frame had been rendered.

I kindof see slab allocator as a happy middle ground between allocating temporary memory from the stack and full-blown free-list allocator (or whatever your classic malloc implementation is.)

Are there any high level languages that have the ability to provision fast memory allocation pools like a slab where garbage collection occurs when the slab is no longer accessible, for instance?

Re: Malloc Challenge

#42

Post by codr4life »

naasking wrote: post #35
codr4life wrote: post #28

Earlier quoted context omitted.

Why wouldn't they? If it turns out to be a good solution for the problem they're trying to solve? There's nothing wrong with coming up with your own solutions, that's why we got brains instead of answering machines.

It is a problem if it's not properly documented. This system will probably outlast their time at that company, so the next poor shmuck is left to figure out what that program is doing.

Agreed, but that's an if; there's no reason to assume anything. And the next scmuck also doesn't need to spend most his time struggling to find a combination of dependencies that still kind of work. There are advantages to owning your code.

Re: Malloc Challenge

#43

Post by codr4life »

throwaway4891a wrote: post #38

See also: - http://locklessinc.com/benchmarks_allocator.shtml ($, use as a minimum performance target) - http://www.nedprod.com/programs/portable/nedmalloc/ - http://phk.freebsd.dk/pubs/malloc.pdf [PDF] (phkmalloc) - https://github.com/gperftools/gperftools (tcmalloc) - https://github.com/ivmai/bdwgc/blob/master/malloc.c - https://github.com/jemalloc/jemalloc - http://gee.cs.oswego.edu/dl/html/malloc.html (dlmalloc)

Thank you, but that's not the problem I'm solving. Any one of those could be used to feed any implementation from the challenge. The idea I'm pushing is using local knowledge to customize memory management, instead of trying to find the perfect one-size-fits-all solution.

Re: Malloc Challenge

#44

Post by wfunction »

What if I want to write a malloc that requires the size to be stored separately? (i.e. one that needs to be paired with free(ptr, length) rather than just free(ptr) for good performance.) Wouldn't that provide more flexibility in the challenge and be more useful (e.g. for C++'s std::allocator)?

Re: Malloc Challenge

#45

Post by JoshTriplett »

EdSharkey wrote: post #41

I recall reading in the last year or two a recount of how a game developer got their PS3 engine to run at 30 or 60Hz framerate by aggressive triple-buffering of their scenes. One of the interesting bits about the article was their memory allocation scheme. Each game frame they'd allocate a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool. I think this is what you descri…

> Are there any high level languages that have the ability to provision fast memory allocation pools like a slab where garbage collection occurs when the slab is no longer accessible, for instance?

Rust has several slab allocation libraries, such as the "slab" crate. They use lifetimes to ensure that the slab outlives the objects stored in it.

Re: Malloc Challenge

#46

Post by codr4life »

wfunction wrote: post #44

What if I want to write a malloc that requires the size to be stored separately? (i.e. one that needs to be paired with free(ptr, length) rather than just free(ptr) for good performance.) Wouldn't that provide more flexibility in the challenge and be more useful (e.g. for C++'s std::allocator)?

The pool reference allocator does just that internally. It prefixes each allocation with a block containing the size among other things. Either base your implementation on top of that or take the idea and run with it.

Re: Malloc Challenge

#47

Post by codr4life »

EdSharkey wrote: post #41

I recall reading in the last year or two a recount of how a game developer got their PS3 engine to run at 30 or 60Hz framerate by aggressive triple-buffering of their scenes. One of the interesting bits about the article was their memory allocation scheme. Each game frame they'd allocate a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool. I think this is what you descri…

The slab reference allocator from the challenge does that, but adds a segmented approach where the memory is allocated in N sized blocks. Go has decent support for doing these kinds of tricks; but nothing really runs faster since there's still too much magic behind the scenes. I suspect the story is the same in Rust land but I honestly never got passed the lifetime hump, too much ceremony for me.

Re: Malloc Challenge

#48

Post by EdSharkey »

JoshTriplett wrote: post #45
EdSharkey wrote: post #41

I recall reading in the last year or two a recount of how a game developer got their PS3 engine to run at 30 or 60Hz framerate by aggressive triple-buffering of their scenes. One of the interesting bits about the article was their memory allocation scheme. Each game frame they'd allocate a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool. I think this is what you descri…

> Are there any high level languages that have the ability to provision fast memory allocation pools like a slab where garbage collection occurs when the slab is no longer accessible, for instance? Rust has several slab allocation libraries, such as the "slab" crate. They use lifetimes to ensure that the slab outlives the objects stored in it.

This is so rad.

Re: Malloc Challenge

#49

Post by MichaelMoser123 »

codr4life wrote: post #15
MichaelMoser123 wrote: post #10

Earlier quoted context omitted.

Depends on the domain - i suspect that this question would cut off qualified application programmers who are not perfectly familiar with lower level/infrastructure code.

Not if they're writing C/C++; it doesn't really matter how hard you try to hide memory management when the whole language is designed around memory and pointers. What kind of programmer is that, anyway? Who can only program specific api's, as long as they don't touch the wrong parts of the language.

There are different strategies for handling perf problems of memory allocation - you can cache blocks of the same size in some linked list within the application (free list) or you can reconsider the allocator/allocation strategy. Both get the job done.

Preferance of the first solution does not make you a worse programmer.

Re: Malloc Challenge

#50

Post by [deleted] »

codr4life wrote: post #15
MichaelMoser123 wrote: post #10

Earlier quoted context omitted.

Depends on the domain - i suspect that this question would cut off qualified application programmers who are not perfectly familiar with lower level/infrastructure code.

Not if they're writing C/C++; it doesn't really matter how hard you try to hide memory management when the whole language is designed around memory and pointers. What kind of programmer is that, anyway? Who can only program specific api's, as long as they don't touch the wrong parts of the language.

[deleted]
Post reply on HN