binaryfusefilter_test.go

package xorfilter

import (
	"fmt"
	"math/rand/v2"
	"slices"
	"sort"
	"strings"
	"sync"
	"testing"

	"github.com/cespare/xxhash/v2"
	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

const NUM_KEYS = 1e6
const MID_NUM_KEYS = 11500
const SMALL_NUM_KEYS = 100

type testType uint8

func TestBinaryFuseNBasic(t *testing.T) {
	keys := make([]uint64, NUM_KEYS)
	for i := range keys {
		keys[i] = rand.Uint64()
	}
	filter, _ := NewBinaryFuse[testType](keys)
	for _, v := range keys {
		assert.Equal(t, true, filter.Contains(v))
	}
	falsesize := 10000000
	matches := 0
	bpv := float64(len(filter.Fingerprints)) * 8.0 / float64(NUM_KEYS)
	fmt.Println("Binary Fuse filter:")
	fmt.Println("bits per entry ", bpv)
	for i := 0; i < falsesize; i++ {
		v := rand.Uint64()
		if filter.Contains(v) {
			matches++
		}
	}
	fpp := float64(matches) * 100.0 / float64(falsesize)
	fmt.Println("false positive rate ", fpp)
	cut := 1000
	if cut > NUM_KEYS {
		cut = NUM_KEYS
	}
	keys = keys[:cut]
	for trial := 0; trial < 10; trial++ {
		r := rand.New(rand.NewPCG(uint64(trial), uint64(trial)))
		for i := range keys {
			keys[i] = r.Uint64()
		}
		filter, _ = NewBinaryFuse[testType](keys)
		for _, v := range keys {
			assert.Equal(t, true, filter.Contains(v))
		}

	}
}

func TestBinaryFuseNIssue23(t *testing.T) {
	for trials := 0; trials < 20; trials++ {
		keys := make([]uint64, MID_NUM_KEYS)
		for i := range keys {
			keys[i] = rand.Uint64()
		}
		filter, error := NewBinaryFuse[testType](keys)
		assert.Equal(t, nil, error)
		for _, v := range keys {
			assert.Equal(t, true, filter.Contains(v))
		}
	}
}

func TestBinaryFuseNSmall(t *testing.T) {
	keys := make([]uint64, SMALL_NUM_KEYS)
	for i := range keys {
		keys[i] = rand.Uint64()
	}
	filter, _ := NewBinaryFuse[testType](keys)
	for _, v := range keys {
		assert.Equal(t, true, filter.Contains(v))
	}
	falsesize := 10000000
	matches := 0

	for i := 0; i < falsesize; i++ {
		v := rand.Uint64()
		if filter.Contains(v) {
			matches++
		}
	}
	cut := 1000
	if cut > SMALL_NUM_KEYS {
		cut = SMALL_NUM_KEYS
	}
	keys = keys[:cut]
	for trial := 0; trial < 10; trial++ {
		r := rand.New(rand.NewPCG(uint64(trial), uint64(trial)))
		for i := range keys {
			keys[i] = r.Uint64()
		}
		filter, _ = NewBinaryFuse[testType](keys)
		for _, v := range keys {
			assert.Equal(t, true, filter.Contains(v))
		}

	}
}

func TestBinaryFuseN_ZeroSet(t *testing.T) {
	keys := []uint64{}
	_, err := NewBinaryFuse[testType](keys)
	if err != nil {
		t.Fatalf("Unexpected error: %v", err)
	}
}

func TestBinaryFuseN_DuplicateKeysBinaryFuseDup(t *testing.T) {
	keys := []uint64{303, 1, 77, 31, 241, 303}
	_, err := NewBinaryFuse[testType](keys)
	if err != nil {
		t.Fatalf("Unexpected error: %v", err)
	}
}

func TestBinaryFuseN_DuplicateKeysBinaryFuseDup_Issue30(t *testing.T) {
	keys := []uint64{
		14032282262966018013,
		14032282273189634013,
		14434670549455045197,
		14434670549455045197,
		14434715112030278733,
		14434715112030278733,
		1463031668069456414,
		1463031668069456414,
		15078258904550751789,
		15081947205023144749,
		15087793929176324909,
		15087793929514872877,
		15428597303557855302,
		15431797104190473360,
		15454853113467544134,
		1577077805634642122,
		15777410361767557472,
		15907998856512513094,
		15919978655645680696,
		1592170445630803483,
		15933058486048027407,
		15933070362921612719,
		15949859010628284683,
		15950094057516674097,
		15950094057516674097,
		15950492113755294966,
		15999960652771912055,
		16104958339467613609,
		16115083045828466089,
		16115119760717288873,
		16126347135921205846,
		16180939948277777353,
		16205881181578942897,
		16207480993107654476,
		1627916223119626716,
		16303139460042870203,
		16303139460042870203,
		1630429337332308348,
		16309304071237318790,
		16314547479302655419,
		16314547479302655419,
		16369820198817029405,
		16448390727851746333,
		16465049428524180509,
		16465073162513458205,
		16465073285148156957,
		16465073285149870384,
		16465073285149877277,
		16465073285893104669,
		16555387163297522125,
		16592146351271542115,
		16682791020048538670,
		16683514177871458902,
		16699277535828137630,
		16716099852308345174,
		16716099868253794902,
		16856736053711445064,
		16856736054253850696,
		16856736060613333064,
		16877690937235789198,
		16963977918744734769,
		16976350133984177557,
		16976376109946388059,
		17041493382094423395,
		17053822556128759139,
		17067586192959011138,
		17088637646961899303,
		17121323146925062160,
		17130440365429237769,
		17130440365429237769,
		17130440597658279433,
		17130440597658279433,
		17181620514756131957,
		17193256430982721885,
		17193256636319002973,
		17264031033993538756,
		17321155670529409646,
		17514402547088160271,
		17514402547088160271,
		1823133498679825084,
		1823180415377412796,
		18278489907932484471,
		1831024066115736252,
		18341786752172751552,
		18378944050902766168,
		18378944052194427480,
		18403514326223737719,
		18405070344654600695,
		2164472587301781504,
		2164472587301781504,
		2290190445057074187,
		2471837983693302824,
		2471837983693302824,
		3138094539259513280,
		3138094539259513280,
		3138153989894179264,
		3138153989894179264,
		3566850904877432832,
		3566850904877432832,
		3868495676835528327,
		3868495676835528327,
		3981182070595518464,
		3981182070595518464,
		3998521163612422144,
		3998521163612422144,
		3998521164578160640,
		3998521164578160640,
		3998521164581306368,
		3998521164581306368,
		3998521164581329296,
		3998521164581329296,
		4334725363086930304,
		4334725363086930304,
		4337388653622853632,
		4337388653622853632,
		4587006656968527746,
		4587006656968527746,
		4587006831041087252,
		4587006831041087252,
		4825061103098367168,
		4825061103098367168,
	}
	_, err := NewBinaryFuse[testType](keys)
	if err != nil {
		t.Fatalf("Unexpected error: %v", err)
	}
}

var (
	bogusbool      bool
	binaryfusedbig *BinaryFuse8
	bogusbinary    *BinaryFuse[testType]
)

func BenchmarkBinaryFusePopulate(b *testing.B) {
	for _, bits := range []int{8, 16} {
		for _, numKeys := range []int{10_000, 100_000, 1_000_000} {
			b.Run(fmt.Sprintf("%d/n=%d", bits, numKeys), func(b *testing.B) {
				keys := make([]uint64, numKeys)
				for i := range keys {
					keys[i] = rand.Uint64()
				}

				b.ResetTimer()
				b.ReportAllocs()

				for n := 0; n < b.N; n++ {
					if bits == 8 {
						_, _ = NewBinaryFuse[uint8](keys)
					} else {
						_, _ = NewBinaryFuse[uint16](keys)
					}
				}
				b.ReportMetric(float64(b.N*numKeys)/b.Elapsed().Seconds()/1e6, "MKeys/s")
			})
		}
	}
}

func BenchmarkConstructBinaryFuseN(b *testing.B) {
	bigrandomarrayInit()
	b.ResetTimer()
	b.ReportAllocs()

	for n := 0; n < b.N; n++ {
		bogusbinary, _ = NewBinaryFuse[testType](bigrandomarray)
	}
}

func BenchmarkBinaryFuseNContains1000000(b *testing.B) {
	keys := make([]uint64, NUM_KEYS)
	for i := range keys {
		keys[i] = rand.Uint64()
	}
	filter, _ := NewBinaryFuse[testType](keys)

	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		bogusbool = filter.Contains(keys[n%len(keys)])
	}
}

func binaryfusedbigInit() {
	fmt.Println("Binary Fuse setup")
	keys := make([]uint64, 50000000)
	for i := range keys {
		keys[i] = rand.Uint64()
	}
	binaryfusedbig, _ = PopulateBinaryFuse8(keys)
	fmt.Println("Binary Fuse setup ok")
}

func BenchmarkBinaryFuseNContains50000000(b *testing.B) {
	if binaryfusedbig == nil {
		binaryfusedbigInit()
	}
	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		bogusbool = binaryfusedbig.Contains(rand.Uint64())
	}
}

func TestBinaryFuseN_Issue35(t *testing.T) {
	for test := 0; test < 100; test++ {
		hashes := make([]uint64, 0)
		for i := 0; i < 40000; i++ {
			v := encode(rand.Int32N(10), rand.Int32N(100000))
			hashes = append(hashes, xxhash.Sum64(v))
		}
		inner, err := NewBinaryFuse[testType](hashes)
		if err != nil {
			panic(err)
		}
		for i, d := range hashes {
			e := inner.Contains(d)
			if !e {
				panic(i)
			}
		}
	}
}

// TestBinaryFuseBuilder verifies that repeated builds with the same builder
// create the exact same filter as using NewBinaryFuse.
func TestBinaryFuseBuilder(t *testing.T) {
	var bld BinaryFuseBuilder
	// Test with and without pre-allocation.
	if rand.IntN(2) == 0 {
		maxSize := 1 + rand.IntN(1<<rand.IntN(20))
		switch rand.IntN(3) {
		case 0:
			bld = MakeBinaryFuseBuilder[uint8](maxSize)
		case 1:
			bld = MakeBinaryFuseBuilder[uint16](maxSize)
		case 2:
			bld = MakeBinaryFuseBuilder[uint32](maxSize)
		}
	}
	for i := 0; i < 100; i++ {
		n := 1 + rand.IntN(1<<rand.IntN(20))
		keys := make([]uint64, n)
		for j := range keys {
			keys[j] = rand.Uint64()
		}
		switch rand.IntN(3) {
		case 0:
			crossCheckFuseBuilder[uint8](t, &bld, keys)
		case 1:
			crossCheckFuseBuilder[uint16](t, &bld, keys)
		case 2:
			crossCheckFuseBuilder[uint32](t, &bld, keys)
		}
	}
}

func crossCheckFuseBuilder[T Unsigned](t *testing.T, bld *BinaryFuseBuilder, keys []uint64) {
	t.Helper()
	filter, err := BuildBinaryFuse[T](bld, slices.Clone(keys))
	require.NoError(t, err)
	expected, err := NewBinaryFuse[T](keys)
	require.NoError(t, err)
	_ = expected
	require.Equal(t, *expected, filter)
}

// TestMakeBinaryFuseBuilder verifies that using MakeBinaryFuseBuilder prevents
// all allocations.
func TestMakeBinaryFuseBuilder(t *testing.T) {
	maxSize := 1000 + rand.IntN(100_000)
	keys := make([]uint64, maxSize)
	for j := range keys {
		keys[j] = rand.Uint64()
	}
	bld := MakeBinaryFuseBuilder[uint16](maxSize)
	numAllocs := testing.AllocsPerRun(100, func() {
		for range 10 {
			var size int
			if rand.IntN(100) == 1 {
				size = maxSize
			} else {
				size = 1 + rand.IntN(maxSize)
			}
			if rand.IntN(2) == 0 {
				// Smaller fingerprints can reuse the same preallocated space.
				_, _ = BuildBinaryFuse[uint8](&bld, keys[:size])
			} else {
				_, _ = BuildBinaryFuse[uint16](&bld, keys[:size])
			}
		}
	})
	require.Zero(t, numAllocs)
}

// segmentLengthSizes contains represents the range of sizes [startSize, endSize] that
// all get the same segmentLength.
type segmentLengthSizes struct {
	segmentLength     uint32
	startSize         uint32
	startSegmentCount uint32
	endSize           uint32
	endSegmentCount   uint32
}

var binaryFuseParamStableOnce struct {
	once   sync.Once
	result []segmentLengthSizes
}

const binaryFuseParamTableMaxSegmentSize = 16384

func binaryFuseSegLenAndCnt(size uint32) (segLen uint32, segCnt uint32) {
	var f BinaryFuse[uint8]
	f.initializeParameters(&BinaryFuseBuilder{}, size)
	return f.SegmentLength, f.SegmentCount
}

func binaryFuseParamsTable() []segmentLengthSizes {
	binaryFuseParamStableOnce.once.Do(func() {
		var table []segmentLengthSizes
		size := uint32(1)
		for {
			segLen, segCnt := binaryFuseSegLenAndCnt(size)
			if segLen > binaryFuseParamTableMaxSegmentSize {
				break
			}
			// Find the first size that changes the segment length.
			n := uint32(sort.Search(int(size*4), func(x int) bool {
				l, _ := binaryFuseSegLenAndCnt(size + uint32(x))
				return l != segLen
			}))
			_, endSegCnt := binaryFuseSegLenAndCnt(size + n - 1)
			table = append(table, segmentLengthSizes{
				segmentLength:     segLen,
				startSize:         size,
				startSegmentCount: segCnt,
				endSize:           size + n - 1,
				endSegmentCount:   endSegCnt,
			})
			size += n
		}
		binaryFuseParamStableOnce.result = table
	})
	return binaryFuseParamStableOnce.result
}

// TestBinaryFuseParams shows the segment count and size range for each segment
// length. Used to verify any changes in parameter calculation.
func TestBinaryFuseParams(t *testing.T) {
	expected := `
| SegLen | SegCnt range |    Size range     |
|--------|--------------|-------------------|
|      4 |    1 - 1     |       1 - 2       |
|      8 |    1 - 1     |       3 - 8       |
|     16 |    1 - 2     |       9 - 27      |
|     32 |    1 - 3     |      28 - 91      |
|     64 |    1 - 5     |      92 - 303     |
|    128 |    2 - 9     |     304 - 1009    |
|    256 |    4 - 16    |    1010 - 3361    |
|    512 |    7 - 26    |    3362 - 11192   |
|   1024 |   12 - 42    |   11193 - 37272   |
|   2048 |   20 - 69    |   37273 - 124117  |
|   4096 |   34 - 114   |  124118 - 413309  |
|   8192 |   56 - 188   |  413310 - 1376321 |
|  16384 |   93 - 313   | 1376322 - 4583149 |
`

	var out strings.Builder
	fmt.Fprintf(&out, "| SegLen | SegCnt range |    Size range     |\n")
	fmt.Fprintf(&out, "|--------|--------------|-------------------|\n")
	for _, row := range binaryFuseParamsTable() {
		fmt.Fprintf(&out, "| %6d | %4d - %-5d | %7d - %-7d |\n",
			row.segmentLength,
			row.startSegmentCount, row.endSegmentCount,
			row.startSize, row.endSize,
		)
	}
	str := out.String()
	require.Equal(t, strings.TrimSpace(expected), strings.TrimSpace(str))
}

func checkNumIterations(t *testing.T, size uint32) {
	const numTrials = 20

	keys := make([]uint64, size)
	var totalIterations, maxIterations int
	for range numTrials {
		for i := range keys {
			keys[i] = rand.Uint64()
		}
		var b BinaryFuseBuilder
		filter, iterations, err := buildBinaryFuse[uint8](&b, keys)
		require.NoError(t, err)
		for range 100 {
			require.True(t, filter.Contains(keys[rand.IntN(len(keys))]))
		}
		totalIterations += iterations
		maxIterations = max(maxIterations, iterations)
	}
	t.Logf("size: %d  iterations: %.2f avg (%d max)", size, float64(totalIterations)/numTrials, maxIterations)
}

func TestBinaryFuseBoundarySizes(t *testing.T) {
	// For each segment length, test the smallest and largest segment count. For a
	// given segment count, we want to choose the largest size for that count
	// (which has the least "slack" space).
	for _, s := range binaryFuseParamsTable() {
		if s.startSize > 1_000_000 {
			// Larger sizes take too long to test.
			break
		}
		if s.startSegmentCount != s.endSegmentCount {
			// Find the first size that doesn't use the start segment count.
			n := uint32(sort.Search(int(s.endSize-s.startSize+1), func(x int) bool {
				l, c := binaryFuseSegLenAndCnt(s.startSize + uint32(x))
				return l != s.segmentLength || c != s.startSegmentCount
			}))
			checkNumIterations(t, s.startSize+n-1)
		}
		checkNumIterations(t, s.endSize)
	}
}