blob: b7010de24b6c98fde3482c178570e047714f7059 [file] [log] [blame]
/*
* Copyright (C) 2009 Google Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following disclaimer
* in the documentation and/or other materials provided with the
* distribution.
* * Neither the name of Google Inc. nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
// GridSort
//
// This test is designed to test the performance of sorting a grid of nodes
// such as what you might use in a spreadsheet application.
// returns an array of integers from 0 to totalCells
function generateValuesArray(totalCells) {
var values = [];
for (var i = 0; i < totalCells; i++)
values[i] = i;
return values;
}
// creates value text nodes in a table using DOM methods
function populateTableUsingDom(tableId, width, height) {
var table = document.getElementById(tableId);
var values = generateValuesArray(width * height);
for (var i = 0; i < height; i++) {
var row = table.insertRow(i);
for (var j = 0; j < width; j++) {
var cell = row.insertCell(j);
var valueIndex = Math.floor(Math.random() * values.length);
var value = values.splice(valueIndex, 1);
cell.appendChild(document.createTextNode(value));
}
}
}
// returns HTML string for rows/columns of table data
function getTableContentHTML(width, height) {
var values = generateValuesArray(width * height);
var html = []; // fragments we will join together at the end
var htmlIndex = 0;
for (var i = 0; i < height; i++) {
html.push("<tr>");
for (var j = 0; j < width; j++) {
html.push("<td>");
var valueIndex = Math.floor(Math.random() * values.length);
var value = values.splice(valueIndex, 1);
html.push(value);
html.push("</td>");
}
html.push("</tr>");
}
return html.join("");
}
// When sorting a table by a column, we create one of these for each
// cell in the column, and it keeps pointers to all the nodes in that
// row. This way we can sort an array of SortHelper objects, and then
// use the sibling node pointers to move all values in a row to their
// proper place according to the new sort order.
function SortHelper(row, index) {
this.nodes = [];
var numCells = row.cells.length;
for (var i = 0; i < numCells; i++)
this.nodes[i] = row.cells[i].firstChild;
this.originalIndex = index;
}
function compare(a, b) {
return a - b;
}
// sorts all rows of the table on a given column
function sortTableOnColumn(table, columnIndex) {
var numRows = table.rows.length;
var sortHelpers = [];
for (var i = 0; i < numRows; i++)
sortHelpers.push(new SortHelper(table.rows[i], i));
// sort by nodeValue with original position breaking ties
sortHelpers.sort(function(a, b) {
var cmp = compare(Number(a.nodes[columnIndex].nodeValue), Number(b.nodes[columnIndex].nodeValue));
if (cmp === 0)
return compare(a.originalIndex, b.originalIndex);
return cmp;
});
// now place all cells in their new position
var numSortHelpers = sortHelpers.length;
for (var i = 0; i < numSortHelpers; i++) {
var helper = sortHelpers[i];
if (i == helper.originalIndex)
continue; // no need to move this row
var columnCount = table.rows[i].cells.length;
for (var j = 0; j < columnCount; j++) {
var cell = table.rows[i].cells[j];
if (cell.firstChild) {
// a SortHelper will still have a reference to this node, so it
// won't get orphaned/garbage collected
cell.removeChild(cell.firstChild);
}
cell.appendChild(helper.nodes[j]);
}
}
}
function clearExistingTable() {
var table = document.getElementById("gridsort_table");
if (table) {
// clear out existing table
table.parentNode.removeChild(table);
}
}
function createTableUsingDom() {
clearExistingTable();
var table = document.createElement("table");
table.id = "gridsort_table";
table.border = 1;
document.getElementById("benchmark_content").appendChild(table);
populateTableUsingDom("gridsort_table", 60, 60);
}
function createTableUsingInnerHtml() {
clearExistingTable();
var tableContent = getTableContentHTML(60, 60);
var html = "<table id='gridsort_table' border='1'>" + tableContent + "</table>";
document.getElementById("benchmark_content").innerHTML = html;
}
function sortTable() {
var table = document.getElementById("gridsort_table");
// TODO - it might be interesting to sort several (or all)
// columns in succession, but for now that's fairly slow
sortTableOnColumn(table, 0);
}
var GridSortTest = new BenchmarkSuite('GridSort', [
new Benchmark("SortDomTable (60x60)", sortTable, createTableUsingDom, null, false),
new Benchmark("SortInnerHtmlTable (60x60)", sortTable, createTableUsingInnerHtml, null, false)
]);