Комментарии 57
очень вкусная статья, спасибо :)
столько трудов вложили, оценил
столько трудов вложили, оценил
Ого. Спасибо за вкусную пищу для ума :) ++ вам в карму.
Спасибо за графики.
Было бы интересно посмотреть как на разных процессорах пройдут тесты :)
Было бы интересно посмотреть как на разных процессорах пройдут тесты :)
очень интересно и видно, что большой труд проделан.
пару вопросов:
а) а такую строку вы из файла брали?
б) считали время выполнения только самого метода? Считали время выполнения за раз или несколько раз проводили тесты?
в) а многопоточность не пробовали как то использовать? Например разбить на два — обработать каждый в своем потоке и потом склеить.
пару вопросов:
а) а такую строку вы из файла брали?
б) считали время выполнения только самого метода? Считали время выполнения за раз или несколько раз проводили тесты?
в) а многопоточность не пробовали как то использовать? Например разбить на два — обработать каждый в своем потоке и потом склеить.
Спасибо за интересную статью.
Всегда было интересно как оно там под капотом работает. Пишите еще.
Всегда было интересно как оно там под капотом работает. Пишите еще.
Полноценное исследование. Некоторые студенты для диплома такого не сделают :)
Присоединяюсь к желанию посмотреть зависимость методов от используемого процессора
Присоединяюсь к желанию посмотреть зависимость методов от используемого процессора
Скорость для ReverseManualHalf упала потому, что дергаются постоянно разные участки памяти. Подготовка данных просто обламывается (готовится один блок, а дергается из другого, идет переподготовка, и опять облом).
Чтобы максимально ускорить копирование, надо копировать несколько байт или (хотя бы) последовательно:
dest[i] = src[j];
dest[i+1] = src[j-1];
dest[i+2] = src[j-2];
dest[i+3] = src[j-3];
Чтобы максимально ускорить копирование, надо копировать несколько байт или (хотя бы) последовательно:
dest[i] = src[j];
dest[i+1] = src[j-1];
dest[i+2] = src[j-2];
dest[i+3] = src[j-3];
Вряд-л там идет захват по 8 байт :) Но, да, такая оптимизация должна ускорить работу. Впрочем она применима практически ко всем рассмотреным функциям.
А еще это уменьшает накладные расходы на организацию цикла.
А еще это уменьшает накладные расходы на организацию цикла.
в кеш загружается X байт, X зависит от железа :)
логично ) а поскольку точные алгоритмы кэширования нам никто не расскажет, то мы можем лишь оценить идеальную ситуацию: X = CacheSize/2 в случае с полным проходом и X = CacheSize/4 в случаем с проходом накрест.
Расскажут и с удовольствием! На этом держатся все ресурсоемкие приложения (от типа и версии процессора выбирается оптимальная для него функция, иногда встречаются даже разные exe и инсталлер создает ярлык на тот exe, который оптимизирован под CPU).
помню как AMD размещали у себя на сайте примеры (с++) для оптимальной работы с памятью для K6. :)
Точные алгоритмы вот так публично не расскажут — конкурент ведь не спит :) Основные идеи — да, наверняка доступны.
Компании, которые делают такие оптимизации как правило тесно сотрудничают с производителями процессоров (и, что важно, могут себе это позволить). Оптимизации уровня «запросить размер кэша и работать с блоками примерно такого размера» не в счет :)
Кстати, в многозадачной среде кэшированию еще и фоновые задачи палки в колеса вставляют, на консольных платформах активному приложению разрешено этим управлять. Все это получается слишком сложно, чтоб анализировать в данном контексте, да и я в данный момент не обладаю достаточным количеством подготовленной информации.
Однако если есть желание рассказать — с удовольствием почитаю :)
Компании, которые делают такие оптимизации как правило тесно сотрудничают с производителями процессоров (и, что важно, могут себе это позволить). Оптимизации уровня «запросить размер кэша и работать с блоками примерно такого размера» не в счет :)
Кстати, в многозадачной среде кэшированию еще и фоновые задачи палки в колеса вставляют, на консольных платформах активному приложению разрешено этим управлять. Все это получается слишком сложно, чтоб анализировать в данном контексте, да и я в данный момент не обладаю достаточным количеством подготовленной информации.
Однако если есть желание рассказать — с удовольствием почитаю :)
Сейчас посмотреть оптимизацию для Intel можно наглядно с помощью их компилятора (он развернет циклы “как надо”, слегка оптимизирует алгоритмы (если возможно), может немного поменять логику работы с памятью). Всё что делает компилятор описано в соответствующих спеках. Логика работы в общем виде всегда была доступна, чтобы программер точно понимал где горлышко и почему все тормозит из-за жутких пенальти. Я довольно далеко ушел от архитектур, последним процем за которым я следил был AMD K7.
Многозадачность — это особенная фишка, которая заставляет постоянно перезагружать данные в кеш. :) При смене контекста, естественно, данные сбрасываются в кеш нижнего уровня (“ниже” нижнего уровня кеша – медленная RAM). Чем больше поток потребляет памяти, тем дороже его переключение, при желании или большой удаче можно “подвесить” поток – вся его работа будет заключатся в ожидании ответа от памяти, а когда ответ придет, квант времени будет исчерпан и уже другой поток запросит свою область.
Тема очень обширна для коммента. :(
Многозадачность — это особенная фишка, которая заставляет постоянно перезагружать данные в кеш. :) При смене контекста, естественно, данные сбрасываются в кеш нижнего уровня (“ниже” нижнего уровня кеша – медленная RAM). Чем больше поток потребляет памяти, тем дороже его переключение, при желании или большой удаче можно “подвесить” поток – вся его работа будет заключатся в ожидании ответа от памяти, а когда ответ придет, квант времени будет исчерпан и уже другой поток запросит свою область.
Тема очень обширна для коммента. :(
Я прекрасно понимаю обширность темы, это я так намекаю что с удовольствием почитал бы что-то более обширное, нежели комментарии :) Если время позволяет, конечно.
Кстати, вернулись же к исходному — алгоритм кэширования (как и предсказания ветвлений) остается «черным ящиком», известно только что он должен делати и есть рекомендации что лучше на вход скармливать.
«То, что скармливать» проистекает из
1. какой объем кешей.
2. какая разрядность у шины
3. какая задержка/частота у шины
4. какое время поиска/открытия ячейки памяти
Это уже не «черный ящик»… В крайнем случае «серый прозрачный» :)
1. какой объем кешей.
2. какая разрядность у шины
3. какая задержка/частота у шины
4. какое время поиска/открытия ячейки памяти
Это уже не «черный ящик»… В крайнем случае «серый прозрачный» :)
Нее, черный :) Он подключен к кэшам по быстрому каналу и к памяти по медленной шине.
А вот какой логикой он руководствуется при захвате блока памяти мало кому известно. Например высока вероятность, что при линейном чтении большого массива, через пару итераций будет захватываться блок большого размера (тем более что спекулятивное выполнение заглядывает на нексколько инструкций вперет и можно предугадывать, что надо подгрузить).
А вот какой логикой он руководствуется при захвате блока памяти мало кому известно. Например высока вероятность, что при линейном чтении большого массива, через пару итераций будет захватываться блок большого размера (тем более что спекулятивное выполнение заглядывает на нексколько инструкций вперет и можно предугадывать, что надо подгрузить).
я задумался на тему «что дать почитать». Вспомнил отличные и прозрачные материалы Николая Радовского. Если надо более серьезное, то могу посоветовать почитать «Архитектуру микропроцессоров» г. 1998 Питер (автора не помню, очень давно было :( ).
что-то я не понял, почему ReverseManualHalf должна работать быстрее ReverseArrayManual (((
количество итераций уменьшилось вдвое, размер итерации увеличился вдвое, в чём выгода?
количество итераций уменьшилось вдвое, размер итерации увеличился вдвое, в чём выгода?
Расходы на организацию цикла. В данном случае они соизмеримы со сложностью одной итерации.
как думаешь, что быстрее будет — десять операций типа х = х + 1 подряд или цикл от одного до десяти с той же самой операцией?
цикл-то не бесплатный, там проверки счетчика стоят, определение куда прыгать и т.д.
поэтому существует такой метод оптимизации скорости, как разворачивание циклов (хотя в памяти такая программа больше места займет, конечно)
цикл-то не бесплатный, там проверки счетчика стоят, определение куда прыгать и т.д.
поэтому существует такой метод оптимизации скорости, как разворачивание циклов (хотя в памяти такая программа больше места займет, конечно)
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Действительно можно попробовать копировать блоки помещающиеся в L1 и переворачивать их in-place. Я хотел это проверить, но по ходу реализации пришел к выводу что это вряд-ли будет быстрее ReverseArrayManual :)
Что касается ReverseArrayFramework — ну так там и особо думать не о чем, прирост производительности в других реализациях достигается исключительно за счет отброса лишних копирований. А в случае unsafe еще исключается лишний промежуточный буфер.
Что касается ReverseArrayFramework — ну так там и особо думать не о чем, прирост производительности в других реализациях достигается исключительно за счет отброса лишних копирований. А в случае unsafe еще исключается лишний промежуточный буфер.
графики — юзеранфрендли… у-шкала — это что: время или скорость? Если я не вникая в суть статьи пролистну сразу до графиков — из них не пойму, какой метод лучший.
Замечательная статья!
Если честно, прочитав сначала заголовок, подумал, что речь пойдет о разворачивании/сворачивании (expanding/collapsing) строчек кода в время редактирования сорца :)
Если честно, прочитав сначала заголовок, подумал, что речь пойдет о разворачивании/сворачивании (expanding/collapsing) строчек кода в время редактирования сорца :)
Звездец.
Строка переворачивается элементарно:
reverse = foldl (flip (:)) []
А если серьезно, то вы впустую тратите время. Расскажите, какие задачи вы решаете, в которых настоящим ботлнеком является тупое переворачивание строки. Иначе же в топку.
Строка переворачивается элементарно:
reverse = foldl (flip (:)) []
А если серьезно, то вы впустую тратите время. Расскажите, какие задачи вы решаете, в которых настоящим ботлнеком является тупое переворачивание строки. Иначе же в топку.
Знаете, а я вот думаю, что strrev(s) в С работает быстрее и эффективнее этого примера. и пишется короче :)
А если серъезно, то дело ведь не столько в самом акте разворачивания строки, лично мне интересней посмотреть, что вообще можно выжать из этой среды.
Есть два противостоящих «мира»: одни строят приложение на сверхвысокоуровневой платформе не думая об эффективности и производительности (об этом за нас подумает платформа ©), другие же пытаются выжать максимум чтою эта «платформа» таки думала за первых. Лично мне ближе второе, закономерно, что я буду везде искать интересные мне аспекты.
А конкретно это пример был «высосан из пальца» в пятницу вечером :)
А если серъезно, то дело ведь не столько в самом акте разворачивания строки, лично мне интересней посмотреть, что вообще можно выжать из этой среды.
Есть два противостоящих «мира»: одни строят приложение на сверхвысокоуровневой платформе не думая об эффективности и производительности (об этом за нас подумает платформа ©), другие же пытаются выжать максимум чтою эта «платформа» таки думала за первых. Лично мне ближе второе, закономерно, что я буду везде искать интересные мне аспекты.
А конкретно это пример был «высосан из пальца» в пятницу вечером :)
> Есть два противостоящих «мира»: одни строят приложение на сверхвысокоуровневой платформе не думая об эффективности и производительности (об этом за нас подумает платформа ©), другие же пытаются выжать максимум чтою эта «платформа» таки думала за первых. Лично мне ближе второе, закономерно, что я буду везде искать интересные мне аспекты.
Ну так эта, если хоцца скорости, то strrev будет вин. А так очередной abuse.
> Кстати вопрос еще что считать «боттлнеком»: если требуется высокая интерактивность, то лишняя экономия не помешает :)
Неправильно. Оптимизировать надо только тогда, когда это действительно скажется на скорости. Ну а если оптимизировать, то скорость должна вырасти НА ПОРЯДОК, а не в два-три-четыре-пять раз (другими словами, 2x буст хоть и заметен пользователю, но жизни его не упростит, и следовательно, не нужен).
Ну так эта, если хоцца скорости, то strrev будет вин. А так очередной abuse.
> Кстати вопрос еще что считать «боттлнеком»: если требуется высокая интерактивность, то лишняя экономия не помешает :)
Неправильно. Оптимизировать надо только тогда, когда это действительно скажется на скорости. Ну а если оптимизировать, то скорость должна вырасти НА ПОРЯДОК, а не в два-три-четыре-пять раз (другими словами, 2x буст хоть и заметен пользователю, но жизни его не упростит, и следовательно, не нужен).
Вы видимо никогда игрушки не писали :) Там даже за прирост скорости в 15% борются.
Согласен, писать динамичные игры на .Net в данный момент глупость, но так уж сложилось что я в силу определенный факторов пришел на эту платформу, а привычки и взгляды остались.
Согласен, писать динамичные игры на .Net в данный момент глупость, но так уж сложилось что я в силу определенный факторов пришел на эту платформу, а привычки и взгляды остались.
> Вы видимо никогда игрушки не писали :)
Ну как же. Писывал, было дело (непрофессионально). На Си, правда. Это был отборрный лапшекод, но тогда я этого не знал. :)
> Там даже за прирост скорости в 15% борются.
Везде одна и та же тенденция: сает — разгоним, игрушку — разгоним, переворачивание строк — разгоним… Это все бессмысленно.
Еще раз повторяю: если игрушка грузилась минуту, а мы ее загрузку ускорили в два раза, то пользователю от этого не стало легче. Он все равно так же уныло смотрит в монитор. Стоит ли такое ускорение проводить или нет? (Ответ, разумеется, нет.)
Что же касается скорости рантайма, то тут надобно находить ботлнеки, и бороться именно с ними, ибо, как известно, 90% времени программа проводит в 10% кода. Алгоритмические оптимизации рулят, а низкоуровневые — нет. (Исключения бывают, конечно, но только как исключения.)
Ну как же. Писывал, было дело (непрофессионально). На Си, правда. Это был отборрный лапшекод, но тогда я этого не знал. :)
> Там даже за прирост скорости в 15% борются.
Везде одна и та же тенденция: сает — разгоним, игрушку — разгоним, переворачивание строк — разгоним… Это все бессмысленно.
Еще раз повторяю: если игрушка грузилась минуту, а мы ее загрузку ускорили в два раза, то пользователю от этого не стало легче. Он все равно так же уныло смотрит в монитор. Стоит ли такое ускорение проводить или нет? (Ответ, разумеется, нет.)
Что же касается скорости рантайма, то тут надобно находить ботлнеки, и бороться именно с ними, ибо, как известно, 90% времени программа проводит в 10% кода. Алгоритмические оптимизации рулят, а низкоуровневые — нет. (Исключения бывают, конечно, но только как исключения.)
>писать динамичные игры на .Net в данный момент глупость
для динамических игр есть XNA, так что не совсем глупость )
для динамических игр есть XNA, так что не совсем глупость )
Ну во-первых далеко не любой игровой платформе он есть :)
А во вторых… есть некоторые познания о жизнеспособности .Net CF в условиях ограниченых ресурсов (около 2М памяти, остальное железо тоже на уровне, .Net CF официальная среда), и они не очень позитивные. Впрочем писали же люди… И работало, правда с гайдлайнами .Net в итоге мало общего имело :)
А во вторых… есть некоторые познания о жизнеспособности .Net CF в условиях ограниченых ресурсов (около 2М памяти, остальное железо тоже на уровне, .Net CF официальная среда), и они не очень позитивные. Впрочем писали же люди… И работало, правда с гайдлайнами .Net в итоге мало общего имело :)
Кстати вопрос еще что считать «боттлнеком»: если требуется высокая интерактивность, то лишняя экономия не помешает :)
А теперь добавьте к исходным условиям задачи кодировку UTF-8 — что для современных приложений by default, и сложность задачи возрастет существенно.
for (int i = str.Length; i-- !=; )
int i =;
С чем связано использование такого не совсем очевидного стиля? Какая практическая польза? (раз уж речь об оптимизации)
С чем связано использование такого не совсем очевидного стиля? Какая практическая польза? (раз уж речь об оптимизации)
1. Хабр нолик сожрал в условии
2. Стиль, как стиль. На С/С++ сплошь и рядом так пишут, главная польза в единоразовом вычислении str.Length. Ну и потенциальном схлопывании сравнения с нулем в одну операцию целевого процессора, хотя и мелочь второе.
2. Стиль, как стиль. На С/С++ сплошь и рядом так пишут, главная польза в единоразовом вычислении str.Length. Ну и потенциальном схлопывании сравнения с нулем в одну операцию целевого процессора, хотя и мелочь второе.
Хабр что-то вообще много чего жрёт )
Я имел ввиду, почему не for (int i = str.Length; i != 0; i-- )?
Кстати, всегда интересно было, i>=0 идёт как одно сравнение? Или лучше использовать i>-1? Есть вообще разница?
Я имел ввиду, почему не for (int i = str.Length; i != 0; i-- )?
Кстати, всегда интересно было, i>=0 идёт как одно сравнение? Или лучше использовать i>-1? Есть вообще разница?
сизифов труд, очевидные и никому не нужные результаты
for (int i = str.Length; i-- != ; )ошибка, вроде бы?
Все неправильно. Unicode-строки так не разворачивают:
StringInfo.GetTextElementEnumerator() и далее.Очень даже разворачивают, только чуть более громоздко это будет.
А фреймворк не есть единственно верное решение, кстати что-то мне кажется что энумератор тормозить ужасно будет. Ну примерно как версия с LINQ, по тем же причинам.
Для большей наглядности, здесь не учтены unicode surrogate code points.
А фреймворк не есть единственно верное решение, кстати что-то мне кажется что энумератор тормозить ужасно будет. Ну примерно как версия с LINQ, по тем же причинам.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
О разворачивании строк в .Net/C# и не только