Sparse Array

Benchmark created on October 26, 2013

Preparation HTML

<script>
var SwitchArray = (function(undefined) {
        'use strict';

        function SparseArray() {
                var root = empty;
                this.get = function(index) {
                        return get(root, index);
                };
                this.set = function(index, value) {
                        root = set(root, index, value);
                };
        }

        var branchTag = 0;
        var leafTag = 1;
        var emptyTag = 2;

        function Node() {}

        Node.prototype.tag = emptyTag;

        function get(node, index) {
                switch (node.tag) {
                case branchTag:
                        if (!hasPrefix(index, node.prefix, node.mask)) {
                                return undefined;
                        }
                        if (zero(index, node.mask)) {
                                return get(node.left, index);
                        }
                        return get(node.right, index);
                case leafTag:
                        return index === node.index? node.value : undefined;
                case emptyTag:
                        return undefined;
                }
        }

        function set(node, index, value) {
                switch (node.tag) {
                case branchTag:
                        if (!hasPrefix(index, node.prefix, node.mask)) {
                                return makeBranch(index, newLeaf(index, value), node.prefix, node);
                        }
                        if (zero(index, node.mask)) {
                                node.left = set(node.left, index, value);
                        } else {
                                node.right = set(node.right, index, value);
                        }
                        return node;
                case leafTag:
                        if (index === node.index) {
                                node.value = value;
                                return node;
                        }
                        return makeBranch(index, newLeaf(index, value), node.index, node);
                case emptyTag:
                        return newLeaf(index, value);
                }
        }

        function makeBranch(prefix1, node1, prefix2, node2) {
                var mask = makeMask(prefix1, prefix2);
                var prefix = makePrefix(prefix1, mask);
                return zero(prefix1, mask)?
                        newBranch(prefix, mask, node1, node2) :
                        newBranch(prefix, mask, node2, node1);
        }

        function newBranch(prefix, mask, left, right) {
                var node = new Node();
                node.tag = branchTag;
                node.prefix = prefix;
                node.mask = mask;
                node.left = left;
                node.right = right;
                return node;
        }

        function newLeaf(index, value) {
                var node = new Node();
                node.tag = leafTag;
                node.index = index;
                node.value = value;
                return node;
        }

        var empty = new Node();

        function hasPrefix(index, prefix, mask) {
                return makePrefix(index, mask) === prefix;
        }

        function zero(index, mask) {
                return (index & mask) === 0;
        }

        function makePrefix(index, mask) {
                return index & (~(mask - 1) ^ mask);
        }

        function makeMask(prefix1, prefix2) {
                return greatestPowerOfTwo(prefix1 ^ prefix2);
        }

        function greatestPowerOfTwo(value) {
                value |= value >> 1;
                value |= value >> 2;
                value |= value >> 4;
                value |= value >> 8;
                value |= value >> 16;
                value ^= value >>> 1;
                return value;
        }

        return SparseArray;
}());
</script>
<script>
var PropertyArray = (function(undefined) {
        'use strict';

        function SparseArray() {
                var root = empty;
                this.get = function(index) {
                        return root.get(index);
                };
                this.set = function(index, value) {
                        root = root.set(index, value);
                };
        }

        function Signed(left, right) {
                this.left = left;
                this.right = right;
        }

        function Unsigned(prefix, mask, left, right) {
                this.prefix = prefix;
                this.mask = mask;
                this.left = left;
                this.right = right;
        }

        function Leaf(index, value) {
                this.index = index;
                this.value = value;
        }

        var empty = {};

        Signed.prototype.get = function(index) {
                return index < 0?
                        this.left.get(index) :
                        this.right.get(index);
        };
        Unsigned.prototype.get = function(index) {
                if (!hasPrefix(index, this.prefix, this.mask)) {
                        return undefined;
                }
                if (zero(index, this.mask)) {
                        return this.left.get(index);
                }
                return this.right.get(index);
        };
        Leaf.prototype.get = function(index) {
                return index === this.index? this.value : undefined;
        };
        empty.get = function() {
                return undefined;
        };

        Signed.prototype.set = function(index, value) {
                if (index < 0) {
                        this.left = this.left.set(index, value);
                } else {
                        this.right = this.right.set(index, value);
                }
                return this;
        };
        Unsigned.prototype.set = function(index, value) {
                if (!hasPrefix(index, this.prefix, this.mask)) {
                        return newBranch(index, new Leaf(index, value), this.prefix, this);
                }
                if (zero(index, this.mask)) {
                        this.left = this.left.set(index, value);
                } else {
                        this.right = this.right.set(index, value);
                }
                return this;
        };
        Leaf.prototype.set = function(index, value) {
                if (this.index === index) {
                        this.value = value;
                        return this;
                }
                return newBranch(index, new Leaf(index, value), this.index, this);
        };
        empty.set = function(index, value) {
                return new Leaf(index, value);
        };

        function newBranch(prefix1, node1, prefix2, node2) {
                var mask = makeMask(prefix1, prefix2);
                var prefix = makePrefix(prefix1, mask);
                if (mask < 0) {
                        return prefix1 < 0?
                                new Signed(node1, node2) :
                                new Signed(node2, node1);
                }
                return zero(prefix1, mask)?
                        new Unsigned(prefix, mask, node1, node2) :
                        new Unsigned(prefix, mask, node2, node1);
        }

        function hasPrefix(index, prefix, mask) {
                return makePrefix(index, mask) === prefix;
        }

        function zero(index, mask) {
                return (index & mask) === 0;
        }

        function makePrefix(index, mask) {
                return index & (~(mask - 1) ^ mask);
        }

        function makeMask(prefix1, prefix2) {
                return greatestPowerOfTwo(prefix1 ^ prefix2);
        }

        function greatestPowerOfTwo(value) {
                value |= value >> 1;
                value |= value >> 2;
                value |= value >> 4;
                value |= value >> 8;
                value |= value >> 16;
                value ^= value >>> 1;
                return value;
        }

        return SparseArray;
}());
</script>
<script>
var arraySize = 2000;
var switchArray = new SwitchArray();
var propertyArray = new PropertyArray();
var object = {};
</script>

Setup

var sum = 0;

Test runner

switchArray = new SwitchArray();
for (var i = 0; i < arraySize; ++i) {
  switchArray.set(i, i);
}
 

propertyArray = new PropertyArray();
for (var i = 0; i < arraySize; ++i) {
  propertyArray.set(i, i);
}
 

for (var i = 0; i < arraySize; ++i) {
  sum += switchArray.get(i);
}

for (var i = 0; i < arraySize; ++i) {
  sum += propertyArray.get(i);
}

var object = {};
for (var i = 0; i < arraySize; ++i) {
  object[i] = i;
}
 

Revisions

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

• Revision 1: published on October 26, 2013