compactindex: insertion freezes at index generation

When creating a compactindex, and trying to insert a specific they, the call to Insert freezes.

Example code to reproduce:

package main

import (
	"fmt"

	"go.firedancer.io/radiance/pkg/compactindex"
)

func main() {
	numItems := 20795660
	targetFileSize := uint64(9872539514)

	fmt.Println("Creating index store")
	c2o, err := compactindex.NewBuilder(
		"",
		uint(numItems),
		(targetFileSize),
	)
	if err != nil {
		panic(fmt.Errorf("failed to open index store: %w", err))
	}
	fmt.Println("Index store created")
	defer c2o.Close()

	key := []byte{1, 113, 18, 32, 234, 71, 2, 40, 186, 29, 43, 126, 42, 219, 250, 129, 194, 218, 238, 7, 169, 143, 196, 29, 242, 8, 186, 195, 135, 156, 166, 46, 123, 235, 1, 205}
	totalOffset := 10988422
	fmt.Println("Inserting key", key, "at offset", totalOffset)
	err = c2o.Insert(key, uint64(totalOffset))
	if err != nil {
		panic(err)
	}
	// this point is never reached
	fmt.Println("Inserted key", key, "at offset", totalOffset)
}

It may be related to

radiance/pkg/compactindex/compactindex.go

Lines 138 to 144 in b79cfae

    
           for { 
        
           	index := xsum & mask 
        
           	if index < uint64(h.NumBuckets) { 
        
           		return uint(index) 
        
           	} 
        
           	xsum = bits.RotateLeft64(xsum, bits.LeadingZeros64(mask)) 
        
           }

spinning in an infinite loop.

@gagliardetto Could you try changing:

 for { 
 	index := xsum & mask 
 	if index < uint64(h.NumBuckets) { 
 		return uint(index) 
 	} 
 	xsum = bits.RotateLeft64(xsum, bits.LeadingZeros64(mask)) 
 }

to

 for { 
 	index := xsum & mask 
 	if index < uint64(h.NumBuckets) { 
 		return uint(index) 
 	} 
 	xsum ^= 33
 	xsum *= 0xff51afd7ed558ccd
 	xsum ^= 33
 	xsum *= 0xc4ceb9fe1a85ec53
 	xsum ^= 33
 }

(This is still going to be very slow in the worst case, need a better uniform hash function here)

Thank you!

Reopening this since this is not yet fixed in this repo

one day I'm gonna open a big (heavy) PR with all the changes

@gagliardetto Should be fixed in f689889

Please let me know if the issue persists

Thank you so much!

	for {
	index := xsum & mask
	if index < uint64(h.NumBuckets) {
	return uint(index)
	}
	xsum = bits.RotateLeft64(xsum, bits.LeadingZeros64(mask))
	}