BitSet vs Set (v2)

Revision 2 of this benchmark created on


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(0, 1000);
const set = new Set();

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

Test runner

Ready to run.

Testing in
TestOps/sec
BitSet
const x = random(0, 1000);
const b = Boolean(random(0, 1));
	
if (b) bitSet.add(x);
else bitSet.delete(x);
bitSet.has(x) === b || (() => { throw "oop" })();
ready
Set
const x = random(0, 1000);
const b = Boolean(random(0, 1));
	
if (b) set.add(x);
else set.delete(x);
set.has(x) === b || (() => { throw "oop" })();
ready

Revisions

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