[jll29]

This code is very beautifully written, thanks for sharing.

However, you should consult the book "C: Interfaces and Implementations" by Dave Hanson, which has a library called "Arena" that is very similar to your "Pool"s, and it shows a few more tricks to make the code safer and easier to read (Chapters 5+6, 6 in particular).

D. Hanson's book (written in the 'literary programming' style invented by Donal Knuth) also demonstrates having debugging and production implementations for the same C API to catch memory errors, and his book is from 1997:

  > Copyright © 1997 by David R. Hanson

(He used to be a SE professor I Princeton before getting hired by Microsoft, I believe.)

[cb321]

Kernighan & Ritchie's "The C Programming Language" also has an example implementation of malloc() & free() { for any-size requests as @kragen notes in sibling } in it in like 3 pages (though, sure, it is far from the most efficient implementation). Since it's the last section of the main text, I'd guess that most readers don't get that far (even though it's a short book).

[IgorPartola]

Even if you don’t program in C, I think K&R should be required reading for anyone who writes software for a living. You can finish it in an afternoon, or two days if you actually write and run the code outlined in the book.

My bucket list includes an item to write a novel efficient implementation of malloc/free. I have taken several stabs at this in the past but have never been happy with it. I have no real need of a custom allocator but it is something that I think would be very cool to have under my belt. This was inspired by K&R.

[kragen]

I think you mean "literate programming".

The arena allocator in Hanson's chapter 6 is an arena allocator, not a "pool allocator" in the sense that 8dcc means, which is to say, a constant-time fixed-size-block allocator. It seems that you had the same reading comprehension problem that I did.

The difference is that Hanson's arena allocator can make allocations of any size (his Arena_alloc takes an nbytes argument) and cannot deallocate individual allocations, only the entire arena (his Arena_free takes only an arena pointer as a parameter). A fixed-size-block allocator like the one we are discussing here can only make allocations of a fixed size, but can recycle them individually, not only all at once.

(If Hanson's name sounds familiar, it might be because you've read the lcc book.)

It may be worth noting that Donald Knuth also invented the font used in 8dcc's article.

[actionfromafar]

Honestly, "literary programming" does better explain how Knuth writes code.

[kragen]

Yes, but that name lacks the benefit of implicitly describing other approaches to programming as "illiterate".

[kevin_thibedeau]

Reading the Metafont source is pretty challenging because of all the transclusions. There's a reason why programs aren't written like journal papers.

[kragen]

I think we can probably do better than METAFONT with the benefit of hindsight. Unit tests would help with comprehensibility. Including example outputs, too, like Darius Bacon's "halp", or R-Markdown, Jupyter, doctest, and org-mode can do. Higher-level languages than Pascal would probably be an improvement. Maybe building up the program as a series of versions, like Kartik Agaram's idea of "layers"; I did something similar but less complete in my literate-programming system "handaxeweb". We can do decent typography on a computer monitor now, so in the worst case, we can attempt to leverage interactivity, as so-called "explorable explanations" do.

Both programs and journal papers are mostly written the way they are because of tradition, not because it's the best way we've found to write them. Two examples:

Nobody would intentionally design a programming language to make it impossible to include the kind of diagrams that illustrate this article, but most programming languages are in fact designed in such a way.

Buckminster-Fuller-style "ventilated prose" turns out to be more readable than traditional paragraph formatting in psychology experiments, which is why we use it universally in our programs. But you can't publish a paper formatted that way unless you call it a poem.

[actionfromafar]

Haha, never thought about that!

[kragen]

Knuth did.

[8dcc]

Thank you so much! I will definitely check it out. I also planned on writing an article about arena allocators soon.

[johnisgood]

My minor nitpick regarding the code is the choice of variable names, but other than that, it is indeed easy to read and it is how I implement data structures and whatnot.

I like that there is a more or less exhaustive blog post about it which happens to look nice as well.

[msla]

Aside from the fact it persistently confuses linear time and constant time, it is good.

[8dcc]

You are right, sorry about that. I fixed it on the most recent commit (73526e0).