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
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions