from Hacker News

A simple, arena-backed, generic dynamic array for C

by david2ndaccount on 10/5/23, 11:19 PM with 23 comments

• by habibur on 10/6/23, 10:20 AM

  And if you are not using arena -- realloc() is your best bet. And no, it won't move your memory around into larger areas every time you call it. Most of the time it will simply bump up the allocation end point. This happens more frequently than you think.

  In my code I don't use allocated_length and used_length seperately in dynamic vectors. Simply realloc() every time one element is added. No measurable difference in speed, and code is much more clean.

• by asicsp on 10/6/23, 10:58 AM

  See also: An easy-to-implement, arena-friendly hash map https://nullprogram.com/blog/2023/09/30/

  Discussion: https://news.ycombinator.com/item?id=37720976

• by fovc on 10/6/23, 2:24 PM

  What’s the difference between this and other dynamic array implementations? I thought they were all data/length/capacity headers with exponential resizing.

  I know when using realloc the old buffer is recycled unlike with this arena, but that seems like more of an arena vs. Malloc distinction, no?

  In contrast the hash map discussion was more interesting to me because it’s a different data structure that’s explicitly arena friendly

• by fovc on 10/6/23, 2:37 PM

  > On average they consume about twice the memory of a fixed array of the same size.

  Not to split hairs, but that’s just the “unfreed” memory overhead.

  If you have 2^n+1 elements, you’ve provisioned 2^(n+1) slots and leaked ~2^(n+1) on top, making the actual overhead there closer to 4x.

  I think that means the average overhead is more like 3x (sometimes 4x, sometimes 2x).

• by yobertz on 10/6/23, 11:41 AM

  I think I would make grow() like this to prevent the mistake of accidentally laying out the array fields in the wrong order.

    void grow(void **ptr, ptrdiff_t *cap, ptrdiff_t *len, arena *a) ...
  
    #define push(s, a) ... grow((void **)&s->data, &s->cap, &s->len)

• by jstimpfle on 10/6/23, 10:47 AM

  The memcpy() from the "specific" slice to the "generic" slice in grow() is technically UB I think. Those slice structures are not the same types.

  Furthermore, a void pointer can be implemented "differently" than a typed pointer. The size of pointers can (theoretically) be different for different types. Any typed pointer roundtrips safely to a void pointer and back, but the inverse doesn't necessarily hold.

  Then again, not sure which implementations might make problems here. For example, keeping a typed version of a void pointer returned by malloc() and using it to free() later is common practice.

• by maccard on 10/6/23, 12:02 PM

  I appreciate the simplicity of this, and it's a great way to learn how memory management works under the hood. It's also a fun series.

  That said, everything in this article is why I prefer C++ to C. All of the scoping is automatic, you get actual type safety, you remove a whole class of bugs around passing in the wrong arena.