Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
Ты не поверишь, но этим озаботились, как только у процессоров появились кэши.
Гугли по терминам cache-aware и cache-oblivious.
Вот работа 1999 года, например, на нее много кто ссылается: http://supertech.csail.mit.edu/papers/Prokop99.pdf
Более того, еще в досовские и до-досовские времена были оверлеи и прочая внешняя память, и народ думал про алгоритмы обработки данных, которые не влезают целиком в оперативную память — сейчас просто добавилось уровней этой самой памяти, а проблематика не поменялась — все данные по-прежнему в кэш L1 не запихнешь.
И структуры данных, специально заточенные под работу с кэшами, тоже есть, те же хэш-таблицы, например. http://crpit.com/confpapers/CRPITV91Askitis.pdf (Askitis вообще давно эту тему разрабатывает)
Господа, а не кажется ли вам, что их больше нет вообще ?
Поясню свою мысль.
Классические структуры прямого доступа — файл и массив.
Файл в раннедосовские времена (когда еще кэша не было) — безусловно структура прямого доступа. Да, для доступа к кластеру нужно просмотреть элементы FAT, но поскольку этих элементов на порядки меньше, чем число байтов в файле, то этим можно пренебречь, равно как и тем, что головка должна совершать различные перемещения — в среднем будет примерно одинаково. В остальном же время доступа к любому кластеру (а значит, и байту) не зависит от его номера в файле.
Но даже в те раннедосовские времена это было верно, пока не использовали stdio с ее буферизацией. С буферизацией — уже неверно, последовательное чтение намного быстрее произвольного. Ну а в наши времена, когда между моим запросом и файлом на диске сидит несколько кешей, это вообще неверно.
Массив. Опять же в раннедосовсеие времена скорость доступа не зависит от того, в каком порядке выбираем элементы. RAM, одним словом. Но и RAM у нас тоже больше нет, по крайней мере напрямую мы к ней не обращаемся. Есть несколько уровней кеша, да еще и подкачка, чего доброго, а они все хорошо работают при последовательном доступе и гораздо хуже при прямом.
Резюме : когда мы используем алгоритмы, требующие прямого доступа, надо отдавать себе отчет, что мы имеем дело фактически с компьютером, намного более медленным, чем мы считаем. Иными словами, если мы думаем, что со времен ДОС скорость работы машины увеличилась в N раз (я не обсуждаю многоядерность и многопоточность), то реально она увеличилась лишь в N/K раз.
А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
Здравствуйте, Pavel Dvorkin, Вы писали:
__>>я в Микрософте работаю, если чо PD>Так спроси разработчиков, если это возможно
Мне это напомнило вопрос, который задал сын моего знакомого после очередного посещения фитнеса (а он любитель покачаться): "пап, а ты качков там видел?"
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
PD>А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
Кстати, никто не в курсе — после бани принято говорить с легким паром, а что принято говорить после разморозки?
Здравствуйте, Pavel Dvorkin, Вы писали: PD>От того, насколько эффективно реализована банальная strcpy (конечно, для примера), зависит скорость программ на С++ и C#, Java и Python, Windows и Linux и всех их приложений, потому что все эти системы в конечном счете вызывают библиотеки нативного кода.
у меня ощущение такое что вы оптимизацией никогда не занимались. на самом деле если strcpy станет в разы тормознее этого просто никто не заметит. то, что ее оптимизировали — молодцы, но в тех областях где скорость важна можно испоганить множество ф-ий и все равно никто ничего не заметит. посколько специфика реализации быстрых алгоритмов такова, что там все операции чтения-записи в память, кэш и прочее контролируются ручками.
PD>Ему-то ладно, а вот этот самый код, реализующий sql запрос, сам по себе оптимизирован в вышеуказанном смысле ? В SQL порой создаются структуры совсем не маленького размера. Может быть, конечный пользователь, оптимизирующий sql запрос (в смысле sql) и не догадывается, что этот sql мог бы работать в несколько раз быстрее без всякой оптимизации на уровне sql, если бы был написан более эффективно на уровне реализации sql ? На уровне strcpy
это ковыряние из носа. самая лучшая оптимизация это алгоримическая оптимизация. часто новички берут хреновый алгоритм, а потом пытаются там что-то оптимизировать в его выполнении. там 10% взять, там 5%. это просто не стоит затрат временных. борьба за финальные пару процентов идет только когда уже никаких вариантов больше нет. проблемы в произсодительности берутся не из-за того, что там strcpy тормозит, а в веб приложениях это, например, то, что выполняется куча мелких и к тому же излишних часто запросов вместо одного большого. в многопоточных приложениях провалы в работе часто результат кривой реализации синхронизации потоков и т.д.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Резюме : когда мы используем алгоритмы, требующие прямого доступа, надо отдавать себе отчет, что мы имеем дело фактически с компьютером, намного более медленным, чем мы считаем. Иными словами, если мы думаем, что со времен ДОС скорость работы машины увеличилась в N раз (я не обсуждаю многоядерность и многопоточность), то реально она увеличилась лишь в N/K раз.
А ничего, что в кэш второго уровня одного современного ядра поместится несколько раз по 640kb (тех самых, которых во времена ДОС хватало на всё)?
PD>А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
Поздравляю с разморозкой. Это и так всегда делается. Этому в школе учат, классе эдак в первом. Даже любой студент-двоечник знает, как адаптировать алгоритмы под особенности кэшей.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Взять тот же бинарный поиск в массиве. Можно ли утверждать, что он по-прежнему является наиболее эффективным алгоритмом поиска в массиве, даже с учетом того, что он в плане работы с кешем идет "поперек шерсти" ? Или же существует некий более эффективный алгоритм поиска, который , формально в чем-то проигрывая бинарному поиску (в предположении равной скорости доступа к любому элементу), реально выигрывает именно за счет эффектов кэша ?
PD>Проще говоря, не используем ли мы до сих пор по инерции не самый эффективные алгоритмы ?
Локальность того же бинарного поиска можно неплохо улучшить, разбив массив на мелкие участки, и заранее скопировав элементы, через которые ты будешь проходить в процессе поиска (а их не так много), в отдельный маленький массивчик, и искать сначала в нем — все будет локально. А потом, когда найден нужный мелкий участок, прогнать на нем обычный бинарный поиск — он и так уже будет достаточно локальным.
ЗЫ Естественно, это все зависит от того, какого размера массив и какого размера объекты в массиве — если здоровые, то кэш по-любому загадится.
Здравствуйте, Pavel Dvorkin, Вы писали: __>>мое мнение что классические реализации алгоритмов типа сортировки используются только для "сортировки пунктов меню" PD>А какие используются ? Большинство просто возьмет какую-нибудь библиотечную функцию (метод) и все...
есть такие области, где на алгоритмах все и строится. например, софт для навигатора
да, можно использовать какую-нить библиотечную ф-ию для работы с графами — поиском там, и прочим. но в итоге все равно придется ее выкинуть и прямо ручками все, ручками, с учетом специфики
PD>С этим не могу не согласиться, но вот какой нюанс. Оптимизировать скорее всего будут собственный код, а вот что касается библиотечных вызовов... Положа руку на сердце — будешь писать свой поиск или свою сортировку даже если тебе надо во что бы то ни стало увеличить скорость ? Сомневаюсь. Да и писать ее (с учетом темы треда) не так уж легко — тут надо досконально работу всех этих кешей знать.
я много раз так делал. ну это чисто из-за специфики задач. в каком-нибудь там веб-магазине программист может вообще не подозревать как работает сортировка
>>а, можно сделать что-то лучше бинарного поиска. но нужна доп инфа — конкретные числа, как часто ищем, нет ли специфики значений и все остальное за что можно зацепиться. ну и ес-но нафиг бинарный поиск не нужно оптимизировать если задачи сделать быстрее нет PD>Это уже другой вопрос — надо или не надо, не буду сейчас обсуждать.
есть такие области, когда "весь мир подождет". типа там, бухгатерского софта или сайта, который может по 10 секунд каждое окошко открывать.
есть такие области, где тормознутость делает приложение полностью бесполезным — например, игры. 5 фпс играть ты не будешь. или там, драйвера, DSP
есть области, где что-то считается сутками, а можно немного подумать и сделать, чтобы считалось за час. антивирусы, какие-нить архивирование бэкапов, кодирование видео-аудио, научный софт
95% задач сейчас относятся к первой области. вторая область традиционно считается нищебродской или на любителя, третья вообще мизерная, хотя и является самой тру с точки зрения программирования.
с 90% вероятностью человек идет в веб, а, значит, под словом оптимизация он понимает "sql оптимизация" и алгоритмы знать ему так же бесполезно, как функан обычному программисту. ему сто лет не нужно ничего писать, только использовать библиотечные ф-ии от греха подальше.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>ArrayList при своем росте, требует периодической полной реаллокации, что ведет к инвалидации данных кеша.
Переаллокация по алгоритму с арифметической прогрессией намного лучше для кеша, чем размазанный по памяти связный список.
PD> Кроме того, если в нем не 5-10 элементов, эта переаллокация на нижнем уровне может привести к выделению новых страниц памяти
При 5-10 элементах никакой переаллокации не происходит — у него есть минимальный размер (обычно 16 элементов) сразу при создании.
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
PD>>>>Во-первых, нетрудно сообразить, что коль в качестве примера приведена strcpy, то речь идет не о яве и дотнете AVK>>>Да? Твоя цитата: AVK>>>
AVK>>>От того, насколько эффективно реализована банальная strcpy (конечно, для примера), зависит скорость программ на С++ и C#, Java
PD>>Моя, конечно. И вот еще моя. Ты ее почему-то убрал. А зря. Потому что именно она и поясняет мою мысль.
AVK>Ты сперва определись, шла речь о джаве и шарпе, или не шла.
Ну что же, придется, видимо, мне и впрямь взять на себя роль КО. Потому что эти О для тебя , оказывается, вовсе и не О...
O#1. strcpy есть фигура речи, естественно, имеется в виду код нативных библиотек в целом
O#2. Нативный код выполняется не только в чисто нативных приложениях, но и в ненативных тоже.
O#3. Более того, управляемые приложения в значительной степени исполняют ненативный код. Более того, если речь идет о GUI, то львиная доля — ненативный код, исполняемый как в 3 кольце, так и в ядре.
O#4 (вывод) Поэтому от того, насколько эффективно реализованы библиотеки нативного кода , зависит эффективность нативного приложения.
PD>>И наконец, в пятых, хоть ява, хоть дотнет программа исполняет большое количество нативного кода если не прямо, так косвенно.
AVK>А как же тогда: AVK>
AVK>нетрудно сообразить, что коль в качестве примера приведена strcpy, то речь идет не о яве и дотнете
А очень просто. Речь идет о нативном коде поддержки java и дотнет, то есть о коде, который в приложениях , написанных на яве и дотнете (а также питоне, бейсике и т.д.) исполняется, хотя и не является собственно результатом компиляции с явы или с#.
Нетрудно было понять, но ты не захотел.
AVK>Да, к страшным методам — не ведусь на твою лапшу.
Более серьезные аргументы, видимо, отсутствуют.
AVK>>>Это не то. RAW разделы это древний артефакт для совместимости. Но и файл БД открывается с флажком, запрещающим кеширование. PD>>Открытие файлов без кеширования — вещь вполне банальная, флаг в CreateFile.
AVK>Спасибо, КО.
Всегда пожалуйста
PD>> Только вот при чем тут учет структуры диска ?
AVK>При том что кеширование отключается как раз для того, чтобы сам сиквел содержит более качественные и специализированные алгоритмы ускорения доступа к диску. В том числе и свой собственный кеш страниц.
Спасибо. Я бы сам никогда не догадался
PD>>А если через драйвер, то учитывать структуру диска будет он, а не мы
AVK>В винде есть способы узнать физическую структуру диска даже через драйвер ФС.
Несомненно. Только не физическую структуру диска, а структуру файловой системы. За физической структурой диска надо к драйверу HDD обращаться.
PD>>, так как влиять на размещение файла при живом драйвере не получится — это его обязанности.
AVK>Влиять может и не получится, а вот учитывать — запросто.
PD>>Да вполне угодила, что тут особенного, банальность.
AVK>Так и вопросы у тебя более чем банальные. Ты внезапно осознал вполне очевидные вещи — линейный доступ к памяти и, особенно, к диску быстрее, чем случайный. И теперь, судя по всему, считаешь что сделал открытие.
Не понял ты. То, что быстрее, я осознал лет 15 назад. А вот то, что системные библиотеки (в большинстве своем) по-прежнему этот фактор игнорируют и работают как если бы мы все еще имели RAM — вот это да.
PD>> Но я же не об этом говорил, а о скорости доступа как к структурам прямого доступа. В памяти. Код то есть самого sql парсера и его структур даных.
AVK>В чем принципиальная разница? Проблемы то те же самые. Про код парсера (а точнее оптимизатора, парсер никого давно уже не колышет) сиквела тебе тут вряд ли кто что скажет, это один из самых охраняемых секретовв mssql. Но предположить, что те люди, которые этот код писали, были не в курсе особенностей доступа к памяти, ну это надо быть совсем незамутненным.
А я где-то предположил ? Можно такое упоминание ? Наоборот, я написал
PD>Наверное, можно при этом отключить и кеширование, тем более, что авторы его из MS, а значит, все могут
Здравствуйте, Sinclair, Вы писали:
S>Павел, ты вот сейчас троллишь, или это конец света наступил? Все эти "секретные новости" были хорошо известны ещё во времена Delphi 2.
Антон, постарайся понять, о чем я говорю. Не о каких-то секретах, хорошо известных уже 15 лет или более, а о том, что библиотеки для самых массовых действий по-прежнему в значительной степени эти "секреты" игнорируют.
Здравствуйте, 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, Вы писали:
... J>>И структуры данных, специально заточенные под работу с кэшами, тоже есть, те же хэш-таблицы, например. PD>Ну хеш-таблицы ладно...
Кэш кэшу рознь.
Вот была задачка. Из обработки изображений. Взять из картинки вертикальную линию и посчитать среднюю яркость.
Но когда ширина изображения равна 2048, то алгоритм работает заметно медленнее,
чем тогда, когда ширина равна 2049.
Здравствуйте, minorlogic, Вы писали:
M>Вспомнил кононический пример. Это кастомные аллокаторы для STL контейнеров , которые выделяют память большими блоками и улучшают локальность и т.п.
Не из-за этого они делают. Тут просто механизм выделения страницами учитывается, а не кеш.
PD>А очень просто. Речь идет о нативном коде поддержки java и дотнет, то есть о коде, который в приложениях , написанных на яве и дотнете (а также питоне, бейсике и т.д.) исполняется, хотя и не является собственно результатом компиляции с явы или с#.
Ну и что с этим кодом? Его авторы не умеют работать с целевыми системами? Понятно, что это не так. JIT в дотнете и яве как раз сделан так, чтобы генерировать код для целевой платформы.
Тебя волнуют кэши процессора? А с какого перепугу они тебя волнуют? В 99.9999% приложений банальная алгоритмическая оптимизация сделает в разы больше, чем любые попытки попасть в кэш процессора.
И ты не поверишь, в 0.00001% задач, где это действительно надо, люди садятся и пишут код, который попадает в кэш процессора, сам работает с файлами на диске и т.п. Это как раз то, о чем тебе Андрей написал про SQL Server, например:
кеширование отключается как раз для того, чтобы сам сиквел содержит более качественные и специализированные алгоритмы ускорения доступа к диску. В том числе и свой собственный кеш страниц.
ЗЫ. Тут в Erlang VM оптимизируют VM для улучшения работы на многопроцессорных системах. Там учитывается все: кэши процессоров, resource contention, lock-free алгоритмы, memory barriers. Нужно ли это все для VM? Безусловно. И ВНЕЗАПНО программисты, которые ей занимаются, это все знают и используют. Для 99.9999% приложений внутри этой VM знать это банально не нужно.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Резюме : когда мы используем алгоритмы, требующие прямого доступа, надо отдавать себе отчет, что мы имеем дело фактически с компьютером, намного более медленным, чем мы считаем. Иными словами, если мы думаем, что со времен ДОС скорость работы машины увеличилась в N раз (я не обсуждаю многоядерность и многопоточность), то реально она увеличилась лишь в N/K раз.
Не понял, что за N, что за K и что такое скорость работы машины. Только у одной памяти куча параметров, каждый из которых увеличился (улучшился) в разы. В десяток увеличилась частота процессора, но процессор стал выполнять дофига инструкций за такт. Даже если не брать в расчет кэши, непонятно, на что ориентироваться что бы оценить разы. Потому используются бенчмарки.
PD>А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
Конечно означает. На практике видел ускорение от 40 до 250и раз на разных задачах. 250 — это была синтетика для демонстрации. 40 — из реальной жизни при работе с большими медицинскими снимками (до 40Мб). Что за задача — уже не помню. То ли транспонирование, то ли свертка (давно уже было).
Здравствуйте, dilmah, Вы писали:
D>Кстати, никто не в курсе — после бани принято говорить с легким паром, а что принято говорить после разморозки?
Поздравить надо человека, налить и опрокинуть!
Я вот не могу сказать что сам дошел. Мне в свое время показали на моем же коде. Пребывал с отпавшей челюстью как на асфальте в лыжи обутый.
Здравствуйте, samius, Вы писали:
PD>>А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ? S>Конечно означает. На практике видел ускорение от 40 до 250и раз на разных задачах. 250 — это была синтетика для демонстрации. 40 — из реальной жизни при работе с большими медицинскими снимками (до 40Мб). Что за задача — уже не помню. То ли транспонирование, то ли свертка (давно уже было).
Тогда вопрос — что на этот счет есть ? Конкретно — какие-то теоретические или практические разработки на предмет этого самого преобразования алгоритмов ? В сущности, именно об этом и был мой постинг.
Вот по той ссылке, что я привел, как раз и изложено такое преобразование для этой узкой задачи. Человек нашел опытным путем. А что-то более фундаментальное есть ?
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Вот по той ссылке, что я привел, как раз и изложено такое преобразование для этой узкой задачи. Человек нашел опытным путем. А что-то более фундаментальное есть ?
короче, вы говорите про специфические алгоритмы расчитанные на гетерогенную (разногородную) память. судя по таким вещам как C++ AMP крупнейшие компании вообще слабо понимают что это такое, пытаясь оградить мозг человека от такого понятия. Однако если брать высокопроизводительные штуки, то вагон алгоритмов ориентированные на гетерогенную память создается в области GPGPU. они, конечно, все самопальные и литература по ним достаточно смешная и отсталая, но можете копнуть в эту область. в области классического программирования все двигается скорее в сторону какого-нить Питона или прочей шняги
Спасибо за ссылки.
J>Более того, еще в досовские и до-досовские времена были оверлеи и прочая внешняя память, и народ думал про алгоритмы обработки данных, которые не влезают целиком в оперативную память — сейчас просто добавилось уровней этой самой памяти, а проблематика не поменялась — все данные по-прежнему в кэш L1 не запихнешь.
J>И структуры данных, специально заточенные под работу с кэшами, тоже есть, те же хэш-таблицы, например. J>http://crpit.com/confpapers/CRPITV91Askitis.pdf (Askitis вообще давно эту тему разрабатывает)
Ну хеш-таблицы ладно...
Если это так, то насколько современные стандартные библиотеки учитывают это ?
Взять тот же бинарный поиск в массиве. Можно ли утверждать, что он по-прежнему является наиболее эффективным алгоритмом поиска в массиве, даже с учетом того, что он в плане работы с кешем идет "поперек шерсти" ? Или же существует некий более эффективный алгоритм поиска, который , формально в чем-то проигрывая бинарному поиску (в предположении равной скорости доступа к любому элементу), реально выигрывает именно за счет эффектов кэша ?
Проще говоря, не используем ли мы до сих пор по инерции не самый эффективные алгоритмы ?
Здравствуйте, __kot2, Вы писали:
__>короче, вы говорите про специфические алгоритмы расчитанные на гетерогенную (разногородную) память.
Нет. Со специфическими как раз более или менее в принципе ясно, на то они и специфические, чтобы их исследовать. А я имею в виду самые общеприменительные алгоритмы, для которых мы давно и хорошо знаем их t = f(N), только вот при этом неявно исходим из того, что доступ к любому элементу требует одно и то же время.А если это не так, не следует ли пересмотреть наши представления ? А то и некоторые библиотеки переписать ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
PD>Тогда вопрос — что на этот счет есть ? Конкретно — какие-то теоретические или практические разработки на предмет этого самого преобразования алгоритмов ? В сущности, именно об этом и был мой постинг. PD>Вот по той ссылке, что я привел, как раз и изложено такое преобразование для этой узкой задачи. Человек нашел опытным путем. А что-то более фундаментальное есть ?
Вот конкретно модификации для решения узких задач встречаются в достатке. А так что бы руководство, которое бы работало для любых алгоритмов — сильно сомневаюсь. Не попадались, но и не интересовался специально этой областью.
Здравствуйте, мыщъх, Вы писали:
М>на одном из собеседований я обосновал, что сложность разворота списка на си порядка O(N log N) именно в силу того, что элементы списка хаотично разбросаны по памяти и этой памяти у нас намного больше, чем кэша. конечно, N log N взято с "потолка", ибо зависит и от железа и от операционки, но если их писали не полные идиоты, то где-то так и будет.
Это как объяснить собеседующему что 2+2 = 5 или ты всерьез так рассуждаешь ?
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Проще говоря, не используем ли мы до сих пор по инерции не самый эффективные алгоритмы ?
мое мнение что классические реализации алгоритмов типа сортировки используются только для "сортировки пунктов меню"
а если мы хотим скорости, то любой алгоритм добивается всегда до нужной скорости зная специфику задачу. да, можно сделать что-то лучше бинарного поиска. но нужна доп инфа — конкретные числа, как часто ищем, нет ли специфики значений и все остальное за что можно зацепиться. ну и ес-но нафиг бинарный поиск не нужно оптимизировать если задачи сделать быстрее нет
Здравствуйте, minorlogic, Вы писали:
M>Вы наверняка , мы нет (шутка). Этими вопросами занимаются профи , для которых это все азбука.
Профи-то профи, да вот только если эти эффекты должны учитываться в общеупотребительном коде, то и библиотеки соответствующие должны это учитывать. Вот тут jazzer упомянул про вариацию бинарного поиска. Это в библиотеках общего назначения есть ?
Подчеркиваю — речь идет о библиотеках общего пользования, а не о чем-то узкоспециализированном.
Здравствуйте, __kot2, Вы писали:
__>мое мнение что классические реализации алгоритмов типа сортировки используются только для "сортировки пунктов меню"
А какие используются ? Большинство просто возьмет какую-нибудь библиотечную функцию (метод) и все...
__>а если мы хотим скорости, то любой алгоритм добивается всегда до нужной скорости зная специфику задачу.
С этим не могу не согласиться, но вот какой нюанс. Оптимизировать скорее всего будут собственный код, а вот что касается библиотечных вызовов... Положа руку на сердце — будешь писать свой поиск или свою сортировку даже если тебе надо во что бы то ни стало увеличить скорость ? Сомневаюсь. Да и писать ее (с учетом темы треда) не так уж легко — тут надо досконально работу всех этих кешей знать.
>а, можно сделать что-то лучше бинарного поиска. но нужна доп инфа — конкретные числа, как часто ищем, нет ли специфики значений и все остальное за что можно зацепиться. ну и ес-но нафиг бинарный поиск не нужно оптимизировать если задачи сделать быстрее нет
Это уже другой вопрос — надо или не надо, не буду сейчас обсуждать.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, minorlogic, Вы писали:
M>>Вы наверняка , мы нет (шутка). Этими вопросами занимаются профи , для которых это все азбука.
PD>Профи-то профи, да вот только если эти эффекты должны учитываться в общеупотребительном коде, то и библиотеки соответствующие должны это учитывать. Вот тут jazzer упомянул про вариацию бинарного поиска. Это в библиотеках общего назначения есть ? PD>Подчеркиваю — речь идет о библиотеках общего пользования, а не о чем-то узкоспециализированном.
Обязательно есть в библиотеках для которых скорость выполнения сильно важна. Начиная от Intel IPP заканчивая драйверами видеокарты или видеокодеками. С++ STL тоже может быть заточена на целевую платформу.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>С этим не могу не согласиться, но вот какой нюанс. Оптимизировать скорее всего будут собственный код, а вот что касается библиотечных вызовов... Положа руку на сердце — будешь писать свой поиск или свою сортировку даже если тебе надо во что бы то ни стало увеличить скорость ? Сомневаюсь. Да и писать ее (с учетом темы треда) не так уж легко — тут надо досконально работу всех этих кешей знать.
И линейную алгебру переписываешь по 10 раз под специфический случай, если это бутылочное горлышко. Недавно приводимл пример set_intersection переписанный для random_iterator с лучшей асимптотикой.
Здравствуйте, minorlogic, Вы писали:
PD>>Подчеркиваю — речь идет о библиотеках общего пользования, а не о чем-то узкоспециализированном.
M>Обязательно есть в библиотеках для которых скорость выполнения сильно важна. Начиная от Intel IPP заканчивая драйверами видеокарты или видеокодеками. С++ STL тоже может быть заточена на целевую платформу.
Может быть — ненесомненно, все можно заточить. Действительно заточена ? В какой системе ? В чем именно это заключается ?
Здравствуйте, minorlogic, Вы писали:
PD>>С этим не могу не согласиться, но вот какой нюанс. Оптимизировать скорее всего будут собственный код, а вот что касается библиотечных вызовов... Положа руку на сердце — будешь писать свой поиск или свою сортировку даже если тебе надо во что бы то ни стало увеличить скорость ? Сомневаюсь. Да и писать ее (с учетом темы треда) не так уж легко — тут надо досконально работу всех этих кешей знать.
M>И линейную алгебру переписываешь по 10 раз под специфический случай, если это бутылочное горлышко. Недавно приводимл пример set_intersection переписанный для random_iterator с лучшей асимптотикой.
Может быть. Я однажды два дня изгонял из кода квадратный корень. На моей машине он работал довольно быстро, а у заказчика медленно. Не знаю почему. Пришлось заняться аналитическими преобразованиями, чтобы от него вообще избавиться.
Но я же не об этом. Большинство все же доверяет методам стандартной библиотеки. Начни я переписывать сортировку и скажи об этом — сразу начнется про велосипеды. В ней код должен быть оптимизирован.
Здравствуйте, __kot2, Вы писали:
__>да, можно использовать какую-нить библиотечную ф-ию для работы с графами — поиском там, и прочим. но в итоге все равно придется ее выкинуть и прямо ручками все, ручками, с учетом специфики
С графами — пусть так.
__>я много раз так делал. ну это чисто из-за специфики задач. в каком-нибудь там веб-магазине программист может вообще не подозревать как работает сортировка
О чем я и говорю. Берет просто библиотечную функцию и вызывает, в полной уверенности, что лучше и быть не может.
__>есть такие области, когда "весь мир подождет". типа там, бухгатерского софта или сайта, который может по 10 секунд каждое окошко открывать. __>есть такие области, где тормознутость делает приложение полностью бесполезным — например, игры. 5 фпс играть ты не будешь. или там, драйвера, DSP __>есть области, где что-то считается сутками, а можно немного подумать и сделать, чтобы считалось за час. антивирусы, какие-нить архивирование бэкапов, кодирование видео-аудио, научный софт
Вот тут позволю себе отчасти не согласиться.
От того, насколько эффективно реализована банальная strcpy (конечно, для примера), зависит скорость программ на С++ и C#, Java и Python, Windows и Linux и всех их приложений, потому что все эти системы в конечном счете вызывают библиотеки нативного кода. Конечно, не только от strcpy, а вообще от библиотеки нативного кода. Посмотри код strcpy — там высокооптимизированный ассемблерный код, весьма далекий от побайтового копирования. Оптимизировали под учет специфики x86. А вот оптимизировали ли под учет всех этих кешей ? Конечно, strcpy под это, может быть, оптимизировать вовсе и не надо, а надо что-то другое из нативного кода.
Если такое не делалось, то надо признать, чт работаем мы не с тем быстродействием компьютера (процессора , памяти), которое декларируется, а с существенно меньшим.
__>95% задач сейчас относятся к первой области. вторая область традиционно считается нищебродской или на любителя, третья вообще мизерная, хотя и является самой тру с точки зрения программирования. __>с 90% вероятностью человек идет в веб, а, значит, под словом оптимизация он понимает "sql оптимизация" и алгоритмы знать ему так же бесполезно, как функан обычному программисту. ему сто лет не нужно ничего писать, только использовать библиотечные ф-ии от греха подальше.
Ему-то ладно, а вот этот самый код, реализующий sql запрос, сам по себе оптимизирован в вышеуказанном смысле ? В SQL порой создаются структуры совсем не маленького размера. Может быть, конечный пользователь, оптимизирующий sql запрос (в смысле sql) и не догадывается, что этот sql мог бы работать в несколько раз быстрее без всякой оптимизации на уровне sql, если бы был написан более эффективно на уровне реализации sql ? На уровне strcpy
Здравствуйте, AndrewVK, Вы писали:
PD>>Если это так, то насколько современные стандартные библиотеки учитывают это ?
AVK>Учитывают. К примеру, сейчас намного реже используется связный список, и основным типом списка стал array list.
Очень хорошо. Рассмотрим именно этот пример.
ArrayList при своем росте, требует периодической полной реаллокации, что ведет к инвалидации данных кеша. Кроме того, если в нем не 5-10 элементов, эта переаллокация на нижнем уровне может привести к выделению новых страниц памяти, то есть к системному вызову с переходом в режим ядра и связанными с этим затратами. Это как-то учитывается ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>От того, насколько эффективно реализована банальная strcpy (конечно, для примера), зависит скорость программ на С++ и C#, Java
Плохой пример. Во-первых и в джаве и в дотнете строки strcpy не скопируешь, там структура строки немного посложнее. Во-вторых строки там иммутабельные, так что полезность самой операции под большим вопросом — у иммутабельной строки достаточно просто передать тот же указатель, а не копировать ее.
PD>Ему-то ладно, а вот этот самый код, реализующий sql запрос, сам по себе оптимизирован в вышеуказанном смысле ?
И еще как. Конкретно у mssql есть специальные алгоритмы, учитывающие структуру диска, на котором хранятся данные. Он при этом дисковый кеш ОС полностью отключает.
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
Здравствуйте, __kot2, Вы писали:
PD>>От того, насколько эффективно реализована банальная strcpy (конечно, для примера), зависит скорость программ на С++ и C#, Java и Python, Windows и Linux и всех их приложений, потому что все эти системы в конечном счете вызывают библиотеки нативного кода.
__>у меня ощущение такое что вы оптимизацией никогда не занимались.
Ошибочное. Я именно ей и занимался все время.
>на самом деле если strcpy станет в разы тормознее этого просто никто не заметит. то, что ее оптимизировали — молодцы, но в тех областях где скорость важна можно испоганить множество ф-ий и все равно никто ничего не заметит. посколько специфика реализации быстрых алгоритмов такова, что там все операции чтения-записи в память, кэш и прочее контролируются ручками.
strcpy была приведена просто для примера. я об этом писал. А вот насчет того, что можно испоганить те методы, которые лежат в основе базовых компонентов и при этом никто не заметить — сильно сомневаюсь. В каждом конкретном месте , возможно, скажется и не так уж заметно, а вот в итоге очень даже.
__>это ковыряние из носа. самая лучшая оптимизация это алгоримическая оптимизация. часто новички берут хреновый алгоритм, а потом пытаются там что-то оптимизировать в его выполнении. там 10% взять, там 5%. это просто не стоит затрат временных. борьба за финальные пару процентов идет только когда уже никаких вариантов больше нет. проблемы в произсодительности берутся не из-за того, что там strcpy тормозит, а в веб приложениях это, например, то, что выполняется куча мелких и к тому же излишних часто запросов вместо одного большого. в многопоточных приложениях провалы в работе часто результат кривой реализации синхронизации потоков и т.д.
Да никто против алгоритмичесой оптимизации и не возражает, но не о ней же тут я речь завел. Что же касается примера с strcpy, то именно тот факт, что ее высоко оптимизировали, говорит, что ее эффективнсть — совсем не мелочь. Если бы ее эфективность мало на что влияла, зачем бы авторы библиотеки это сделали ?
Здравствуйте, AndrewVK, Вы писали:
PD>>ArrayList при своем росте, требует периодической полной реаллокации, что ведет к инвалидации данных кеша.
AVK>Переаллокация по алгоритму с арифметической прогрессией намного лучше для кеша, чем размазанный по памяти связный список.
Эээ, батенька, не увиливай. Я разве выступал за связный список ? Я совсем другой вопрос задал — как реализация ArrayList учитывает переаллокации, страничные ошибки в их случае и как она оптимизировна на этот счет ?
PD>> Кроме того, если в нем не 5-10 элементов, эта переаллокация на нижнем уровне может привести к выделению новых страниц памяти
AVK>При 5-10 элементах никакой переаллокации не происходит — у него есть минимальный размер (обычно 16 элементов) сразу при создании.
Читай внимательно. Я сказал "если в нем не 5-10 элементов". Именно "не
Здравствуйте, AndrewVK, Вы писали:
PD>>От того, насколько эффективно реализована банальная strcpy (конечно, для примера), зависит скорость программ на С++ и C#, Java
AVK>Плохой пример. Во-первых и в джаве и в дотнете строки strcpy не скопируешь, там структура строки немного посложнее. Во-вторых строки там иммутабельные, так что полезность самой операции под большим вопросом — у иммутабельной строки достаточно просто передать тот же указатель, а не копировать ее.
Во-первых, нетрудно сообразить, что коль в качестве примера приведена strcpy, то речь идет не о яве и дотнете
Во-вторых, случай, когда копируется ссылка, а не содержимое, немного не из той области, и уж никак не может быть аргументом при обсуждении вопроса о кипировании именно содержимого
В-третьих, и в яве, и в дотнете есть копирование блоков памяти. Про System.arraycopy напомнить ?
А в четвертых, скорость работы библиотеки C/C++ весьма влияет на работу приложений Явы и дотнета. Если и не самих приложений, то по крайней мере JIT, который, в сущности, часть приложения, так как без него работать ява-дотнет-программа не может. А он не на Яве-дотнете написан.
И наконец, в пятых, хоть ява, хоть дотнет программа исполняет большое количество нативного кода если не прямо, так косвенно.
AVK>И еще как. Конкретно у mssql есть специальные алгоритмы, учитывающие структуру диска, на котором хранятся данные. Он при этом дисковый кеш ОС полностью отключает.
Не совсем так. Насколько я помню, он просто может работать с raw разделами на диске, создавая там свои "файлы", то есть фактически берет на себя роль, которую играет обычно драйвер ФС. Ничего особенного тут нет, это совсем не сложно сделать, правда, придется писать свой распределитель дискового пространства (фактически свою, мб, очень упрощенную ФС). Наверное, можно при этом отключить и кеширование, тем более, что авторы его из MS, а значит, все могут. . Впрочем, запретить кеширование обычного файла тоже несложно.
Здравствуйте, Pavel Dvorkin, Вы писали:
AVK>>Плохой пример. Во-первых и в джаве и в дотнете строки strcpy не скопируешь, там структура строки немного посложнее. Во-вторых строки там иммутабельные, так что полезность самой операции под большим вопросом — у иммутабельной строки достаточно просто передать тот же указатель, а не копировать ее.
PD>Во-первых, нетрудно сообразить, что коль в качестве примера приведена strcpy, то речь идет не о яве и дотнете
Да? Твоя цитата:
От того, насколько эффективно реализована банальная strcpy (конечно, для примера), зависит скорость программ на С++ и C#, Java
PD>В-третьих, и в яве, и в дотнете есть копирование блоков памяти.
Это не тоже самое, что strcpy. Там блоки копируются в основном большие, от единиц мегабайтов размером, поэтому с неоднородностью доступа к памяти все хорошо.
AVK>>И еще как. Конкретно у mssql есть специальные алгоритмы, учитывающие структуру диска, на котором хранятся данные. Он при этом дисковый кеш ОС полностью отключает. PD>Не совсем так.
Совсем так.
PD> Насколько я помню, он просто может работать с raw разделами на диске
Это не то. RAW разделы это древний артефакт для совместимости. Но и файл БД открывается с флажком, запрещающим кеширование.
PD>Но я же не об этом говорил...
Чем тебе не угодила оптимизация в зависимости от расположения страницы на диске? Там как раз учитывается неоднородность доступа, и специальный алгоритм переупорядочивает чтение и запись страниц, все как ты хотел.
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
Здравствуйте, Pavel Dvorkin, Вы писали:
AVK>>Переаллокация по алгоритму с арифметической прогрессией намного лучше для кеша, чем размазанный по памяти связный список. PD>Эээ, батенька, не увиливай.
Я никуда не увиливаю. Ты спросил про системные библиотеки, я тебе привел пример, когда явно видно влияние неоднородности доступа к ОЗУ.
PD>Я совсем другой вопрос задал — как реализация ArrayList учитывает переаллокации, страничные ошибки в их случае и как она оптимизировна на этот счет ?
Сам выбор array list вместо связанного списка в немалой степени обусловлен как раз тем, что на реальных компьютерах из-за размазанности второго по памяти сильно деградирует производительность.
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
PD>>Во-первых, нетрудно сообразить, что коль в качестве примера приведена strcpy, то речь идет не о яве и дотнете
AVK>Да? Твоя цитата: AVK>
AVK>От того, насколько эффективно реализована банальная strcpy (конечно, для примера), зависит скорость программ на С++ и C#, Java
Моя, конечно. И вот еще моя. Ты ее почему-то убрал. А зря. Потому что именно она и поясняет мою мысль.
PD>А в четвертых, скорость работы библиотеки C/C++ весьма влияет на работу приложений Явы и дотнета. Если и не самих приложений, то по крайней мере JIT, который, в сущности, часть приложения, так как без него работать ява-дотнет-программа не может. А он не на Яве-дотнете написан.
И наконец, в пятых, хоть ява, хоть дотнет программа исполняет большое количество нативного кода если не прямо, так косвенно.
Причем характерный момент. То, что я написал раньше (может, не вполне пояснив свою мысль, впрочем, я надеялся, что меня и так поймут — оказалось, зря) — ты с радостью процитировал. А вот то, что поясняет мою мысль, разжевывает ее, если уж на то пошло, причем не где-нибудь, а именно в том сообщении, на которое ты сейчас отвечаешь — ты просто убрал. Ну как с тобой дискутировать, если ты к таким методам прибегаешь...
PD>>В-третьих, и в яве, и в дотнете есть копирование блоков памяти.
AVK>Это не тоже самое, что strcpy. Там блоки копируются в основном большие, от единиц мегабайтов размером, поэтому с неоднородностью доступа к памяти все хорошо.
Да ну. А как же быть с переаллокацией в ArrayList ? Закажем его на 50 жлементов, и как только нужно добавить 51-й — на тебе, System.arraycopy.
AVK>>>И еще как. Конкретно у mssql есть специальные алгоритмы, учитывающие структуру диска, на котором хранятся данные. Он при этом дисковый кеш ОС полностью отключает. PD>>Не совсем так.
AVK>Совсем так.
PD>> Насколько я помню, он просто может работать с raw разделами на диске
AVK>Это не то. RAW разделы это древний артефакт для совместимости. Но и файл БД открывается с флажком, запрещающим кеширование.
Открытие файлов без кеширования — вещь вполне банальная, флаг в CreateFile. Только вот при чем тут учет структуры диска ? Одно из двух — или мы работает с raw разделами, и тогда, конечно, сами и планируем структуру диска, либо все же через драйвер ФС (а коли уж открываем файл , то через драйвер несомненно, так как иначе пришлось бы открывать раздел как raw). А если через драйвер, то учитывать структуру диска будет он, а не мы, так как влиять на размещение файла при живом драйвере не получится — это его обязанности.
Вот в пределах файла , действительно можно все переупорядочивать как угодно. Однако файл при этом размещать будет все же драйвер...
PD>>Но я же не об этом говорил...
AVK>Чем тебе не угодила оптимизация в зависимости от расположения страницы на диске? Там как раз учитывается неоднородность доступа, и специальный алгоритм переупорядочивает чтение и запись страниц, все как ты хотел.
Да вполне угодила, что тут особенного, банальность. Но я же не об этом говорил, а о скорости доступа как к структурам прямого доступа. В памяти. Код то есть самого sql парсера и его структур даных.
Вот же цитата
PD>что этот sql мог бы работать в несколько раз быстрее без всякой оптимизации на уровне sql, если бы был написан более эффективно на уровне реализации sql ? На уровне strcpy
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>>Во-первых, нетрудно сообразить, что коль в качестве примера приведена strcpy, то речь идет не о яве и дотнете AVK>>Да? Твоя цитата: AVK>>
AVK>>От того, насколько эффективно реализована банальная strcpy (конечно, для примера), зависит скорость программ на С++ и C#, Java
PD>Моя, конечно. И вот еще моя. Ты ее почему-то убрал. А зря. Потому что именно она и поясняет мою мысль.
Ты сперва определись, шла речь о джаве и шарпе, или не шла.
PD>И наконец, в пятых, хоть ява, хоть дотнет программа исполняет большое количество нативного кода если не прямо, так косвенно.
А как же тогда:
нетрудно сообразить, что коль в качестве примера приведена strcpy, то речь идет не о яве и дотнете
PD>Ну как с тобой дискутировать, если ты к таким методам прибегаешь...
Да, к страшным методам — не ведусь на твою лапшу.
AVK>>Это не то. RAW разделы это древний артефакт для совместимости. Но и файл БД открывается с флажком, запрещающим кеширование. PD>Открытие файлов без кеширования — вещь вполне банальная, флаг в CreateFile.
Спасибо, КО.
PD> Только вот при чем тут учет структуры диска ?
При том что кеширование отключается как раз для того, чтобы сам сиквел содержит более качественные и специализированные алгоритмы ускорения доступа к диску. В том числе и свой собственный кеш страниц.
PD>А если через драйвер, то учитывать структуру диска будет он, а не мы
В винде есть способы узнать физическую структуру диска даже через драйвер ФС.
PD>, так как влиять на размещение файла при живом драйвере не получится — это его обязанности.
Влиять может и не получится, а вот учитывать — запросто.
PD>Да вполне угодила, что тут особенного, банальность.
Так и вопросы у тебя более чем банальные. Ты внезапно осознал вполне очевидные вещи — линейный доступ к памяти и, особенно, к диску быстрее, чем случайный. И теперь, судя по всему, считаешь что сделал открытие.
PD> Но я же не об этом говорил, а о скорости доступа как к структурам прямого доступа. В памяти. Код то есть самого sql парсера и его структур даных.
В чем принципиальная разница? Проблемы то те же самые. Про код парсера (а точнее оптимизатора, парсер никого давно уже не колышет) сиквела тебе тут вряд ли кто что скажет, это один из самых охраняемых секретовв mssql. Но предположить, что те люди, которые этот код писали, были не в курсе особенностей доступа к памяти, ну это надо быть совсем незамутненным.
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Что же касается примера с strcpy, то именно тот факт, что ее высоко оптимизировали, говорит, что ее эффективнсть — совсем не мелочь. Если бы ее эфективность мало на что влияла, зачем бы авторы библиотеки это сделали ?
а теперь я вообще соневаюсь, что вы работаете где-то. неужели всегда все что люди делают оно исключительно разумные цели преследует? любая разработка большого проекта напоминает хаотичный бред обычно
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>ArrayList при своем росте, требует периодической полной реаллокации, что ведет к инвалидации данных кеша. Кроме того, если в нем не 5-10 элементов, эта переаллокация на нижнем уровне может привести к выделению новых страниц памяти, то есть к системному вызову с переходом в режим ядра и связанными с этим затратами. Это как-то учитывается ?
Учитывается при помощи свойства Capacity.
Павел, ты вот сейчас троллишь, или это конец света наступил? Все эти "секретные новости" были хорошо известны ещё во времена Delphi 2.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, __kot2, Вы писали:
PD>>Что же касается примера с strcpy, то именно тот факт, что ее высоко оптимизировали, говорит, что ее эффективнсть — совсем не мелочь. Если бы ее эфективность мало на что влияла, зачем бы авторы библиотеки это сделали ? __>а теперь я вообще соневаюсь, что вы работаете где-то. неужели всегда все что люди делают оно исключительно разумные цели преследует? любая разработка большого проекта напоминает хаотичный бред обычно
А вот тут ты глубоко неправ. Разработка программы на заказ — порой да. И то не всегда. Мне довелось участвовать в проекте, который продолжался несколько лет и отнюдь не напоминал хаотичный бред. И задачей моей было именно оптимизировать код.
А вот разработка библиотеки, да не какой-нибудь, а стандартной библиотеки среды программирования, да не какой-нибудь среды программирования, а среды #1 — тот, кто позволит себе хаотичный бред в такой работе, быстро в трубу вылетит.
Так что поищи другой ответ на этот вопрос...
А еще есть Intel C++, который делает более эффективный код, чем VC++.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>а о том, что библиотеки для самых массовых действий по-прежнему в значительной степени эти "секреты" игнорируют.
Докажи
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
Здравствуйте, Pavel Dvorkin, Вы писали: PD>А вот тут ты глубоко неправ. Разработка программы на заказ — порой да. И то не всегда. Мне довелось участвовать в проекте, который продолжался несколько лет и отнюдь не напоминал хаотичный бред. И задачей моей было именно оптимизировать код.
PD>А вот разработка библиотеки, да не какой-нибудь, а стандартной библиотеки среды программирования, да не какой-нибудь среды программирования, а среды #1 — тот, кто позволит себе хаотичный бред в такой работе, быстро в трубу вылетит.
PD>Так что поищи другой ответ на этот вопрос...
я в Микрософте работаю, если чо
Здравствуйте, __kot2, Вы писали:
PD>>А вот разработка библиотеки, да не какой-нибудь, а стандартной библиотеки среды программирования, да не какой-нибудь среды программирования, а среды #1 — тот, кто позволит себе хаотичный бред в такой работе, быстро в трубу вылетит.
PD>>Так что поищи другой ответ на этот вопрос... __>я в Микрософте работаю, если чо
M>Тебя волнуют кэши процессора? А с какого перепугу они тебя волнуют? В 99.9999% приложений банальная алгоритмическая оптимизация сделает в разы больше, чем любые попытки попасть в кэш процессора.
Посмотри мое первое сообщение. Там ссылка на исходный постинг, вызвавший это мое сообщение. В нем обсуждается бинарный поиск и его специфика в связи с кешем. Там именно предложена некая оптимизация, пусть и для частного случая поиска многих, а не одного.
Вот и вопрос — где эта (или подобная) оптимизация в системных библиотеках ?
M>И ты не поверишь, в 0.00001% задач, где это действительно надо, люди садятся и пишут код, который попадает в кэш процессора, сам работает с файлами на диске и т.п. Это как раз то, о чем тебе Андрей написал про SQL Server, например: M>
M>кеширование отключается как раз для того, чтобы сам сиквел содержит более качественные и специализированные алгоритмы ускорения доступа к диску. В том числе и свой собственный кеш страниц.
Вопрос-то тоньше. Люди пишут, верно. Сам писал. Но это свой код. А библиотеки ? Их-то код мало кто переписывает. Вот и получается, что полагаемся на не самый эффективный код... И не только генерируемый JIT и т.д, но и нативный код, принмающий участие в работе процесса на базе .net или java или что угодно.
M>>Тебя волнуют кэши процессора? А с какого перепугу они тебя волнуют? В 99.9999% приложений банальная алгоритмическая оптимизация сделает в разы больше, чем любые попытки попасть в кэш процессора.
PD>Посмотри мое первое сообщение. Там ссылка на исходный постинг, вызвавший это мое сообщение. В нем обсуждается бинарный поиск и его специфика в связи с кешем. Там именно предложена некая оптимизация, пусть и для частного случая поиска многих, а не одного. PD>Вот и вопрос — где эта (или подобная) оптимизация в системных библиотеках ?
Вопрос неправильный. Правильные: Эта оптимизация нужна? Если она нужна, доступны ли библиотеки, где она выполнена? Если библиотеки недоступны, есть ли возможность реализовать это самому?
Ответы:
— Эта оптимизация нужна?
Нет, в 99.99999% приложений она не нужна, потому что алгоритмические оптимизации в разы лучше, чем попытка уложится в кэш процессора
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Кстати, интересный вопрос. Можно как-то узнать, сколько времени в некотором дотнет или ява-приложении исполняется управляемый код и сколько — нативный ? Я имею в виду "чистое" (не астрономическое) время исполнения процесса. Узнать, сколько времени исполняется код ядра и код юзермоде для процесса — никаких проблем, а вот это можно ли узнать ?
А чем при выполнении managed отличается от unmanaged? Например a+b на C# как будет отличаться от a+b на C++? ИМХО никак.
Так что непонятно что ты спросить хочешь.
Можешь просто посчитать время выполнения простых операций в цикле на .NET и на C++ — разница это то что дает именно managed.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Кстати, интересный вопрос. Можно как-то узнать, сколько времени в некотором дотнет или ява-приложении исполняется управляемый код и сколько — нативный ?
Можно. Профайлером.
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, Pavel Dvorkin, Вы писали: G>А чем при выполнении managed отличается от unmanaged? Например a+b на C# как будет отличаться от a+b на C++? ИМХО никак. G>Так что непонятно что ты спросить хочешь.
Может, я не совсем прав, но...
При исполнении управляемого кода имеем
1. Общее время в юзермоде (кернелмоде опустим)
2. Время, потраченное самим JIT — это он измерить вполне мог бы
3. Время от момента входа в некий нативный код до выхода из него — тоже можно бы измерить
O>Поздравляю с разморозкой. Это и так всегда делается. Этому в школе учат, классе эдак в первом. Даже любой студент-двоечник знает, как адаптировать алгоритмы под особенности кэшей.
Ну и расскажи, как? Особенно если кол-во кешей, их размеры и размеры линеек у целевых камней сильно разнятся.
