Здравствуйте, MShura, Вы писали:
S>>Интересуют предложения по оптимизации.
MS>В свой время Крис Касперски оптимизировал memcpy за счет периодического чтения "вперед". MS>За счет этого уменьшались простои самого внутреннего кэша процессора, который, кстати, разного размера для разных CPU.
MS>Он приводил очень убедительные результаты сравнения разных реализаций memcpy в свою пользу.
Эти оптимизации перестали работать, начиная с P4. Я сам пробовал. На P3 работало, на P4 — уже нет. Prefetcher в процессорах стал более умный и он уже сам понимает, как эффективно заполнить кэш.
S>>>Интересуют предложения по оптимизации.
MS>>В свой время Крис Касперски оптимизировал memcpy за счет периодического чтения "вперед". MS>>За счет этого уменьшались простои самого внутреннего кэша процессора, который, кстати, разного размера для разных CPU.
MS>>Он приводил очень убедительные результаты сравнения разных реализаций memcpy в свою пользу.
A>Эти оптимизации перестали работать, начиная с P4. Я сам пробовал. На P3 работало, на P4 — уже нет. Prefetcher в процессорах стал более умный и он уже сам понимает, как эффективно заполнить кэш.
SC>>Здравствуйте, sokel, Вы писали:
S>1. MS-specific не надо. Да и функцию такого размера как haszero любой компилятор заинлайнит без вопросов.
Я имел ввиду inline на саму функцию. Конечно может привести к разбуханию кода, но тем не менее может дать приличный выигрыш в производительности, если функция вызывается достаточно часто с не очень длинными строками. Впрочем, тут больше зависит от контекста использования. чем от самой функции, как часто и бывает при агрессивной низкоуровневой оптимизации.
S>3. так лучше?:
значительно.
Здравствуйте, djs_, Вы писали:
К>>Ты выравниваешь по sizeof(size_t), а не по sizeof(int). Но именно int является наиболее родным типом данных для процессора.
_>Извините, а разве size_t не есть просто целочисленный define или typedef соотв. типа для данной платформы?
Нет, это самостоятельный тип. Эквивалентный unsigned int или unsigned long.
Хотя некоторые криворукие компиляторы действительно определяют его как синоним.
_>Т.е. где-то он будет 4 байта, где-то 16, а где-то даже и 20 бит (2,5 байта)?
Ну уж полубайтами он точно не будет. Размер всегда меряется в байтах (хотя не все старшие биты этих байтов обязаны быть значащими).
_>Или вы что-то иное имете ввиду?
Я имею в виду, что int и size_t — это родные для компилятора типы. Да, они платформенно-зависимы.
int — тип, наиболее удобный для целочисленной арифметики; size_t и ptrdiff_t — достаточные для адресной.
Всё тот же реальный режим x86, где длина адреса — 20 бит, а длина регистра данных — 16.
Сделать 20- или 32-битную арифметику большого труда не составляет, но этот труд ненулевой. Даже если это копирование.
Поэтому использовать long вместо int без нужды — неоправданно.
К>Я имею в виду, что int и size_t — это родные для компилятора типы. Да, они платформенно-зависимы. К>int — тип, наиболее удобный для целочисленной арифметики; size_t и ptrdiff_t — достаточные для адресной.
Только вот я не встречал компилятора где sizeof(int) != 4. Та же реализация strncpy с выравниванием по int на 64-битной платформе занчительно уступает реализации с выравниванием по size_t.
> К>Я имею в виду, что int и size_t — это родные для компилятора типы. Да, они платформенно-зависимы. > К>int — тип, наиболее удобный для целочисленной арифметики; size_t и ptrdiff_t — достаточные для адресной. > > Только вот я не встречал компилятора где sizeof(int) != 4.
Не так давно таких компиляторов было полно
Posted via RSDN NNTP Server 2.1 beta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, sokel, Вы писали:
S>Только вот я не встречал компилятора где sizeof(int) != 4. Та же реализация strncpy с выравниванием по int на 64-битной платформе занчительно уступает реализации с выравниванием по size_t.
Вот упёрся же ты рогом в size_t.
Для IA64 с сегментной моделью sizeof(size_t) должен быть не менее 10. (8 байт — смещение, хранимое в регистрах общего назначения, и 2 байта — селектор сегмента).
Плоская модель — это всего лишь подарок микрософта благодарным прикладным программистам.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, sokel, Вы писали:
S>>Только вот я не встречал компилятора где sizeof(int) != 4. Та же реализация strncpy с выравниванием по int на 64-битной платформе занчительно уступает реализации с выравниванием по size_t.
К>Вот упёрся же ты рогом в size_t. К>Для IA64 с сегментной моделью sizeof(size_t) должен быть не менее 10. (8 байт — смещение, хранимое в регистрах общего назначения, и 2 байта — селектор сегмента). К>Плоская модель — это всего лишь подарок микрософта благодарным прикладным программистам.
К>Форум-то называется "С++", а не "Intel Pentium"?
Не подарок микрософта, а механизм страничной трансляции. А сегментная модель памяти, это как раз для форума "Intel Pentium".
Здравствуйте, sokel, Вы писали:
К>>Плоская модель — это всего лишь подарок микрософта благодарным прикладным программистам. S>Не подарок микрософта, а механизм страничной трансляции. А сегментная модель памяти, это как раз для форума "Intel Pentium".
Ну раз уж спускаемся до этого уровня — то процессоры с сегментно-страничной памятью — это не только интелы (макинтоши, VAXы, что там ещё было).
А подарок микрософта состоит в том, что прикладных программистов освободили, во-первых, от секса с ручным управлением сегментами, и во-вторых, от недо-гарвардской архитектуры (когда стек, данные и код лежат в разных сегментах). Хорошо известной ещё под досом.
Вот не помню, какую модель предлагает OS/2 warp. Там, кажется, как раз рукоделия приветствовались.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, sokel, Вы писали:
К>>>Плоская модель — это всего лишь подарок микрософта благодарным прикладным программистам. S>>Не подарок микрософта, а механизм страничной трансляции. А сегментная модель памяти, это как раз для форума "Intel Pentium".
К>Ну раз уж спускаемся до этого уровня — то процессоры с сегментно-страничной памятью — это не только интелы (макинтоши, VAXы, что там ещё было). К>А подарок микрософта состоит в том, что прикладных программистов освободили, во-первых, от секса с ручным управлением сегментами, и во-вторых, от недо-гарвардской архитектуры (когда стек, данные и код лежат в разных сегментах). Хорошо известной ещё под досом.
К>Вот не помню, какую модель предлагает OS/2 warp. Там, кажется, как раз рукоделия приветствовались.
Ладно, не суть. В общем, size_t я выбрал потому что этот тип определяет возможности адресации и, как правило, покрывает разрядность процессора, соответственно, оптимален для пословного копирования. А двухкомпонентная адресация и сегментная модель памяти, как я думал, просто наследие 286-х и 16-битной адресации, что упоминается, например, здесь или здесь.
Здравствуйте, sokel, Вы писали:
S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.
Тогда уж можно попробовать поэкспериментировать с такой штукойтакой штукой
Здравствуйте, se_sss, Вы писали:
_>Здравствуйте, sokel, Вы писали:
S>>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.
_>Тогда уж можно попробовать поэкспериментировать с _>такой штукойтакой штукой
_>-)
экспериментировал, бесполезно.
Re: fast strncpy
От:
Аноним
Дата:
18.01.08 08:39
Оценка:
Здравствуйте, sokel, Вы писали:
S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.
Конструктивную критику принимаете? Может Вы где-нибудь уже ответили, но когда пишут "fast strncpy" приводят относительно чего fast? Никаких таблиц сравнения не заметил. В классических изложениях также перед кодом алгоритма дают его основную идею.
MSVC8 — Intel Pentium D 2.8GHz.
dst_sz, src_sz — это размеры строки получателя и строки источника соответственно.
strncpy|my_strncpy|memcpy — время выполнения функции в микросекундах.
Первая часть таблицы иллюстрирует выгоду использования my_strncpy перед strcpy. Из таблицы следует, что strncpy явно проигрывает my_strncpy, но это мы выяснили и ранее
Вторая часть таблицы сравнивает my_strncpy с memcpy. Тут однозначно выигрывает memcpy. Это по сути сравнение null-terminated строк со строками с заданной длиной.
Вывод: в общем случае выгоднее всего использовать my_strncpy, но когда известна длина буфера получателя и длина строки источника лучше использовать memcpy. Если пишите какую либо программу, активно работающую со строками не забывайте о memcpy, она значительно быстрее любой реализации strncpy. Если хотите получить высокую скорость работы со строками, то не используйте null-terminated строки и функции для работы с ними.
Здравствуйте, sokel, Вы писали:
S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.
Если речь идет о версиях компилятора от
Microsoft VC 8+, то в стандартных библиотеках появился целый набор функций с постфиксом "_s".
В частности, имеется функция strncpy_s, которая описанного выше недостатка не имеет.
Однако есть небольшая понкость — в Debug версии она все же заполняет буффер данными (0xfd).
Это значительно помогает искать многие трудновыявляемые баги. В релизе же работает как и положено — без лишних операций по заполнению.
Здравствуйте, sokel, Вы писали:
S>Интересуют предложения по оптимизации.
Оптимизация таких вещей — это всегда платформенно-зависимая вещь.
Во-первых, тебе надо определиться, для чего ты хочешь применять эту функцию. Варианты: для копирования маленьких областей, для копирования очень больших областей, для всего подряд.
Например для копирования очень больших областей на x86 тебе надо применять non-temporal сохранения + non-temporal предвыборку в L1$ + барьер на запись. Смотри описание и гугли по инструкциям MOVNTQ, PREFETCHNTA, SFENCE.
Во-вторых, погляди, не можешь ли ты наложить какие-то дополнительные ограничения на входные данные.
Например ты можешь потребовать, что бы обе области были выровнены на 16 байт + размер памяти под области тоже кратен 16 байтам. Тогда ты можешь не обрабатывать отдельным образом начало и конец области, а сразу и до конца шпарить по 16 байт. Я думаю, это должно дать выигрыш для маленьких областей, т.к. функция будет маленькой и простой и без дополнительных ветвлений.
Если же ты хочешь функцию портируемую, для всех размеров областей и без дополнительных ограничений на входные данные, то тут и никакого простора для оптимизаций нет. Остаётся только оставить функцию как есть и надеяться на оптимизатор компилятора. Но тут ты скорее всего всегда будешь отставать от библиотечной memcpy() и от intrinsic'а компилятора.
Здравствуйте, sokel, Вы писали:
S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.
Прокомментирую не только по оптимизации:)
Во-первых, интерфейс strncpy() действительно немного неадекватен обычному использованию — дело в том, что эта функция была придумана в Unix именно для заполнения полей фиксированного размера так, чтобы они потом были пригодны для memcmp (а не с ограничением по размеру), поэтому там доливание нулями. Поэтому все тесты, в которых размер приёмника больше размера источника, заведомо неадекватны; сравнивать надо не с классической strncpy(), а с, лучше всего, strcpy_s() или strncpy_s() (ISO drafts, из платформ — последние MSVC). Если же смотреть на приведённые дальше сравнения скоростей, Ваша strncpy заметно проигрывает штатной memcpy(), а это показывает, что таки старания на Си не дают достаточного результата, и ассемблер тут таки прогрессивнее. (Разумеется, если надо так делать. Я не премину повторить, что NUL-terminated strings — зло, и от них надо избавляться при любой возможности.)
Во-вторых, если strlen(src)>=dst_size, я бы делал не так — буфер заполняется полностью, \0 в него не дописывается, а возвращается dst_size. (Кстати, оригинальная strncpy делает именно так.) Это позволяет немедленно проверять на переполнение; у Вас же не отличить переполнения от полного заполнения буфера. Если кому нужна в таком случае урезанная строка, он может и вручную дописать \0 в конец буфера.