~skeeto/public-inbox

2 2

Re: Arena allocator tips and tricks

Details
Message ID
<pt5ygbbgieki6kxp3pc3touexwex624x5dlctm6aar3e52lfg7@vh2t5crfhbn7>
DKIM signature
missing
Download raw message
Hi,

I'm really enjoying the post about Arena based data structures. Great work - thanks!

I came up with this realloc method that I use for arena backed strings in a streaming context. Can you have a quick look if it makes sense?

void *realloc(Arena *a, void *ptr, size oldsz, size newsz, size align) {
  if (newsz <= oldsz) {
    return ptr;
  }

  if (a->beg - oldsz == ptr) {
    // pointer to realloc is the last element, we can simply grow it
    alloc(a, newsz - oldsz, align, 1, ARENA_NO_FLAGS);
    return ptr;
  }

  void *newptr = arena_alloc(a, newsz, align, 1, ARENA_NO_FLAGS);
  memcpy(newptr, ptr, oldsz);
  return newptr;
}

Thanks!
Dennis

-- 
Dennis Schön
https://www.dennis-schoen.de

Re: Arena allocator tips and tricks

Details
Message ID
<20231006142505.cuuz4ds2akhxgxgn@nullprogram.com>
In-Reply-To
<pt5ygbbgieki6kxp3pc3touexwex624x5dlctm6aar3e52lfg7@vh2t5crfhbn7> (view parent)
DKIM signature
missing
Download raw message
Neat idea, Dennis! This looks reasonable to me (as long as you don't use 
that reserved name literally) and it should cover common cases, including 
two of my three dynamic array examples — possibly even the third depending 
on access patterns. I hadn't considered recovering and checking against 
the original pointer like that. All this information is already available 
in my dynamic array grow() function, so it could be enhanced in place 
using your idea. I'll have to try this out!

Re: Arena allocator tips and tricks

Details
Message ID
<pbqohviujljceliye6demdvlswno4kgg4unjdh7l7g3ostq5o3@s2xfx3hb237x>
In-Reply-To
<pt5ygbbgieki6kxp3pc3touexwex624x5dlctm6aar3e52lfg7@vh2t5crfhbn7> (view parent)
DKIM signature
missing
Download raw message
Hi Dennis,

The idea behind your "realloc" seems to be fairly common. Ginger Bill
for example keeps track of a `prev_offset` to effectively do the same
thing in his linear allocator article:
https://www.gingerbill.org/article/2019/02/08/memory-allocation-strategies-002/#resize

However, in my experience the "grow" mindset (which usually originates
from using typical malloc like interface) might not always be
appropriate when using an arena. Sometimes, it's simpler to have a
"shrink" mindset instead. That is: A) allocate as much as possible
B) "push" as many items you need into it C) "shrink" the allocation when
done. A (completely untested) pseudo-code example:

	ptrdiff_t nalloced, off;
	int *buffer = arena_alloc_max(a, int, &nalloced);
	bool done = false;
	for (off = 0; !done && off < nalloced; ++off) {
		// ... do "work"
		buffer[off] = ...;
	}
	if (off == nalloced && !done)
		OOM();
	buffer = arena_shrink(a, buffer, int, off);

Aside from being (arguably) simpler, it might also be more efficient
since the bound-check is now done outside the loop. The downside of this
is that the arena cannot be used for anything else until you're done
pushing.

One more thing to be wary of is to avoid unnecessarily creating
over-flexible interfaces. More tightly scoped functions can be assert-ed
more aggressively and thus can be more robust at detecting bugs. For
example, if someone calls arena_grow() with new_size smaller than
old_size, then you know that's a bug and can assert on it. But with
realloc() style interface you can't do that.

Flexible interfaces *can* be useful for simplifying code by avoiding
unnecessary if-elses in the usage code. If that's the case, I'd provide
the "flexible" function *on top* of the more tightly scoped ones. This
way you get to have strict assertions on the tight functions but still
use the flexible function where it actually simplifies the code.

(How likely a bug is to occur also should be taken into account. No
point in doing busywork trying to catch highly unlike bugs).

- NRK
Reply to thread Export thread (mbox)