arenas in the newdle solver
i finally started using arenas and i think i love them
Memory management. Two words that scare everyone away from writing C
code. I think a big part of that is because at some point programmers
collectively decided that granular malloc / free was the way to
manage memory in C. I completely agree with anyone who thinks malloc and
free are scary. There are very few scenarios where I think you should
use them.
Usually when I write C I try to keep just a handful of global or
static variables, keep as much as possible on the stack, and use fixed
size buffers. But after reading about
arena-based memory management I decided to give that a try. I put together a super simple arena
implementation and used it within my solver for newdle. It worked great!
what does
managing memory with arenas look like?
Arenas take a long-lived underlying buffer and slice it up. Instead
of calling malloc to get a little bit of memory from the
system every time you need it, you get one big buffer and then store
objects into slices of that buffer. You can use any buffer as
the backing for an arena.
The tricky part is figuring out how large of a buffer you need. For
most small programs you can just pick a value and adjust it until your
program stops running out of memory. Seriously, you can get a lot of
mileage out of just doubling the size of the buffer over and over until
it’s enough.
For more sophisticated programs, you probably want to define a limit
in terms of the domain, and then figure out how that translates to an
arena size. For example in newdle we might set a word list limit of 500k
words. If we assume a maximum word size of 15 letters, that’ll be 16
bytes per word stored in the arena. So 500,000 × 16 bytes = 8MB buffer.
We also store two pointers to the words in that memory; the full word
list stores a pointer to each word, and then a filtered copy of the
wordlist stores some subset of those pointers. 500,000 × 8 bytes × 2 =
another 8MB needed for pointers. So 16MB total for the buffer should be
sufficient. The program should enforce the domain limits: the
size of the word list and the length of an allowed word. Enforcing those
limits will give clearer feedback than “word list arena out of space”,
and will also ensure the arena does not run out of space.
Sometimes, you’ll notice at this point that you don’t even need an
arena at all, a fixed buffer can handle your data just fine. Arenas work
great when you know how much data you have, but you don’t know exactly
how it will be arranged. You might have a known upper bound on how many
linked list or tree nodes you need, but you don’t know how they’ll be
connected. In this case I was on the fence, but I decided I liked the
version with arenas better (and I wanted to try them!)
Once you have your backing buffer, you can create an
Arena struct for bookkeeping and start allocating objects
from it. As often as possible my structs do
useful defaults when they’re zero initialized, so my Make
function zero-initializes the memory before returning it. I also have
mine set up to simply abort when it’s out of memory. At
some point I’ll add better error handling.
byte wordlistBacking[16 * MEGABYTE];
Arena wordlistArena = ArenaInit(wordlistBacking, sizeof(wordlistBacking));
char *foo = Make(wordlistArena, 16);
// foo now points to 16 bytes of memory inside the wordlistBacking, zero
// initialized by `Make`.
With traditional malloc / free, running out of memory is a very
annoying thing to handle. If malloc fails, then any error
handling you do needs to avoid allocating. A nice perk of arenas is that
if something consumes more memory than you anticipated, it only affects
one arena. Your error handler doesn’t need to assume that the whole
system is out of memory. For now the programs I’m writing don’t need to
do anything fancy, aborting with an error message is fine. If I need to
add better handling later, I’ll add a new Make variant
which returns an error if the arena is empty.
lifetimes
Normally tracking the lifetime of objects in C or C++ is a big
nightmare. Something gets malloc’d somewhere, and you need
to keep track of freeing it exactly once sometime later.
One of the best benefits of arenas is bundling the end of the lifetime
together for a bunch of objects. If your arena has a clear lifetime, so
does everything inside of it.
For small or simple programs it’s really easy. You can set up one
global arena, use it everywhere, and just let it clean up when your
process exits.
Arenas really shine in longer running programs. You can often find a
very natural home for an arena that makes cleanup and lifetimes very
easy to think about. In a server, you might create an arena per-request
to handle allocations related to serving the request. In a game, you
might have an arena per-frame. Tying the arena lifetime to an obvious
scope makes it easier to reason about lifetimes.
My arena header is based on Chris’s arena post at
nullprogram. The arena structure itself is just two pointers. They
mark the start and end of the available arena space. When you ask for an
allocation from the arena, it checks that there’s space available, and
then just bumps up the start pointer.
I usually use a LOCAL_ARENA macro to define a backing
buffer and arena struct in one line. Local arenas are a convenient way
to get an arena that is cleaned up “automatically” when it goes out of
scope. The macro defines its backing buffer
as a function-scoped static variable, so it works on the
assumption that we’re single-threaded. The
Arena struct is allocated on the stack and is not
static. The idea is that we avoid having to do a
malloc or use a VLA, by just reusing the static backing
buffer each time we enter the function.
#define LOCAL_ARENA(name, size) \
static byte _##name[size]; \
Arena name = { (byte*) _##name, (byte *) _##name + size }
I also have a GlobalArena function which gives a pointer
to a global arena. My current implementation just mmaps a
huge 4GB buffer. mmap reserves the virtual address space,
but the pages don’t actually show up as resident memory usage until I
use them. So in newdle for example we allocate a huge 4GB buffer but
only show 16MB of memory usage in practice. The Arena
struct itself is a singleton, so I can call GlobalArena
wherever an arena is needed instead of threading that through code
everywhere.
Arena *GlobalArena(void)
{
static Arena global = {0};
if (global.buf == NULL) {
size reserve = (size) 4 * GIGABYTE; // 4GB
global.buf = mmap(
NULL,
reserve,
PROT_READ | PROT_WRITE,
MAP_ANON | MAP_PRIVATE,
-1,
0
);
if (global.buf == MAP_FAILED) exit(99);
global.end = global.buf + reserve;
}
return &global;
}
I named my allocator Make. It just takes an arena and
size and aborts if the arena’s out of space. Chris’s implementation
takes an alignment parameter and uses that to ensure proper alignment.
He also has a convenience macro that uses _Alignof to
automatically set the alignment correctly. I chose to simplify that and
just accept less optimal alignment. So my version aligns everything to 8
bytes, and wastes some space for smaller objects.
void *Make(Arena *a, size sz)
{
size addr = (uintptr_t) a->buf;
size padding = addr % 8;
if (padding) padding = 8 - padding;
if (a->buf + padding + sz > a->end) {
fprintf(stderr, "arena out of space\n");
abort();
}
a->buf += padding;
void *p = a->buf;
memset(p, 0, sz);
a->buf += sz;
return p;
}
how the newdle solver uses
it
I’ve been testing out arenas in my newdle solver. In a future
version of newdle the solver could be used to tell players which
trophies are possible on a given day, which would be a nice improvement
over the current web version.
WordList is the biggest arena win in newdle. newdle has
a 📚 trophy which is awarded when you use valid scrabble words for every
word in your solution. You can still complete a puzzle without the
books, but you’ll have to argue with your friends about whether it
counts. The word list is loaded from file,
so I can easily reuse the file both on the web version and in the C
solver.
The WordList struct is small, just a
char ** into the word list, a sz tracking how
many words have been added to the word list, and a cap to
track how much space we’ve reserved in the list. The bulk of the word
list lives in the arena memory. Arenas make it quite a bit easier to
keep track of when a WordList is valid.
The main word lists get loaded into the global arena, so we know
those pointers are always valid. The solvers can create their own
filtered word lists. They take an arena parameter and use that arena to
store their results and intermediate word list. Callers can control how
long the results live by passing in an appropriate arena. A filtered
word list is able to reuse the string pointers from the original word
list, so we avoid re-copying all the text.
Long term, I’m not totally sure how the solver will be used. For now,
newdlebot runs daily and sends its findings to our discord server. We
get to see a sample solution of the puzzle, some information about the
longest possible words, and whether donuts are possible. Since this just
runs and then exits, the memory management isn’t really all that
important yet. It was a good testing area for arenas and I think if I
end up incorporating the solver into a server or app in the future
arenas will make it straightforward to control how the memory is used
and cleaned up later.
typedef struct {
str *words;
size sz;
size cap;
} WordList;
static WordList *MakeWordList(size cap, Arena *arena)
{
WordList *wordList = Make(arena, sizeof(WordList));
wordList->words = Make(arena, sizeof(str) * cap);
wordList->cap = cap;
return wordList;
}
static void WordListAdd(WordList *wl, str word)
{
assert(wl->sz < wl->cap, "word list overflow");
if (wl->sz > 0) {
str prevWord = wl->words[wl->sz - 1];
assert(strcmp(prevWord, word) <= 0, "word list must be sorted");
}
wl->words[wl->sz] = word;
wl->sz++;
}
// Loads a word list.
static WordList *LoadWordList(str filename, Arena *arena)
{
WordList *wordList = MakeWordList(MAX_WORDS, arena);
FILE *f = fopen(filename, "r");
if (!f) {
perror("error opening word list: ");
exit(1);
}
char line[32] = {0};
while (fgets(line, countof(line), f) != 0) {
assert(wordList->sz < MAX_WORDS, "too many words in word list");
// Trim the newline.
line[strcspn(line, "\n")] = 0;
// Copy it into the arena buffer and store the pointer to it in the
// word list.
size len = strlen(line);
str w = Make(arena, len + 1);
strlcpy(w, line, len + 1);
WordListAdd(wordList, w);
}
return wordList;
}
static bool CheckWord(str word, WordList *wordList)
{
size lo = 0;
size hi = lo + wordList->sz;
do {
size i = (hi - lo) / 2 + lo;
i32 cmp = strcmp(word, wordList->words[i]);
if (cmp == 0) {
return true;
} else if (cmp > 0) {
lo = i + 1;
} else if (cmp < 0) {
hi = i;
}
} while (lo < hi);
// No words matched.
return false;
}