Эффективность реализации алгоритма reflow (layout) в браузерах

Реализация shadow DOM была удалена из кода WebKit, чтобы переписать её заново в отдельной ветке. По замыслу авторов это должно позволить

1. избавиться от устаревшего кода, который много раз менялся вместе с изменениями спеки
2. контролировать влияние на производительность (постепенные изменения кода в течение нескольких лет дали в итоге замедление времени загрузки страницы на 5%, но измерить результат было сложно, теперь сравнивать производительность разных веток кода будет проще)

> The old implementation on trunk resulted in 5% overall slowdown in the page load time but we didn't quantify that until we removed the feature entirely last year.  That's probably because the feature was added over years as a pile of small changesets each of which introduced immeasurably small performance regressions.  Development in a branch allows a faithful performance comparison between the two.

> JSC team has been utilizing SVN branches to work on Concurrent JIT, Generational GC, FTL, etc... to quantity the total performance cost and benefit of each feature, and it has been working very well as far as I could tell.

Наиболее интересный комментарий указал на глобальную неэффективность алгоритма пересчёта стилей (он же reflow, layout, или recalculateStyle) в WebKit. Его асимптотическая сложность составляет O(N^2), в то время как в Blink сложность уменьшена до O(N). После этой оптимизации ущерб производительности от shadow DOM стал пренебрежимо малым и необходимость в его глобальном переписывании надолго отпала:

> once we removed the N^2 algorithms in Blink, the shadow DOM code dropped off the profile because we called it N times instead of N^2 times

Там же приводилась ссылка на jsfiddle и сравнение Chrome Canary и WebKit nightly. Скрипт измеряет время на вычисление document.body.offsetTop (или любого другого значения, требующего reflow) для N и 10*N элементов. При сложности алгоритма O(N^2) время выполнения reflow в WebKit вырастает примерно на два порядка при увеличении количества элементов на порядок. По результатам сравнения разработчиками был создан баг на WebKit.

Для меня интересно было оценить сложность алгоритма reflow в других браузерах (jsfiddle для экспериментов). Простейшая характеристика - отношение времён выполнения reflow для разного количества элементов в DOM: factor = time(reflow(10*N))/time(reflow(N))

Браузер        Factor

Chrome 33      9..11 первый раз, 6.3..6.5 после прогрева

Firefox 27     9..11

Opera 12*      8.2..9.3 первый раз, 3.5..5.1 после прогрева

IE10**         5.0..8.3

Konqueror 4.10 9..11

Safari 5.1***  95..107 первый раз, 64..70 после прогрева

* http://jsfiddle.net/vwG2J/6/ - для Opera количество элементов прищлось увеличить, чтобы время выполнения не было слишком малым

** http://jsfiddle.net/vwG2J/7/ - для IE количество элементов пришлось уменьшить, иначе ему становилось совсем плохо (Error: Not enough storage is available to complete this operation. Error: 'Class' is undefined Error: Object doesn't support property or method 'addEvent'), и приходилось закрывать вкладку.

*** http://jsfiddle.net/vwG2J/7/ - для Safari количество элементов пришлось уменьшить, чтобы время выполнения не было слишком большим