Chrome плагин для сортировки комментариев на DOU

Sergii Voloshyn Product Manager в DOU.ua 16.07.2014 22:37

Используйте imgur.com

Mykola Kosianchuk

Iryna Volkodav engineer в e-commerce startup 17.07.2014 14:41

Может я, конечно, чего-то не понял, но у меня не сортирует...Точнее сортирует, но как-то странно
uaimage.com/...US4D7-NdkkRmdQw

Спасибо, Коля, за Ваш коментарий. Ваш скриншот не доступен, могли бы Вы пожалуйста его переаттачить заново, либо воспользоваться другим сервисом, например который предложил Серёжа: imgur.com ?
А также уточните пожалуйста проблему:

Что именно Вам показалось странным в сортировки?
Какой версией Chrome вы пользуетесь?
Какой версией расширения вы пользуетесь?

Mykola Kosianchuk

Iryna Volkodav engineer в e-commerce startup 16.07.2014 00:28

Обновила версию расширения новыми улучшениями от Alexey Migutsky. Благодаря ему производительность расширения была увеличена в ~ 2 раза!
Вот метрики производительности расширения до (before — версия 0.11) и после (after — версия 0.13) изменений Alexey Migutsky:

+--------+---------------------+-------------------+-----------------+
| state  | fullsort[median],ms | fullsort[mean],ms | fullsort[range] |
+--------+---------------------+-------------------+-----------------+
| before |                 273 | 276.4             |              23 |
| after  |                 116 | 115.8             |              22 |
+--------+---------------------+-------------------+-----------------+

Метрики снимались на 5 повторениях по 1682 комментариях (против 1619 комментариев при прошлой проверке — dou.ua/...c/10383/#502837) из топика dou.ua/...ums/topic/9946

Все изменения Лёша сделал в соответствии со своим предложением в комментарии по ссылке dou.ua/...c/10383/#503002
Детали коммитов можно посмотреть в списке коммитов GitHub’а по ссылке github.com/.../commits/master

Новая версия расширения доступна для установки по ссылке (версия 0.13): chrome.google.com/...leededehadkpcfe

Alexey Migutsky Senior Software Development Engineer в Microsoft 16.07.2014 01:00

Стоит учитывать, что цифры не совсем точные. Полная сортировка во втором случае не учитывает время рендеринга результатов, т.к. рендеринг асинхронный.
Приведеённое время — это время на непосредственную сортировку + отрисовку первых 50 результатов.

Максим М Software developer в Atollon Ireland Ltd. 15.07.2014 17:48

В Opera 24.0.1558.3 работает хорошо, 1022 коммента в топике про «мажоров» :) сортирует около 2 секунд.

P.S. Кто не в курсе, для установки плагинов от хрома нужен плагин Download Chrome Extension addons.opera.com/...me-extension-9

Iryna Volkodav engineer в e-commerce startup 15.07.2014 17:55

1022 коммента в топике про «мажоров» :) сортирует около 2 секунд.

Надеюсь, что это ещё не предел, Максим, ещё поборимся за производительнось.

Максим М

Vladislav Povedyuk Java Developer 15.07.2014 13:30

ммм... после сортировки пропадает блок «Лучшие комментарии»?
До:
content.screencast.com/...-07-15_1329.png
После:
content.screencast.com/...-07-15_1330.png

Iryna Volkodav engineer в e-commerce startup 15.07.2014 13:45

Да они пропадают после сортировки, Владик. А как вы счтитаете, они нужны после сортировки? Если да, то объясните пожалуйста свою позицию. Если вашу позицию поддержат, скажем, больше 10 человек, то зареквестим ваше предложение, как фичу, которую нужно будет допилить к расшерению. Спасибо.

Vladislav Povedyuk

Vladislav Povedyuk Java Developer 15.07.2014 13:47

Баг это или фича решать Вам. Мне это не мешает, просто заметил.

Iryna Volkodav engineer в e-commerce startup 15.07.2014 14:05

Спасибо, Владик, я не собиралась и не собираюсь оспаривать вашу точку зрения, мне важно получить конструктивную критику (обратную связь от пользователей, если хотите), и посмотреть, какой поддержкой она будет пользоватся среди интересующихся, так как плагин я писала не только для себя. Если у вас всё ещё осталось желание и время на коментарий, то я правда буду рада услышать ваше мнение на этот счёт.

Заранее благодарна вам, Владик.

Vladislav Povedyuk

hs 15.07.2014 14:26

можна ж додати сторінку налаштувань :))

Iryna Volkodav engineer в e-commerce startup 15.07.2014 14:45

Спасибо, hs. Отчасти я согласна с вами. Но ведь можно много чего опционального подабавлять в конфигуратор расширение, из-за чего оно разрастётся до размеров конфигурации браузера. Поэтому я считаю, что лучше добавлять только самое необходимое, что было аргументировано и получило достаточную поддержку среди потенциальных пользователей.

А вы сможете аргументировать в контексте отсортированых коментариев, зачем могут пригодиться список лучших коментариев?

hs

hs 15.07.2014 15:19

А вы сможете аргументировать в контексте отсортированых коментариев, зачем могут пригодиться список лучших коментариев?

я взагалі туда заглядаю лише для старих топіків куда попав вперше.. а так одразу до непрочитаних коментарів

Iryna Volkodav engineer в e-commerce startup 14.07.2014 23:07

Обновила версию расширения последними изменениями от Alexey Migutsky. Благодаря ему производительность расширения была увеличена в ~ 61 раз!
Вот метрики производительности расширения до (before) и после (after) изменений Alexey Migutsky:

+--------+---------------------+-------------------+-----------------+
| state  | fullsort[median],ms | fullsort[mean],ms | fullsort[range] |
+--------+---------------------+-------------------+-----------------+
| before |               16821 | 16958.6           |            1635 |
| after  |                 273 | 276.4             |              23 |
+--------+---------------------+-------------------+-----------------+

Метрики снимались на 5 повторениях по 1619 комментариях из топика dou.ua/...ums/topic/9946

Новая версия расширения доступна для установки по ссылке (версия 0.11): chrome.google.com/...leededehadkpcfe

Oksana Kyrychenko 14.07.2014 14:39

Ирина, а на мозю планируется что-то подобное? А то Хром уж много жрЁтЪ оперативки сразу...

Sergii Voloshyn Product Manager в DOU.ua 14.07.2014 14:40

dou.ua/...ms/topic/10298

Oksana Kyrychenko

Iryna Volkodav engineer в e-commerce startup 17.07.2014 22:22

Оксана, для информации — обновился плагин под Firefox (статья здесь: dou.ua/...ms/topic/10298) в соответствии с рекомендациями от Alexey Migutsky. Детали обновления доступны здесь dou.ua/...c/10383/#502837

Расширение было переработано и теперь плагин интегрируется в существующую страницу, поэтому никаких кнопок на панели инструментов Firefox’а вы не увидите, только на странице ссылку с названием Отсортировать комментарии рядом со ссылкой — Подписаться на комментарии. Производительность расширения была увеличена в ~ 61 раз! Всё по примеру того, как было сделано для Chrome’а.

Последняя версия плагина 0.5.
Установить его можно по ссылки addons.mozilla.org/...-sort-comments

Oksana Kyrychenko

Sergii Korochkin DevOps Engineer в Star 14.07.2014 00:52

«Отсортировать комментарии» в dou.ua/...ums/topic/7607 повесил вкладку хрома (там 900+ комментов) :)

Iryna Volkodav engineer в e-commerce startup 14.07.2014 07:55

Спасибо, Сергей, вижу проблему, на этой недели планирую исправить.

Сперва я пробовала такую проблему решить через асинхронный вызов сортировки комментариев, думала, что асинхронные вызов отработает в отдельном потоке, что развяжет проблему с ощутимым подвисанием в длинных топиках, например, у меня на сортировку dou.ua/...rums/topic/7607 уходит 3.5 — 4 сек (конечно это всё индивидуально и зависит от мощности железа, качества связи и др.).

Реализовывала я это через механизмы sendRequest/onRequest.addListener следующим образом:

chrome.extension.sendRequest({'action': 'sort_click'}, function (response) {
  sort();
});

и обработчик в виде:

chrome.extension.onRequest.addListener(function (request, sender, callback) {
    if (request.action === 'sort_click') {
        callback();
    }
});

но проблема с подвисанием не исчезла. Мне порекомендовали посмотреть в сторону Web Workers, что я и сделаю на этой неделе. Я думаю, что проблему с подвисанием вкладки можно будет решить этим путём, так как сортировка в случае с Web Workers будет явно выполнятся в отдельном потоке.

Исходя из проблем, описанных Rob W по ссылке stackoverflow.com/a/22719772 буду делать исправление на worker_proxy (Web Workers in content scripts [GitHub репозиторий]), которое разработал Rob W.
Его комментарий (© Rob W):

crbug.com/357664 is the bug report about not being able to load extension scripts as a web worker.
The work-around to this problem is to load the worker script using XMLHttpRequest, then load the worker from a string. When I faced this problem in the past, I created a wrapper that transparently modifies the Worker constructor, so you can use new Worker(chrome.runtime.getURL(’worker.js’)) without any problems.

See patch-worker.js (documentation) for the implementation of the prevuous idea.

patch-worker.js has some limitations (e.g. importScripts does not work as expected), mainly related to the fact that it does not run in the chrome-extension:-origin. To solve these problems, I have created another library that uses an iframe to create the Worker. See worker_proxy for the source code and documentation.

Любые комментарии раскрывающие эту проблему лучше, или предлагающие решение — очень приветствуются.

Sergii Korochkin

Alexey Migutsky Senior Software Development Engineer в Microsoft 14.07.2014 12:51

Вы бы замерили, что у вас тормозит. Скорее всего — работа с DOM-нодами. Воркеры тут не помогут, а поможет requestAnimationFrame и сортировка кусками, чтобы дать браузеру «отдохнуть». А ещё лучше так:
1. Прятать комментарии через display:none
2. «Отрывать» их от элемента-контейнера (gist.github.com/cowboy/938767)
3. Сортировать оторванные элементы
4. Присоединить обратно.
5. Profit!

Iryna Volkodav engineer в e-commerce startup 14.07.2014 14:08

Спасибо большое, Лёша! Я попробую следовать вашему совету, Лёша, и отпишусь о своём результате обязательно.

Для общей информации, что я накопала на сейчас: проблема с Web Worker’ами еще в том, что из них нет возможности работать с DOM’ом страниц, так как DOM модель — не потокобезопасна. О том, почему, можно прочитать здесь: stackoverflow.com/a/18102539 Ну и список доступных фич Web Worker’ов приведён здесь www.html5rocks.com/...rnment-features

Alexey Migutsky Senior Software Development Engineer в Microsoft 14.07.2014 16:27

Я вам на гитхабе запилил пул-реквест со всеми этими оптимизациями.
Скорость выросла на порядок.

Я не оформлял оптимизации разными коммитами, но оставил в коде полезные комментарии.
Надеюсь, они вам помогут разобраться что к чему ;)
Советую попробовать поиграться с кодом и сравнить время выполнения до и после конкретных изменений.

Iryna Volkodav engineer в e-commerce startup 14.07.2014 16:44

Спасибо огромное, Лёша, я очень вам благодарна!

Iryna Volkodav engineer в e-commerce startup 14.07.2014 17:03

Лёша, вы красиво и понятно пишите код, приятно читать. Я уже вмержила pull request в свою ветку, спасибо.

Iryna Volkodav engineer в e-commerce startup 14.07.2014 19:12

Я почитала по requestAnimationFrame API от сюда www.html5rocks.com/...peed/rendering и реализовала, как вы рекомендовали, Лёша. Вот пример того, как я использовала requestAnimationFrame API у себя в коде:

function sortFn() {
    console.time('fullsort');
    var requestID = requestAnimationFrame(sortFn);
	...
    cancelAnimationFrame(requestID);
    console.timeEnd('fullsort');
}

В итоге у меня по производительности получились следующие результаты на основе 5 повторений для топика dou.ua/...rums/topic/9946 из 1617 комментариев:

+------------------------+-------------------+-----------------+-----------------+
|         mode           | fullsort[median]  | fullsort[mean]  | fullsort[range] |
+------------------------+-------------------+-----------------+-----------------+
| +requestAnimationFrame |              360  | 357.2           |              52 |
| -requestAnimationFrame |              350  | 356.8           |              54 |
+------------------------+-------------------+-----------------+-----------------+

+------------------------+---------------+-------------+-------------+
|         mode           | sort[median]  | sort[mean]  | sort[range] |
+------------------------+---------------+-------------+-------------+
| +requestAnimationFrame |          153  | 150.4       |          15 |
| -requestAnimationFrame |          152  | 155         |          22 |
+------------------------+---------------+-------------+-------------+

+------------------------+--------------------+------------------+------------------+
|         mode           | expandAll[median]  | expandAll[mean]  | expandAll[range] |
+------------------------+--------------------+------------------+------------------+
| +requestAnimationFrame |                14  | 19.8             |               21 |
| -requestAnimationFrame |                13  | 17.2             |               20 |
+------------------------+--------------------+------------------+------------------+

где,
+requestAnimationFrame - реализация на основе requestAnimationFrame API
-requestAnimationFrame - без requestAnimationFrame API

* Таблицы нарисованы с помощью сервиса www.sensefulsolutions.com/...t-as-table.html

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

Что думаете по этому поводу, Лёша?

Iryna Volkodav engineer в e-commerce startup 14.07.2014 19:24

Может быть это потому, что мы делаем манипуляции с DOM’ом в памяти, а не дергая каждый раз страницу, модифицируя DOM? Я имею ввиду, что мы первый раз после загрузки страницы вычитали комментарии, и дальше с ними работаем, трогая страницу только при добавлении на страницу отсортированного множества (результата) с помощью метода .appendTo($commentsList).

Nico Trygub Front-end в PD 14.07.2014 21:26

На requestAnimationFrame и display: none; забейте, в вашем случае их не используют. Лучше выбросите Жквери (для выборки можете использовать querySelectorAll). Вместо $.sort() используйте Array.prototype.sort().

Iryna Volkodav engineer в e-commerce startup 14.07.2014 22:14

Nico, спасибо большое, я прочла про requestAnimationFrame, и поняла, что это API зачастую используют в анимации. Вот выдержка из статьи Jank Busting for Better Rendering Performance:

To get a smooth animation you need a new frame to be ready every time a screen refresh happens. This has two big implications: frame timing (that is, when the frame needs to be ready by) and frame budget (that is, how long the browser has to produce a frame). You only have the time between screen refreshes to complete a frame (~16ms on a 60Hz screen), and you want to start producing the next frame as soon as the last one was put up on the screen.

Но в статье так же написано следующее:

Recall the frame timing problem mentioned above: you need a completed animation frame, finished with any JavaScript, DOM manipulation, layout, painting, etc, to be ready before the next screen refresh occurs.

Могли бы вы пожалуйста объяснить мне, чем requestAnimationFrame помогает во время DOM manipulation? Я так понимаю тем, чем и в случае с анимацией, то есть для решения проблем со Screen tearing’ом, верно? То есть при частом обновлении DOM’а страницы браузер может не успевать нормально отрисовывать кадры. И ещё, возможно, как мне подсказал Alexey Migutsky здесь: dou.ua/...c/10383/#502540 — за тем, чтоб дать браузеру возможность выполнить другие задачи. Верно?

Если я ошибаюсь, то дайте мне пожалуйста развёрнутый ответ, Nico, либо ссылки на ресурсы, где я смогу сама в этом разобраться.

Nico Trygub

Iryna Volkodav engineer в e-commerce startup 14.07.2014 22:33

Nico, объясните ещё мне пожалуйста, почему мне лучше отказаться от display: none?

Вмето $.sort() то понятно мне, почему использовать Array.prototype.sort(), потому как JQuery sort API — это просто прокси над Array.prototype.sort(), которая (из исходного кода прочла) всё что делает — просто вызывает Array.prototype.sort(). Но и то тут спорный вопрос, нужно проверить производительность, так как вызов JQuery sort API вызывается лишь один раз за один полный проход сортировки. Так что может и не стоит оптимизировать это место... Насчёт querySelectorAll посмотрю, спасибо.

Nico Trygub

Nico Trygub Front-end в PD 15.07.2014 08:32

www.paulirish.com/...mart-animating . Первое предложение блока «Why should I use it?».

requestAnimationFrame помогает во время DOM manipulation?

RAF помогает сократить количество reflow и repaint при изменении свойств елемента(-ов). DOM manipulation, широкое понятие и в этом контексте это скорее всего изменение цсс свойств элемента.

Я так понимаю тем, чем и в случае с анимацией, то есть для решения проблем со Screen tearing’ом, верно? То есть при частом обновлении DOM’а страницы браузер может не успевать нормально отрисовывать кадры.

Ну почти, браузер не отрисовывает кадры только конкретного элемента, он перерисовывает всю страницу. Более детально вы можете почитать на хабре или HTML5Rocks, ищите «Как работает браузер» или reflow & repaint.

лучше отказаться от display: none?

Вы удаляете элементы, в display:none нету необходимости. Пруф display:none в том, что браузер не отрисовывает елемент с этим свойством, а у вас и так ничего рисовать.

так как вызов JQuery sort API вызывается лишь один раз за один полный проход сортировки

Array.prototype.sort() вызывается тоже один раз, если хотите еще быстее нагуглите алгоритм побыстее или посмотрите как это сделано в underscore или lodash.
PS. Сортировку можно делать 1 раз (desc), а оригинальную структуру хранить в SessionStorage или кешировать

Alexey Migutsky Senior Software Development Engineer в Microsoft 15.07.2014 11:48

У вас сейчас есть 2 узких места — вставка отсортированных элементов в ДОМ и сама сортировка.

Про оптимизацию сортировки можно почитать тут: blog.rodneyrehm.de/...g-It-Wrong.html

У вас есть ещё шаг для упрощения предиката сортировки — вынести поиск hash у элемента на этап инициализации, т.е. делать предобработку (т.е. присобачивать hashId к каждому элементу в массиве заранее перед сортировкой)

requestAnimationFrame может помочь вам сделать процесс сортировки «визуально» быстрее на этапе вставки ДОМ-элементов. Вам нужно сделать вставку элементов батчами. Это усложнит код и замедлит процесс в целом, но визуально это будет быстрее — пользователь будет видеть первые элементы сразу после сортировки.

Iryna Volkodav engineer в e-commerce startup 15.07.2014 16:19

Я прочла Sorting — We’re Doing It Wrong, и хотела бы подсумировать задачу (а заодно и уточнить некоторые моменты), которую буду решать:

Изменить сортировку по примеру того, как расказано в этой части топика blog.rodneyrehm.de/...ng.html#mapping , из-за того, что у нас в коде
```
var firstId = parseInt(first.querySelector('.comment-link').hash.substring(1));
var secondId = parseInt(second.querySelector('.comment-link').hash.substring(1));
```
, где для двух элементов first и second будут вычисляться querySelector('.comment-link').hash.substring(1) каждую новую итерацию заново, что накладывает определённые расходы на ресурсы, верно?
По поводу вставки элементов батчами, то я представляю себе реализацию такого решения следующими способами.
Итак, вариант первый:
1. Формируем весь список коментариев, которые нужно упорядочить
2. Делаем батч из 250 (например) коментариев
3. Заполняем батч отсортированными данными
4. Результат каждого батча вставляем в страницу
5. Повторяем до тех пор, пока весь список коментариев не будет обработан
Но тут есть момент в выборе правильного алгоритма, который бы позволял нам с точностью сказать, что батч, отправленный на страницу правильно вписывается в остальную часть неотсортированного множества, тоесть батч должен содержать упорядоченные элементами, которые являются минимальными (или максимальными) из всего остального набора (коментариев), иначе мы не сможем эти батчи вставлять в страницу в правильные места. В Chrom’e, например, используют алгоритм QuickSort для сортировки Array (из документации Sorting — We’re Doing It Wrong, которую вы мне показали), который также можно будет использовать для сортировки набора данных частями (батчами). Ещё проще реализовать сортировку на алгоритмах Bubble sort (большие значения всплывают вверх, тоесть батч формируем из последних N элементов, где N — количество элементов батча) и Selection sort (меньшие значения опускаются на дно, тоесть батч формируем из первых N элементов, где N — количество элементов батча), но они в среднем медленней, чем, QuickSort, но может так, как у нас комплексное решение (сортировка коментариев, вставка результата в DOM), то может и стоит попробовать?
вариант второй:
1. Формируем весь список коментариев, которые нужно упорядочить
2. Сортируем весь набор коментариев (используем Chrome’овскую реализацию на базе QuickSort’а, если будем использовать структуру Array, например)
3. Вставляем весь результат по батчам из 250 (например) коментариев

Что скажете, Лёша?

Iryna Volkodav engineer в e-commerce startup 15.07.2014 16:39

для двух элементов first и second будут вычисляться querySelector(’.comment-link’).hash.substring(1) каждую новую итерацию заново

Здесь я имею ввиду, что для одного и того же элемента first (или second), который встретится во время сравнения с другими элементами в последующих итерациях при проходе списка.

Iryna Volkodav engineer в e-commerce startup 16.07.2014 00:42

Спасибо, Лёша, за твой вклад в расширения. Оба pull request’а от тебя я замержила в master. С твоими изменениями разобралась. Детали добавила сюда: dou.ua/...c/10383/#503434

Будут ещё идеи, буду рада тебя услышать снова.

Максим Кондаков web программист, weblancer.net 14.07.2014 17:15

Мне кажется надо использовать documentFragment. Пихаете все дивы в него, а потом просто вставляете его в дом. У вас же каждая итерация изменяет дом дерево, и это приводит к тормозам.

Iryna Volkodav engineer в e-commerce startup 14.07.2014 17:38

Спасибо, Max, Лёша так и сделал в своих коммитах, которые я замержила себе в репозиторий. Вот его куски кода:

var $comments = $commentsList.find('[class*="b-comment level-"]');
...
$comments.sort(function (first, second) {
...

Максим Кондаков

Alexey Migutsky Senior Software Development Engineer в Microsoft 16.07.2014 00:58

Нет, документФрагмент я не использовал. В последней версии (0.13) сделана визуальная оптимизация, которая вставляет элементы батчами для того, чтобы пользователь скорее увидел результат сортировки.
На моей машине сортировка «топика про мажоров» до первой перерисовки занимает примерно пол секунды.

anonymous 13.07.2014 23:07

-

Iryna Volkodav engineer в e-commerce startup 13.07.2014 14:57

У меня установлено это расширение и я довольная, как слон, и не только потому, что сама написала его :)

Sergii Nikolayev Front End 13.07.2014 21:38

Какая вы молодец, спасибо вам!

Iryna Volkodav engineer в e-commerce startup 13.07.2014 22:13

Спасибо, Коля, старалась сделать что-то полезное для этого замечательного ресурса и его обитателей (к коим и себя отношу). В целом ничего гениального в моей работе нет, просто попался отличный туториал от Christian’а.