Skip to content

Perf: Implement a more cache-friendly construction for bcVector #17

@meling

Description

@meling

We currently use two separate slices for the bit vector and collision vector:

// bcVector represents a combined bit and collision vector.
type bcVector struct {
	v []uint64
	c []uint64
}

This could lead to cache misses on every access.

Here are two ideas we could try.

  • Option 1: Use a single slice to represent the bit and collision vector. See below.
  • Option 2: Make sure each vector is small enough to fit in cache (use fixed-size array).
    • This could be done by picking the number of partitions to make each partition fit exactly in the cache.
    • We can create partitions that scale with the number of chunks instead of partition size.
    • Add more levels since each level can fit only a fixed number of bits. This may slow down Find, since it may need to traverse more levels.

For Option 1, instead of using:

b.v[x]
b.c[x]

We can do this:

bc[x]
bc[x+1]

(Calculating x will be more complicated though.)

Metadata

Metadata

Assignees

No one assigned

    Labels

    performanceCan possibly improve performance

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions