From ff1074cd53a1818d415c5da0a0acb516e6c02d65 Mon Sep 17 00:00:00 2001 From: Robert Konigsberg Date: Tue, 10 Jul 2012 11:54:13 -0400 Subject: [PATCH] Iterator performance enhancements - turn hasNext and peek into element access, and inline the advance() method. --- auto_tests/tests/utils_test.js | 54 +++++++++++++++++++++--------------------- dygraph-canvas.js | 10 ++++---- dygraph-utils.js | 45 ++++++++++++++--------------------- 3 files changed, 50 insertions(+), 59 deletions(-) diff --git a/auto_tests/tests/utils_test.js b/auto_tests/tests/utils_test.js index 9c8974c..62b2c63 100644 --- a/auto_tests/tests/utils_test.js +++ b/auto_tests/tests/utils_test.js @@ -80,60 +80,60 @@ UtilsTestCase.prototype.testUpdateDeepDecoupled = function() { UtilsTestCase.prototype.testIterator_nopredicate = function() { var array = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']; var iter = Dygraph.createIterator(array, 1, 4); - assertTrue(iter.hasNext()); - assertEquals('b', iter.peek()); + assertTrue(iter.hasNext); + assertEquals('b', iter.peek); assertEquals('b', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); - assertEquals('c', iter.peek()); + assertEquals('c', iter.peek); assertEquals('c', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); assertEquals('d', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); assertEquals('e', iter.next()); - assertFalse(iter.hasNext()); + assertFalse(iter.hasNext); } UtilsTestCase.prototype.testIterator_predicate = function() { var array = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']; var iter = Dygraph.createIterator(array, 1, 4, function(array, idx) { return array[idx] !== 'd' }); - assertTrue(iter.hasNext()); - assertEquals('b', iter.peek()); + assertTrue(iter.hasNext); + assertEquals('b', iter.peek); assertEquals('b', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); - assertEquals('c', iter.peek()); + assertEquals('c', iter.peek); assertEquals('c', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); assertEquals('e', iter.next()); - assertFalse(iter.hasNext()); + assertFalse(iter.hasNext); } UtilsTestCase.prototype.testIterator_empty = function() { var array = []; var iter = Dygraph.createIterator([], 0, 0); - assertFalse(iter.hasNext()); + assertFalse(iter.hasNext); } UtilsTestCase.prototype.testIterator_outOfRange = function() { var array = ['a', 'b', 'c']; var iter = Dygraph.createIterator(array, 1, 4, function(array, idx) { return array[idx] !== 'd' }); - assertTrue(iter.hasNext()); - assertEquals('b', iter.peek()); + assertTrue(iter.hasNext); + assertEquals('b', iter.peek); assertEquals('b', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); - assertEquals('c', iter.peek()); + assertEquals('c', iter.peek); assertEquals('c', iter.next()); - assertFalse(iter.hasNext()); + assertFalse(iter.hasNext); } // Makes sure full array is tested, and that the predicate isn't called @@ -148,25 +148,25 @@ UtilsTestCase.prototype.testIterator_whole_array = function() { return true; }; }); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); assertEquals('a', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); assertEquals('b', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); assertEquals('c', iter.next()); - assertFalse(iter.hasNext()); + assertFalse(iter.hasNext); assertNull(iter.next()); } UtilsTestCase.prototype.testIterator_no_args = function() { var array = ['a', 'b', 'c']; var iter = Dygraph.createIterator(array); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); assertEquals('a', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); assertEquals('b', iter.next()); - assertTrue(iter.hasNext()); + assertTrue(iter.hasNext); assertEquals('c', iter.next()); - assertFalse(iter.hasNext()); + assertFalse(iter.hasNext); assertNull(iter.next()); } diff --git a/dygraph-canvas.js b/dygraph-canvas.js index 4a29848..1bd3595 100644 --- a/dygraph-canvas.js +++ b/dygraph-canvas.js @@ -791,7 +791,7 @@ DygraphCanvasRenderer.prototype._drawSeries = function( strategy.init(); - while(iter.hasNext()) { + while(iter.hasNext) { point = iter.next(); if (point.canvasy === null || point.canvasy != point.canvasy) { if (stepPlot && prevCanvasX !== null) { @@ -802,7 +802,7 @@ DygraphCanvasRenderer.prototype._drawSeries = function( } prevCanvasX = prevCanvasY = null; } else { - nextCanvasY = iter.hasNext() ? iter.peek().canvasy : null; + nextCanvasY = iter.hasNext ? iter.peek.canvasy : null; // TODO: we calculate isNullOrNaN for this point, and the next, and then, when // we iterate, test for isNullOrNaN again. Why bother? var isNextCanvasYNullOrNaN = nextCanvasY === null || nextCanvasY != nextCanvasY; @@ -811,7 +811,7 @@ DygraphCanvasRenderer.prototype._drawSeries = function( // Also consider a point to be "isolated" if it's adjacent to a // null point, excluding the graph edges. if ((!first && !prevCanvasX) || - (iter.hasNext() && isNextCanvasYNullOrNaN)) { + (iter.hasNext && isNextCanvasYNullOrNaN)) { isIsolated = true; } } @@ -936,7 +936,7 @@ DygraphCanvasRenderer.prototype._renderLineChart = function() { fillAlpha + ')'; ctx.fillStyle = err_color; ctx.beginPath(); - while (iter.hasNext()) { + while (iter.hasNext) { point = iter.next(); if (point.name == setName) { // TODO(klausw): this is always true if (!Dygraph.isOK(point.y)) { @@ -1005,7 +1005,7 @@ DygraphCanvasRenderer.prototype._renderLineChart = function() { fillAlpha + ')'; ctx.fillStyle = err_color; ctx.beginPath(); - while(iter.hasNext()) { + while(iter.hasNext) { point = iter.next(); if (point.name == setName) { // TODO(klausw): this is always true if (!Dygraph.isOK(point.y)) { diff --git a/dygraph-utils.js b/dygraph-utils.js index 8cfd861..7aeca8d 100644 --- a/dygraph-utils.js +++ b/dygraph-utils.js @@ -684,46 +684,37 @@ Dygraph.isAndroid = function() { Dygraph.Iterator = function(array, start, length, predicate) { start = start || 0; length = length || array.length; + this.hasNext = true; // Use to identify if there's another element. + this.peek = null; // Use for look-ahead this.array_ = array; this.predicate_ = predicate; this.end_ = Math.min(array.length, start + length); - this.nextIdx_ = start - 1; // use -1 so initial call to advance works. - this.hasNext_ = true; - this.peek_ = null; - this.advance_(); -} - -Dygraph.Iterator.prototype.hasNext = function() { - return this.hasNext_; + this.nextIdx_ = start - 1; // use -1 so initial advance works. + this.next(); // ignoring result. } Dygraph.Iterator.prototype.next = function() { - if (this.hasNext_) { - var obj = this.peek_; - this.advance_(); - return obj; + if (!this.hasNext) { + return null; } - return null; -} + var obj = this.peek; -Dygraph.Iterator.prototype.peek = function() { - return this.peek_; -} - -Dygraph.Iterator.prototype.advance_ = function() { - var nextIdx = this.nextIdx_; - nextIdx++; - while(nextIdx < this.end_) { + var nextIdx = this.nextIdx_ + 1; + var found = false; + while (nextIdx < this.end_) { if (!this.predicate_ || this.predicate_(this.array_, nextIdx)) { - this.peek_ = this.array_[nextIdx]; - this.nextIdx_ = nextIdx; - return; + this.peek = this.array_[nextIdx]; + found = true; + break; } nextIdx++; } this.nextIdx_ = nextIdx; - this.hasNext_ = false; - this.peek_ = null; + if (!found) { + this.hasNext = false; + this.peek = null; + } + return obj; } /** -- 2.7.4