Здравствуйте, Дарней, Вы писали:

Д>Здравствуйте, c-smile, Вы писали:

CS>>Примерно же такая оптимизация работает в Mozilla насколько мне известно.

Д>то есть примерно то же самое, что я предлагал
Д>хотя дьявол, как всегда, в деталях

CS>>У меня используется несколько иная схема — традиционный caching. Быстрее работает в моем случае.

CS>>Приведенный список 10 ситуаций (особенно последняя тема) сводят на нет возможные способы редуцирования O(N*M*D)
CS>>Например сайты семейства wikipedia в принципе не оптимизируемы из-за своей системы стилей.

Д>тем не менее, мне кажется, что случай когда каждый элемент на странице имеет отличающийся от других стиль — это исключение, а не правило

Собственно нахождение однотипных элементов это и есть задача style resolving.

Для того чтобы сказать элемент A подобен элементу B нужно проанализировать и A и B
на предмет атрибутов, всех родителей, индекса его в родительской коллекции, состояния и пр.

Например есть селекторы

div:nth-child(odd) p:nth-child(even) {}
div:nth-child(even) p:nth-child(odd) {}

На какие "кучки" будем раскладывать элементы?
А вот это например:
div:nth-child(2)
div:nth-child(3)
div:nth-child(4)
...
?

Итого разобравшись в предмете попытаемся еще раз осмыслить следующее:
"В любом случае, сложность O(N * M * D) — это реально только для самой примитивной лобовой реализации "
Есть еще непримитивные варианты?

Здравствуйте, Дарней, Вы писали:

S>>Я не специалист, но геморрой тут заметен невооруженным взглядом.

Д>геморрой конечно немаленький, но по моему впечатлению, его происхождение — в основном в сложности самой системы применения правил CSS. А от этого в любом случае никуда не деться

А чего ж там сложного? Правила просты и детерменированы.
В том то все и дело. Набор атомарно простых операций порождает серьезную вычислительную задачу.

Возвращаясь к предмету разговора:

Pavel Dvorkin:

А кстати, какой клиент это все потянет ? Netscape 3.0 на 16 Мб под Windows 95 потянет ? Тянул же он раньше...

ну дык не тянет он собственно...

У меня кстати и не было мысли что речь может идти о кодовой оптимизации. Это даже не рутинная работа , это просто происходит на уровне автомата.

То есть все равно что набирать правильно операторы языка. Если говорить про "оптимизацию" как переписыванеи существующего кода напрмиер под MMX и т.д. то это действительно скучновато.

Кстати говоря я с таким сталкивался , меня один специалист учил как "оптимизировать" это запустит VTune , и те функции которые на самом верху переписать на ассемблере. Возможно , что кто то из учасниковв дискусии думает примерно также ? Если так , то официально заявляю , я говорю о совершенно другом. Максим отлично продемонстрировал . Что можно до скончания века оптимизировать индуччкий код , на уровне кода , но если не поменять алгоритм , то ничего не изменится.

Здравствуйте, minorlogic, Вы писали:

M>Кстати говоря я с таким сталкивался , меня один специалист учил как "оптимизировать" это запустит VTune , и те функции которые на самом верху переписать на ассемблере. Возможно , что кто то из учасниковв дискусии думает примерно также ? Если так , то официально заявляю , я говорю о совершенно другом. Максим отлично продемонстрировал . Что можно до скончания века оптимизировать индуччкий код , на уровне кода , но если не поменять алгоритм , то ничего не изменится.

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

Так что элементарную эффективность на уровне кода так же нельзя сбрасывать со счетов.

Возникла мысль что некоторые учасники дискусии не вполне разделяют понимание что такое оптимизация.

Попробую привести пример из реальной жизни.
Кратко , есть в сжатии MP3 такой алгоритм , когда надо запихнуть сжатые данные в лимитированный объем(битрейт).

алгоритм
1. Бинарным делением мы находим величину квантизатора дающего ближайший по размеру результат.

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

3. После каждого изменения опять персчитываем сколько же места займет полученная информация.

(не будем заострять внимание что этот подход не эфективен в целом , можно лучше)


Так вот после замеров производительности , стало ясно что самым критичным является непосредственно нелинейная квантизация.

Анализ кода показал , что его разработчики знали об этой проблеме и уже постарались выжать из этого все что можно .

Что делать ? переписать на асемблере ? КОНЕЧНО ! Мне такое предлагали, даже настаивали . Но это ПОСЛЕДНЕЕ что я стал бы делать .

Первое правило оптимизатора какое ?
"Самый быстрый код — это тот который не выполняется"
И я подумал а можно ли сократить количество вызовов квантизатора ? И конечно , сразу понял что в большинстве случаев мы на каждой итерации квантизуем одни и теже данные с тем же самым шагом.

И тут добавление информации что на предыдущам шаге у нас была подобная квантизация и пересчитывать ее не надо дало прирост на порядок (этого шага)!!! И функция квантизации престала быть бутылочным горлышаком.

После этого было пару эвристик чтобы ускорить спуск бинарным поиском и т.д.

Так вот мысль , если бы я пытался оптимизировать квантизатор и переписывать на асемблере это дало бы минимальный прирост . А немного подумав , представив процес в целом пришло замечательное и во многом очевидное решение .

По жизни уже давным давно повторяю как мантру
"оптимизируйте алгоритмы а не код" нет неправильно , правильно так "ОПТИМИЗИРУЙТЕ АЛГОРИТМЫ А НЕ КОД !!!!!!"

Мне кажется что и Максим , когда говорит про "оптимизацию" совсем не имеет ввиду причесывание кода.


К сожалению в приведенном примере , для нахождения такого очевидного решения , пришлось ПОНЯТЬ что именно делает весь код в целом, а для этого надо знать и предметную область и многое другое.

Здравствуйте, Дарней, Вы писали:
Д>можно закэшировать полученную плоскую CSS (если исходить из предположения, что CSS не будет меняться при каждой загрузке страницы )
Гм. Я, может быть, страшно туплю, но этот кэш вообще будет не очень применим. В том смысле, что следующая показанная страница, скорее всего будет содержать другой HTML. И для него придется решать задачу планаризации заново и с нуля. А ситуация типа "если мы смотрим гарантированно тот же контент с гарантированно тем же CSS" — имхо конь в вакууме.
Д>геморрой конечно немаленький, но по моему впечатлению, его происхождение — в основном в сложности самой системы применения правил CSS. А от этого в любом случае никуда не деться
Ну? Так тебя вроде бы в этом и убеждают. Что рендеринг HTML c учетом CSS — дорогая задача.

Здравствуйте, eao197, Вы писали:

E>Может измениться. Вот у меня был случай -- в одном месте, которое вызывалось слишком часто, было два обращения к new. В многопоточном приложении, где каждый new -- это очень дорого. Я переписал это место так, что new вызывался только один раз. В результате большой кусок кода заработал в два раза быстрее и перестал быть узким местом. Еще больших результатов можно было бы достичь, конечно, изменением алгоритма (там даже не алгоритм а целая идеология бы поменялась), но затраты на такие изменения алгоритма были бы не соизмеримы с полученным выигрышем, а сложность решения серьезно бы увеличилась.

Угу. Я именно подобное и имел в виду. У меня, к примеру, new где-то в глубине циклов априорно антипатию вызывает — знаю, чего это стоит, Это не значит. что я от него обязательно откажусь, но стоп-сигнал сразу срабатывает — дескать, что это я такое здесь делаю ? Может, и оставлю в конце концов, но бездумно не пропущу.

Здравствуйте, minorlogic, Вы писали:

M>По жизни уже давным давно повторяю как мантру
M>"оптимизируйте алгоритмы а не код" нет неправильно , правильно так "ОПТИМИЗИРУЙТЕ АЛГОРИТМЫ А НЕ КОД !!!!!!"

M>Мне кажется что и Максим , когда говорит про "оптимизацию" совсем не имеет ввиду причесывание кода.

M>К сожалению в приведенном примере , для нахождения такого очевидного решения , пришлось ПОНЯТЬ что именно делает весь код в целом, а для этого надо знать и предметную область и многое другое.

К этому многому другому нужно обязательно еще и такое условие:

M>Анализ кода показал , что его разработчики знали об этой проблеме и уже постарались выжать из этого все что можно .

т.е., наличие настолько эффективного кода, который уже бесполезно вылизывать. А то может оказаться, к пример, что алгоритму требуется удалить пробелы из C-шного кода, а делается это так:

for(i = 0; i < strlen(str); i++)
{
   if(str[i] == ' ') { strcpy(str + i, str + i + 1); i--; }
}

(взято из Re[7]: Об эффективности — с другой стороны

Автор: McSeem2
Дата: 20.11.05

).

Здравствуйте, eao197, Вы писали:

E>К этому многому другому нужно обязательно еще и такое условие:
E>

M>>Анализ кода показал , что его разработчики знали об этой проблеме и уже постарались выжать из этого все что можно .

E>т.е., наличие настолько эффективного кода, который уже бесполезно вылизывать.

Нет не безполезно , там было куда вылизывать , но было видно : "разработчики знали, что это узкое место".

Здравствуйте, minorlogic, Вы писали:

E>>т.е., наличие настолько эффективного кода, который уже бесполезно вылизывать.

M>Нет не безполезно , там было куда вылизывать , но было видно : "разработчики знали, что это узкое место".

Но ведь затраты на оптимизацию достаточно хорошего кода не окупились бы, т.е. код был достаточно хорош. Что уже не мало.
Почему-то по ходу дискуссии здесь подразумевается, что все сразу пишут совершенный код, который дальнейшей оптимизации уже не поддается. Поэтому единственный способ дальнейшей оптимизации -- это смена алгоритма. А вот у меня другой опыт. Лично мне профайлер частенько показывает места, в которых я просто-напросто лопухнулся. И переписывание десяти-пятнадцати наиболее критичных для производительности методов поднимало производительность на порядок. Без смены основного алгоритма. И это при том, что я довольно ревносно к качеству кода отношусь.

Здравствуйте, eao197, Вы писали:

E>Здравствуйте, minorlogic, Вы писали:

E>>>т.е., наличие настолько эффективного кода, который уже бесполезно вылизывать.

M>>Нет не безполезно , там было куда вылизывать , но было видно : "разработчики знали, что это узкое место".

E>Но ведь затраты на оптимизацию достаточно хорошего кода не окупились бы, т.е. код был достаточно хорош. Что уже не мало.
E>Почему-то по ходу дискуссии здесь подразумевается, что все сразу пишут совершенный код, который дальнейшей оптимизации уже не поддается. Поэтому единственный способ дальнейшей оптимизации -- это смена алгоритма. А вот у меня другой опыт. Лично мне профайлер частенько показывает места, в которых я просто-напросто лопухнулся. И переписывание десяти-пятнадцати наиболее критичных для производительности методов поднимало производительность на порядок. Без смены основного алгоритма. И это при том, что я довольно ревносно к качеству кода отношусь.

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

Здравствуйте, McSeem2, Вы писали:

MS>"Выжимание скорости" бывает разым. Вот простейшая иллюстрация — надо удалить все пробелы из Сишной строки.
MS>Реализация раз, индуссого типа:
MS>

MS>for(i = 0; i < strlen(str); i++)
MS>{
MS>   if(str[i] == ' ') { strcpy(str + i, str + i + 1); i--; }
MS>}
MS>

Индус — гений. Такое придумать жутко умная голова нужна.
MS>Знаешь, какова сложность данного цикла? O(N^3).
Учитывая особенности функции strcpy — меньше. Правда картины не меняет. Но все равно круто.

С уважением, Gleb.

Здравствуйте, Sinclair, Вы писали:

S>Гм. Я, может быть, страшно туплю, но этот кэш вообще будет не очень применим. В том смысле, что следующая показанная страница, скорее всего будет содержать другой HTML. И для него придется решать задачу планаризации заново и с нуля. А ситуация типа "если мы смотрим гарантированно тот же контент с гарантированно тем же CSS" — имхо конь в вакууме.

мне все-таки кажется, что предаврительно обработанные части CSS можно использовать повторно. Хотя я могу и ошибаться

S>Ну? Так тебя вроде бы в этом и убеждают. Что рендеринг HTML c учетом CSS — дорогая задача.

согласен, что сложная. Может быть даже действительно O(N*M*D), если взять относительно небольшой документ и большую и сложную таблицу стилей. Но это только как частный случай.

Здравствуйте, gwg-605, Вы писали:

Это что-то новое. Вы хотели сказать: "кадры решают все"?

Здравствуйте, GlebZ, Вы писали:

GZ>Здравствуйте, McSeem2, Вы писали:

MS>>"Выжимание скорости" бывает разым. Вот простейшая иллюстрация — надо удалить все пробелы из Сишной строки.
MS>>Реализация раз, индуссого типа:
MS>>

MS>>for(i = 0; i < strlen(str); i++)
MS>>{
MS>>   if(str[i] == ' ') { strcpy(str + i, str + i + 1); i--; }
MS>>}
MS>>

GZ>Индус — гений. Такое придумать жутко умная голова нужна.
MS>>Знаешь, какова сложность данного цикла? O(N^3).
GZ>Учитывая особенности функции strcpy — меньше. Правда картины не меняет. Но все равно круто.

GZ>С уважением, Gleb.

ну можно и за N это сделать и без дополнительной памяти даже, указателей прикрутить, хорошенько скрыть смысл и устроить утечку памяти, чтоб боялись. А какой-нибудь библиотечной или,упаси бог,стандартной функцией пользоваться это не по-нашему

Здравствуйте, Дарней, Вы писали:
Д>согласен, что сложная. Может быть даже действительно O(N*M*D), если взять относительно небольшой документ и большую и сложную таблицу стилей. Но это только как частный случай.
Относительно небольшой документ — это всего лишь малое N. Несложный документ — небольшое D. Сложная таблица стилей — это большое M.
Понятно, что глядя в документ мы можем сказать, что для многих элементов применяется ровно один и тот же набор стилей. Я имею в виду — глядя глазами. Построить алгоритм, который сможет этим воспользоваться, в целях перехода напрмер от O(n*m*d) к хотя бы O(log(n)*m*d) — весьма нетривиальная задача.

Здравствуйте, GlebZ, Вы писали:

GZ>Индус — гений. Такое придумать жутко умная голова нужна.

Нет, Глеб. Это нормальный код, который напишет любой начинающий программист. Он уже понял, как писать программы и работать со строками. И если забыть про эффективность — в этом коде ничего плохого нет. Он, кстати, понятнее и логичнее.

Здравствуйте, eao197, Вы писали:

E>Может измениться. Вот у меня был случай -- в одном месте, которое вызывалось слишком часто, было два обращения к new. В многопоточном приложении, где каждый new -- это очень дорого. Я переписал это место так, что new вызывался только один раз. В результате большой кусок кода заработал в два раза быстрее и перестал быть узким местом. Еще больших результатов можно было бы достичь, конечно, изменением алгоритма (там даже не алгоритм а целая идеология бы поменялась), но затраты на такие изменения алгоритма были бы не соизмеримы с полученным выигрышем, а сложность решения серьезно бы увеличилась.

E>Так что элементарную эффективность на уровне кода так же нельзя сбрасывать со счетов.
Со временем это работает на автомате.

Здравствуйте, McSeem2, Вы писали:

MS>Строить ввысь — это как раз и есть возводить здание из надежых и эффективных конструкций, устроенное примерно как цепочка неопровержимых математических доказательств. Это то, к чему я и стремлюсь (но основная доля моей работы — это пока что рутина, тем не менее).



Очень хорошая мысль.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, GlebZ, Вы писали:

GZ>>Индус — гений. Такое придумать жутко умная голова нужна.

PD>Нет, Глеб. Это нормальный код, который напишет любой начинающий программист. Он уже понял, как писать программы и работать со строками. И если забыть про эффективность — в этом коде ничего плохого нет. Он, кстати, понятнее и логичнее.
Maybe. Я чаще встречаюсь с незнанием подобных функций. И в очень извращенной форме. Благодаря плюсикам и минусикам получается такой ребус, что распутав его и поняв что-же здесь делается, чувствуешь себя героем.

С уважением, Gleb.
ЗЫ Какой негодяй написал что while(*p++==*p1++); нормальный способ копирования строки(хотя знаю кто , но IMHO — это ошибка)? А самое главное сказал что это нормально.