638
edits
User:Jorend/Deterministic hash tables: Difference between revisions
Jump to navigation
Jump to search
User:Jorend/Deterministic hash tables (view source)
Revision as of 14:57, 23 February 2012
, 23 February 2012→Method
(→Method) |
|||
| Line 35: | Line 35: | ||
* The purpose of the typedefs KeyArg and ValueArg is to make it possible to switch the API from pass-by-value to pass-by-reference by editing just a couple of lines of code. (I tried this. Pass-by-reference is no faster on 64-bit machines.) | * The purpose of the typedefs KeyArg and ValueArg is to make it possible to switch the API from pass-by-value to pass-by-reference by editing just a couple of lines of code. (I tried this. Pass-by-reference is no faster on 64-bit machines.) | ||
* CloseTable attempts to allocate chunks of memory with sizes that are near powers of 2. This is to avoid wasting space when used with size-class-based malloc implementations. | |||
* A Close table can trade some speed for compactness, but it seems to be a bad bargain: | |||
** The load factor is adjustable. (The hash table size must remain at a power of two, but the data vector can have non-power-of-2 sizes.) However, increasing the load factor directly affects LookupMiss speed. | |||
** An implementation could grow the data array by less than doubling it each time. I tried this. Insert speed suffered; lookup speed was unaffected; but the modified CloseTable still used more memory than OpenTable. | |||
Benchmark design notes: | Benchmark design notes: | ||