Господа, а не кажется ли вам, что их больше нет вообще ?
Поясню свою мысль.
Классические структуры прямого доступа — файл и массив.
Файл в раннедосовские времена (когда еще кэша не было) — безусловно структура прямого доступа. Да, для доступа к кластеру нужно просмотреть элементы FAT, но поскольку этих элементов на порядки меньше, чем число байтов в файле, то этим можно пренебречь, равно как и тем, что головка должна совершать различные перемещения — в среднем будет примерно одинаково. В остальном же время доступа к любому кластеру (а значит, и байту) не зависит от его номера в файле.
Но даже в те раннедосовские времена это было верно, пока не использовали stdio с ее буферизацией. С буферизацией — уже неверно, последовательное чтение намного быстрее произвольного. Ну а в наши времена, когда между моим запросом и файлом на диске сидит несколько кешей, это вообще неверно.
Массив. Опять же в раннедосовсеие времена скорость доступа не зависит от того, в каком порядке выбираем элементы. RAM, одним словом. Но и RAM у нас тоже больше нет, по крайней мере напрямую мы к ней не обращаемся. Есть несколько уровней кеша, да еще и подкачка, чего доброго, а они все хорошо работают при последовательном доступе и гораздо хуже при прямом.
Резюме : когда мы используем алгоритмы, требующие прямого доступа, надо отдавать себе отчет, что мы имеем дело фактически с компьютером, намного более медленным, чем мы считаем. Иными словами, если мы думаем, что со времен ДОС скорость работы машины увеличилась в N раз (я не обсуждаю многоядерность и многопоточность), то реально она увеличилась лишь в N/K раз.
А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Резюме : когда мы используем алгоритмы, требующие прямого доступа, надо отдавать себе отчет, что мы имеем дело фактически с компьютером, намного более медленным, чем мы считаем. Иными словами, если мы думаем, что со времен ДОС скорость работы машины увеличилась в N раз (я не обсуждаю многоядерность и многопоточность), то реально она увеличилась лишь в N/K раз.
Не понял, что за N, что за K и что такое скорость работы машины. Только у одной памяти куча параметров, каждый из которых увеличился (улучшился) в разы. В десяток увеличилась частота процессора, но процессор стал выполнять дофига инструкций за такт. Даже если не брать в расчет кэши, непонятно, на что ориентироваться что бы оценить разы. Потому используются бенчмарки.
PD>А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
Конечно означает. На практике видел ускорение от 40 до 250и раз на разных задачах. 250 — это была синтетика для демонстрации. 40 — из реальной жизни при работе с большими медицинскими снимками (до 40Мб). Что за задача — уже не помню. То ли транспонирование, то ли свертка (давно уже было).
PD>А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
Кстати, никто не в курсе — после бани принято говорить с легким паром, а что принято говорить после разморозки?
Здравствуйте, dilmah, Вы писали:
D>Кстати, никто не в курсе — после бани принято говорить с легким паром, а что принято говорить после разморозки?
Поздравить надо человека, налить и опрокинуть!
Я вот не могу сказать что сам дошел. Мне в свое время показали на моем же коде. Пребывал с отпавшей челюстью как на асфальте в лыжи обутый.
Здравствуйте, samius, Вы писали:
PD>>А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ? S>Конечно означает. На практике видел ускорение от 40 до 250и раз на разных задачах. 250 — это была синтетика для демонстрации. 40 — из реальной жизни при работе с большими медицинскими снимками (до 40Мб). Что за задача — уже не помню. То ли транспонирование, то ли свертка (давно уже было).
Тогда вопрос — что на этот счет есть ? Конкретно — какие-то теоретические или практические разработки на предмет этого самого преобразования алгоритмов ? В сущности, именно об этом и был мой постинг.
Вот по той ссылке, что я привел, как раз и изложено такое преобразование для этой узкой задачи. Человек нашел опытным путем. А что-то более фундаментальное есть ?
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Вот по той ссылке, что я привел, как раз и изложено такое преобразование для этой узкой задачи. Человек нашел опытным путем. А что-то более фундаментальное есть ?
короче, вы говорите про специфические алгоритмы расчитанные на гетерогенную (разногородную) память. судя по таким вещам как C++ AMP крупнейшие компании вообще слабо понимают что это такое, пытаясь оградить мозг человека от такого понятия. Однако если брать высокопроизводительные штуки, то вагон алгоритмов ориентированные на гетерогенную память создается в области GPGPU. они, конечно, все самопальные и литература по ним достаточно смешная и отсталая, но можете копнуть в эту область. в области классического программирования все двигается скорее в сторону какого-нить Питона или прочей шняги
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Навеяно вот этим сообщением
PD>Файл в раннедосовские времена (когда еще кэша не было) — безусловно структура прямого доступа.
последовательное чтение даже в дос было сильно быстрее произвольного без всяких кэшей как на дискетах, так и на винтах.
PD>Массив. Опять же в раннедосовсеие времена скорость доступа PD>не зависит от того, в каком порядке выбираем элементы. RAM, одним словом.
у RAM даже в дос цикл пакетного обмена никогда не состоял из одного байта. ну оооочень давно пересылали строку и стробец каждый раз. а потом поставили защелки исходя из предположения, что данные последовательно читаются чаще чем вразброс.
как раз в древние времена вычисления выполнялись на регистрах, а оперативная память была своеобразным "кэшем" долговременной памяти на лентах, т.к. оперативной памяти было несоизмеримо меньше, чем требовалось для обработки данных. в том же дос были оверлеи -- подгружаемые куски кода, ибо весь код в память тоже упорно не желал вмещаться.
PD>Резюме : когда мы используем алгоритмы, требующие прямого доступа, PD>надо отдавать себе отчет, что мы имеем дело фактически с компьютером, PD>намного более медленным, чем мы считаем. Иными словами, если мы думаем,
на одном из собеседований я обосновал, что сложность разворота списка на си порядка O(N log N) именно в силу того, что элементы списка хаотично разбросаны по памяти и этой памяти у нас намного больше, чем кэша. конечно, N log N взято с "потолка", ибо зависит и от железа и от операционки, но если их писали не полные идиоты, то где-то так и будет.
именно поэтому имеет смысл организовать гибридный список, состоящий из "чанков" -- массивов, объединенных в список. пусть размер массива не больше размера минимальной порции пересылки данных ПАМЯТЬ <--> ЦП (порядка 2 ~ 8 Кб) и влезает в кэш первого уровня. тогда вставка/удаление/обход элементов одного чанка происходят на форсаже, практически со скоростью последовательного доступа, даже если они внутри чанка сильно фрагментированы. а фрагментация самого списка -- не влияет на результат, т.к. произвольное чтение чанков не сильно медленнее последовательного (при правильно подобранном размере чанка, конечно, но размер может быть адаптивным, т.к. он инкапсулирован).
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
Ты не поверишь, но этим озаботились, как только у процессоров появились кэши.
Гугли по терминам cache-aware и cache-oblivious.
Вот работа 1999 года, например, на нее много кто ссылается: http://supertech.csail.mit.edu/papers/Prokop99.pdf
Более того, еще в досовские и до-досовские времена были оверлеи и прочая внешняя память, и народ думал про алгоритмы обработки данных, которые не влезают целиком в оперативную память — сейчас просто добавилось уровней этой самой памяти, а проблематика не поменялась — все данные по-прежнему в кэш L1 не запихнешь.
И структуры данных, специально заточенные под работу с кэшами, тоже есть, те же хэш-таблицы, например. http://crpit.com/confpapers/CRPITV91Askitis.pdf (Askitis вообще давно эту тему разрабатывает)
Спасибо за ссылки.
J>Более того, еще в досовские и до-досовские времена были оверлеи и прочая внешняя память, и народ думал про алгоритмы обработки данных, которые не влезают целиком в оперативную память — сейчас просто добавилось уровней этой самой памяти, а проблематика не поменялась — все данные по-прежнему в кэш L1 не запихнешь.
J>И структуры данных, специально заточенные под работу с кэшами, тоже есть, те же хэш-таблицы, например. J>http://crpit.com/confpapers/CRPITV91Askitis.pdf (Askitis вообще давно эту тему разрабатывает)
Ну хеш-таблицы ладно...
Если это так, то насколько современные стандартные библиотеки учитывают это ?
Взять тот же бинарный поиск в массиве. Можно ли утверждать, что он по-прежнему является наиболее эффективным алгоритмом поиска в массиве, даже с учетом того, что он в плане работы с кешем идет "поперек шерсти" ? Или же существует некий более эффективный алгоритм поиска, который , формально в чем-то проигрывая бинарному поиску (в предположении равной скорости доступа к любому элементу), реально выигрывает именно за счет эффектов кэша ?
Проще говоря, не используем ли мы до сих пор по инерции не самый эффективные алгоритмы ?
Здравствуйте, __kot2, Вы писали:
__>короче, вы говорите про специфические алгоритмы расчитанные на гетерогенную (разногородную) память.
Нет. Со специфическими как раз более или менее в принципе ясно, на то они и специфические, чтобы их исследовать. А я имею в виду самые общеприменительные алгоритмы, для которых мы давно и хорошо знаем их t = f(N), только вот при этом неявно исходим из того, что доступ к любому элементу требует одно и то же время.А если это не так, не следует ли пересмотреть наши представления ? А то и некоторые библиотеки переписать ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Взять тот же бинарный поиск в массиве. Можно ли утверждать, что он по-прежнему является наиболее эффективным алгоритмом поиска в массиве, даже с учетом того, что он в плане работы с кешем идет "поперек шерсти" ? Или же существует некий более эффективный алгоритм поиска, который , формально в чем-то проигрывая бинарному поиску (в предположении равной скорости доступа к любому элементу), реально выигрывает именно за счет эффектов кэша ?
PD>Проще говоря, не используем ли мы до сих пор по инерции не самый эффективные алгоритмы ?
Локальность того же бинарного поиска можно неплохо улучшить, разбив массив на мелкие участки, и заранее скопировав элементы, через которые ты будешь проходить в процессе поиска (а их не так много), в отдельный маленький массивчик, и искать сначала в нем — все будет локально. А потом, когда найден нужный мелкий участок, прогнать на нем обычный бинарный поиск — он и так уже будет достаточно локальным.
ЗЫ Естественно, это все зависит от того, какого размера массив и какого размера объекты в массиве — если здоровые, то кэш по-любому загадится.
Здравствуйте, Pavel Dvorkin, Вы писали:
... J>>И структуры данных, специально заточенные под работу с кэшами, тоже есть, те же хэш-таблицы, например. PD>Ну хеш-таблицы ладно...
Кэш кэшу рознь.
Вот была задачка. Из обработки изображений. Взять из картинки вертикальную линию и посчитать среднюю яркость.
Но когда ширина изображения равна 2048, то алгоритм работает заметно медленнее,
чем тогда, когда ширина равна 2049.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
PD>Тогда вопрос — что на этот счет есть ? Конкретно — какие-то теоретические или практические разработки на предмет этого самого преобразования алгоритмов ? В сущности, именно об этом и был мой постинг. PD>Вот по той ссылке, что я привел, как раз и изложено такое преобразование для этой узкой задачи. Человек нашел опытным путем. А что-то более фундаментальное есть ?
Вот конкретно модификации для решения узких задач встречаются в достатке. А так что бы руководство, которое бы работало для любых алгоритмов — сильно сомневаюсь. Не попадались, но и не интересовался специально этой областью.
Здравствуйте, мыщъх, Вы писали:
М>на одном из собеседований я обосновал, что сложность разворота списка на си порядка O(N log N) именно в силу того, что элементы списка хаотично разбросаны по памяти и этой памяти у нас намного больше, чем кэша. конечно, N log N взято с "потолка", ибо зависит и от железа и от операционки, но если их писали не полные идиоты, то где-то так и будет.
Это как объяснить собеседующему что 2+2 = 5 или ты всерьез так рассуждаешь ?
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Проще говоря, не используем ли мы до сих пор по инерции не самый эффективные алгоритмы ?
мое мнение что классические реализации алгоритмов типа сортировки используются только для "сортировки пунктов меню"
а если мы хотим скорости, то любой алгоритм добивается всегда до нужной скорости зная специфику задачу. да, можно сделать что-то лучше бинарного поиска. но нужна доп инфа — конкретные числа, как часто ищем, нет ли специфики значений и все остальное за что можно зацепиться. ну и ес-но нафиг бинарный поиск не нужно оптимизировать если задачи сделать быстрее нет
Здравствуйте, minorlogic, Вы писали:
M>Вы наверняка , мы нет (шутка). Этими вопросами занимаются профи , для которых это все азбука.
Профи-то профи, да вот только если эти эффекты должны учитываться в общеупотребительном коде, то и библиотеки соответствующие должны это учитывать. Вот тут jazzer упомянул про вариацию бинарного поиска. Это в библиотеках общего назначения есть ?
Подчеркиваю — речь идет о библиотеках общего пользования, а не о чем-то узкоспециализированном.
Здравствуйте, __kot2, Вы писали:
__>мое мнение что классические реализации алгоритмов типа сортировки используются только для "сортировки пунктов меню"
А какие используются ? Большинство просто возьмет какую-нибудь библиотечную функцию (метод) и все...
__>а если мы хотим скорости, то любой алгоритм добивается всегда до нужной скорости зная специфику задачу.
С этим не могу не согласиться, но вот какой нюанс. Оптимизировать скорее всего будут собственный код, а вот что касается библиотечных вызовов... Положа руку на сердце — будешь писать свой поиск или свою сортировку даже если тебе надо во что бы то ни стало увеличить скорость ? Сомневаюсь. Да и писать ее (с учетом темы треда) не так уж легко — тут надо досконально работу всех этих кешей знать.
>а, можно сделать что-то лучше бинарного поиска. но нужна доп инфа — конкретные числа, как часто ищем, нет ли специфики значений и все остальное за что можно зацепиться. ну и ес-но нафиг бинарный поиск не нужно оптимизировать если задачи сделать быстрее нет
Это уже другой вопрос — надо или не надо, не буду сейчас обсуждать.
