BitSet vs Set

Benchmark created on December 22, 2023

Setup

"use strict";
var _a;
/**
 * BitSet is a Set implementation that uses bits are the backing structure. For safety, values added to the BitSet
 * must be between `min` and `max`. Using values outside of this range will produce undefined behavior.
 */
class BitSet {
    /**
     * BitSet is a Set implementation that uses bits are the backing structure. For safety, values added to the BitSet
     * must be between `min` and `max`. Using values outside of this range will produce undefined behavior.
     *
     * @param min The smallest value this set can track.
     * @param max The largest value this set can track.
     * @param startFull Whether to instantiate the BitSet with all values between `min` and `max` set to true.
     */
    constructor(min = 0, max = 63, startFull = false) {
        this.min = min;
        this.max = max;
        this[_a] = "BitSet";
        this.data = Array(Math.ceil((max - min + 1) / 64)).fill(startFull ? 0xFFFFFFFF : 0);
    }
    getOffset(x) {
        const index = Math.floor((x - this.min) / 64);
        const offset = (x - this.min) % 64;
        return [index, offset];
    }
    [(_a = Symbol.toStringTag, Symbol.iterator)]() {
        return function* () {
            for (let i = this.min; i <= this.max; i++) {
                if (this.has(i)) {
                    yield i;
                }
            }
        }.bind(this)();
    }
    get size() {
        let count = 0;
        for (let i = 0; i < 64 * this.data.length; i++) {
            const [index, offset] = this.getOffset(i);
            count += this.data[index] << offset;
        }
        return count;
    }
    add(value) {
        const [index, offset] = this.getOffset(value);
        this.data[index] |= 1 << offset;
        return this;
    }
    clear() {
        this.data.fill(0);
    }
    delete(value) {
        const [index, offset] = this.getOffset(value);
        const hadValue = this.has(value);
        this.data[index] &= ~(1 << offset);
        return hadValue;
    }
    entries() {
        return function* () {
            for (let i = this.min; i <= this.max; i++) {
                if (this.has(i)) {
                    yield [i, i];
                }
            }
        }.bind(this)();
    }
    forEach(callback, thisArg) {
        for (let i = this.min; i <= this.max; i++) {
            if (this.has(i)) {
                callback(i, i, thisArg !== null && thisArg !== void 0 ? thisArg : this);
            }
        }
    }
    has(value) {
        const [index, offset] = this.getOffset(value);
        return (this.data[index] & (1 << offset)) !== 0;
    }
    keys() {
        return this[Symbol.iterator]();
    }
    values() {
        return this[Symbol.iterator]();
    }
}

const bitSet = new BitSet();
const set = new Set();

function random(min, max) { // min and max included 
  return Math.floor(Math.random() * (max - min + 1) + min)
}

Test runner

const x = random(0, 63);
const b = random(0, 1);
	
if (b === 0) bitSet.add(x);
else bitSet.delete(x);

const x = random(0, 63);
const b = random(0, 1);
	
if (b === 0) set.add(x);
else set.delete(x);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on December 22, 2023
• Revision 2: published on December 22, 2023