Add StyleBench
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 30 Nov 2017 12:30:25 +0000 (12:30 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 30 Nov 2017 12:30:25 +0000 (12:30 +0000)
https://bugs.webkit.org/show_bug.cgi?id=180140

Reviewed by Simon Fraser and Joseph Pecoraro.

StyleBench tests performance of the CSS style resolution and style invalidation. Each test run
creates a large document and a large stylesheet using varying settings. It then applies
a series of mutations to the document and measures the time to update the style and rendering.
The resulting layout is simple, most of the pressure is on selector matching.

StyleBench uses Speedometer framework for UI and measurements. For profiling purposes, it can also
be run locally by opening style-bench.html directly.

There are currently four subtests:

- child and descendant combinators only (all other tests have these too).
- sibling combinators: '~' and '+'
- positional pseudo classes: :nth-child and similar
- ::before and ::after pseudo elements

The measured DOM mutations are:

- add classes
- remove classes
- add leaf elements
- remove leaf elements

* StyleBench: Added.
* StyleBench/InteractiveRunner.html: Added.

    Copied and customized from Speedometer.

* StyleBench/index.html: Added.

    Copied and customized from Speedometer.

* StyleBench/resources: Added.
* StyleBench/resources/style-bench.html: Added.
* StyleBench/resources/style-bench.js: Added.

    The test class.

(Random):
(Random.prototype.get next):
(Random.prototype.chance):
(Random.prototype.number):
(nextAnimationFrame):
(defaultConfiguration):
(descendantCombinatorConfiguration):
(siblingCombinatorConfiguration):
(pseudoClassConfiguration):
(beforeAndAfterConfiguration):
(predefinedConfigurations):

    Four predefined configurations.

(prototype.randomElementName):
(prototype.randomCombinator):
(prototype.randomPseudoClass):
(prototype.makeSimpleSelector):
(prototype.makeSelector):
(prototype.get randomColorComponent):
(prototype.makeDeclaration):
(prototype.makeRule):
(prototype.makeStylesheet):
(prototype.makeStyle):
(prototype.makeElement):
(prototype.makeTreeWithDepth):
(prototype.makeTree):
(prototype.updateCachedTestElements):
(prototype.randomTreeElement):
(prototype.addClasses):
(prototype.removeClasses):
(prototype.addLeafElements):
(prototype.removeLeafElements):
(prototype.async.runForever):
* StyleBench/resources/tests.js: Added.
(makeSteps):
(makeSuite):

    Generates Speedometer Suites.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@225324 268f45cc-cd09-0410-ab3c-d52691b4dbfc

PerformanceTests/ChangeLog
PerformanceTests/StyleBench/InteractiveRunner.html [new file with mode: 0644]
PerformanceTests/StyleBench/index.html [new file with mode: 0644]
PerformanceTests/StyleBench/resources/style-bench.html [new file with mode: 0644]
PerformanceTests/StyleBench/resources/style-bench.js [new file with mode: 0644]
PerformanceTests/StyleBench/resources/tests.js [new file with mode: 0644]

index c13efdf..a6f3edb 100644 (file)
@@ -1,3 +1,87 @@
+2017-11-30  Antti Koivisto  <antti@apple.com>
+
+        Add StyleBench
+        https://bugs.webkit.org/show_bug.cgi?id=180140
+
+        Reviewed by Simon Fraser and Joseph Pecoraro.
+
+        StyleBench tests performance of the CSS style resolution and style invalidation. Each test run
+        creates a large document and a large stylesheet using varying settings. It then applies
+        a series of mutations to the document and measures the time to update the style and rendering.
+        The resulting layout is simple, most of the pressure is on selector matching.
+
+        StyleBench uses Speedometer framework for UI and measurements. For profiling purposes, it can also
+        be run locally by opening style-bench.html directly.
+
+        There are currently four subtests:
+
+        - child and descendant combinators only (all other tests have these too).
+        - sibling combinators: '~' and '+'
+        - positional pseudo classes: :nth-child and similar
+        - ::before and ::after pseudo elements
+
+        The measured DOM mutations are:
+
+        - add classes
+        - remove classes
+        - add leaf elements
+        - remove leaf elements
+
+        * StyleBench: Added.
+        * StyleBench/InteractiveRunner.html: Added.
+
+            Copied and customized from Speedometer.
+
+        * StyleBench/index.html: Added.
+
+            Copied and customized from Speedometer.
+
+        * StyleBench/resources: Added.
+        * StyleBench/resources/style-bench.html: Added.
+        * StyleBench/resources/style-bench.js: Added.
+
+            The test class.
+
+        (Random):
+        (Random.prototype.get next):
+        (Random.prototype.chance):
+        (Random.prototype.number):
+        (nextAnimationFrame):
+        (defaultConfiguration):
+        (descendantCombinatorConfiguration):
+        (siblingCombinatorConfiguration):
+        (pseudoClassConfiguration):
+        (beforeAndAfterConfiguration):
+        (predefinedConfigurations):
+
+            Four predefined configurations.
+
+        (prototype.randomElementName):
+        (prototype.randomCombinator):
+        (prototype.randomPseudoClass):
+        (prototype.makeSimpleSelector):
+        (prototype.makeSelector):
+        (prototype.get randomColorComponent):
+        (prototype.makeDeclaration):
+        (prototype.makeRule):
+        (prototype.makeStylesheet):
+        (prototype.makeStyle):
+        (prototype.makeElement):
+        (prototype.makeTreeWithDepth):
+        (prototype.makeTree):
+        (prototype.updateCachedTestElements):
+        (prototype.randomTreeElement):
+        (prototype.addClasses):
+        (prototype.removeClasses):
+        (prototype.addLeafElements):
+        (prototype.removeLeafElements):
+        (prototype.async.runForever):
+        * StyleBench/resources/tests.js: Added.
+        (makeSteps):
+        (makeSuite):
+
+            Generates Speedometer Suites.
+
 2017-11-29  Robin Morisset  <rmorisset@apple.com>
 
         The recursive tail call optimisation is wrong on closures
diff --git a/PerformanceTests/StyleBench/InteractiveRunner.html b/PerformanceTests/StyleBench/InteractiveRunner.html
new file mode 100644 (file)
index 0000000..04ffa4b
--- /dev/null
@@ -0,0 +1,174 @@
+<!DOCTYPE html>
+<html>
+<head>
+<title>Speedometer 2.0 Interactive Runner</title>
+<script src="../Speedometer/resources/benchmark-runner.js" defer></script>
+<script src="../Speedometer/resources/selector-bench.js" defer></script>
+<script src="../Speedometer/resources/tests.js" defer></script>
+<style>
+iframe { border: 1px solid black; }
+ol { list-style: none; margin: 0; padding: 0; }
+ol ol { margin-left: 2em; list-position: outside; }
+.running { text-decoration: underline; }
+.ran { color: grey; }
+nav { position: absolute; right: 10px; height: 600px; }
+nav > ol { height: 100%; overflow-y: scroll; }
+</style>
+</head>
+<body>
+<script>
+
+function formatTestName(suiteName, testName) {
+    return suiteName + (testName ? '/' + testName : '');
+}
+
+function createUIForSuites(suites, onstep, onrun) {
+    var control = document.createElement('nav');
+    var ol = document.createElement('ol');
+    var checkboxes = [];
+    for (var suiteIndex = 0; suiteIndex < suites.length; suiteIndex++) {
+        var suite = suites[suiteIndex];
+        var li = document.createElement('li');
+        var checkbox = document.createElement('input');
+        checkbox.id = suite.name;
+        checkbox.type = 'checkbox';
+        checkbox.checked = !suite.disabled;
+        checkbox.onchange = (function (suite, checkbox) { return function () { suite.disabled = !checkbox.checked; } })(suite, checkbox);
+        checkbox.onchange();
+        checkboxes.push(checkbox);
+
+        li.appendChild(checkbox);
+        var label = document.createElement('label');
+        label.appendChild(document.createTextNode(formatTestName(suite.name)));
+        li.appendChild(label);
+        label.htmlFor = checkbox.id;
+
+        var testList = document.createElement('ol');
+        for (var testIndex = 0; testIndex < suite.tests.length; testIndex++) {
+            var testItem = document.createElement('li');
+            var test = suite.tests[testIndex];
+            var anchor = document.createElement('a');
+            anchor.id = suite.name + '-' + test.name;
+            test.anchor = anchor;
+            anchor.appendChild(document.createTextNode(formatTestName(suite.name, test.name)));
+            testItem.appendChild(anchor);
+            testList.appendChild(testItem);
+        }
+        li.appendChild(testList);
+
+        ol.appendChild(li);
+    }
+
+    control.appendChild(ol);
+
+    var button = document.createElement('button');
+    button.textContent = 'Step';
+    button.onclick = onstep;
+    control.appendChild(button);
+
+    var button = document.createElement('button');
+    button.textContent = 'Run';
+    button.id = 'runSuites';
+    button.onclick = onrun;
+    control.appendChild(button);
+
+    var button = document.createElement('button');
+    button.textContent = 'Select all';
+    button.onclick = function () {
+        for (var suiteIndex = 0; suiteIndex < suites.length; suiteIndex++) {
+            suites[suiteIndex].disabled = false;
+            checkboxes[suiteIndex].checked = true;
+        }
+    };
+    control.appendChild(button);
+
+    var button = document.createElement('button');
+    button.textContent = 'Unselect all';
+    button.onclick = function () {
+        for (var suiteIndex = 0; suiteIndex < suites.length; suiteIndex++) {
+            suites[suiteIndex].disabled = true;
+            checkboxes[suiteIndex].checked = false;
+        }
+
+    };
+    control.appendChild(button);
+
+    return control;
+}
+
+var parseQueryString = (function (pairList) {
+    var pairs = {};
+    for (var i = 0; i < pairList.length; ++i) {
+        var keyValue = pairList[i].split('=', 2);
+        if (keyValue.length == 1)
+            pairs[keyValue[0]] = '';
+        else
+            pairs[keyValue[0]] = decodeURIComponent(keyValue[1].replace(/\+/g, ' '));
+    }
+    return pairs;
+})(window.location.search.substr(1).split('&'));
+
+function disableAllSuitesExcept(suiteName) {
+    Suites.forEach(function(element) {
+        if (element.name !== suiteName)
+            element.disabled = true;
+    });
+}
+
+function startTest() {
+    var queryParam = parseQueryString['suite'];
+    if (queryParam !== undefined)
+        disableAllSuitesExcept(queryParam);
+
+    var runner = new BenchmarkRunner(Suites, {
+        willRunTest: function (suite, test) {
+            test.anchor.classList.add('running');
+        },
+        didRunTest: function (suite, test) {
+            var classList = test.anchor.classList;
+            classList.remove('running');
+            classList.add('ran');
+        },
+        didRunSuites: function (measuredValues) {
+            var results = '';
+            for (var suiteName in measuredValues.tests) {
+                var suiteResults = measuredValues.tests[suiteName];
+                for (var testName in suiteResults.tests) {
+                    var testResults = suiteResults.tests[testName];
+                    for (var subtestName in testResults.tests) {
+                        results += suiteName + ' : ' + testName + ' : ' + subtestName
+                            + ': ' + testResults.tests[subtestName] + ' ms\n';
+                    }
+                }
+                results += suiteName + ' : ' + suiteResults.total + ' ms\n';
+            }
+            results += 'Arithmetic Mean : ' + measuredValues.mean  + ' ms\n';
+            results += 'Geometric Mean : ' + measuredValues.geomean  + ' ms\n';
+            results += 'Total : ' + measuredValues.total + ' ms\n';
+            results += 'Score : ' + measuredValues.score + ' rpm\n';
+
+            if (!results)
+                return;
+
+            var pre = document.createElement('pre');
+            document.body.appendChild(pre);
+            pre.textContent = results;
+        }
+    });
+
+    var currentState = null;
+
+    // Don't call step while step is already executing.
+    document.body.appendChild(createUIForSuites(Suites,
+        function () { runner.step(currentState).then(function (state) { currentState = state; }); },
+        function () { runner.runAllSteps(currentState); currentState = null; }));
+
+    if (parseQueryString['startAutomatically'] !== undefined)
+        document.getElementById('runSuites').click();
+}
+
+window.addEventListener('load', startTest);
+
+</script>
+</body>
+</html>
diff --git a/PerformanceTests/StyleBench/index.html b/PerformanceTests/StyleBench/index.html
new file mode 100644 (file)
index 0000000..46af83b
--- /dev/null
@@ -0,0 +1,85 @@
+<!DOCTYPE html>
+<html>
+<head>
+    <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
+    <title>StyleBench 0.1</title>
+    <link rel="stylesheet" href="../Speedometer/resources/main.css">
+    <script src="../Speedometer/resources/main.js" defer></script>
+    <script src="../Speedometer/resources/benchmark-runner.js" defer></script>
+    <script src="../Speedometer/resources/benchmark-report.js" defer></script>
+    <script src="../resources/statistics.js" defer></script>
+    <script src="resources/style-bench.js" defer></script>
+    <script src="resources/tests.js" defer></script>
+    <script>
+        addEventListener('load', () => {
+            if (!window.location.protocol.startsWith('http'))
+                showSection('local-message', false);
+        });
+    </script>
+</head>
+<body>
+<main>
+    <a id="logo-link" href="javascript:showHome()"></a>
+
+    <section id="home" class="selected">
+        <p>
+            StyleBench is a browser benchmark that measures the performance of the style resolution mechanism.
+        </p>
+        <p id="screen-size-warning"><strong>
+            Your browser window is too small. For most accurate results, please make the view port size at least 850px by 650px.<br>
+            It's currently <span id="screen-size"></span>.
+        </strong>
+        <div class="buttons">
+            <button onclick="startTest()">Start Test</button>
+        </div>
+        <p class="show-about"><a href="javascript:showAbout()">About StyleBench</a></p>
+    </section>
+
+    <section id="running">
+        <div id="testContainer"></div>
+        <div id="progress"><div id="progress-completed"></div></div>
+        <div id="info"></div>
+    </section>
+
+    <section id="summarized-results">
+        <h1>Runs / Minute</h1>
+        <div class="gauge"><div class="window"><div class="needle"></div></div></div>
+        <hr>
+        <div id="result-number"></div>
+        <div id="confidence-number"></div>
+        <div class="buttons">
+            <button onclick="startTest()">Test Again</button>
+            <button class="show-details" onclick="showResultDetails()">Details</button>
+        </div>
+    </section>
+
+    <section id="detailed-results">
+        <h1>Detailed Results</h1>
+        <table class="results-table"></table>
+        <table class="results-table"></table>
+        <div class="arithmetic-mean"><label>Arithmetic Mean:</label><span id="results-with-statistics"></span></div>
+        <div class="buttons">
+            <button onclick="startTest()">Test Again</button>
+            <button id="show-summary" onclick="showResultsSummary()">Summary</button>
+        </div>
+        <p class="show-about"><a href="javascript:showAbout()">About StyleBench</a></p>
+    </section>
+
+    <section id="about">
+        <h1>About StyleBench</h1>
+
+        <p>StyleBench tests performance of CSS style resolution and style invalidation. Each test run creates a large document and a large stylesheet using varying settings. It then applies a series of mutations to the document and measures the time to update the rendering. The resulting layout is simple, most of the pressure is on selector matching.</p>
+
+        <p>StyleBench uses Speedometer framework for UI and measurements.</p>
+    </section>
+    <section id="local-message">
+        <h2>Access via 'file:' protocol</h1>
+        <p>To run locally, launch a web server under PerformanceTests directory with 'python -m SimpleHTTPServer 8001' and access via <a href="http://localhost:8001/StyleBench">http://localhost:8001/StyleBench</a>.
+        </p>
+        <p>
+            Individual tests (without measurement) can also be run locally by opening <a href="resources/style-bench.html">PerformanceTests/StyleBench/resources/style-bench.html</a>
+        </p>
+    </section>
+</main>
+</body>
+</html>
diff --git a/PerformanceTests/StyleBench/resources/style-bench.html b/PerformanceTests/StyleBench/resources/style-bench.html
new file mode 100644 (file)
index 0000000..ce55e10
--- /dev/null
@@ -0,0 +1,32 @@
+<!doctype html>
+<script src="style-bench.js"></script>
+<body>
+<div id="testroot"></div>
+<div id="controls">
+<select></select>
+<button onclick="createBenchmarkFromSelect()">Initialize</button>
+<button onclick="createBenchmarkFromSelect().runForever()">Initialize and run</button>
+</div>
+<script>
+const configurations = StyleBench.predefinedConfigurations();
+
+const select = document.querySelector("#controls select");
+for (const configuration of configurations) {
+    const option = document.createElement("option");
+    option.innerHTML = configuration.name;
+    select.appendChild(option);
+}
+
+function createBenchmark(configuration)
+{
+    controls.remove();
+
+    return new StyleBench(configuration);
+}
+
+function createBenchmarkFromSelect()
+{
+    return createBenchmark(configurations[select.selectedIndex]);
+}
+</script>
+
diff --git a/PerformanceTests/StyleBench/resources/style-bench.js b/PerformanceTests/StyleBench/resources/style-bench.js
new file mode 100644 (file)
index 0000000..3765ba6
--- /dev/null
@@ -0,0 +1,385 @@
+class Random
+{
+    constructor(seed)
+    {
+        this.seed = seed % 2147483647;
+        if (this.seed <= 0)
+            this.seed += 2147483646;
+    }
+
+    get next()
+    {
+        return this.seed = this.seed * 16807 % 2147483647;
+    }
+
+    chance(chance)
+    {
+        return this.next % 1048576 < chance * 1048576;
+    }
+
+    number(under)
+    {
+        return this.next % under;
+    }
+}
+
+function nextAnimationFrame()
+{
+    return new Promise(resolve => requestAnimationFrame(resolve));
+}
+
+class StyleBench
+{
+    static defaultConfiguration()
+    {
+        return {
+            name: 'Default',
+            elementTypeCount: 10,
+            elementChance: 0.5,
+            classCount: 200,
+            classChance: 0.3,
+            combinators: [' ', '>',],
+            pseudoClasses: [],
+            pseudoClassChance: 0,
+            beforeAfterChance: 0,
+            maximumSelectorLength: 6,
+            ruleCount: 5000,
+            elementCount: 20000,
+            maximumTreeDepth: 6,
+            maximumTreeWidth: 50,
+            repeatingSequenceChance: 0.2,
+            repeatingSequenceMaximumLength: 3,
+            leafClassMutationChance: 0.1,
+            styleSeed: 1,
+            domSeed: 2,
+        };
+    }
+
+    static descendantCombinatorConfiguration()
+    {
+        return Object.assign(this.defaultConfiguration(), {
+            name: 'Descendant and child combinators',
+        });
+    }
+
+    static siblingCombinatorConfiguration()
+    {
+        return Object.assign(this.defaultConfiguration(), {
+            name: 'Sibling combinators',
+            combinators: [' ', ' ', '>', '>', '~', '+',],
+        });
+    }
+
+    static pseudoClassConfiguration()
+    {
+        return Object.assign(this.defaultConfiguration(), {
+            name: 'Positional pseudo classes',
+            pseudoClassChance: 0.1,
+            pseudoClasses: [
+                'nth-child(2n+1)',
+                'nth-last-child(3n)',
+                'nth-of-type(3n)',
+                'nth-last-of-type(4n)',
+                'first-child',
+                'last-child',
+                'first-of-type',
+                'last-of-type',
+                'only-of-type',
+            ],
+        });
+    }
+
+    static beforeAndAfterConfiguration()
+    {
+        return Object.assign(this.defaultConfiguration(), {
+            name: 'Before and after pseudo elements',
+            beforeAfterChance: 0.1,
+        });
+    }
+
+    static predefinedConfigurations()
+    {
+        return [
+            this.descendantCombinatorConfiguration(),
+            this.siblingCombinatorConfiguration(),
+            this.pseudoClassConfiguration(),
+            this.beforeAndAfterConfiguration(),
+        ];
+    }
+
+    constructor(configuration)
+    {
+        this.configuration = configuration;
+
+        this.baseStyle = document.createElement("style");
+        this.baseStyle.textContent = `
+            #testroot {
+                font-size: 10px;
+                line-height: 10px;
+            }
+            #testroot * {
+                display: inline-block;
+            }
+            #testroot :empty {
+                width:10px;
+                height:10px;
+            }
+        `;
+        document.head.appendChild(this.baseStyle);
+
+        this.random = new Random(this.configuration.styleSeed);
+        this.makeStyle();
+
+        this.random = new Random(this.configuration.domSeed);
+        this.makeTree();
+    }
+
+    randomElementName()
+    {
+        const elementTypeCount = this.configuration.elementTypeCount;
+        return `elem${ this.random.number(elementTypeCount) }`;
+    }
+
+    randomClassName()
+    {
+        const classCount = this.configuration.classCount;
+        return `class${ this.random.number(classCount) }`;
+    }
+
+    randomClassNameFromRange(range)
+    {
+        const maximum = Math.round(range * this.configuration.classCount);
+        return `class${ this.random.number(maximum) }`;
+    }
+
+    randomCombinator()
+    {
+        const combinators = this.configuration.combinators;
+        return combinators[this.random.number(combinators.length)]
+    }
+
+    randomPseudoClass()
+    {
+        const pseudoClasses = this.configuration.pseudoClasses;
+        return pseudoClasses[this.random.number(pseudoClasses.length)]
+    }
+
+    makeSimpleSelector(index, length)
+    {
+        const isLast = index == length - 1;
+        const usePseudoClass = this.random.chance(this.configuration.pseudoClassChance) && this.configuration.pseudoClasses.length;
+        const useElement = usePseudoClass || this.random.chance(this.configuration.elementChance); // :nth-of-type etc only make sense with element
+        const useClass = !useElement || this.random.chance(this.configuration.classChance);
+        const useBeforeOrAfter = isLast && this.random.chance(this.configuration.beforeAfterChance);
+        let result = "";
+        if (useElement)
+            result += this.randomElementName();
+        if (useClass) {
+            // Use a smaller pool of class names on the left side of the selectors to create containers.
+            result += "." + this.randomClassNameFromRange((index + 1) / length);
+        }
+        if (usePseudoClass)
+            result +=  ":" + this.randomPseudoClass();
+        if (useBeforeOrAfter) {
+            if (this.random.chance(0.5))
+                result +=  "::before";
+            else
+                result +=  "::after";
+        }
+        return result;
+    }
+
+    makeSelector()
+    {
+        const length = this.random.number(this.configuration.maximumSelectorLength) + 1;
+        let result = this.makeSimpleSelector(0, length);
+        for (let i = 0; i < length; ++i) {
+            const combinator = this.randomCombinator();
+            if (combinator != ' ')
+                result += " " + combinator;
+            result += " " + this.makeSimpleSelector(i, length);
+        }
+        return result;
+    }
+
+    get randomColorComponent()
+    {
+        return this.random.next % 256;
+    }
+
+    makeDeclaration(selector)
+    {
+        let declaration = `background-color: rgb(${this.randomColorComponent}, ${this.randomColorComponent}, ${this.randomColorComponent});`;
+
+        if (selector.endsWith('::before') || selector.endsWith('::after'))
+            declaration += " content: '\xa0';";
+
+        return declaration;
+    }
+
+    makeRule()
+    {
+        const selector = this.makeSelector();
+        return selector + " { " + this.makeDeclaration(selector) + " }";
+    }
+
+    makeStylesheet(size)
+    {
+        let cssText = "";
+        for (let i = 0; i < size; ++i)
+            cssText += this.makeRule() + "\n";
+        return cssText;
+    }
+
+    makeStyle()
+    {
+        this.testStyle = document.createElement("style");
+        this.testStyle.textContent = this.makeStylesheet(this.configuration.ruleCount);
+
+        document.head.appendChild(this.testStyle);
+    }
+
+    makeElement()
+    {
+        const element = document.createElement(this.randomElementName());
+        const hasClasses = this.random.chance(0.5);
+        if (hasClasses) {
+            const count = this.random.number(3) + 1;
+            for (let i = 0; i < count; ++i)
+                element.classList.add(this.randomClassName());
+        }
+        return element;
+    }
+
+    makeTreeWithDepth(parent, remainingCount, depth)
+    {
+        const maximumDepth = this.configuration.maximumTreeDepth;
+        const maximumWidth =  this.configuration.maximumTreeWidth;
+        const nonEmptyChance = (maximumDepth - depth) / maximumDepth;
+
+        const shouldRepeat = this.random.chance(this.configuration.repeatingSequenceChance);
+        const repeatingSequenceLength = shouldRepeat ? this.random.number(this.configuration.repeatingSequenceMaximumLength) + 1 : 0;
+
+        let childCount = 0;
+        if (depth == 0)
+            childCount = remainingCount;
+        else if (this.random.chance(nonEmptyChance))
+            childCount = this.random.number(maximumWidth * depth / maximumDepth);
+
+        let repeatingSequence = [];
+        let repeatingSequenceSize = 0;
+        for (let i = 0; i < childCount; ++i) {
+            if (shouldRepeat && repeatingSequence.length == repeatingSequenceLength && repeatingSequenceSize < remainingCount) {
+                for (const subtree of repeatingSequence)
+                    parent.appendChild(subtree.cloneNode(true));
+                remainingCount -= repeatingSequenceSize;
+                if (!remainingCount)
+                    return 0;
+                continue;
+            }
+            const element = this.makeElement();
+            parent.appendChild(element);
+
+            if (!--remainingCount)
+                return 0;
+            remainingCount = this.makeTreeWithDepth(element, remainingCount, depth + 1);
+            if (!remainingCount)
+                return 0;
+
+            if (shouldRepeat && repeatingSequence.length < repeatingSequenceLength) {
+                repeatingSequence.push(element);
+                repeatingSequenceSize += element.querySelectorAll("*").length + 1;
+            }
+        }
+        return remainingCount;
+    }
+
+    makeTree()
+    {
+        this.testRoot = document.querySelector("#testroot");
+        const elementCount = this.configuration.elementCount;
+
+        this.makeTreeWithDepth(this.testRoot, elementCount, 0);
+
+        this.updateCachedTestElements();
+    }
+
+    updateCachedTestElements()
+    {
+        this.testElements = this.testRoot.querySelectorAll("*");
+    }
+
+    randomTreeElement()
+    {
+        const randomIndex = this.random.number(this.testElements.length);
+        return this.testElements[randomIndex]
+    }
+
+    addClasses(count)
+    {
+        for (let i = 0; i < count;) {
+            const element = this.randomTreeElement();
+            // There are more leaves than branches. Avoid skewing towards leaf mutations.
+            if (!element.firstChild && !this.random.chance(this.configuration.leafClassMutationChance))
+                continue;
+            ++i;
+            const classList = element.classList;
+            classList.add(this.randomClassName());
+        }
+    }
+
+    removeClasses(count)
+    {
+        for (let i = 0; i < count;) {
+            const element = this.randomTreeElement();
+            const classList = element.classList;
+            if (!element.firstChild && !this.random.chance(this.configuration.leafClassMutationChance))
+                continue;
+            if (!classList.length)
+                continue;
+            ++i;
+            classList.remove(classList[0]);
+        }
+    }
+
+    addLeafElements(count)
+    {
+        for (let i = 0; i < count;) {
+            const parent = this.randomTreeElement();
+            // Avoid altering tree shape by turning many leaves into containers.
+            if (!parent.firstChild)
+                continue;
+            ++i;
+            const children = parent.childNodes;
+            const index = this.random.number(children.length + 1);
+            parent.insertBefore(this.makeElement(), children[index]);
+        }
+        this.updateCachedTestElements();
+    }
+
+    removeLeafElements(count)
+    {
+        for (let i = 0; i < count;) {
+            const element = this.randomTreeElement();
+
+            const canRemove = !element.firstChild && element.parentNode;
+            if (!canRemove)
+                continue;
+            ++i;
+            element.parentNode.removeChild(element);
+        }
+        this.updateCachedTestElements();
+    }
+
+    async runForever()
+    {
+        while (true) {
+            this.addClasses(10);
+            this.removeClasses(10);
+            this.addLeafElements(10);
+            this.removeLeafElements(10);
+
+            await nextAnimationFrame();
+        }
+    }
+}
diff --git a/PerformanceTests/StyleBench/resources/tests.js b/PerformanceTests/StyleBench/resources/tests.js
new file mode 100644 (file)
index 0000000..bd554c0
--- /dev/null
@@ -0,0 +1,37 @@
+function makeSteps(count)
+{
+    let steps = [];
+    for (let i = 0; i < count; ++i) {
+        steps.push(new BenchmarkTestStep('Adding classes', (bench, contentWindow, contentDocument) => {
+            bench.addClasses(100);
+        }));
+        steps.push(new BenchmarkTestStep('Removing classes', (bench, contentWindow, contentDocument) => {
+            bench.removeClasses(100);
+        }));
+        steps.push(new BenchmarkTestStep('Adding leaf elements', (bench, contentWindow, contentDocument) => {
+            bench.addLeafElements(100);
+        }));
+        steps.push(new BenchmarkTestStep('Removing leaf elements', (bench, contentWindow, contentDocument) => {
+            bench.removeLeafElements(100);
+        }));
+    }
+    return steps;
+}
+
+function makeSuite(configuration)
+{
+    return {
+        name: configuration.name,
+        url: 'style-bench.html',
+        prepare: (runner, contentWindow, contentDocument) => {
+            return runner.waitForElement('#testroot').then((element) => {
+                return contentWindow.createBenchmark(configuration);
+            });
+        },
+        tests: makeSteps(5),
+    };
+}
+
+var Suites = [];
+for (const configuration of StyleBench.predefinedConfigurations())
+    Suites.push(makeSuite(configuration));