1 /* 2 * Copyright (C) 2009 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google Inc. nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 // GridSort 32 // 33 // This test is designed to test the performance of sorting a grid of nodes 34 // such as what you might use in a spreadsheet application. 35 36 // returns an array of integers from 0 to totalCells 37 function generateValuesArray(totalCells) { 38 var values = []; 39 for (var i = 0; i < totalCells; i++) 40 values[i] = i; 41 return values; 42 } 43 44 // creates value text nodes in a table using DOM methods 45 function populateTableUsingDom(tableId, width, height) { 46 var table = document.getElementById(tableId); 47 var values = generateValuesArray(width * height); 48 49 for (var i = 0; i < height; i++) { 50 var row = table.insertRow(i); 51 for (var j = 0; j < width; j++) { 52 var cell = row.insertCell(j); 53 var valueIndex = Math.floor(Math.random() * values.length); 54 var value = values.splice(valueIndex, 1); 55 cell.appendChild(document.createTextNode(value)); 56 } 57 } 58 } 59 60 // returns HTML string for rows/columns of table data 61 function getTableContentHTML(width, height) { 62 var values = generateValuesArray(width * height); 63 64 var html = []; // fragments we will join together at the end 65 var htmlIndex = 0; 66 67 for (var i = 0; i < height; i++) { 68 html.push("<tr>"); 69 for (var j = 0; j < width; j++) { 70 html.push("<td>"); 71 var valueIndex = Math.floor(Math.random() * values.length); 72 var value = values.splice(valueIndex, 1); 73 html.push(value); 74 html.push("</td>"); 75 } 76 html.push("</tr>"); 77 } 78 return html.join(""); 79 } 80 81 // When sorting a table by a column, we create one of these for each 82 // cell in the column, and it keeps pointers to all the nodes in that 83 // row. This way we can sort an array of SortHelper objects, and then 84 // use the sibling node pointers to move all values in a row to their 85 // proper place according to the new sort order. 86 function SortHelper(row, index) { 87 this.nodes = []; 88 var numCells = row.cells.length; 89 for (var i = 0; i < numCells; i++) 90 this.nodes[i] = row.cells[i].firstChild; 91 this.originalIndex = index; 92 } 93 94 function compare(a, b) { 95 return a - b; 96 } 97 98 // sorts all rows of the table on a given column 99 function sortTableOnColumn(table, columnIndex) { 100 var numRows = table.rows.length; 101 var sortHelpers = []; 102 for (var i = 0; i < numRows; i++) 103 sortHelpers.push(new SortHelper(table.rows[i], i)); 104 105 // sort by nodeValue with original position breaking ties 106 sortHelpers.sort(function(a, b) { 107 var cmp = compare(Number(a.nodes[columnIndex].nodeValue), Number(b.nodes[columnIndex].nodeValue)); 108 if (cmp === 0) 109 return compare(a.originalIndex, b.originalIndex); 110 return cmp; 111 }); 112 113 // now place all cells in their new position 114 var numSortHelpers = sortHelpers.length; 115 for (var i = 0; i < numSortHelpers; i++) { 116 var helper = sortHelpers[i]; 117 if (i == helper.originalIndex) 118 continue; // no need to move this row 119 var columnCount = table.rows[i].cells.length; 120 for (var j = 0; j < columnCount; j++) { 121 var cell = table.rows[i].cells[j]; 122 if (cell.firstChild) { 123 // a SortHelper will still have a reference to this node, so it 124 // won't get orphaned/garbage collected 125 cell.removeChild(cell.firstChild); 126 } 127 cell.appendChild(helper.nodes[j]); 128 } 129 } 130 } 131 132 function clearExistingTable() { 133 var table = document.getElementById("gridsort_table"); 134 if (table) { 135 // clear out existing table 136 table.parentNode.removeChild(table); 137 } 138 } 139 140 function createTableUsingDom() { 141 clearExistingTable(); 142 var table = document.createElement("table"); 143 table.id = "gridsort_table"; 144 table.border = 1; 145 document.getElementById("benchmark_content").appendChild(table); 146 populateTableUsingDom("gridsort_table", 60, 60); 147 } 148 149 function createTableUsingInnerHtml() { 150 clearExistingTable(); 151 var tableContent = getTableContentHTML(60, 60); 152 var html = "<table id='gridsort_table' border='1'>" + tableContent + "</table>"; 153 document.getElementById("benchmark_content").innerHTML = html; 154 } 155 156 function sortTable() { 157 var table = document.getElementById("gridsort_table"); 158 // TODO - it might be interesting to sort several (or all) 159 // columns in succession, but for now that's fairly slow 160 sortTableOnColumn(table, 0); 161 } 162 163 var GridSortTest = new BenchmarkSuite('GridSort', [ 164 new Benchmark("SortDomTable (60x60)", sortTable, createTableUsingDom, null, false), 165 new Benchmark("SortInnerHtmlTable (60x60)", sortTable, createTableUsingInnerHtml, null, false) 166 ]); 167