webkit/data/test_shell/sort/sort.js

   1 // sort object
   2
   3 var manual = 0; // single stepping
   4 var interval_time = 0; // setTimeout interval
   5 var inner_loop_enabled = 1; // should the stepper iterate a little during each step
   6
   7 // number of elements
   8 var size = 300;
   9 var query = window.location.search.substring(1);
  10 var params = query.split('&');
  11 for (var i = 0; i < params.length; i++) {
  12   var pos = params[i].indexOf('=');
  13   var key = params[i].substring(0, pos);
  14   var val = params[i].substring(pos+1);
  15   if (key == "size") {
  16     var sz = parseInt(val);
  17     size = Math.max(sz, 3);
  18     size = Math.min(1000, size);
  19   }
  20 }
  21
  22 var log;
  23 function log(msg) {
  24   if (window.console != undefined) {
  25     window.console.log(msg);
  26   }
  27 }
  28
  29 function Sort(name, func) {
  30   this.name = name;
  31   this.func = func;
  32   this.size = size;
  33   this.compare_x = null;
  34   this.compare_y = null;
  35   this.compares = 0;
  36   this.swap_x = null;
  37   this.swap_y = null;
  38   this.swaps = 0;
  39   this.start_time = 0;
  40   this.stop_time = 0;
  41   this.work_queue = new Array();
  42   this.timer = 0;
  43   this.last_time = 0;
  44   this.num_iterations = 0;
  45   this.num_jobs = 0;
  46   this.overhead_total = 0;
  47   this.overhead_min = 1000000;
  48   this.overhead_max = 0;
  49   this.processing_total = 0;
  50   this.processing_min = 1000000;
  51   this.processing_max = 0;
  52   this.step_min = 1000000;
  53   this.step_max = 0;
  54
  55   this.setup();
  56 }
  57
  58 Sort.prototype.setup = function() {
  59   this.size = size;
  60   this.bars = new Array(this.size);
  61   this.numbers = new Array(this.size);
  62   for (i = 0; i < this.size; i++) {
  63     this.numbers[i] = i + 1;
  64   }
  65   for (i = 0; i < this.size; i++) {
  66     var r = Math.floor(Math.random() * this.numbers.length);
  67     if (i != r) {
  68       var tmp = this.numbers[i];
  69       this.numbers[i] = this.numbers[r];
  70       this.numbers[r] = tmp;
  71     }
  72   }
  73 }
  74
  75 Sort.prototype.status = function(str) {
  76   var label = document.getElementById(this.name + "_label");
  77   label.innerHTML = "<b>" + this.name + " Sort</b><br />" + str;
  78 }
  79
  80 Sort.prototype.stepper = function() {
  81   if (!manual) {
  82     var sort = this;
  83     this.timer = setTimeout(function(){sort.stepper();},interval_time);
  84   }
  85   var t = new Date();
  86   var overhead = t - this.last_time;
  87   this.overhead_total += overhead;
  88   this.overhead_min = Math.min(this.overhead_min, overhead);
  89   this.overhead_max = Math.max(this.overhead_max, overhead);
  90   this.last_time = t;
  91
  92   var elapsed = t - this.start_time;
  93   var avg =
  94     Math.floor((elapsed - this.processing_total) / this.num_iterations);
  95   this.status("Overhead: " + avg + "ms");
  96
  97   var ops = 0;
  98   for (;;) {
  99     var count = this.work_queue.length;
 100     if (count > 0) {
 101       var func = this.work_queue.pop();
 102       if (func.status != undefined) {
 103         //this.status(func.status);
 104       }
 105       ops++;
 106       this.num_jobs++;
 107       func();
 108     } else {
 109       break;
 110     }
 111     if (manual || inner_loop_enabled == 0) {
 112       break;
 113     }
 114     t = new Date();
 115     // If any measurable time has passed, we're good.
 116     // Since the Date has a resolution of 15ms on Windows
 117     // there's no way to differentiate accurately for anything
 118     // less than that.  We don't want to process for longer than
 119     // the timer interval anyway (which is about 10ms), so this
 120     // is fine.
 121     // NOTE: on non-windows platforms, this actually does matter since
 122     // their timer resolution is higher
 123     // TODO(erikkay): make this a parameter
 124     if (t - this.last_time > 10) {
 125       break;
 126     }
 127   }
 128   var processing = t - this.last_time;
 129   this.processing_min = Math.min(this.processing_min, processing);
 130   this.processing_max = Math.max(this.processing_max, processing);
 131   this.processing_total += processing;
 132   var step_time = processing + overhead;
 133   this.step_min = Math.min(this.step_min, step_time);
 134   this.step_max = Math.max(this.processing_max, step_time);
 135   this.num_iterations++;
 136   this.last_time = new Date();
 137
 138   if (ops == 0) {
 139     this.finished();
 140   }
 141 }
 142
 143 Sort.prototype.add_work = function(work, name) {
 144   if (name != undefined) {
 145     work.status = name;
 146   }
 147   this.work_queue.push(work);
 148 }
 149
 150 Sort.prototype.init = function() {
 151   this.print();
 152   this.status("");
 153 }
 154
 155 Sort.prototype.reset = function() {
 156   this.stop();
 157   this.start_time = 0;
 158   this.stop_time = 0;
 159   this.setup();
 160   this.print();
 161 }
 162
 163 Sort.prototype.start = function() {
 164   if (this.start_time > 0) {
 165     if (this.stop_time > 0) {
 166       this.shuffle();
 167       this.start_time = 0;
 168       this.stop_time = 0;
 169       this.status("");
 170       return;
 171     } else if (manual) {
 172       this.stepper();
 173       return;
 174     } else {
 175       this.finished();
 176       return;
 177     }
 178   }
 179   if (!manual) {
 180     var t = this;
 181     this.timer = setTimeout(function(){t.stepper();},interval_time);
 182   }
 183   this.compares = 0;
 184   this.swaps = 0;
 185   this.start_time = (new Date()).getTime();
 186   this.last_time = this.start_time;
 187   this.num_jobs = 0;
 188   this.stop_time = 0;
 189   this.overhead_total = 0;
 190   this.overhead_min = 1000000;
 191   this.overhead_max = 0;
 192   this.processing_total = 0;
 193   this.processing_min = 1000000;
 194   this.processing_max = 0;
 195   this.num_iterations = 0;
 196   this.func(this);
 197 }
 198
 199 Sort.prototype.cleanup = function() {
 200   if (this.compare_x) {
 201     this.compare_x.style.borderColor = "black";
 202     this.compare_y.style.borderColor = "black";
 203   }
 204   if (this.swap_x) {
 205     this.swap_x.style.backgroundColor = "green";
 206     this.swap_y.style.backgroundColor = "green";
 207   }
 208   this.work_queue = new Array();
 209 }
 210
 211 Sort.prototype.stop = function() {
 212   if (this.timer != 0) {
 213     clearTimeout(this.timer);
 214     this.timer = 0;
 215   }
 216   this.cleanup();
 217 }
 218
 219 Sort.prototype.finished = function(err) {
 220   this.stop();
 221
 222   this.stop_time = (new Date()).getTime();
 223
 224   var total = (this.stop_time - this.start_time);
 225   if (err == null) {
 226     var step_avg = Math.floor(total / this.num_iterations);
 227     var overhead = total - this.processing_total;
 228     var overhead_avg = Math.floor(overhead / this.num_iterations);
 229     var processing_avg = Math.floor(this.processing_total / this.num_iterations);
 230     var table = "<table><tr><td>Times(ms)</td><td>Total</td><td>Avg</td><td>Max</td></tr>"
 231       + "<tr><td>Total</td><td>" + total + "</td><td>" + step_avg + "</td><td>" + this.step_max + "</tr>"
 232       + "<tr><td>Work</td><td>" + this.processing_total + "</td><td>" + processing_avg + "</td><td>" +  this.processing_max + "</tr>"
 233       + "<tr><td>Overhead</td><td>" + overhead + "</td><td>" + overhead_avg + "</td><td>" + this.overhead_max + "</tr>"
 234       + "</table>";
 235     this.status(table);
 236   } else {
 237     this.status(err);
 238     log("error: " + err);
 239   }
 240   log("finished in: " + total);
 241 }
 242
 243 Sort.prototype.shuffle = function() {
 244   for (i = 0; i < this.size; i++) {
 245     var r = Math.floor(Math.random() * this.size);
 246     if (i != r) {
 247       this.swap(i,r);
 248     }
 249   }
 250   this.cleanup();
 251 }
 252
 253 Sort.prototype.print = function() {
 254   var graph = document.getElementById(this.name);
 255   if (graph == undefined) {
 256     alert("can't find " + this.name);
 257   }
 258   var text = "<div id='" + this.name + "_label' class='label'>" + this.name + " Sort</div>";
 259   var len = this.numbers.length;
 260   var height_multiple = (graph.clientHeight-20) / len;
 261   var width = Math.max(1,Math.floor((graph.clientWidth-10) / len));
 262   if (width < 3) {
 263     border = 0;
 264   } else {
 265     border = 1;
 266   }
 267   var left_offset = Math.round((graph.clientWidth - (width*len))/2);
 268   for (i = 0; i < len; i++) {
 269     var val = this.numbers[i];
 270     var height = Math.max(1, Math.floor(val * height_multiple));
 271     var left = left_offset + i * width;
 272     text += "<li class='bar' style='border: " + border + "px solid black; height:" + height + "px; left:" + left + "; width:" + width + "' id='" + this.name + val + "' value='" + val + "'></li>";
 273   }
 274   graph.innerHTML = text;
 275   var nodes = document.getElementsByTagName("li");
 276   var j = 0;
 277   for (i = 0; i < nodes.length; i++) {
 278     var name = nodes[i].id;
 279     if (name.indexOf(this.name) == 0) {
 280       this.bars[j] = nodes[i];
 281       j++;
 282     }
 283   }
 284 }
 285
 286 Sort.prototype.compare = function(x, y) {
 287   var bx = this.bars[x];
 288   var by = this.bars[y];
 289   //log("compare " + x + "(" + bx.value + ")," + y + "(" + by.value + ")");
 290   if (this.compare_x != bx) {
 291     if (this.compare_x) {
 292       this.compare_x.style.borderColor="black";
 293     }
 294     bx.style.borderColor="yellow";
 295     this.compare_x = bx;
 296   }
 297   if (this.compare_y != by) {
 298     if (this.compare_y) {
 299       this.compare_y.style.borderColor="black";
 300     }
 301     by.style.borderColor="white";
 302     this.compare_y = by;
 303   }
 304   this.compares++;
 305   return bx.value - by.value;
 306 }
 307
 308 Sort.prototype.swap = function(x, y) {
 309   var bx = this.bars[x];
 310   var by = this.bars[y];
 311   //log("swap " + x + "(" + bx.value + ")," + y + "(" + by.value + ")");
 312   if (this.swap_x != x) {
 313     if (this.swap_x) {
 314       this.swap_x.style.backgroundColor="green";
 315     }
 316     bx.style.backgroundColor="blue";
 317     this.swap_x = bx;
 318   }
 319   if (this.swap_y != y) {
 320     if (this.swap_y) {
 321       this.swap_y.style.backgroundColor="green";
 322     }
 323     by.style.backgroundColor="red";
 324     this.swap_y = by;
 325   }
 326   var tmp = bx.style.left;
 327   bx.style.left = by.style.left;
 328   by.style.left = tmp;
 329   this.bars[x] = by;
 330   this.bars[y] = bx;
 331   this.swaps++;
 332 }
 333
 334 Sort.prototype.insert = function(from, to) {
 335   var bf = this.bars[from];
 336   if (from > to) {
 337     for (i = from; i > to; i--) {
 338       var b1 = this.bars[i];
 339       var b2 = this.bars[i-1];
 340       b2.style.left = b1.style.left;
 341       this.bars[i] = b2;
 342     }
 343     bf.style.left = this.bars[to].style.left;
 344     this.bars[to] = bf;
 345   } else {
 346     // TODO
 347   }
 348 }