167 lines
6.1 KiB
JavaScript
167 lines
6.1 KiB
JavaScript
/*
|
|
* 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)
|
|
]);
|