В сабжевой статье Poul-Henning Kamp показывает, что вроде бы признанный всеми (и описанный Кнутом) алгоритм оказывается далеко не самым оптимальным, потому как сказываются подробности архитектуры современных компьютеров.
Наверное, это не единственный пример?

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

К>В сабжевой статье Poul-Henning Kamp показывает, что вроде бы признанный всеми (и описанный Кнутом) алгоритм оказывается далеко не самым оптимальным, потому как сказываются подробности архитектуры современных компьютеров.
К>Наверное, это не единственный пример?
Конечно не единственный, индексы в БД хранятся в таком виде, именно чтобы уменьшить количество чтений с диска.
Только в БД чтение с диска выполняется явно, а в случае с виртуальной памятью — неявно и размеры страниц, их вытеснение (особенно), итп находится вне контроля приложения.

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

G>Здравствуйте, Курилка, Вы писали:

К>>В сабжевой статье Poul-Henning Kamp показывает, что вроде бы признанный всеми (и описанный Кнутом) алгоритм оказывается далеко не самым оптимальным, потому как сказываются подробности архитектуры современных компьютеров.
К>>Наверное, это не единственный пример?
G>Конечно не единственный, индексы в БД хранятся в таком виде, именно чтобы уменьшить количество чтений с диска.
G>Только в БД чтение с диска выполняется явно, а в случае с виртуальной памятью — неявно и размеры страниц, их вытеснение (особенно), итп находится вне контроля приложения.

Мой вопрос был не про конкретно данный алгоритм/струкутуру данных, а вообще о таких приёмах, которые становятся не совсем эффективными потому как... (см. выше)

К>В сабжевой статье Poul-Henning Kamp показывает, что вроде бы признанный всеми (и описанный Кнутом) алгоритм оказывается далеко не самым оптимальным, потому как сказываются подробности архитектуры современных компьютеров.
К>Наверное, это не единственный пример?

Спасибо, понравилась статья. Комменты там тоже полезные.

К сожалению, на ACM очень много содержимого (в том числе, научных статей) такого качества.

Эта статья просто нелепа своим кретинизмом — это все равно, что сказать, например: посмотрите, я сортирую 100-гигабайтный массив пузырьком и вот я придумал способ, который позволяет лучше использовать виртуальную память. И привести пример какой-нибудь челночной сортировки в качестве "изобретения".

Этот человек разрабатывал ядро FreeBSD?

Мне как-то и в голову не приходило, что кэши таких размеров, которые еще к тому же не влезают в оперативную память, можно делать на бинарном хипе.

Кстати, "You're Doing It Wrong" — просто идеальное название для статьи.

Хотя, может быть, я просто чего-то не знаю?

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

К>Мой вопрос был не про конкретно данный алгоритм/струкутуру данных, а вообще о таких приёмах, которые становятся не совсем эффективными потому как... (см. выше)
Вообще все приёмы, разработанные для баз данных, становятся актуальны для "обычных программ в памяти". По странному стечению обстоятельств "классическая" алгоритмика работает в предположении "изотропной памяти", что в наше время применимо только в пределах линейки кэша или страницы виртуальной памяти. А вот СУБД с самого начала столкнулись с тем, что не весь storage одинаково доступен, в связи с чем и разработали массу решений этой проблемы.

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

S>Здравствуйте, Курилка, Вы писали:

К>>Мой вопрос был не про конкретно данный алгоритм/струкутуру данных, а вообще о таких приёмах, которые становятся не совсем эффективными потому как... (см. выше)
S>Вообще все приёмы, разработанные для баз данных, становятся актуальны для "обычных программ в памяти". По странному стечению обстоятельств "классическая" алгоритмика работает в предположении "изотропной памяти", что в наше время применимо только в пределах линейки кэша или страницы виртуальной памяти. А вот СУБД с самого начала столкнулись с тем, что не весь storage одинаково доступен, в связи с чем и разработали массу решений этой проблемы.

А может есть примеры, касающиеся не только распределения памяти? С ходу в мою голову приходят только проблемы с изменяемым состоянием для многопроцессорной обработки.

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

К>А может есть примеры, касающиеся не только распределения памяти? С ходу в мою голову приходят только проблемы с изменяемым состоянием для многопроцессорной обработки.
Лексеры, например.
"Академические" лексеры обречены быть менее быстрыми, чем могли бы быть. Упирается опять отчасти в память, блочный i/o, и ветвление (кода).

Не статья а детский сад какой-то, ее правильнее было бы назвать "мой первый опыт в использовании алгоритмов на внешней памяти"
Алгоритмы на внешней памяти это отделаная тема которую кнут не рассматривал и пинать его за это — признак глубокого невежества.
Литературы по этой теме маловато, но если кому интересно то можете покопаться в stxxl или поглядеть вот эту книгу http://www.ozon.ru/context/detail/id/1685709/

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

К>В сабжевой статье Poul-Henning Kamp показывает, что вроде бы признанный всеми (и описанный Кнутом) алгоритм оказывается далеко не самым оптимальным, потому как сказываются подробности архитектуры современных компьютеров.

а ты вообще оптимизацией занимаешься? такие примеры сплошь да рядом. например, мне пришлось к большому хешу 32-битных значений, занимающему десятки мегабайт, добавить маленький хеш присутствия, который влезал в l2 cache, и потому делал весь процесс в несколько раз быстрее

кстати, ещё один классический пример — линейное рехеширование vs скачкообразное. какое эффективней? одна из причин быстродействия freearc — замена традиционного в архиваторах скачкообразного рехеширования линейным

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

BZ>кстати, ещё один классический пример — линейное рехеширование vs скачкообразное. какое эффективней? одна из причин быстродействия freearc — замена традиционного в архиваторах скачкообразного рехеширования линейным

Автоцитата из соседнего поста:

А может есть примеры, касающиеся не только распределения памяти? С ходу в мою голову приходят только проблемы с изменяемым состоянием для многопроцессорной обработки.

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

К>Автоцитата из соседнего поста:
К>

К>А может есть примеры, касающиеся не только распределения памяти? С ходу в мою голову приходят только проблемы с изменяемым состоянием для многопроцессорной обработки.

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

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

BZ>почему только с изменяемым состоянием? понятие эффективности алгоритма сейчас меняется — эффективен тот, кого можно распараллелить. а если нельзя, то будь ты хоть семи пядей во лбу — через пару лет проиграешь

Параллелить можно во многих местах, не обязательно сам алгоритм. Очень часто в общей задаче находится место, где параллелизм возникает естественным образом.

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

BZ>Здравствуйте, Курилка, Вы писали:

К>>Автоцитата из соседнего поста:
К>>

К>>А может есть примеры, касающиеся не только распределения памяти? С ходу в мою голову приходят только проблемы с изменяемым состоянием для многопроцессорной обработки.

BZ>почему только с изменяемым состоянием? понятие эффективности алгоритма сейчас меняется — эффективен тот, кого можно распараллелить. а если нельзя, то будь ты хоть семи пядей во лбу — через пару лет проиграешь

Булат, скажи мне, где я написал "только"?

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

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

BZ>>почему только с изменяемым состоянием? понятие эффективности алгоритма сейчас меняется — эффективен тот, кого можно распараллелить. а если нельзя, то будь ты хоть семи пядей во лбу — через пару лет проиграешь

M>Параллелить можно во многих местах, не обязательно сам алгоритм. Очень часто в общей задаче находится место, где параллелизм возникает естественным образом.

эффективен тот метод решения задачи, который можно распараллелить...

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

BZ>эффективен тот метод решения задачи, который можно распараллелить...

Прямо матра какая-то, самогипноз... Зачем параллелить генератор ходов в шахматах, если сверху все равно будет перебор? Зачем параллелить вычисление некоторого критерия (критериев), если все это выполняется внутри генетического алгоритма? Имхо, максимальная производительность будет там, где место параллелизма выбрано с умом. А для этого нужны оптимальные однопоточные реализации.

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

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

BZ>>эффективен тот метод решения задачи, который можно распараллелить...

M>Прямо матра какая-то, самогипноз... Зачем параллелить генератор ходов в шахматах, если сверху все равно будет перебор? Зачем параллелить вычисление некоторого критерия (критериев), если все это выполняется внутри генетического алгоритма? Имхо, максимальная производительность будет там, где место параллелизма выбрано с умом.
http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BA%D0%BE%D0%BD_%D0%90%D0%BC%D0%B4%D0%B0%D0%BB%D0%B0

M>А для этого нужны оптимальные однопоточные реализации.
Можно поподробнее?

Не всегда оптимальные однопоточные программы можно распараллелить.

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

G>Не всегда оптимальные однопоточные программы можно распараллелить.

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

G>Можно поподробнее?

классический пример -- вместо того чтобы дико усложнять код компилятора и делать его многопоточным, паралеллелят на уровне make -jN

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

G>>Можно поподробнее?

D>классический пример -- вместо того чтобы дико усложнять код компилятора и делать его многопоточным, паралеллелят на уровне make -jN

Еще раз

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

Связь между предложениями понять не могу.

Вполне логично что надо параллелить там где легко параллелится и будет наибольший эффект. Но зачем для этого оптимальные однопоточные реализации?