Benchmark: HashBounds - MeasureThat.net

Script Preparation code:


function Grid(g, p, size,minc) {
    this.MIN = minc * -1;
    this.POWER = g;
    this.LEVEL = p;
    this.SIZE = size;
    this.DATA = {};
    this.LENGTH = 0;
    this.init()
}
Grid.prototype.init = function () {
    if (this.SIZE >= 65535) {
        throw "Maximum amount of buckets are 65535^2"
    } // Max limit is 65535 (16 bits) 
    // console.log(this.SIZE)
    for (var j = this.MIN; j <= this.SIZE; ++j) {
        var x = j << 16
        for (var i = this.MIN; i <= this.SIZE; ++i) {

            var key = this._getKey(x, i);
            // console.log(key)
            this.DATA[key] = new Map()

        }
    }

}
Grid.prototype._every = function (m, c) {
    var a = m.entries()
    var b;
    while (b = a.next().value) {
        if (!c(b[1], b[0])) return false;
    }
    return true;
}

Grid.prototype.getKey = function (x, y) {
    return {
        x: x >> this.POWER,
        y: y >> this.POWER
    }
}
Grid.prototype._getKey = function (x, y) {
    return x | y

}
Grid.prototype.checkBorders = function (x, y) {
    return !(x > this.SIZE || y > this.SIZE)

}
Grid.prototype.insert = function (node) {

    //   var a = this.getKey(node.bounds.width, node.bounds.height);
    // if (a.x + a.y >= 2 && this.LEVEL != 0) return false;
    this.LENGTH++;
    var x1 = node.bounds.x,
        y1 = node.bounds.y,
        x2 = node.bounds.x + node.bounds.width,
        y2 = node.bounds.y + node.bounds.height;

    var k1 = this.getKey(x1, y1)
    var k2 = this.getKey(x2, y2)
    node.hash.k1 = k1
    node.hash.k2 = k2
    node.hash.level = this.LEVEL
    var lenX = k2.x + 1,
        lenY = k2.y + 1;
    for (var j = k1.x; j < lenX; ++j) {
        var x = j << 16;
        for (var i = k1.y; i < lenY; ++i) {

            var ke = this._getKey(x, i);
            // console.log(ke)
            this.DATA[ke].set(node._HashID, node)
        }

    }
    return true;
}
Grid.prototype.delete = function (node) {
    var k1 = node.hash.k1
    var k2 = node.hash.k2
    this.LENGTH--;
    var lenX = k2.x + 1,
        lenY = k2.y + 1;
    for (var j = k1.x; j < lenX; ++j) {
        var x = j << 16;
        for (var i = k1.y; i < lenY; ++i) {


            var ke = this._getKey(x, i);

            this.DATA[ke].delete(node._HashID)
        }

    }
}
Grid.prototype.toArray = function (array, bounds) {
    if (this.LENGTH <= 0) return;

    var x1 = bounds.x,
        y1 = bounds.y,
        x2 = bounds.x + bounds.width,
        y2 = bounds.y + bounds.height,
        h = {};

    var k1 = this.getKey(x1, y1)
    var k2 = this.getKey(x2, y2)
    for (var j = k1.x; j <= k2.x; ++j) {
        var x = j << 16;
        for (var i = k1.y; i <= k2.y; ++i) {

            var ke = this._getKey(x, i);

            if (this.DATA[ke]) this.DATA[ke].forEach((node, i) => {

                if (h[i]) return;
                h[i] = true;
                array.push(node)
            })
        }

    }
}
Grid.prototype.every = function (bounds, call) {
    if (this.LENGTH <= 0) return true;
    var x1 = bounds.x,
        y1 = bounds.y,
        x2 = bounds.x + bounds.width,
        y2 = bounds.y + bounds.height,
        h = {};

    var k1 = this.getKey(x1, y1)
    var k2 = this.getKey(x2, y2)
    for (var j = k1.x; j <= k2.x; ++j) {
        var x = j << 16;
        for (var i = k1.y; i <= k2.y; ++i) {

            var ke = this._getKey(x, i);

            if (this.DATA[ke])
                if (!this._every(this.DATA[ke], (a, b) => {

                        if (h[b]) return true;
                        h[b] = true;
                        return call(a, b);
                    })) return false;
        }

    }
    return true;
}
Grid.prototype.forEach = function (bounds, call) {
    if (this.LENGTH <= 0) return;
    var x1 = bounds.x,
        y1 = bounds.y,
        x2 = bounds.x + bounds.width,
        y2 = bounds.y + bounds.height,
        h = {};

    var k1 = this.getKey(x1, y1)
    var k2 = this.getKey(x2, y2)

    for (var j = k1.x; j <= k2.x; ++j) {
        var x = j << 16;
        for (var i = k1.y; i <= k2.y; ++i) {

            var ke = this._getKey(x, i);

            if (this.DATA[ke])
                this.DATA[ke].forEach((a, b) => {
                    if (h[b]) return;
                    h[b] = true;
                    call(a, b)
                })
        }

    }

}

function HashBounds(power, lvl, max,minc) {
    this.INITIAL = power;
    this.LVL = lvl;
this.MINC = minc;
    this.MAX = max;
    this.MIN = power + 1;
    this.LEVELS = []
    this.lastid = 0;
    this.createLevels()
    this.SQRT = [];
    this.setupSQRT()
}

HashBounds.prototype.setupSQRT = function () {
    for (var i = 0; i < 255; ++i) {
        this.SQRT.push(Math.floor(Math.sqrt(i)))
    }
}

HashBounds.prototype.createLevels = function () {
    this.LEVELS = [];
    var a = this.INITIAL;
    for (var i = 0; i < this.LVL; i++, a++) {

        this.LEVELS.push(new Grid(a, i, this.MAX >> a,this.MINC >> a))
    }
}
HashBounds.prototype.clear = function () {
    this.createLevels();
}
HashBounds.prototype.update = function (node) {
    this.delete(node)
    this.insert(node)
}
HashBounds.prototype.insert = function (node) {
    if (node.hash) throw "ERR: A node cannot be already in a hash!"
    var bounds = node.bounds;
    node.hash = {}
    if (!node._HashID) node._HashID = ++this.lastid;
    if (node._HashSize == node.bounds.width + node.bounds.height) {
        this.LEVELS[node._HashIndex].insert(node);
        return;
    }

    var index = this.SQRT[(node.bounds.width + node.bounds.height) >> this.MIN]
    if (index >= this.LVL) index = this.LVL - 1;

    node._HashIndex = index;
    node._HashSize = node.bounds.width + node.bounds.height;
    this.LEVELS[index].insert(node);
    //for (var i = 0; i < len; ++i) {
    //   if (this.LEVELS[len - i - 1].insert(node)) break;
    //}
}


HashBounds.prototype.delete = function (node) {
    if (!node.hash) throw "ERR: Node is not in a hash!"
    this.LEVELS[node.hash.level].delete(node)
    node.hash = null;
}
HashBounds.prototype.toArray = function (bounds) {
    var array = [];
    for (var i = 0; i < this.LEVELS.length; i++) {
        this.LEVELS[i].toArray(array, bounds)
    }
    return array;
}
HashBounds.prototype.every = function (bounds, call) {
    for (var i = 0; i < this.LEVELS.length; i++) {
        if (!this.LEVELS[i].every(bounds, call)) return false;
    }
    return true;
}
HashBounds.prototype.forEach = function (bounds, call) {
    for (var i = 0; i < this.LEVELS.length; i++) {
        this.LEVELS[i].forEach(bounds, call)
    }
}


if (typeof module !== 'undefined' && typeof module.exports !== 'undefined') {
    module.exports = HashBounds;
} else {
    if (typeof define === 'function' && define.amd) {
        define([], function () {
            return HashBounds;
        });
    } else {
        window.HashBounds = HashBounds;
    }
}

var Hash = new HashBounds(4,4,150)
var obj = {
 bounds: {
 x: Math.floor(Math.random() * 100),
   y: Math.floor(Math.random() * 100),
   width: Math.floor(Math.random() * 49),
   height: Math.floor(Math.random() * 49)
   
 }
  
}
Hash.insert(obj)

obj.x = Math.floor(Math.random() * 100)
obj.y = Math.floor(Math.random() * 100)
var obj2 = {
 bounds: {
 x: Math.floor(Math.random() * 100),
   y: Math.floor(Math.random() * 100),
   width: Math.floor(Math.random() * 49),
   height: Math.floor(Math.random() * 49)
   
 }
  
}
Hash.insert(obj2)

obj2.x = Math.floor(Math.random() * 100)
obj2.y = Math.floor(Math.random() * 100)

Tests:

Insert
Hash.insert({ bounds: { x: Math.floor(Math.random() * 100), y: Math.floor(Math.random() * 100), width: Math.floor(Math.random() * 49), height: Math.floor(Math.random() * 49) } })
Update
Hash.update(obj)
delete-insert
Hash.delete(obj2) Hash.insert(obj2)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Insert
Update
delete-insert

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

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

LLMs can make mistakes. Check important info.

Based on the provided code, I'll assume that this is a JavaScript implementation of a hash table data structure. The task seems to be to analyze and optimize the performance of the `HashBounds` class.

After analyzing the code, here are some observations and potential improvements:

1. **Performance optimization**: The `HashBounds.prototype.every` and `HashBounds.prototype.forEach` methods seem to be iterating over the levels of the hash table, but without any obvious optimizations. Consider using a more efficient data structure or algorithm for these operations.
2. **Bounds calculations**: In the `Insert` method, bounds are calculated using `Math.floor(Math.random() * 100)`. This could lead to frequent recalculations if the random values are not properly bounded. Consider using a fixed range or scaling the random values to reduce calculation frequency.
3. **Hash table resizing**: The code does not seem to handle hash table resizing, which can significantly impact performance as the size of the hash table grows. Consider adding logic to resize the hash table when it reaches a certain threshold.

To provide a more specific answer, I would need more information about the desired optimizations and the current performance characteristics of the `HashBounds` class. However, some general suggestions for improvement could be:

* Use a more efficient data structure, such as a binary search tree or a skip list, to reduce the time complexity of bounds calculations and updates.
* Implement bounds caching or memoization to reduce the number of recalculations.
* Add logic to resize the hash table when it reaches a certain threshold to maintain optimal performance.

Please provide more context or information about the desired optimizations, and I'll be happy to help you further.

Related benchmarks:

HashBounds (version: 0)

Comparing performance of: Insert vs Update vs delete-insert

Created: 9 years ago by: Guest

Jump to the latest result

Insert

Update

delete-insert

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

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