41–50 of 59 posts
Increase the size of the bitmap in each node from 32 bits to 64 bits. You are wasting 4 bytes per node, and wider nodes mean fewer indirections for each lookup.
Change the recursion in the lookup to iteration. You used iteration in other traversals, and it should be much more efficient.
In case this is unfamiliar topic - immutable value based programming is super cool because it simplifies the cognitive load of reasoning about your program - hence enabling you to write better programs per-unit-of-effort consumed.
Earlier quoted context omitted.
You don't need the cookie then. You can just allocate a larger struct (sort of subclassing it). You save a pointer indirection.
There's a limit to what can be crammed into a HN comment!
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 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);
}Earlier quoted context omitted.
Beohm is not refcounting, it's a tracing GC.
Boehm is not tracing, it's a conservative GC. PS admittedly, terminology is not precise enough in this space.
Tracing GCs might be precise (or not), they might handle internal-pointers (or not), they might move the data (or not), they might handle variable sized allocations (or not).
How does this compare to https://github.com/arximboldi/immer (other than the C/C++ difference)? Also, it's my understanding that, in practice, persistent data structures require a garbage collector in order to handle deallocation when used in a general-purpose way. How does your implementation handle that? Also, have you seen https://github.com/cnuernber/ham-fisted ? I think there are a few other Java-based persisten…
> How does your implementation handle that? This is explained in the readme[1]. You can pass custom allocation functions (mallic, realloc, free), so you can plug in Boehm fex. [1]: https://github.com/mkirchner/hamt#memory-management
Good datastructure, code looks quite clean for C. Your API is missing some of the advantages relative to hash tables though. Because it's a tree, operations like union and difference of two instances can be sublinear in the size of the instances. E.g. union can copy subtrees when the other instance has empty at the corresponding position. You're also missing a batch construction call, create a new tree out of N key/v…
Regarding the batch construction, it's not immediately clear to me how to implement sorting since the order is implicit through the hash function (it seems one would need to construct a trie to build a trie?) but I might be wrong...
I have spotted a couple of ways to improve performance: Increase the size of the bitmap in each node from 32 bits to 64 bits. You are wasting 4 bytes per node, and wider nodes mean fewer indirections for each lookup. Change the recursion in the lookup to iteration. You used iteration in other traversals, and it should be much more efficient.
Re the impact of the recursion, that's actually zero for the search code since clang does a tail call optimization; it's a fair point for the removal code.
Nice! I think you should really add a userdata member to hamt_allocator. Not every memory allocator is global!