Benchmark: SparseSet - object literal vs class

Script Preparation code:

var SparseSet1 = (input) => {
    const dense = input !== undefined ? new Array(input.length) : [];
    const sparse = [];

    const has = (value) => {
        return dense[sparse[value]] === value;
    };

    const add = (value) => {
        if (has(value)) return false;

        sparse[value] = dense.push(value) - 1;

        return true;
    };

    const remove = (value) => {
        if (!has(value)) return;

        const index = sparse[value];
        const swapped = dense.pop();
        if (swapped !== value) {
            dense[index] = swapped;
            sparse[swapped] = index;
        }
    };

    if (input !== undefined) {
        for (let i = 0; i < input.length; i++) {
            dense[i] = input[i];
            sparse[input[i]] = i;
        }
    }

    return {
        dense,
        sparse,
        has,
        add,
        remove,
    };
};

class SparseSet {
    constructor(input) {
        this.dense = input !== undefined ? new Array(input.length) : [];
        this.sparse = [];

        if (input !== undefined) {
            for (let i = 0; i < input.length; i++) {
                this.dense[i] = input[i];
                this.sparse[input[i]] = i;
            }
        }
    }

    has(value) {
        return this.dense[this.sparse[value]] === value;
    };

    add(value) {
        if (this.has(value)) return false;

        this.sparse[value] = this.dense.push(value) - 1;

        return true;
    };

    remove(value) {
        if (!this.has(value)) return;

        const index = this.sparse[value];
        const swapped = this.dense.pop();
        if (swapped !== value) {
            this.dense[index] = swapped;
            this.sparse[swapped] = index;
        }
    };
};
var SparseSet2 = SparseSet;

Tests:

Object literal
var set = SparseSet1([64, 11, 97, 1, 24, 25, 67, 100, 120, 130, 1001, 8, 2163]); for(let i = 1000; i < 1100; i++) { set.add(i); } for(let i = 0; i < 100; i++) { set.remove(i); }
Class
var set = new SparseSet2([64, 11, 97, 1, 24, 25, 67, 100, 120, 130, 1001, 8, 2163]); for(let i = 1000; i < 1100; i++) { set.add(i); } for(let i = 0; i < 100; i++) { set.remove(i); }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Object literal
Class

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Linux; Android 12; Redmi 5 Plus) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/111.0.0.0 Mobile Safari/537.36

Browser/OS: Chrome Mobile 111 on Android

View result in a separate tab

Test name	Executions per second
Object literal	18611.1 Ops/sec
Class	20943.9 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 2 months ago):

LLMs can make mistakes. Check important info.

Let's break down the provided benchmark definition and test cases.

**Benchmark Definition**

The benchmark is comparing two approaches to implement a sparse set data structure in JavaScript:

1. **Object Literal**: The `SparseSet` function is implemented using an object literal (a JavaScript object) to store the dense and sparse arrays, as well as the `has`, `add`, and `remove` methods.
2. **Class**: The same `SparseSet` class is defined using the ES6 class syntax, which provides a similar implementation as the object literal approach.

**Options Compared**

The two approaches are compared in terms of:

* Execution time: The benchmark measures how long it takes to execute the test cases for each approach.
* Memory usage: Although not explicitly measured in this benchmark, the difference in memory usage between the two approaches is likely to be minimal due to the small size of the sparse sets being created.

**Pros and Cons**

* **Object Literal Approach**:
	+ Pros:
		- Easier to implement and understand for those familiar with object literals.
		- May require less memory allocation and garbage collection, as it uses a single object instead of two separate arrays.
	+ Cons:
		- Might be slower due to the overhead of creating and manipulating an object.
* **Class Approach**:
	+ Pros:
		- Can provide better encapsulation and abstraction, making it easier to extend or modify the sparse set implementation in the future.
		- May be faster due to the use of a class, which can optimize memory allocation and garbage collection.
	+ Cons:
		- More complex to implement and understand, especially for those unfamiliar with ES6 classes.

**Other Considerations**

* **Libraries**: Neither approach uses any external libraries. However, if you were to compare against a library implementation, some popular options include Lodash's `Set` or the native `Set` object in modern JavaScript environments.
* **Special JS Features**: The benchmark does not use any special JavaScript features such as async/await, generators, or WebAssembly.

**Alternatives**

If you're interested in exploring alternative approaches to implementing a sparse set data structure in JavaScript, consider:

1. Using the native `Set` object: While it may not provide all the functionality of a custom implementation, the native `Set` object can be fast and efficient.
2. Implementing a trie-based sparse set: A trie (prefix tree) can provide an efficient way to store and query sparse sets, especially for large datasets.
3. Using a third-party library: As mentioned earlier, libraries like Lodash or other specialized data structures might offer optimized implementations of sparse sets.

Related benchmarks:

SparseSet - object literal vs class (version: 0)

Comparing performance of: Object literal vs Class

Created: one year ago by: Registered User

Jump to the latest result

Object literal

Class

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 2 months ago):