Create js Sets using arrays

[kwcantrell]

The .add() function of Set is much slower than .push of an array. See this post for more details.

I also created simple test to verify and it seems creating an array and then converting it to a set is much faster than just using set.add(). In the below example, 'add by set' takes ~4 seconds will 'add by index' takes ~0.5 seconds. So, if we initialize all sets using arrays, we can save a significant amount of time. This would be especially helpful for the coloring/bar plot methods. Note: we still want to use sets because .has is much faster than indexOf.

var f = function() {
    var t = [];
    var d = new Date();
    for (var i = 0; i < 10000000; i ++) {
        t[i] = 1;
    }
    var st = new Set(t);
    st.has(1) ? console.log("!!!") : console.log(":(");
    var dt = new Date();
    console.log("add by index", dt.getTime() - d.getTime());

    var t = [];
    var d = new Date();
    for (var i = 0; i < 10000000; i ++) {
        t.push(i)
    }
    var st = new Set(t);
    st.has(1) ? console.log("!!!") : console.log(":(");
    var dt = new Date();
    console.log("add by push", dt.getTime() - d.getTime());

    var t = new Set();
    var d = new Date();
    for (var i = 0; i < 10000000; i ++) {
        t.add(i);
    }
    var dt = new Date();
    console.log("add by set", dt.getTime() - d.getTime());

    var d = new Date();
    var t = new Array(10000000);
    for (var i = 0; i < 10000000; i ++) {
        t[i] = 1;
    }
    var st = new Set(t);
    st.has(1) ? console.log("!!!") : console.log(":(");
    var dt = new Date();
    console.log("add by init", dt.getTime() - d.getTime());

    var d = new Date();
    var t = new Array(10000000).fill(0);
    for (var i = 0; i < 10000000; i ++) {
        t[i] = 1;
    }
    var st = new Set(t);
    st.has(1) ? console.log("!!!") : console.log(":(");
    var dt = new Date();
    console.log("add by init and fill", dt.getTime() - d.getTime());
}
f();

[kwcantrell]

We can actually remove Sets all together and use a boolean array in it place. According to this arrays only allocate memory to elements that actually hold a value. Thus, instead of adding a node to a set, we can simply use the nodes post-order position to set the corresponding array element to true. This would be beneficial for two reasons. 1) Creating an element in an array is much faster than adding an element to a Set. 2) We would no longer need to convert the Set back to an array.