Hacker News new | past | comments | ask | show | jobs | submit login

You mentioned it yourself, but please use `strncmp` - you don't want to have unbounded c style strings like that as keys.

A lot of mallocs. Just malloc a pool and implement an allocation strategy on top of it. Malloc more as necessary (say 2^n).

You mention map types in other languages. They're not always implemented as a hashmap. A tree is commonly used to implement maps too.

Embedded environments generally avoid `malloc` and the heap entirely. You have a simple allocator on top of a fixed allotment of memory instead.




> A lot of mallocs. Just malloc a pool and implement an allocation strategy on top of it. Malloc more as necessary (say 2^n).

Good mallocs do that themselves already. It's built in, they use a pool. Really good mallocs use a fast, cache-friendly pool, typically per CPU-core or per-thread.

By using a pool on top of a good malloc, you are implementing a second pool on top of the first pool. For something general purpose like a general purpoe hash table, layering pools like that often provides no advantage and some disadvantages including to performance. It's often, though not always, better to use a really good malloc

> You mention map types in other languages. They're not always implemented as a hashmap. A tree is commonly used to implement maps too.

Notably the C++ `std::map` is a tree. A later standard added `std::unordered_map` which is a hash table. The effect is many C++ programs use trees for their maps, and some C++ devs don't realise they are using a tree with O(log N) time operations instead of a hash table with O(1) time operations.

> Embedded environments generally avoid `malloc` and the heap entirely. You have a simple allocator on top of a fixed allotment of memory instead.

I think that's a strange way to look at it, because `malloc` is a simple allocator on top of a fixed allotment of memory when you have a fixed allotment of memory to work with. You can write whatever `malloc` and `free` functions you like to suit the situation. You don't have to use the one in libc, and small embedded environments often don't have one. E.g. I've seen extremely memory-constrained bootloaders and DSPs where there is still a function called `malloc`, but it is a very simple allocator for the situation.

In high reliability systems you might need to control the pattern of allocations in the progam so that memory use stays bounded. But in a general purpose hash table, the way to bound memory use is to control the pattern of hash table usage, i.e. the callers.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: