5 ms·

Just a note about your 'exported memory allocation' API: struct hamt_allocator { void (malloc)(const size_t size); void (realloc)(void

Just a note about your 'exported memory allocation' API: struct hamt_allocator { void *(*malloc)(const size_t size); void *(*realloc)(void *chunk, const size_t size); void (*free)(void *chunk); }; This whole thing could just be: struct hamt_allocator { void *cookie; void* (*realloc) (struct hamt_allocator* h, void* chk, const size_t size); }; With the following constraints: 1. `realloc(H, nullptr, N)` -- allocated N bytes 2. `realloc(H, p, 0)` -- frees the pointer p 3. `realloc(H, p, N)` -- resizes the pointer p And, the user has access to a 'context' (`cookie`) so they can use a (for instance) pool allocation scheme. Personally, I like a slightly different API: struct hamt_allocator { void *cookie; void* (*realloc) (struct hamt_allocator* h, void* chk, const size_t oldsize, const size_t newsize); }; With the following constraints: 1. `realloc(H, nullptr, 0, N)` -- allocated N bytes 2. `realloc(H, p, N, 0)` -- frees the pointer p 3. `realloc(H, p, N, M)` -- resizes the pointer p But I know a lot of people get confused and/or don't like having to pass (& thus keep) so much information to the allocator.

david2ndaccount 3y ago
I generally like this pattern, but why pass the allocator instead of the cookie?
- thechao 3y ago
  If you want to "shim" the API, then it's easier to have the whole previous object, rather than just the cookie.
  - cataphract 3y ago
    You don't need the cookie then. You can just allocate a larger struct (sort of subclassing it). You save a pointer indirection.
    - thechao 3y ago
      There's a limit to what can be crammed into a HN comment!
      - pixelpoet 3y ago
        I have discovered a truly marvelous allocator pattern which this HN comment is too small to contain.
        jjgreen 3y ago
        [350 years later] I have confirmed the optimality of the allocator pattern as a special case in my proof of the Inter-universal Teichmüller theorem (Springer, 879pp).
      - inopinatus 3y ago
        The solution is obviously to realloc the comment.
      - cataphract 3y ago
        Fair enough: struct hamt_allocator { void *(*realloc)(struct hamt_allocator *h, void *chk, size_t oldsize, size_t newsize); }; struct my_allocator { struct hamt_allocator parent; size_t used; char buffer[8192]; }; static void *alloc_func(struct hamt_allocator *h, void *chk, const size_t oldsize, const size_t newsize) { if (!newsize) { return NULL; } if (h && newsize <= oldsize) { return h; } // this cast is allowed by the standard for this purpose __auto_type *alloc = (struct my_allocator*) h; if (newsize > sizeof(alloc->buffer) - alloc->used) { return NULL; } void *ret = alloc->buffer + alloc->used; alloc->used += newsize; if (h && oldsize) { memcpy(ret, h, oldsize); } return ret; } void func_taking_allocator(struct hamt_allocator *h); void user_code() { struct my_allocator alloc = { .parent.realloc = alloc_func }; func_taking_allocator(&alloc.parent); }
torstenvl 3y ago
Sadly, this pattern doesn't work with standard realloc() anymore. C23 makes this undefined behavior due to existing non-conforming implementations. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2464.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2464.pdf
- kazinator 3y ago
  The pattern was never specified as fully working. Not in C99 and C90. It's due to the following reason: it was never specified that realloc(ptr, 0) behaves like free(ptr). The case of size == 0 is not separately discussed in the C99 description of realloc. realloc(ptr, 0) can behave like (free(ptr), malloc(0)), where malloc(0) doesn't necessarily behave like ((void *) 0). Malloc may return a unique object that may be later freed. That is to say, realloc can effectively reduce an object to zero size without freeing it, or possibly even free an object only to replace it with a different, unique zero-sized object. Note that in the case when ptr == NULL, which is discussed in C99, realloc behaves like malloc. So in the case realloc(NULL, 0), we know that it's the same as malloc(0). That's a case when size == 0, and realloc is required to behave like malloc. This is a standard-conforming realloc, and always has been: void *realloc(void *oldptr, size_t newsize) { size_t oldsize = __allocated_size(oldptr); // this handles NULL, and returns 0 void *newptr = malloc(newsize); if (newptr != NULL && oldptr != NULL) memcpy(newptr, oldptr, min(newsize, oldsize); return newptr; } This realloc will not behave like free if malloc(0) returns unique pointers. If you want a realloc-like function that behaves like an "all in one allocator", you have to write your own: void *git_reset_of_allocators(void *oldptr, size_t newsize) { if (size == 0) { free(oldptr); return NULL; } else { // handles all other cases OK return realloc(oldptr, newsize); } }
  - torstenvl 3y ago
    I stand corrected! Thanks :)
- dataflow 3y ago
  POSIX loosened its guarantee here too? https://pubs.opengroup.org/onlinepubs/009696899/functions/realloc.html https://pubs.opengroup.org/onlinepubs/009696899/functions/re... https://pubs.opengroup.org/onlinepubs/9699919799/functions/realloc.html https://pubs.opengroup.org/onlinepubs/9699919799/functions/r...
cataphract 3y ago
The biggest advantages here are not having a single function, but instead: 1. Having a context. 2. Having free and realloc getting the old size. Not having the size passed is more or less consensually regarded as a mistake in the C stdlib.
spacechild1 3y ago
That's also what Lua does: https://www.lua.org/manual/5.3/manual.html#lua_Alloc https://www.lua.org/manual/5.3/manual.html#lua_Alloc
kazinator 3y ago
I would drop the API directly and concentrate on the algorithm. If users integrating HAMT need a different allocator situation, they can solve that problem by themselves, without a run-time indirection shim. You can help those users by providing some macros somewhere like #define hamt_malloc(ctx, x) malloc(x) and so forth, so it can be retargeted in one place. Leave an ignored context argument in place for those who would like to have a run-time switch per-instance.
- hgs3 3y ago
  I've seen this type of API design in C before, but not with a context. I'm curious where HAMT would get the ctx instance to pass to hamt_malloc in this design?
  - kazinator 3y ago
    If the macro doesn't use the argument, it doesn't have to exist. Currently the code does use macros, e.g. mem_alloc(h->ator, size). Firstly, I'd hide the detail of how the allocator is derived from h into the allocator wrapper routines and just make it mem_alloc(h, size). It's mem_alloc which can do h->ator. Now the nice thing is that h always exists. So even mem_alloc ignores the first parameter, we don't have to pass something fictional as an argument: #define mem_alloc(h, size) malloc(size) then remove the h->ator and related cruft. Someone who needs a context for their allocator can hack that in. By the way, if you're going to have allocator providers, you want: #define mem_alloc(h, size) h->ator->alloc(h->ator, size) ^^^^^^^ and not: #define mem_alloc(h, size) h->ator->alloc(size) like the code has it now. Thou shalt not define a C callback interface without a context pointer. Without a context pointer, you cannot have an allocator module where you can bind different allocator arenas to different objects.
- flohofwoe 3y ago
  I used macros in my libraries for overriding the allocation functions before, but have switched to runtime callbacks later, same for logging btw (I'd need to look through the issues list for the exact reasons which led to this decision though). In any case, passing callbacks as part of the initialization "feels" right and I didn't hear any complaints since the switch (and it's definitely a lot more convenient for the library user). Also, if the library calls those function so frequently that the pointer indirection would be a performance problem, then there's arguably something very wrong with the library's design.
lelanthran 3y ago
> But I know a lot of people get confused and/or don't like having to pass (& thus keep) so much information to the allocator. That's not why I think it' a bad idea. I prefer the original because: 1. I can pass use the existing `free`, `malloc` and `realloc` implementations. By using a function with a different set of params I cannot do that. The user has to always write the `realloc` function you propose. 2. The interface for free, malloc and realloc is already documented, I don't have to explain to the programmers what constraints are needed for their memory allocator function. Under your proposal the programmer has to now have, and read, the documentation
flohofwoe 3y ago
The advantage of the alloc/realloc/free interface is that you can simply plug in the standard functions malloc, realloc and free though, and any other allocator implementation which follows this convention without your own wrapper function inbetween.

Just a note about your 'exported memory allocation' API: struct hamt_allocator { void *(*malloc)(const size_t size); void *(*realloc)(void

david2ndaccount 3y ago

I generally like this pattern, but why pass the allocator instead of the cookie?

thechao 3y ago
If you want to "shim" the API, then it's easier to have the whole previous object, rather than just the cookie.
- cataphract 3y ago
  You don't need the cookie then. You can just allocate a larger struct (sort of subclassing it). You save a pointer indirection.
  - thechao 3y ago
    There's a limit to what can be crammed into a HN comment!
    - pixelpoet 3y ago
      I have discovered a truly marvelous allocator pattern which this HN comment is too small to contain.
      - jjgreen 3y ago
        [350 years later] I have confirmed the optimality of the allocator pattern as a special case in my proof of the Inter-universal Teichmüller theorem (Springer, 879pp).
    - inopinatus 3y ago
      The solution is obviously to realloc the comment.
    - cataphract 3y ago
      Fair enough: struct hamt_allocator { void *(*realloc)(struct hamt_allocator *h, void *chk, size_t oldsize, size_t newsize); }; struct my_allocator { struct hamt_allocator parent; size_t used; char buffer[8192]; }; static void *alloc_func(struct hamt_allocator *h, void *chk, const size_t oldsize, const size_t newsize) { if (!newsize) { return NULL; } if (h && newsize <= oldsize) { return h; } // this cast is allowed by the standard for this purpose __auto_type *alloc = (struct my_allocator*) h; if (newsize > sizeof(alloc->buffer) - alloc->used) { return NULL; } void *ret = alloc->buffer + alloc->used; alloc->used += newsize; if (h && oldsize) { memcpy(ret, h, oldsize); } return ret; } void func_taking_allocator(struct hamt_allocator *h); void user_code() { struct my_allocator alloc = { .parent.realloc = alloc_func }; func_taking_allocator(&alloc.parent); }

torstenvl 3y ago

Sadly, this pattern doesn't work with standard realloc() anymore. C23 makes this undefined behavior due to existing non-conforming implementations. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2464.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2464.pdf

kazinator 3y ago
The pattern was never specified as fully working. Not in C99 and C90. It's due to the following reason: it was never specified that realloc(ptr, 0) behaves like free(ptr). The case of size == 0 is not separately discussed in the C99 description of realloc. realloc(ptr, 0) can behave like (free(ptr), malloc(0)), where malloc(0) doesn't necessarily behave like ((void *) 0). Malloc may return a unique object that may be later freed. That is to say, realloc can effectively reduce an object to zero size without freeing it, or possibly even free an object only to replace it with a different, unique zero-sized object. Note that in the case when ptr == NULL, which is discussed in C99, realloc behaves like malloc. So in the case realloc(NULL, 0), we know that it's the same as malloc(0). That's a case when size == 0, and realloc is required to behave like malloc. This is a standard-conforming realloc, and always has been: void *realloc(void *oldptr, size_t newsize) { size_t oldsize = __allocated_size(oldptr); // this handles NULL, and returns 0 void *newptr = malloc(newsize); if (newptr != NULL && oldptr != NULL) memcpy(newptr, oldptr, min(newsize, oldsize); return newptr; } This realloc will not behave like free if malloc(0) returns unique pointers. If you want a realloc-like function that behaves like an "all in one allocator", you have to write your own: void *git_reset_of_allocators(void *oldptr, size_t newsize) { if (size == 0) { free(oldptr); return NULL; } else { // handles all other cases OK return realloc(oldptr, newsize); } }
- torstenvl 3y ago
  I stand corrected! Thanks :)
dataflow 3y ago
POSIX loosened its guarantee here too? https://pubs.opengroup.org/onlinepubs/009696899/functions/realloc.html https://pubs.opengroup.org/onlinepubs/009696899/functions/re... https://pubs.opengroup.org/onlinepubs/9699919799/functions/realloc.html https://pubs.opengroup.org/onlinepubs/9699919799/functions/r...

cataphract 3y ago

The biggest advantages here are not having a single function, but instead: 1. Having a context. 2. Having free and realloc getting the old size. Not having the size passed is more or less consensually regarded as a mistake in the C stdlib.

spacechild1 3y ago

That's also what Lua does: https://www.lua.org/manual/5.3/manual.html#lua_Alloc https://www.lua.org/manual/5.3/manual.html#lua_Alloc

kazinator 3y ago

I would drop the API directly and concentrate on the algorithm. If users integrating HAMT need a different allocator situation, they can solve that problem by themselves, without a run-time indirection shim. You can help those users by providing some macros somewhere like #define hamt_malloc(ctx, x) malloc(x) and so forth, so it can be retargeted in one place. Leave an ignored context argument in place for those who would like to have a run-time switch per-instance.

hgs3 3y ago
I've seen this type of API design in C before, but not with a context. I'm curious where HAMT would get the ctx instance to pass to hamt_malloc in this design?
- kazinator 3y ago
  If the macro doesn't use the argument, it doesn't have to exist. Currently the code does use macros, e.g. mem_alloc(h->ator, size). Firstly, I'd hide the detail of how the allocator is derived from h into the allocator wrapper routines and just make it mem_alloc(h, size). It's mem_alloc which can do h->ator. Now the nice thing is that h always exists. So even mem_alloc ignores the first parameter, we don't have to pass something fictional as an argument: #define mem_alloc(h, size) malloc(size) then remove the h->ator and related cruft. Someone who needs a context for their allocator can hack that in. By the way, if you're going to have allocator providers, you want: #define mem_alloc(h, size) h->ator->alloc(h->ator, size) ^^^^^^^ and not: #define mem_alloc(h, size) h->ator->alloc(size) like the code has it now. Thou shalt not define a C callback interface without a context pointer. Without a context pointer, you cannot have an allocator module where you can bind different allocator arenas to different objects.
flohofwoe 3y ago
I used macros in my libraries for overriding the allocation functions before, but have switched to runtime callbacks later, same for logging btw (I'd need to look through the issues list for the exact reasons which led to this decision though). In any case, passing callbacks as part of the initialization "feels" right and I didn't hear any complaints since the switch (and it's definitely a lot more convenient for the library user). Also, if the library calls those function so frequently that the pointer indirection would be a performance problem, then there's arguably something very wrong with the library's design.

lelanthran 3y ago

> But I know a lot of people get confused and/or don't like having to pass (& thus keep) so much information to the allocator. That's not why I think it' a bad idea. I prefer the original because: 1. I can pass use the existing `free`, `malloc` and `realloc` implementations. By using a function with a different set of params I cannot do that. The user has to always write the `realloc` function you propose. 2. The interface for free, malloc and realloc is already documented, I don't have to explain to the programmers what constraints are needed for their memory allocator function. Under your proposal the programmer has to now have, and read, the documentation

flohofwoe 3y ago

The advantage of the alloc/realloc/free interface is that you can simply plug in the standard functions malloc, realloc and free though, and any other allocator implementation which follows this convention without your own wrapper function inbetween.