hashdict.c
hashdict.c copied to clipboard
Optimize hash index calculation using bitmasking
This PR improves the performance of the hash table (hashdict) by replacing the modulo operation used for index calculation with a bitmask, which is significantly faster when the table size is a power of two.
Changes
- Modified dic_new to ensure dic->length is always a power of 2.
- Updated dic->table allocation to match the adjusted length.
- Replaced the hash % length operation with hash & (length - 1) in index calculations.
Using a power-of-two length allows efficient use of bitmasking instead of modulo for hash index calculation, reducing CPU overhead during key insertion and lookup.
Benchmark Results Using the following benchmark parameters:
int best_ins = 9999, best_find = 9999, t, iters = 10;
__int64_t STEPS = 300000, STEP = 500000000;
Average results before optimization:
lowest insert time: 16
lowesr find time: 7
lowest insert time: 14
lowesr find time: 7
lowest insert time: 16
lowesr find time: 8
Average results after optimization:
lowest insert time: 12
lowesr find time: 7
lowest insert time: 13
lowesr find time: 6
lowest insert time: 13
lowesr find time: 8
The change results in a consistent reduction in insert time (by ~2-3ms) with stable find performance. This makes the dictionary more efficient under heavy use.