dragonfly icon indicating copy to clipboard operation
dragonfly copied to clipboard

Ideas about DenseSet improvement

Open BorysTheDev opened this issue 1 year ago • 0 comments

  1. Displacement improving: Instead of displacing (2 bits that describe left and right alternative cell), we can use shift (2 current bits can provide us with the next 3 positions or we can use even 3 or 4 bits and utilize the next 8 or 16 cells). Such improvement allows us to use a simple FOR cycle (and utilize parallel prefetching more efficiently) instead of several IF's logic.
  2. Also as an alternative approach instead of shift/displacing bits, we can use something like a bloom filter, and for every bucket store up to 8 next positions where the element can be placed.
  3. Links optimization: instead of a simple forward_list approach we can use links for N (shift distance / 2 like an option) number of elements that should be created if we find N elements in the SHIFT/DISPLACEMENT positions. Such an approach should improve memory locality and reduce memory consumption.

BorysTheDev avatar Oct 15 '24 07:10 BorysTheDev