Performance (Canvas implementation)

[galund]

First of all just wanted to say thank you for OpenHeatMap, it was very fun to play around with...

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.right())&&
<             (y<this.bottom());
<         return isInside;
<     };
<     
<     this.containsPoint = function(point) {
<         return this.contains(point.x, point.y);
<     };
<     
<     this.containsRect = function(rect) {
<         var isInside = 
<             (rect.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<this.right())&&
>   (y<this.bottom());
>     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._rows; rowIndex+=1)
>     {
>   this._grid[rowIndex] = [];
>   
>   var rowTop = (this._originTop+(this._rowHeight*rowIndex));
>   
>   for (var columnIndex = 0; columnIndex<this._columns; columnIndex+=1)
>   {
>       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<this._rows; rowIndex+=1)
<         {
<             this._grid[rowIndex] = [];
<             
<             var rowTop = (this._originTop+(this._rowHeight*rowIndex));
<             
<             for (var columnIndex = 0; columnIndex<this._columns; columnIndex+=1)
<             {
<                 var columnLeft = (this._originLeft+(this._columnWidth*columnIndex));
<                 this._grid[rowIndex][columnIndex] = {
<                     head_index: 0,
<                     contents: { }
<                 };
<             }
<         }         
< 
<     };
<     
<     this.insertObjectAtPoint = function(point, object)
<     {
<         this.insertObjectAt(new Rectangle(point.x, point.y, 0, 0), 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<bucket.contents.length; index+=1)
>       {
>       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<bucket.contents.length; index+=1)
<                 {
<                     if (bucket.contents[index]==object)
<                     {
<                         delete bucket.contents[index];
<                         break;
<                     }
<                 }
<             }
<         }
<         
<     };
<     
<     this.getContentsAtPoint = function(point)
<     {
<         return this.getContentsAt(new Rectangle(point.x, point.y, 0, 0));
<     };

---
> 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;
> };

[FKasa]

It looks like this should be closed.