hashdict.c icon indicating copy to clipboard operation
hashdict.c copied to clipboard

Optimize hash index calculation using bitmasking

Open AurelienBaraquin opened this issue 6 months ago • 0 comments

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.

AurelienBaraquin avatar Jun 12 '25 09:06 AurelienBaraquin