Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(36)

Side by Side Diff: chrome/test/data/dromaeo/tests/v8-deltablue.html

Issue 269054: Importing dromaeo performance tests to src/chrome/test/data.... (Closed) Base URL: svn://chrome-svn/chrome/trunk/src/
Patch Set: Created 11 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
(Empty)
1 <html>
2 <head>
3 <script src="../htmlrunner.js"></script>
4 <script>
5 // Copyright 2008 the V8 project authors. All rights reserved.
6 // Copyright 1996 John Maloney and Mario Wolczko.
7
8 // This program is free software; you can redistribute it and/or modify
9 // it under the terms of the GNU General Public License as published by
10 // the Free Software Foundation; either version 2 of the License, or
11 // (at your option) any later version.
12 //
13 // This program is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 // GNU General Public License for more details.
17 //
18 // You should have received a copy of the GNU General Public License
19 // along with this program; if not, write to the Free Software
20 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21
22
23 // This implementation of the DeltaBlue benchmark is derived
24 // from the Smalltalk implementation by John Maloney and Mario
25 // Wolczko. Some parts have been translated directly, whereas
26 // others have been modified more aggresively to make it feel
27 // more like a JavaScript program.
28
29
30 /**
31 * A JavaScript implementation of the DeltaBlue constrain-solving
32 * algorithm, as described in:
33 *
34 * "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver"
35 * Bjorn N. Freeman-Benson and John Maloney
36 * January 1990 Communications of the ACM,
37 * also available as University of Washington TR 89-08-06.
38 *
39 * Beware: this benchmark is written in a grotesque style where
40 * the constraint model is built by side-effects from constructors.
41 * I've kept it this way to avoid deviating too much from the original
42 * implementation.
43 */
44
45
46 /* --- O b j e c t M o d e l --- */
47
48 function inherits(orig, shuper) {
49 function Inheriter() { }
50 Inheriter.prototype = shuper.prototype;
51 orig.prototype = new Inheriter();
52 orig.superConstructor = shuper;
53 }
54
55 function OrderedCollection() {
56 this.elms = new Array();
57 }
58
59 OrderedCollection.prototype.add = function (elm) {
60 this.elms.push(elm);
61 }
62
63 OrderedCollection.prototype.at = function (index) {
64 return this.elms[index];
65 }
66
67 OrderedCollection.prototype.size = function () {
68 return this.elms.length;
69 }
70
71 OrderedCollection.prototype.removeFirst = function () {
72 return this.elms.pop();
73 }
74
75 OrderedCollection.prototype.remove = function (elm) {
76 var index = 0, skipped = 0;
77 for (var i = 0; i < this.elms.length; i++) {
78 var value = this.elms[i];
79 if (value != elm) {
80 this.elms[index] = value;
81 index++;
82 } else {
83 skipped++;
84 }
85 }
86 for (var i = 0; i < skipped; i++)
87 this.elms.pop();
88 }
89
90 /* --- *
91 * S t r e n g t h
92 * --- */
93
94 /**
95 * Strengths are used to measure the relative importance of constraints.
96 * New strengths may be inserted in the strength hierarchy without
97 * disrupting current constraints. Strengths cannot be created outside
98 * this class, so pointer comparison can be used for value comparison.
99 */
100 function Strength(strengthValue, name) {
101 this.strengthValue = strengthValue;
102 this.name = name;
103 }
104
105 Strength.stronger = function (s1, s2) {
106 return s1.strengthValue < s2.strengthValue;
107 }
108
109 Strength.weaker = function (s1, s2) {
110 return s1.strengthValue > s2.strengthValue;
111 }
112
113 Strength.weakestOf = function (s1, s2) {
114 return this.weaker(s1, s2) ? s1 : s2;
115 }
116
117 Strength.strongest = function (s1, s2) {
118 return this.stronger(s1, s2) ? s1 : s2;
119 }
120
121 Strength.prototype.nextWeaker = function () {
122 switch (this.strengthValue) {
123 case 0: return Strength.WEAKEST;
124 case 1: return Strength.WEAK_DEFAULT;
125 case 2: return Strength.NORMAL;
126 case 3: return Strength.STRONG_DEFAULT;
127 case 4: return Strength.PREFERRED;
128 case 5: return Strength.REQUIRED;
129 }
130 }
131
132 // Strength constants.
133 Strength.REQUIRED = new Strength(0, "required");
134 Strength.STONG_PREFERRED = new Strength(1, "strongPreferred");
135 Strength.PREFERRED = new Strength(2, "preferred");
136 Strength.STRONG_DEFAULT = new Strength(3, "strongDefault");
137 Strength.NORMAL = new Strength(4, "normal");
138 Strength.WEAK_DEFAULT = new Strength(5, "weakDefault");
139 Strength.WEAKEST = new Strength(6, "weakest");
140
141 /* --- *
142 * C o n s t r a i n t
143 * --- */
144
145 /**
146 * An abstract class representing a system-maintainable relationship
147 * (or "constraint") between a set of variables. A constraint supplies
148 * a strength instance variable; concrete subclasses provide a means
149 * of storing the constrained variables and other information required
150 * to represent a constraint.
151 */
152 function Constraint(strength) {
153 this.strength = strength;
154 }
155
156 /**
157 * Activate this constraint and attempt to satisfy it.
158 */
159 Constraint.prototype.addConstraint = function () {
160 this.addToGraph();
161 planner.incrementalAdd(this);
162 }
163
164 /**
165 * Attempt to find a way to enforce this constraint. If successful,
166 * record the solution, perhaps modifying the current dataflow
167 * graph. Answer the constraint that this constraint overrides, if
168 * there is one, or nil, if there isn't.
169 * Assume: I am not already satisfied.
170 */
171 Constraint.prototype.satisfy = function (mark) {
172 this.chooseMethod(mark);
173 if (!this.isSatisfied()) {
174 if (this.strength == Strength.REQUIRED)
175 alert("Could not satisfy a required constraint!");
176 return null;
177 }
178 this.markInputs(mark);
179 var out = this.output();
180 var overridden = out.determinedBy;
181 if (overridden != null) overridden.markUnsatisfied();
182 out.determinedBy = this;
183 if (!planner.addPropagate(this, mark))
184 alert("Cycle encountered");
185 out.mark = mark;
186 return overridden;
187 }
188
189 Constraint.prototype.destroyConstraint = function () {
190 if (this.isSatisfied()) planner.incrementalRemove(this);
191 else this.removeFromGraph();
192 }
193
194 /**
195 * Normal constraints are not input constraints. An input constraint
196 * is one that depends on external state, such as the mouse, the
197 * keybord, a clock, or some arbitraty piece of imperative code.
198 */
199 Constraint.prototype.isInput = function () {
200 return false;
201 }
202
203 /* --- *
204 * U n a r y C o n s t r a i n t
205 * --- */
206
207 /**
208 * Abstract superclass for constraints having a single possible output
209 * variable.
210 */
211 function UnaryConstraint(v, strength) {
212 UnaryConstraint.superConstructor.call(this, strength);
213 this.myOutput = v;
214 this.satisfied = false;
215 this.addConstraint();
216 }
217
218 inherits(UnaryConstraint,Constraint);
219
220 /**
221 * Adds this constraint to the constraint graph
222 */
223 UnaryConstraint.prototype.addToGraph = function () {
224 this.myOutput.addConstraint(this);
225 this.satisfied = false;
226 }
227
228 /**
229 * Decides if this constraint can be satisfied and records that
230 * decision.
231 */
232 UnaryConstraint.prototype.chooseMethod = function (mark) {
233 this.satisfied = (this.myOutput.mark != mark)
234 && Strength.stronger(this.strength, this.myOutput.walkStrength);
235 }
236
237 /**
238 * Returns true if this constraint is satisfied in the current solution.
239 */
240 UnaryConstraint.prototype.isSatisfied = function () {
241 return this.satisfied;
242 }
243
244 UnaryConstraint.prototype.markInputs = function (mark) {
245 // has no inputs
246 }
247
248 /**
249 * Returns the current output variable.
250 */
251 UnaryConstraint.prototype.output = function () {
252 return this.myOutput;
253 }
254
255 /**
256 * Calculate the walkabout strength, the stay flag, and, if it is
257 * 'stay', the value for the current output of this constraint. Assume
258 * this constraint is satisfied.
259 */
260 UnaryConstraint.prototype.recalculate = function () {
261 this.myOutput.walkStrength = this.strength;
262 this.myOutput.stay = !this.isInput();
263 if (this.myOutput.stay) this.execute(); // Stay optimization
264 }
265
266 /**
267 * Records that this constraint is unsatisfied
268 */
269 UnaryConstraint.prototype.markUnsatisfied = function () {
270 this.satisfied = false;
271 }
272
273 UnaryConstraint.prototype.inputsKnown = function () {
274 return true;
275 }
276
277 UnaryConstraint.prototype.removeFromGraph = function () {
278 if (this.myOutput != null) this.myOutput.removeConstraint(this);
279 this.satisfied = false;
280 }
281
282 /* --- *
283 * S t a y C o n s t r a i n t
284 * --- */
285
286 /**
287 * Variables that should, with some level of preference, stay the same.
288 * Planners may exploit the fact that instances, if satisfied, will not
289 * change their output during plan execution. This is called "stay
290 * optimization".
291 */
292 function StayConstraint(v, str) {
293 StayConstraint.superConstructor.call(this, v, str);
294 }
295
296 inherits(StayConstraint,UnaryConstraint);
297
298 StayConstraint.prototype.execute = function () {
299 // Stay constraints do nothing
300 }
301
302 /* --- *
303 * E d i t C o n s t r a i n t
304 * --- */
305
306 /**
307 * A unary input constraint used to mark a variable that the client
308 * wishes to change.
309 */
310 function EditConstraint(v, str) {
311 EditConstraint.superConstructor.call(this, v, str);
312 }
313
314 inherits(EditConstraint,UnaryConstraint);
315
316 /**
317 * Edits indicate that a variable is to be changed by imperative code.
318 */
319 EditConstraint.prototype.isInput = function () {
320 return true;
321 }
322
323 EditConstraint.prototype.execute = function () {
324 // Edit constraints do nothing
325 }
326
327 /* --- *
328 * B i n a r y C o n s t r a i n t
329 * --- */
330
331 var Direction = new Object();
332 Direction.NONE = 0;
333 Direction.FORWARD = 1;
334 Direction.BACKWARD = -1;
335
336 /**
337 * Abstract superclass for constraints having two possible output
338 * variables.
339 */
340 function BinaryConstraint(var1, var2, strength) {
341 BinaryConstraint.superConstructor.call(this, strength);
342 this.v1 = var1;
343 this.v2 = var2;
344 this.direction = Direction.NONE;
345 this.addConstraint();
346 }
347
348 inherits(BinaryConstraint,Constraint);
349
350 /**
351 * Decides if this constratint can be satisfied and which way it
352 * should flow based on the relative strength of the variables related,
353 * and record that decision.
354 */
355 BinaryConstraint.prototype.chooseMethod = function (mark) {
356 if (this.v1.mark == mark) {
357 this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, t his.v2.walkStrength))
358 ? Direction.FORWARD
359 : Direction.NONE;
360 }
361 if (this.v2.mark == mark) {
362 this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, t his.v1.walkStrength))
363 ? Direction.BACKWARD
364 : Direction.NONE;
365 }
366 if (Strength.weaker(this.v1.walkStrength, this.v2.walkStrength)) {
367 this.direction = Strength.stronger(this.strength, this.v1.walkStrength)
368 ? Direction.BACKWARD
369 : Direction.NONE;
370 } else {
371 this.direction = Strength.stronger(this.strength, this.v2.walkStrength)
372 ? Direction.FORWARD
373 : Direction.BACKWARD
374 }
375 }
376
377 /**
378 * Add this constraint to the constraint graph
379 */
380 BinaryConstraint.prototype.addToGraph = function () {
381 this.v1.addConstraint(this);
382 this.v2.addConstraint(this);
383 this.direction = Direction.NONE;
384 }
385
386 /**
387 * Answer true if this constraint is satisfied in the current solution.
388 */
389 BinaryConstraint.prototype.isSatisfied = function () {
390 return this.direction != Direction.NONE;
391 }
392
393 /**
394 * Mark the input variable with the given mark.
395 */
396 BinaryConstraint.prototype.markInputs = function (mark) {
397 this.input().mark = mark;
398 }
399
400 /**
401 * Returns the current input variable
402 */
403 BinaryConstraint.prototype.input = function () {
404 return (this.direction == Direction.FORWARD) ? this.v1 : this.v2;
405 }
406
407 /**
408 * Returns the current output variable
409 */
410 BinaryConstraint.prototype.output = function () {
411 return (this.direction == Direction.FORWARD) ? this.v2 : this.v1;
412 }
413
414 /**
415 * Calculate the walkabout strength, the stay flag, and, if it is
416 * 'stay', the value for the current output of this
417 * constraint. Assume this constraint is satisfied.
418 */
419 BinaryConstraint.prototype.recalculate = function () {
420 var ihn = this.input(), out = this.output();
421 out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength);
422 out.stay = ihn.stay;
423 if (out.stay) this.execute();
424 }
425
426 /**
427 * Record the fact that this constraint is unsatisfied.
428 */
429 BinaryConstraint.prototype.markUnsatisfied = function () {
430 this.direction = Direction.NONE;
431 }
432
433 BinaryConstraint.prototype.inputsKnown = function (mark) {
434 var i = this.input();
435 return i.mark == mark || i.stay || i.determinedBy == null;
436 }
437
438 BinaryConstraint.prototype.removeFromGraph = function () {
439 if (this.v1 != null) this.v1.removeConstraint(this);
440 if (this.v2 != null) this.v2.removeConstraint(this);
441 this.direction = Direction.NONE;
442 }
443
444 /* --- *
445 * S c a l e C o n s t r a i n t
446 * --- */
447
448 /**
449 * Relates two variables by the linear scaling relationship: "v2 =
450 * (v1 * scale) + offset". Either v1 or v2 may be changed to maintain
451 * this relationship but the scale factor and offset are considered
452 * read-only.
453 */
454 function ScaleConstraint(src, scale, offset, dest, strength) {
455 this.direction = Direction.NONE;
456 this.scale = scale;
457 this.offset = offset;
458 ScaleConstraint.superConstructor.call(this, src, dest, strength);
459 }
460
461 inherits(ScaleConstraint,BinaryConstraint);
462
463 /**
464 * Adds this constraint to the constraint graph.
465 */
466 ScaleConstraint.prototype.addToGraph = function () {
467 ScaleConstraint.superConstructor.prototype.addToGraph.call(this);
468 this.scale.addConstraint(this);
469 this.offset.addConstraint(this);
470 }
471
472 ScaleConstraint.prototype.removeFromGraph = function () {
473 ScaleConstraint.superConstructor.prototype.removeFromGraph.call(this);
474 if (this.scale != null) this.scale.removeConstraint(this);
475 if (this.offset != null) this.offset.removeConstraint(this);
476 }
477
478 ScaleConstraint.prototype.markInputs = function (mark) {
479 ScaleConstraint.superConstructor.prototype.markInputs.call(this, mark);
480 this.scale.mark = this.offset.mark = mark;
481 }
482
483 /**
484 * Enforce this constraint. Assume that it is satisfied.
485 */
486 ScaleConstraint.prototype.execute = function () {
487 if (this.direction == Direction.FORWARD) {
488 this.v2.value = this.v1.value * this.scale.value + this.offset.value;
489 } else {
490 this.v1.value = (this.v2.value - this.offset.value) / this.scale.value;
491 }
492 }
493
494 /**
495 * Calculate the walkabout strength, the stay flag, and, if it is
496 * 'stay', the value for the current output of this constraint. Assume
497 * this constraint is satisfied.
498 */
499 ScaleConstraint.prototype.recalculate = function () {
500 var ihn = this.input(), out = this.output();
501 out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength);
502 out.stay = ihn.stay && this.scale.stay && this.offset.stay;
503 if (out.stay) this.execute();
504 }
505
506 /* --- *
507 * E q u a l i t y C o n s t r a i n t
508 * --- */
509
510 /**
511 * Constrains two variables to have the same value.
512 */
513 function EqualityConstraint(var1, var2, strength) {
514 EqualityConstraint.superConstructor.call(this, var1, var2, strength);
515 }
516
517 inherits(EqualityConstraint,BinaryConstraint);
518
519 /**
520 * Enforce this constraint. Assume that it is satisfied.
521 */
522 EqualityConstraint.prototype.execute = function () {
523 this.output().value = this.input().value;
524 }
525
526 /* --- *
527 * V a r i a b l e
528 * --- */
529
530 /**
531 * A constrained variable. In addition to its value, it maintain the
532 * structure of the constraint graph, the current dataflow graph, and
533 * various parameters of interest to the DeltaBlue incremental
534 * constraint solver.
535 **/
536 function Variable(name, initialValue) {
537 this.value = initialValue || 0;
538 this.constraints = new OrderedCollection();
539 this.determinedBy = null;
540 this.mark = 0;
541 this.walkStrength = Strength.WEAKEST;
542 this.stay = true;
543 this.name = name;
544 }
545
546 /**
547 * Add the given constraint to the set of all constraints that refer
548 * this variable.
549 */
550 Variable.prototype.addConstraint = function (c) {
551 this.constraints.add(c);
552 }
553
554 /**
555 * Removes all traces of c from this variable.
556 */
557 Variable.prototype.removeConstraint = function (c) {
558 this.constraints.remove(c);
559 if (this.determinedBy == c) this.determinedBy = null;
560 }
561
562 /* --- *
563 * P l a n n e r
564 * --- */
565
566 /**
567 * The DeltaBlue planner
568 */
569 function Planner() {
570 this.currentMark = 0;
571 }
572
573 /**
574 * Attempt to satisfy the given constraint and, if successful,
575 * incrementally update the dataflow graph. Details: If satifying
576 * the constraint is successful, it may override a weaker constraint
577 * on its output. The algorithm attempts to resatisfy that
578 * constraint using some other method. This process is repeated
579 * until either a) it reaches a variable that was not previously
580 * determined by any constraint or b) it reaches a constraint that
581 * is too weak to be satisfied using any of its methods. The
582 * variables of constraints that have been processed are marked with
583 * a unique mark value so that we know where we've been. This allows
584 * the algorithm to avoid getting into an infinite loop even if the
585 * constraint graph has an inadvertent cycle.
586 */
587 Planner.prototype.incrementalAdd = function (c) {
588 var mark = this.newMark();
589 var overridden = c.satisfy(mark);
590 while (overridden != null)
591 overridden = overridden.satisfy(mark);
592 }
593
594 /**
595 * Entry point for retracting a constraint. Remove the given
596 * constraint and incrementally update the dataflow graph.
597 * Details: Retracting the given constraint may allow some currently
598 * unsatisfiable downstream constraint to be satisfied. We therefore collect
599 * a list of unsatisfied downstream constraints and attempt to
600 * satisfy each one in turn. This list is traversed by constraint
601 * strength, strongest first, as a heuristic for avoiding
602 * unnecessarily adding and then overriding weak constraints.
603 * Assume: c is satisfied.
604 */
605 Planner.prototype.incrementalRemove = function (c) {
606 var out = c.output();
607 c.markUnsatisfied();
608 c.removeFromGraph();
609 var unsatisfied = this.removePropagateFrom(out);
610 var strength = Strength.REQUIRED;
611 do {
612 for (var i = 0; i < unsatisfied.size(); i++) {
613 var u = unsatisfied.at(i);
614 if (u.strength == strength)
615 this.incrementalAdd(u);
616 }
617 strength = strength.nextWeaker();
618 } while (strength != Strength.WEAKEST);
619 }
620
621 /**
622 * Select a previously unused mark value.
623 */
624 Planner.prototype.newMark = function () {
625 return ++this.currentMark;
626 }
627
628 /**
629 * Extract a plan for resatisfaction starting from the given source
630 * constraints, usually a set of input constraints. This method
631 * assumes that stay optimization is desired; the plan will contain
632 * only constraints whose output variables are not stay. Constraints
633 * that do no computation, such as stay and edit constraints, are
634 * not included in the plan.
635 * Details: The outputs of a constraint are marked when it is added
636 * to the plan under construction. A constraint may be appended to
637 * the plan when all its input variables are known. A variable is
638 * known if either a) the variable is marked (indicating that has
639 * been computed by a constraint appearing earlier in the plan), b)
640 * the variable is 'stay' (i.e. it is a constant at plan execution
641 * time), or c) the variable is not determined by any
642 * constraint. The last provision is for past states of history
643 * variables, which are not stay but which are also not computed by
644 * any constraint.
645 * Assume: sources are all satisfied.
646 */
647 Planner.prototype.makePlan = function (sources) {
648 var mark = this.newMark();
649 var plan = new Plan();
650 var todo = sources;
651 while (todo.size() > 0) {
652 var c = todo.removeFirst();
653 if (c.output().mark != mark && c.inputsKnown(mark)) {
654 plan.addConstraint(c);
655 c.output().mark = mark;
656 this.addConstraintsConsumingTo(c.output(), todo);
657 }
658 }
659 return plan;
660 }
661
662 /**
663 * Extract a plan for resatisfying starting from the output of the
664 * given constraints, usually a set of input constraints.
665 */
666 Planner.prototype.extractPlanFromConstraints = function (constraints) {
667 var sources = new OrderedCollection();
668 for (var i = 0; i < constraints.size(); i++) {
669 var c = constraints.at(i);
670 if (c.isInput() && c.isSatisfied())
671 // not in plan already and eligible for inclusion
672 sources.add(c);
673 }
674 return this.makePlan(sources);
675 }
676
677 /**
678 * Recompute the walkabout strengths and stay flags of all variables
679 * downstream of the given constraint and recompute the actual
680 * values of all variables whose stay flag is true. If a cycle is
681 * detected, remove the given constraint and answer
682 * false. Otherwise, answer true.
683 * Details: Cycles are detected when a marked variable is
684 * encountered downstream of the given constraint. The sender is
685 * assumed to have marked the inputs of the given constraint with
686 * the given mark. Thus, encountering a marked node downstream of
687 * the output constraint means that there is a path from the
688 * constraint's output to one of its inputs.
689 */
690 Planner.prototype.addPropagate = function (c, mark) {
691 var todo = new OrderedCollection();
692 todo.add(c);
693 while (todo.size() > 0) {
694 var d = todo.removeFirst();
695 if (d.output().mark == mark) {
696 this.incrementalRemove(c);
697 return false;
698 }
699 d.recalculate();
700 this.addConstraintsConsumingTo(d.output(), todo);
701 }
702 return true;
703 }
704
705
706 /**
707 * Update the walkabout strengths and stay flags of all variables
708 * downstream of the given constraint. Answer a collection of
709 * unsatisfied constraints sorted in order of decreasing strength.
710 */
711 Planner.prototype.removePropagateFrom = function (out) {
712 out.determinedBy = null;
713 out.walkStrength = Strength.WEAKEST;
714 out.stay = true;
715 var unsatisfied = new OrderedCollection();
716 var todo = new OrderedCollection();
717 todo.add(out);
718 while (todo.size() > 0) {
719 var v = todo.removeFirst();
720 for (var i = 0; i < v.constraints.size(); i++) {
721 var c = v.constraints.at(i);
722 if (!c.isSatisfied())
723 unsatisfied.add(c);
724 }
725 var determining = v.determinedBy;
726 for (var i = 0; i < v.constraints.size(); i++) {
727 var next = v.constraints.at(i);
728 if (next != determining && next.isSatisfied()) {
729 next.recalculate();
730 todo.add(next.output());
731 }
732 }
733 }
734 return unsatisfied;
735 }
736
737 Planner.prototype.addConstraintsConsumingTo = function (v, coll) {
738 var determining = v.determinedBy;
739 var cc = v.constraints;
740 for (var i = 0; i < cc.size(); i++) {
741 var c = cc.at(i);
742 if (c != determining && c.isSatisfied())
743 coll.add(c);
744 }
745 }
746
747 /* --- *
748 * P l a n
749 * --- */
750
751 /**
752 * A Plan is an ordered list of constraints to be executed in sequence
753 * to resatisfy all currently satisfiable constraints in the face of
754 * one or more changing inputs.
755 */
756 function Plan() {
757 this.v = new OrderedCollection();
758 }
759
760 Plan.prototype.addConstraint = function (c) {
761 this.v.add(c);
762 }
763
764 Plan.prototype.size = function () {
765 return this.v.size();
766 }
767
768 Plan.prototype.constraintAt = function (index) {
769 return this.v.at(index);
770 }
771
772 Plan.prototype.execute = function () {
773 for (var i = 0; i < this.size(); i++) {
774 var c = this.constraintAt(i);
775 c.execute();
776 }
777 }
778
779 /* --- *
780 * M a i n
781 * --- */
782
783 /**
784 * This is the standard DeltaBlue benchmark. A long chain of equality
785 * constraints is constructed with a stay constraint on one end. An
786 * edit constraint is then added to the opposite end and the time is
787 * measured for adding and removing this constraint, and extracting
788 * and executing a constraint satisfaction plan. There are two cases.
789 * In case 1, the added constraint is stronger than the stay
790 * constraint and values must propagate down the entire length of the
791 * chain. In case 2, the added constraint is weaker than the stay
792 * constraint so it cannot be accomodated. The cost in this case is,
793 * of course, very low. Typical situations lie somewhere between these
794 * two extremes.
795 */
796 function chainTest(n) {
797 planner = new Planner();
798 var prev = null, first = null, last = null;
799
800 // Build chain of n equality constraints
801 for (var i = 0; i <= n; i++) {
802 var name = "v" + i;
803 var v = new Variable(name);
804 if (prev != null)
805 new EqualityConstraint(prev, v, Strength.REQUIRED);
806 if (i == 0) first = v;
807 if (i == n) last = v;
808 prev = v;
809 }
810
811 new StayConstraint(last, Strength.STRONG_DEFAULT);
812 var edit = new EditConstraint(first, Strength.PREFERRED);
813 var edits = new OrderedCollection();
814 edits.add(edit);
815 var plan = planner.extractPlanFromConstraints(edits);
816 for (var i = 0; i < 100; i++) {
817 first.value = i;
818 plan.execute();
819 if (last.value != i)
820 alert("Chain test failed.");
821 }
822 }
823
824 /**
825 * This test constructs a two sets of variables related to each
826 * other by a simple linear transformation (scale and offset). The
827 * time is measured to change a variable on either side of the
828 * mapping and to change the scale and offset factors.
829 */
830 function projectionTest(n) {
831 planner = new Planner();
832 var scale = new Variable("scale", 10);
833 var offset = new Variable("offset", 1000);
834 var src = null, dst = null;
835
836 var dests = new OrderedCollection();
837 for (var i = 0; i < n; i++) {
838 src = new Variable("src" + i, i);
839 dst = new Variable("dst" + i, i);
840 dests.add(dst);
841 new StayConstraint(src, Strength.NORMAL);
842 new ScaleConstraint(src, scale, offset, dst, Strength.REQUIRED);
843 }
844
845 change(src, 17);
846 if (dst.value != 1170) alert("Projection 1 failed");
847 change(dst, 1050);
848 if (src.value != 5) alert("Projection 2 failed");
849 change(scale, 5);
850 for (var i = 0; i < n - 1; i++) {
851 if (dests.at(i).value != i * 5 + 1000)
852 alert("Projection 3 failed");
853 }
854 change(offset, 2000);
855 for (var i = 0; i < n - 1; i++) {
856 if (dests.at(i).value != i * 5 + 2000)
857 alert("Projection 4 failed");
858 }
859 }
860
861 function change(v, newValue) {
862 var edit = new EditConstraint(v, Strength.PREFERRED);
863 var edits = new OrderedCollection();
864 edits.add(edit);
865 var plan = planner.extractPlanFromConstraints(edits);
866 for (var i = 0; i < 10; i++) {
867 v.value = newValue;
868 plan.execute();
869 }
870 edit.destroyConstraint();
871 }
872
873 // Global variable holding the current planner.
874 var planner = null;
875
876 window.onload = function(){ startTest("v8-deltablue", '');
877
878 test("Constraint Solving", function deltaBlue() {
879 chainTest(100);
880 projectionTest(100);
881 });
882
883 endTest(); };
884 </script>
885 </head>
886 <body></body>
887 </html>
OLDNEW
« no previous file with comments | « chrome/test/data/dromaeo/tests/v8-crypto.html ('k') | chrome/test/data/dromaeo/tests/v8-earley-boyer.html » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698