Malloc Challenge

&gt;[libc4life] is aiming for simplicity and leverage; and it makes a real effort to get there by playing on C&#x27;s strengths, rather than just inventing yet another buggy Lisp.<p>Ouch, right in the feels, I&#x27;ve been working on <a href="https:&#x2F;&#x2F;buildyourownlisp.com" rel="nofollow">https:&#x2F;&#x2F;buildyourownlisp.com</a> in my spare time. (EDIT: I was looking for a name for the repo, YABLisp it is.)<p>&gt; coding in C is a welcome therapy after seemingly wasting years exploring various ways of pretending the hidden complexity in my stack was someone else&#x27;s problem<p>I&#x27;ve noticed several older talented programmers express similar feelings. I was watching Casey Muratori&#x27;s Handmade Hero stream, where he writes a game in C from scratch, and he said, I don&#x27;t know who would watch this except aging C programmers.<p>I&#x27;m less than 30 but I already feel like an aging C programmer. Most OOP seems like a morass; I&#x27;ve switched to writing my own projects in C and my prototypes in C-like Python. But I wonder what hope there is for people like us in the industry, which seems to be moving ever further away from this type of programming.

Before I read the article or the comments I thought it would be about rewriting code to <i>not</i> use dynamic allocation, which is IMHO a far more interesting (and challenging to some) exercise. Contrary to common expectations, it often doesn&#x27;t mean e.g. restricting the lengths of inputs, and can result in simpler, more efficient, and less buggy code. From my experience it is usually those with a background in higher-level languages who overuse malloc().

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

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.<p>One of the interesting bits about the article was their memory allocation scheme. Each game frame they&#x27;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()&#x27;d their allocations, they just recycled the pool after each frame had been rendered.<p>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.)<p>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?

All past 15-213 students go in search of their malloc lab solution.

Awesome challenge.<p>Back when I worked in a C&#x2F;C++ shop we&#x27;d use this as an in-person interview question for senior positions. The candidate was never expected to finish but more as a springboard to talk about the pro&#x2F;cons and issues they&#x27;d seen with performance&#x2F;etc of various approaches.

How about: mmap() a few terabytes of virtual space let malloc() be pointer addition and let free() be a no-op?

Let&#x27;s all just agree to use Perl. It&#x27;s just dynamic, functional, OOPy C isn&#x27;t it?<p>J&#x2F;K. I think this is an interesting problem in that its a sandbox for allocation and GC in pretty much any dynamic interpreter&#x27;s implementation. My qualm is that it would be &quot;easy&quot; to tune for the test. Consider the difference between dynamic blocks of a small but fixed size, getting alloc&#x27;d&#x2F;freed in an asynchronous way (a network stack?) versus a pool of variable byte length strings getting shuffled around (a key&#x2F;value store?). Those are simple, but drastically different, strategies for your heap. There won&#x27;t be a &quot;best&quot; answer besides the limits of your problem domain.

A malloc benchmark that doesn&#x27;t measure multithreaded performance is worse than useless.

at UIUC, there&#x27;s a project in the systems class (CS241) that is exactly this. there&#x27;s a leaderboard with projects and how it compares to the system malloc for a variety of metrics<p>this is definitely one of the best projects i ever did in school and a great coming of age project. worst case, there&#x27;s always an implementation at the back of K&amp;R ;)

What&#x27;s the incentive? Credits? Give me a break.<p>It&#x27;s fairly easy to beat the given examples but in the end heap management is heavily dependent on application, client code, platform, hardware and many other criteria. It&#x27;s a very complex problem space and what matters here is how existing important code behaves and continues to behave given that existing code has most likely made assumptions how the heap is managed.<p>glibc is a good example of a perfectly fine compromise not optimized for any particular use case. Anyone who has had performance issues with it has most likely already implemented their own solution for their problem set.<p>It might much more worthwhile to develop a set of malloc like implementations a developer can chose from instead of going for a fits all approach.

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&#x27;t that provide more flexibility in the challenge and be more useful (e.g. for C++&#x27;s std::allocator)?

I&#x27;m trying to build it in MacOS but I&#x27;m inundated with errors. For example malloc_perf.c:39:3: error: implicit declaration of function &#x27;clock_gettime&#x27; is invalid in C99 [-Werror,-Wimplicit-function-declaration] BENCHMARK(&quot;basic&quot;, &amp;c4malloc); ^

its an interesting exercise for learning but the code style is awful.<p>freel instead of freelist? ffs.<p>abbreviating memory to mem is enough of a mistake in the standard library without going further to m like malloc does and some of the examples here.<p>still, much respect, to the coder4life for making such a good effort and having such an awesome name...

Looks like fun. Wish I had time to join in :(

GitHub apparently infests every code snippet in existence. People work for free and GitHub gets the credit&#x2F;branding.