Где почитать (тем более не русском), не знаю — делал это 3+ года назад — путем проб и ошибок.
Тогда информации было еще меньше — т.к. кросс-браузерность, неустоявшиеся спеки и т.д — никто в продакшен не брал.
На мой взгляд, инструментов в хроме вполне достаточно, чтобы понять где затык.
Timeline в хроме вполне наглядно всё показывает.
Да — вынес каждую строчку в слой.
Перефразируя «на пальцах»:
свойство translate3d(0, 0, 0) — а ля галочка «запихни это в слой».
слой (при статичном содержании) рендерится (лейаутится, рисуется) на CPU 1 раз — читай, растровое изображение/текстура.
при последующих перерисовках (например, прокрутка, или что-то другое) слои композитятся на GPU.
если ничего не путаю, кто-то из родителей тоже должен быть слоем.
«chrome developer tools -> rendering -> show layer borders» обводит каждый слой.
Каждая строчка = отдельный слой => profit.
Мой data-grid за эти 3 года править не пришлось — всё работает.
Нужен был data-grid на html5 (в узко-специализированную админ-панель):
1) 40+ строк * 20+ столбцов
2) нетормозящая прокрутка
3) мгновенная отрисовка
4) динамическая подгрузка данных с сервиса
Все готовые решения жутко тормозили.
Стал копать где «узкое горлышко» — выяснилось:
1) создание DOM на каждую строчку. Решилось lazy-созданием, и перемещением (а не удалением/пересозданием) строчек за границой видимости.
2) отрисовка 800+ div'ов с данными. GPU в помощь.
Хром умеет композитить 3d слои при наличии GPU (гугл: GPU Accelerated Compositing in Chrome)
Написал свой дата-грид, использующий это свойство — решил все задачи.
Если в 2х словах, то в хроме:
1) запихнуть кусок DOM'а в слой: css свойство transform: translate3d(0, 0, 0);
2) посмотреть границы 3d-слоев: chrome developer tools -> rendering -> show layer borders
Да этот конкус выйденого яйца не стоит.
Об этом и весь спич.
Пойди туда не зная куда…
Я, может, категоричен, но хочется самому приложиться.
Но есть одно «но»: в реальных системах не оптимизируют функции, а оптимизируют подход.
Назвали бы свой конкурс «оптимизация под v8», ни у кого бы вопросов не возникло.
Ладно, ладно — хватит минусовать.
По делу.
Своим постом выше, я пытался сказать, что (при нормальной реализации) затраты на «поддержание» данных намного меньше (место/время), чем то, что предложили нам в этом задании.
Я, может, додумываю, но мне так кажется, что вопрос в самом слове «много».
Что для Вас «много» — обычный нечищеный почтовый ящик, и функция фильтр будет вызываться на каждый такой ящик?
У меня в спам-ящике 6к сообщений…
Или разговор идет о строке (если конкатенировать все from в сумме) в сотни мегабайт?
Если второе — я бы с удовольствием поучастовал.
Как можно что-то оптимизировать, когда не заданы граничные (реальные) условия?
В общем, в моём понимании, «много» — это сферический конь в вакууме.
Дальше.
Данная задача на матчинг по паттерну больших объёмов данных.
Вы боритесь за скорость, но не говорите об ограничениях по памяти.
Как и всё в программировании, есть трейд-оф.
Потратили память на дерево, записали в него предварительно (при поступлении письма в базу) — тогда искомая функция будет быстрее некуда.
Оптимизировать вызов самой функции (т.е. строить леса внутри самой функции), есть… даже не знаю — зачем так тупо делать?
Ну или опять — недостаток исходной информации — может Вы хотите не тратить память? Почему не сказали?
Резюмируя.
Вы хотите найти человека, который умеет оптимизировать под v8?
Тогда условия задачи понятны.
Или Вы хотите решить реальную задачу?
Тогда Ваше заявление, что всё будет задано «конкретно» в этот раз — не прокатывает.
И пост скриптум.
Никогда не пишу комментарии в принципе, и я так «завёлся» потому, что у меня есть один могильничек алгоритмик на яваскрипте…
Пришлось писать велосипед используя мат-выкладки одного гения (заняло месяц понять, что он имелл в виду, т.к. реализации не было на тот момент в принципе...)
История простая.
Нужен был быстрый поиск с ошибками по большому объёму строковых данных (привет биоинформатика!)
Исходные данные:
1) полный японский словарь с полным переводом на английский (10Mb данных, что равно ~3 раза вся «Война и Мир» целиком)
2) работаем на клиенте в хроме
Задачи:
1) бытро искать
2) искать с ошибками
Первый результат был не ахти: дерево строилось (по искомым 10Mb) ~30 сек и весило 750Mb.
Обход же был впечатляющим, например:
1) найти все буквы «a» во всех переводах японских слов (давно было, не помню точную цифру, но больше полумиллиона результатов)
2) отранжировать результаты по появлению буквы в слове
3) отранжировать результаты по длинне слова
4) отрисовать первую сотню
= ~10ms (chrome, i3, 8Mb RAM)
Уточнение — хром падал, если забрать больше 500Mb памяти.
1я оптимизация
скорость построения 5-7сек, вес дерева 170Mb (тут можно еще много чего накрутить, но задачи не было)
2я оптимизация
Поскольку словарь статичный, то операции добавления и удаления были не нужны.
Всё сократилось до ~7Mb под дерево
3я оптимизация
Сам словарь в дереве задан неявно = исходные данные не нужны = 10Mb исходников -> ~7Mb дерева + быстрый поиск
Имея в виду всё что выше, что вы, блин, хотите сделать то?
Давайте тестанём эту историю?
Ну и пост пост скриптум.
1) этот алгоритм был «лучшее что я сделал за 25 лет стажа» (ну или может самое интересное)
2) имея этот опыт, очень захотелось поучаствовать (не ради копеек, конечно), но я действительно не понимаю, чего Вы хотите добиться
Ну и в догонку.
Если задаваться вопросом «зачем» — мой подход к программированию на с++ прост.
Программа при исполнениии может совершать ошибки: мета-программа на этапе компиляции, программа на этапе исполнения.
И, на мой взгляд, допустить ошибку в мета-программе дешевле, т.к. (в случае ошибки в мета-коде) нативный код тогда просто не соберется.
Соответственно, спрятаться багам становится сложнее.
Поэтому и написан этот «везде использующийся» костыль.
Конечно, я понимаю, что это (с одной стороны) самооправдание фанатизма «тотальной шаблонизизации»… но так, в моем случае, генерируется больше фана при работе.
Да какие обиды.
Честно — теперь я хоть понимаю почему минусы и плюсы прыгают туда сюда.
Если у кого возникнет желание переделать это творчество в статью — так как он это видит, и кто-то посчитает этот код достойным оного — милости просим.
Писал исключительно поделиться достижениями и обсудить недостатки подхода. Ну, видимо, недопонял формат.
Тогда информации было еще меньше — т.к. кросс-браузерность, неустоявшиеся спеки и т.д — никто в продакшен не брал.
На мой взгляд, инструментов в хроме вполне достаточно, чтобы понять где затык.
Timeline в хроме вполне наглядно всё показывает.
Да — вынес каждую строчку в слой.
Перефразируя «на пальцах»:
свойство translate3d(0, 0, 0) — а ля галочка «запихни это в слой».
слой (при статичном содержании) рендерится (лейаутится, рисуется) на CPU 1 раз — читай, растровое изображение/текстура.
при последующих перерисовках (например, прокрутка, или что-то другое) слои композитятся на GPU.
если ничего не путаю, кто-то из родителей тоже должен быть слоем.
«chrome developer tools -> rendering -> show layer borders» обводит каждый слой.
Каждая строчка = отдельный слой => profit.
Мой data-grid за эти 3 года править не пришлось — всё работает.
P.S. А вот flexbox уже раза 4 ломали…
У меня был юз-кейс.
Нужен был data-grid на html5 (в узко-специализированную админ-панель):
1) 40+ строк * 20+ столбцов
2) нетормозящая прокрутка
3) мгновенная отрисовка
4) динамическая подгрузка данных с сервиса
Все готовые решения жутко тормозили.
Стал копать где «узкое горлышко» — выяснилось:
1) создание DOM на каждую строчку. Решилось lazy-созданием, и перемещением (а не удалением/пересозданием) строчек за границой видимости.
2) отрисовка 800+ div'ов с данными. GPU в помощь.
Хром умеет композитить 3d слои при наличии GPU (гугл: GPU Accelerated Compositing in Chrome)
Написал свой дата-грид, использующий это свойство — решил все задачи.
Если в 2х словах, то в хроме:
1) запихнуть кусок DOM'а в слой: css свойство transform: translate3d(0, 0, 0);
2) посмотреть границы 3d-слоев: chrome developer tools -> rendering -> show layer borders
Об этом и весь спич.
Пойди туда не зная куда…
Я, может, категоричен, но хочется самому приложиться.
Но есть одно «но»: в реальных системах не оптимизируют функции, а оптимизируют подход.
Назвали бы свой конкурс «оптимизация под v8», ни у кого бы вопросов не возникло.
По делу.
Своим постом выше, я пытался сказать, что (при нормальной реализации) затраты на «поддержание» данных намного меньше (место/время), чем то, что предложили нам в этом задании.
Жму руку, мысль доехала, как я смотрю.
К сожалению, я немного набухался в данный момент — отвечу завтра на трезвую.
Что для Вас «много» — обычный нечищеный почтовый ящик, и функция фильтр будет вызываться на каждый такой ящик?
У меня в спам-ящике 6к сообщений…
Или разговор идет о строке (если конкатенировать все from в сумме) в сотни мегабайт?
Если второе — я бы с удовольствием поучастовал.
Как можно что-то оптимизировать, когда не заданы граничные (реальные) условия?
В общем, в моём понимании, «много» — это сферический конь в вакууме.
Дальше.
Данная задача на матчинг по паттерну больших объёмов данных.
Вы боритесь за скорость, но не говорите об ограничениях по памяти.
Как и всё в программировании, есть трейд-оф.
Потратили память на дерево, записали в него предварительно (при поступлении письма в базу) — тогда искомая функция будет быстрее некуда.
Оптимизировать вызов самой функции (т.е. строить леса внутри самой функции), есть… даже не знаю — зачем так тупо делать?
Ну или опять — недостаток исходной информации — может Вы хотите не тратить память? Почему не сказали?
Резюмируя.
Вы хотите найти человека, который умеет оптимизировать под v8?
Тогда условия задачи понятны.
Или Вы хотите решить реальную задачу?
Тогда Ваше заявление, что всё будет задано «конкретно» в этот раз — не прокатывает.
И пост скриптум.
Никогда не пишу комментарии в принципе, и я так «завёлся» потому, что у меня есть один
могильничекалгоритмик на яваскрипте…Пришлось писать велосипед используя мат-выкладки одного гения (заняло месяц понять, что он имелл в виду, т.к. реализации не было на тот момент в принципе...)
История простая.
Нужен был быстрый поиск с ошибками по большому объёму строковых данных (привет биоинформатика!)
Исходные данные:
1) полный японский словарь с полным переводом на английский (10Mb данных, что равно ~3 раза вся «Война и Мир» целиком)
2) работаем на клиенте в хроме
Задачи:
1) бытро искать
2) искать с ошибками
Первый результат был не ахти: дерево строилось (по искомым 10Mb) ~30 сек и весило 750Mb.
Обход же был впечатляющим, например:
1) найти все буквы «a» во всех переводах японских слов (давно было, не помню точную цифру, но больше полумиллиона результатов)
2) отранжировать результаты по появлению буквы в слове
3) отранжировать результаты по длинне слова
4) отрисовать первую сотню
= ~10ms (chrome, i3, 8Mb RAM)
Уточнение — хром падал, если забрать больше 500Mb памяти.
1я оптимизация
скорость построения 5-7сек, вес дерева 170Mb (тут можно еще много чего накрутить, но задачи не было)
2я оптимизация
Поскольку словарь статичный, то операции добавления и удаления были не нужны.
Всё сократилось до ~7Mb под дерево
3я оптимизация
Сам словарь в дереве задан неявно = исходные данные не нужны = 10Mb исходников -> ~7Mb дерева + быстрый поиск
Имея в виду всё что выше, что вы, блин, хотите сделать то?
Давайте тестанём эту историю?
Ну и пост пост скриптум.
1) этот алгоритм был «лучшее что я сделал за 25 лет стажа» (ну или может самое интересное)
2) имея этот опыт, очень захотелось поучаствовать (не ради копеек, конечно), но я действительно не понимаю, чего Вы хотите добиться
Если задаваться вопросом «зачем» — мой подход к программированию на с++ прост.
Программа при исполнениии может совершать ошибки: мета-программа на этапе компиляции, программа на этапе исполнения.
И, на мой взгляд, допустить ошибку в мета-программе дешевле, т.к. (в случае ошибки в мета-коде) нативный код тогда просто не соберется.
Соответственно, спрятаться багам становится сложнее.
Поэтому и написан этот «везде использующийся» костыль.
Конечно, я понимаю, что это (с одной стороны) самооправдание фанатизма «тотальной шаблонизизации»… но так, в моем случае, генерируется больше фана при работе.
Честно — теперь я хоть понимаю почему минусы и плюсы прыгают туда сюда.
Если у кого возникнет желание переделать это творчество в статью — так как он это видит, и кто-то посчитает этот код достойным оного — милости просим.
Писал исключительно поделиться достижениями и обсудить недостатки подхода. Ну, видимо, недопонял формат.