petewarden/openheatmap — Issue #9: Performance (Canvas implementation)
Author: galund-mintel
Created: 2012-02-03 14:46:57+00:00
State: open

We were using the Canvas implementation of OpenHeatMap, and were trying to push through several frames per second of CSV data, for a dynamically updating map. Performance was poor and we were getting only about 1fps, but with a few code changes we were able to get a good result up to about 10fps, which looked smooth enough.

The issue was that the Rectangle constructor had to be called many times, and its implementation wasn't very efficient - the fix was to use prototype to create the object's functions (patch below).

Here's some profiling done (in Chrome) before our change:

77.86%	79.37%	jquery.openheatmap.js:4464
Rectangle
8.93%	10.14%	jquery.openheatmap.js:4771
BucketGrid.getContentsAt
3.54%	3.54%	(garbage collector)
1.81%	1.87%	jquery.openheatmap.js:4218
OpenHeatMap.drawImage
1.80%	93.39%	jquery.openheatmap.js:3707
OpenHeatMap.drawPointBlobTile
1.73%	91.13%	jquery.openheatmap.js:4766
BucketGrid.getContentsAtPoint
0.44%	0.45%	jquery.openheatmap.js:4502
Rectangle.right
0.39%	0.39%	jquery.openheatmap.js:4483
Rectangle.bottom
0.33%	0.33%	jquery.openheatmap.js:4233
OpenHeatMap.writePixel

(etc.)

And after:
63%	50.20%	jquery.openheatmap.js:4767
BucketGrid.getContentsAt
13.92%	13.92%	(program)
12.34%	12.56%	jquery.openheatmap.js:4218
OpenHeatMap.drawImage
7.64%	67.30%	jquery.openheatmap.js:3707
OpenHeatMap.drawPointBlobTile
3.75%	55.72%	jquery.openheatmap.js:4762
BucketGrid.getContentsAtPoint
1.79%	80.50%	jquery.openheatmap.js:2156
OpenHeatMap.drawMapIntoMainBitmap
1.76%	1.76%	jquery.openheatmap.js:4464
Rectangle
1.65%	1.65%	(garbage collector)
1.32%	1.32%	jquery.openheatmap.js:4233
OpenHeatMap.writePixel
1.14%	1.22%	jquery.openheatmap.js:4410
Point
0.89%	0.90%	jquery.openheatmap.js:4485
Rectangle.bottom
0.87%	0.92%	jquery.openheatmap.js:4167
OpenHeatMap.clearCanvas
0.66%	0.68%	jquery.openheatmap.js:4504
Rectangle.right
0.63%	0.75%	jquery.openheatmap.js:4143
OpenHeatMap.beginDrawing
(etc.)

Here is the patch, I will attempt to fork and commit the patch somewhere but the repo is massive so I'm having trouble getting it through our firewall.

```

4482,4487d4481
<
< this.bottom = function(newY) {
< if (typeof newY !== 'undefined')
< this.height = (newY-this.y);
< return (this.y+this.height);
< };
4489,4491c4483,4493
< this.bottomRight = function() {
< return new Point(this.right(), this.bottom());
< };
---
> return this;
> }
> Rectangle.prototype.bottom = function(newY) {
> if (typeof newY !== 'undefined')
>	this.height = (newY-this.y);
> return (this.y+this.height);
> };
>
> Rectangle.prototype.bottomRight = function() {
> return new Point(this.right(), this.bottom());
> };
4493,4519c4495,4502
< this.left = function(newX) {
< if (typeof newX !== 'undefined')
< {
< this.width += (this.x-newX);
< this.x = newX;
< }
< return this.x;
< };
<
< this.right = function(newX) {
< if (typeof newX !== 'undefined')
< this.width = (newX-this.x);
< return (this.x+this.width);
< };
<
< this.size = function() {
< return new Point(this.width, this.height);
< };
<
< this.top = function(newY) {
< if (typeof newY !== 'undefined')
< {
< this.height += (this.y-newY);
< this.y = newY;
< }
< return this.y;
< };
---
> Rectangle.prototype.left = function(newX) {
> if (typeof newX !== 'undefined')
> {
>	this.width += (this.x-newX);
>	this.x = newX;
> }
> return this.x;
> };
4521,4523c4504,4520
< this.topLeft = function() {
< return new Point(this.x, this.y);
< };
---
> Rectangle.prototype.right = function(newX) {
> if (typeof newX !== 'undefined')
>	this.width = (newX-this.x);
> return (this.x+this.width);
> };
>
> Rectangle.prototype.size = function() {
> return new Point(this.width, this.height);
> };
> Rectangle.prototype.top = function(newY) {
> if (typeof newY !== 'undefined')
> {
>	this.height += (this.y-newY);
>	this.y = newY;
> }
> return this.y;
> };
4525,4558c4522,4666
< this.clone = function() {
< return new Rectangle(this.x, this.y, this.width, this.height);
< };
<
< this.contains = function(x, y) {
< var isInside =
< (x>=this.x)&&
< (y>=this.y)&&
< (x=this.x)&&
< (rect.y>=this.y)&&
< (rect.right()<=this.right())&&
< (rect.bottom()<=this.bottom());
< return isInside;
< };
<
< this.equals = function(toCompare) {
< var isIdentical =
< (toCompare.x===this.x)&&
< (toCompare.y===this.y)&&
< (toCompare.width===this.width)&&
< (toCompare.height===this.height);
< return isIdentical;
< };
---
> Rectangle.prototype.topLeft = function() {
> return new Point(this.x, this.y);
> };
>
> Rectangle.prototype.clone = function() {
> return new Rectangle(this.x, this.y, this.width, this.height);
> };
>
> Rectangle.prototype.contains = function(x, y) {
> var isInside =
>	(x>=this.x)&&
>	(y>=this.y)&&
>	(x	(y return isInside;
> };
>
> Rectangle.prototype.containsPoint = function(point) {
> return this.contains(point.x, point.y);
> };
>
> Rectangle.prototype.containsRect = function(rect) {
> var isInside =
>	(rect.x>=this.x)&&
>	(rect.y>=this.y)&&
>	(rect.right()<=this.right())&&
>	(rect.bottom()<=this.bottom());
> return isInside;
> };
>
> Rectangle.prototype.equals = function(toCompare) {
> var isIdentical =
>	(toCompare.x===this.x)&&
>	(toCompare.y===this.y)&&
>	(toCompare.width===this.width)&&
>	(toCompare.height===this.height);
> return isIdentical;
> };
>
> Rectangle.prototype.inflate = function(dx, dy) {
> this.x -= dx;
> this.y -= dy;
> this.width += (2*dx);
> this.height += (2*dy);
> };
>
> Rectangle.prototype.inflatePoint = function(point) {
> this.inflate(point.x, point.y);
> };
>
> Rectangle.prototype.inclusiveRangeContains = function(value, min, max) {
> var isInside =
>	(value>=min)&&
>	(value<=max);
>
> return isInside;
> };
>
> Rectangle.prototype.intersectRange = function(aMin, aMax, bMin, bMax) {
>
> var maxMin = Math.max(aMin, bMin);
> if (!this.inclusiveRangeContains(maxMin, aMin, aMax)||
>	!this.inclusiveRangeContains(maxMin, bMin, bMax))
>	return null;
>
> var minMax = Math.min(aMax, bMax);
>
> if (!this.inclusiveRangeContains(minMax, aMin, aMax)||
>	!this.inclusiveRangeContains(minMax, bMin, bMax))
>	return null;
>
> return { min: maxMin, max: minMax };
> };
>
> Rectangle.prototype.intersection = function(toIntersect) {
> var xSpan = this.intersectRange(
>	this.x, this.right(),
>	toIntersect.x, toIntersect.right());
>
> if (!xSpan)
>	return null;
>
> var ySpan = this.intersectRange(
>	this.y, this.bottom(),
>	toIntersect.y, toIntersect.bottom());
>
> if (!ySpan)
>	return null;
>
> var result = new Rectangle(
>	xSpan.min,
>	ySpan.min,
>	(xSpan.max-xSpan.min),
>	(ySpan.max-ySpan.min));
>
> return result;
> };
>
> Rectangle.prototype.intersects = function(toIntersect) {
> var intersection = this.intersection(toIntersect);
>
> return (typeof intersection !== 'undefined');
> };
>
> Rectangle.prototype.isEmpty = function() {
> return ((this.width<=0)||(this.height<=0));
> };
>
> Rectangle.prototype.offset = function(dx, dy) {
> this.x += dx;
> this.y += dy;
> };
>
> Rectangle.prototype.offsetPoint = function(point) {
> this.offset(point.x, point.y);
> };
>
> Rectangle.prototype.setEmpty = function() {
> this.x = 0;
> this.y = 0;
> this.width = 0;
> this.height = 0;
> };
>
> Rectangle.prototype.toString = function() {
> var result = '{';
> result += '"x":'+this.x+',';
> result += '"y":'+this.y+',';
> result += '"width":'+this.width+',';
> result += '"height":'+this.height+'}';
>
> return result;
> };
>
> Rectangle.prototype.union = function(toUnion) {
> var minX = Math.min(toUnion.x, this.x);
> var maxX = Math.max(toUnion.right(), this.right());
> var minY = Math.min(toUnion.y, this.y);
> var maxY = Math.max(toUnion.bottom(), this.bottom());
>
> var result = new Rectangle(
>	minX,
>	minY,
>	(maxX-minX),
>	(maxY-minY));
4560,4579c4668,4669
< this.inflate = function(dx, dy) {
< this.x -= dx;
< this.y -= dy;
< this.width += (2*dx);
< this.height += (2*dy);
< };
<
< this.inflatePoint = function(point) {
< this.inflate(point.x, point.y);
< };
<
< this.inclusiveRangeContains = function(value, min, max) {
< var isInside =
< (value>=min)&&
< (value<=max);
<
< return isInside;
< };
<
< this.intersectRange = function(aMin, aMax, bMin, bMax) {
---
> return result;
> };
4581,4643c4671,4701
< var maxMin = Math.max(aMin, bMin);
< if (!this.inclusiveRangeContains(maxMin, aMin, aMax)||
< !this.inclusiveRangeContains(maxMin, bMin, bMax))
< return null;
<
< var minMax = Math.min(aMax, bMax);
<
< if (!this.inclusiveRangeContains(minMax, aMin, aMax)||
< !this.inclusiveRangeContains(minMax, bMin, bMax))
< return null;
<
< return { min: maxMin, max: minMax };
< };
<
< this.intersection = function(toIntersect) {
< var xSpan = this.intersectRange(
< this.x, this.right(),
< toIntersect.x, toIntersect.right());
<
< if (!xSpan)
< return null;
<
< var ySpan = this.intersectRange(
< this.y, this.bottom(),
< toIntersect.y, toIntersect.bottom());
<
< if (!ySpan)
< return null;
<
< var result = new Rectangle(
< xSpan.min,
< ySpan.min,
< (xSpan.max-xSpan.min),
< (ySpan.max-ySpan.min));
<
< return result;
< };
<
< this.intersects = function(toIntersect) {
< var intersection = this.intersection(toIntersect);
<
< return (typeof intersection !== 'undefined');
< };
<
< this.isEmpty = function() {
< return ((this.width<=0)||(this.height<=0));
< };
<
< this.offset = function(dx, dy) {
< this.x += dx;
< this.y += dy;
< };
<
< this.offsetPoint = function(point) {
< this.offset(point.x, point.y);
< };
<
< this.setEmpty = function() {
< this.x = 0;
< this.y = 0;
< this.width = 0;
< this.height = 0;
< };
---
> function BucketGrid(boundingBox, rows, columns)
> {
> this._boundingBox = boundingBox;
> this._rows = rows;
> this._columns = columns;
>
> this._grid = [];
>
> this._originLeft = boundingBox.left();
> this._originTop = boundingBox.top();
>
> this._columnWidth = this._boundingBox.width/this._columns;
> this._rowHeight = this._boundingBox.height/this._rows;
>
> for (var rowIndex = 0; rowIndex {
>	this._grid[rowIndex] = [];
>
>	var rowTop = (this._originTop+(this._rowHeight*rowIndex));
>
>	for (var columnIndex = 0; columnIndex	{
>	var columnLeft = (this._originLeft+(this._columnWidth*columnIndex));
>	this._grid[rowIndex][columnIndex] = {
>	head_index: 0,
>	contents: { }
>	};
>	}
> }
> return this;
> };
4645,4653c4703,4706
< this.toString = function() {
< var result = '{';
< result += '"x":'+this.x+',';
< result += '"y":'+this.y+',';
< result += '"width":'+this.width+',';
< result += '"height":'+this.height+'}';
<
< return result;
< };
---
> BucketGrid.prototype.insertObjectAtPoint = function(point, object)
> {
> this.insertObjectAt(new Rectangle(point.x, point.y, 0, 0), object);
> };
4655,4668c4708,4728
< this.union = function(toUnion) {
< var minX = Math.min(toUnion.x, this.x);
< var maxX = Math.max(toUnion.right(), this.right());
< var minY = Math.min(toUnion.y, this.y);
< var maxY = Math.max(toUnion.bottom(), this.bottom());
<
< var result = new Rectangle(
< minX,
< minY,
< (maxX-minX),
< (maxY-minY));
<
< return result;
< };
---
> BucketGrid.prototype.insertObjectAt = function(boundingBox, object)
> {
> var leftIndex = Math.floor((boundingBox.left()-this._originLeft)/this._columnWidth);
> var rightIndex = Math.floor((boundingBox.right()-this._originLeft)/this._columnWidth);
> var topIndex = Math.floor((boundingBox.top()-this._originTop)/this._rowHeight);
> var bottomIndex = Math.floor((boundingBox.bottom()-this._originTop)/this._rowHeight);
>
> leftIndex = Math.max(leftIndex, 0);
> rightIndex = Math.min(rightIndex, (this._columns-1));
> topIndex = Math.max(topIndex, 0);
> bottomIndex = Math.min(bottomIndex, (this._rows-1));
>
> for (var rowIndex = topIndex; rowIndex<=bottomIndex; rowIndex+=1)
> {
>	for (var columnIndex = leftIndex; columnIndex<=rightIndex; columnIndex+=1)
>	{
>	var bucket = this._grid[rowIndex][columnIndex];
>	bucket.contents[bucket.head_index] = object;
>	bucket.head_index += 1;
>	}
> }
4670,4671c4730
< return this;
< }
---
> };
4673c4732
< function BucketGrid(boundingBox, rows, columns)
---
> BucketGrid.prototype.removeObjectAt = function(boundingBox, object)
4675,4709c4734,4757
< this.__constructor = function(boundingBox, rows, columns)
< {
< this._boundingBox = boundingBox;
< this._rows = rows;
< this._columns = columns;
<
< this._grid = [];
<
< this._originLeft = boundingBox.left();
< this._originTop = boundingBox.top();
<
< this._columnWidth = this._boundingBox.width/this._columns;
< this._rowHeight = this._boundingBox.height/this._rows;
<
< for (var rowIndex = 0; rowIndex var leftIndex = Math.floor((boundingBox.left()-this._originLeft)/this._columnWidth);
> var rightIndex = Math.floor((boundingBox.right()-this._originLeft)/this._columnWidth);
> var topIndex = Math.floor((boundingBox.top()-this._originTop)/this._rowHeight);
> var bottomIndex = Math.floor((boundingBox.bottom()-this._originTop)/this._rowHeight);
>
> leftIndex = Math.max(leftIndex, 0);
> rightIndex = Math.min(rightIndex, (this._columns-1));
> topIndex = Math.max(topIndex, 0);
> bottomIndex = Math.min(bottomIndex, (this._rows-1));
>
> for (var rowIndex = topIndex; rowIndex<=bottomIndex; rowIndex+=1)
> {
>	for (var columnIndex = leftIndex; columnIndex<=rightIndex; columnIndex+=1)
>	{
>	var bucket = this._grid[rowIndex][columnIndex];
>	for (var index=0; index	{
>	if (bucket.contents[index]==object)
>	{
>	delete bucket.contents[index];
>	break;
>	}
>	}
>	}
4712,4722c4760
< this.insertObjectAt = function(boundingBox, object)
< {
< var leftIndex = Math.floor((boundingBox.left()-this._originLeft)/this._columnWidth);
< var rightIndex = Math.floor((boundingBox.right()-this._originLeft)/this._columnWidth);
< var topIndex = Math.floor((boundingBox.top()-this._originTop)/this._rowHeight);
< var bottomIndex = Math.floor((boundingBox.bottom()-this._originTop)/this._rowHeight);
<
< leftIndex = Math.max(leftIndex, 0);
< rightIndex = Math.min(rightIndex, (this._columns-1));
< topIndex = Math.max(topIndex, 0);
< bottomIndex = Math.min(bottomIndex, (this._rows-1));
---
> };
4724,4769c4762,4765
< for (var rowIndex = topIndex; rowIndex<=bottomIndex; rowIndex+=1)
< {
< for (var columnIndex = leftIndex; columnIndex<=rightIndex; columnIndex+=1)
< {
< var bucket = this._grid[rowIndex][columnIndex];
< bucket.contents[bucket.head_index] = object;
< bucket.head_index += 1;
< }
< }
<
< };
<
< this.removeObjectAt = function(boundingBox, object)
< {
< var leftIndex = Math.floor((boundingBox.left()-this._originLeft)/this._columnWidth);
< var rightIndex = Math.floor((boundingBox.right()-this._originLeft)/this._columnWidth);
< var topIndex = Math.floor((boundingBox.top()-this._originTop)/this._rowHeight);
< var bottomIndex = Math.floor((boundingBox.bottom()-this._originTop)/this._rowHeight);
<
< leftIndex = Math.max(leftIndex, 0);
< rightIndex = Math.min(rightIndex, (this._columns-1));
< topIndex = Math.max(topIndex, 0);
< bottomIndex = Math.min(bottomIndex, (this._rows-1));
<
< for (var rowIndex = topIndex; rowIndex<=bottomIndex; rowIndex+=1)
< {
< for (var columnIndex = leftIndex; columnIndex<=rightIndex; columnIndex+=1)
< {
< var bucket = this._grid[rowIndex][columnIndex];
< for (var index=0; index BucketGrid.prototype.getContentsAtPoint = function(point)
> {
> return this.getContentsAt(new Rectangle(point.x, point.y, 0, 0));
> };
4771,4796c4767,4769
< this.getContentsAt = function(boundingBox)
< {
< var result = [];
<
< var leftIndex = Math.floor((boundingBox.left()-this._originLeft)/this._columnWidth);
< var rightIndex = Math.floor((boundingBox.right()-this._originLeft)/this._columnWidth);
< var topIndex = Math.floor((boundingBox.top()-this._originTop)/this._rowHeight);
< var bottomIndex = Math.floor((boundingBox.bottom()-this._originTop)/this._rowHeight);
<
< leftIndex = Math.max(leftIndex, 0);
< rightIndex = Math.min(rightIndex, (this._columns-1));
< topIndex = Math.max(topIndex, 0);
< bottomIndex = Math.min(bottomIndex, (this._rows-1));
<
< for (var rowIndex = topIndex; rowIndex<=bottomIndex; rowIndex+=1)
< {
< for (var columnIndex = leftIndex; columnIndex<=rightIndex; columnIndex+=1)
< {
< var bucket = this._grid[rowIndex][columnIndex];
< for (var objectIndex in bucket.contents)
< result.push(bucket.contents[objectIndex]);
< }
< }
<
< return result;
< };
---
> BucketGrid.prototype.getContentsAt = function(boundingBox)
> {
> var result = [];
4798c4771,4789
< this.__constructor(boundingBox, rows, columns);
---
> var leftIndex = Math.floor((boundingBox.left()-this._originLeft)/this._columnWidth);
> var rightIndex = Math.floor((boundingBox.right()-this._originLeft)/this._columnWidth);
> var topIndex = Math.floor((boundingBox.top()-this._originTop)/this._rowHeight);
> var bottomIndex = Math.floor((boundingBox.bottom()-this._originTop)/this._rowHeight);
>
> leftIndex = Math.max(leftIndex, 0);
> rightIndex = Math.min(rightIndex, (this._columns-1));
> topIndex = Math.max(topIndex, 0);
> bottomIndex = Math.min(bottomIndex, (this._rows-1));
>
> for (var rowIndex = topIndex; rowIndex<=bottomIndex; rowIndex+=1)
> {
>	for (var columnIndex = leftIndex; columnIndex<=rightIndex; columnIndex+=1)
>	{
>	var bucket = this._grid[rowIndex][columnIndex];
>	for (var objectIndex in bucket.contents)
>	result.push(bucket.contents[objectIndex]);
>	}
> }
4800,4801c4791,4792
< return this;
< }
---
> return result;
> };
```