Author Topic: Allocation strategies  (Read 114 times)

lerno

  • Full Member
  • ***
  • Posts: 239
    • View Profile
Allocation strategies
« on: October 28, 2018, 07:01:28 PM »
One interesting thing would be to make it easy to use allocation transparently.

First of all we introduce a thread local global called "context". There are actually two ways of handling this: either context is a real thread local, or we keep an invisible context pointer locked in a register.

The context is a simple struct

Code: [Select]
type struct Context
{
   i64 thread_id;
   Context *previous;
   Allocator *allocator;
   void *data;
}

We then add func Context *push_context(), which basically creates a new Context, then pushes it on top. And the corresponding pop method that frees the data pointer (if non nil), and switches to the previous context. (Note that the lifetime of the Allocator is not tied to the Context)

The point of all this is that malloc uses the allocator in the current context and not a global allocator. By default the allocator can then be one-per-thread, which prevents need for locks in the allocator.

This functionality has a lot of "giving someone a bazooka to hunt mosquitos with", however it allows us fine grained control over growable arrays, maps and strings.

The usual problem with one of those, is that we need some kind of allocator – but we don't know exactly what is the best. If we want to play PHP we could push a bump allocator on the stack, then free everything when the page request ends. But we could still swap allocators if we needed long lived objects.

Look at Zig's problem... Zig declares "no default allocator" which is a huge problem. To see that, consider this:

Code: [Select]
// Initial design of library function:
char *getBazName(Baz *baz) {
  return baz ? baz.name : "Unknown baz";
}

// New design
char *getBazName(Baz *baz) {
  return baz ? uppercase(baz.name) : "Unknown baz";
}

Now we immediately realize that "uppercase" – by virtue of returning a char* – must allocate a new array. Consequently the real "uppercase" should be uppercase(char *, Allocator *). This also means that getBazName needs an Allocator:

Code: [Select]
char *getBazName(Baz *baz, Allocator *allocator) {
  return baz ? uppercase(baz.name, allocator) : "Unknown baz";
}

Thus the function needs to change when something internal changes. It's very bad. And if some library creator then decides to not explicitly expose the Allocator to configure? Well then you're out of luck trying to get consistent memory handling. Also, those Allocator functions pollutes the function profiles with something you're often not interested in.

The use of a thread local allocator context stack solves those problems.

bas

  • Full Member
  • ***
  • Posts: 217
    • View Profile
Re: Allocation strategies
« Reply #1 on: November 07, 2018, 03:38:49 PM »
Usually you want to hide allocator stuff like this completely in a language. Just like Java/Go do. But the strength
of C is that nothing is hidden from developers, so no funky unexpected stuff is happening. Following your example,
in C, if you want to create an uppercase() function, you either:
  • modify the original input
  • return a pointer to a static buffer
  • allocate so caller has to free