Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualHodgman

Posted 23 February 2013 - 07:04 PM

My argument would be that chained hash tables have the same algorithmic complexity but much better worst case performance. If you are worried about allocations you can plug in a pool allocator to the existing containers.

In my engine, my use cases for flat (and non-resizable) hash containers are mainly for:
* Ones that are "deserialized" from files, as I use in-place loading where the file is loaded into RAM and cast to a struct and is ready to use without parsing. My flat hash table uses only offsets (instead of pointers) and supports only POD types to allow for this.
* Similar to the above, if a hash table is required on a NUMA core, then it needs to be memcpy-able (and needs to keep working if memcpy'ed to a different address space), which is the same requirement as above.
* If a hash table requires simultaneous insertions from multiple cores, then a flat lock-free implementation is much simpler than one that uses traditional allocations.

^Given these quirky requirements, I don't think boost would care for my own implementation laugh.png


#1Hodgman

Posted 23 February 2013 - 07:03 PM

My argument would be that chained hash tables have the same algorithmic complexity but much better worst case performance. If you are worried about allocations you can plug in a pool allocator to the existing containers.

In my engine, my use cases for flat (and non-resizable) hash containers are mainly for:
* Ones that are "deserialized" from files, as I use in-place loading where the file is loaded into RAM and cast to a struct and is ready to use. My flat hash table uses only offsets and POD types to allow for this.
* Similar to the above, if a hash table is required on a NUMA core, then it needs to be memcpy-able (and needs to keep working if memcpy'ed to a different address space), which is the same requirement as above.
* If a hash table requires simultaneous insertions from multiple cores, then a flat lock-free implementation is much simpler than one that uses traditional allocations.

^Given these quirky requirements, I don't think boost would care for my own implementation laugh.png


PARTNERS