fast strncpy - C/C++

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

S>>>Интересуют предложения по оптимизации.

MS>>В свой время Крис Касперски оптимизировал memcpy за счет периодического чтения "вперед".
MS>>За счет этого уменьшались простои самого внутреннего кэша процессора, который, кстати, разного размера для разных CPU.

MS>>Он приводил очень убедительные результаты сравнения разных реализаций memcpy в свою пользу.

A>Эти оптимизации перестали работать, начиная с P4. Я сам пробовал. На P3 работало, на P4 — уже нет. Prefetcher в процессорах стал более умный и он уже сам понимает, как эффективно заполнить кэш.

есть старый документ, мб кому интересен Using Block Prefetch for Optimized Memory Performance

Я провел свой тест данного алгоритма, но решил посмотреть несколько в другую сторону. Я сравнил strncpy, my_strncpy и memcpy. И вот результат:

dst_sz, src_sz                |   strncpy | my_strncpy|    memcpy |
256, 128                      |      0.93 |      0.68 |      0.54 |
8192, 128                     |      3.94 |      0.81 |      0.86 |
16384, 128                    |      8.51 |      0.83 |      0.81 |
32768, 128                    |     19.62 |      0.79 |      0.83 |
65536, 128                    |     49.89 |      0.82 |      0.67 |

131072, 256                   |    104.60 |      0.77 |      1.10 |
131072, 4096                  |    101.42 |      3.22 |      1.46 |
131072, 8192                  |    100.27 |      5.83 |      1.98 |
131072, 16384                 |    110.20 |     10.99 |      3.68 |
131072, 32768                 |    113.72 |     21.35 |      6.79 |
131072, 65536                 |    119.81 |     42.26 |     16.67 |

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 строки и функции для работы с ними.

Сырец:

void test_fast(    size_t dst_sz, size_t src_sz )
{
    tick_count t0, t1;

    char* dst = new char[dst_sz];
    char* src = new char[src_sz];
    memset(src, '-', src_sz);
    src[src_sz-1] = 0;

    t0 = tick_count::now();
    strncpy(dst, src, dst_sz);
    t1 = tick_count::now();
    double tv1 = (t1-t0).seconds()*1000000.;

    t0 = tick_count::now();
    my_strncpy(dst, src, dst_sz);
    t1 = tick_count::now();
    double tv2 = (t1-t0).seconds()*1000000.;

    t0 = tick_count::now();
    memcpy(dst, src, src_sz);
    t1 = tick_count::now();
    double tv3 = (t1-t0).seconds()*1000000.;

    t0 = tick_count::now();
    memcpy(dst, src, strlen(src)+1);
    t1 = tick_count::now();
    double tv4 = (t1-t0).seconds()*1000000.;

    stringstream ost;
    ost << dst_sz << ", " << src_sz;
    print_resilt(ost.str().c_str(), tv1, tv2, tv3, tv4);

    delete src;
    delete dst;
}

int main(int argc, char* argv[])
{
    test_fast(256, 128);
    test_fast(256*32, 128);
    test_fast(256*64, 128);
    test_fast(256*128, 128);
    test_fast(256*256, 128);
    cout << endl;
    test_fast(65536*2, 256);
    test_fast(65536*2, 256*16);
    test_fast(65536*2, 256*32);
    test_fast(65536*2, 256*64);
    test_fast(65536*2, 256*128);
    test_fast(65536*2, 256*256);
    return 0;
}

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

К>Я имею в виду, что int и size_t — это родные для компилятора типы. Да, они платформенно-зависимы.
К>int — тип, наиболее удобный для целочисленной арифметики; size_t и ptrdiff_t — достаточные для адресной.

Только вот я не встречал компилятора где sizeof(int) != 4. Та же реализация strncpy с выравниванием по int на 64-битной платформе занчительно уступает реализации с выравниванием по size_t.

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

К>Здравствуйте, 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>Интересуют предложения по оптимизации.

Оптимизация таких вещей — это всегда платформенно-зависимая вещь.
Во-первых, тебе надо определиться, для чего ты хочешь применять эту функцию. Варианты: для копирования маленьких областей, для копирования очень больших областей, для всего подряд.
Например для копирования очень больших областей на x86 тебе надо применять non-temporal сохранения + non-temporal предвыборку в L1$ + барьер на запись. Смотри описание и гугли по инструкциям MOVNTQ, PREFETCHNTA, SFENCE.
Во-вторых, погляди, не можешь ли ты наложить какие-то дополнительные ограничения на входные данные.
Например ты можешь потребовать, что бы обе области были выровнены на 16 байт + размер памяти под области тоже кратен 16 байтам. Тогда ты можешь не обрабатывать отдельным образом начало и конец области, а сразу и до конца шпарить по 16 байт. Я думаю, это должно дать выигрыш для маленьких областей, т.к. функция будет маленькой и простой и без дополнительных ветвлений.
Если же ты хочешь функцию портируемую, для всех размеров областей и без дополнительных ограничений на входные данные, то тут и никакого простора для оптимизаций нет. Остаётся только оставить функцию как есть и надеяться на оптимизатор компилятора. Но тут ты скорее всего всегда будешь отставать от библиотечной memcpy() и от intrinsic'а компилятора.

Здравствуйте, Сергей Мухин, Вы писали:

СМ>Здравствуйте, remark, Вы писали:

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

S>>>Интересуют предложения по оптимизации.

R>>Оптимизация таких вещей — это всегда платформенно-зависимая вещь.
R>>Во-первых, тебе надо определиться, для чего ты хочешь применять эту функцию. Варианты: для копирования маленьких областей, для копирования очень больших областей, для всего подряд.
R>>Например для копирования очень больших областей на x86 тебе надо применять non-temporal сохранения + non-temporal предвыборку в L1$ + барьер на запись. Смотри описание и гугли по инструкциям MOVNTQ, PREFETCHNTA, SFENCE.

СМ>А потом, когда все сделаешь, надо замерить время выполнения приложения, и увидеть что твоя ф-ия копирования занимает меньше 1% времени. и выкинуть ее.

Дополнение Харриса
Третье правило Гуэста

Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

#define haszero(x) (((x)-~0UL/255)&~(x)&~0UL/255*128)

size_t my_strncpy(register char* dst, register const char* src, register size_t dst_size)
{
    if(!dst_size) return 0;
    register const char* begin = dst;
    if(dst_size > sizeof(size_t))
    {
        // вычисляем выравнивание по size_t
        register size_t src_pad = (sizeof(size_t)-((size_t)(src))%sizeof(size_t))&(sizeof(size_t)-1);
        register size_t dst_pad = (sizeof(size_t)-((size_t)(dst))%sizeof(size_t))&(sizeof(size_t)-1);
        if(dst_pad == src_pad) 
        {
            while(src_pad--){ if(!(*dst = *src++)) return (dst-begin); ++dst; --dst_size; }
            while(dst_size >= sizeof(size_t) && !haszero(*((const size_t*)src)))
            {
                *((size_t*&)dst)++ = *((const size_t*&)src)++; 
                dst_size -= sizeof(size_t);
            }
            if(!dst_size) { --dst; ++dst_size; }
        }
    }
    while(--dst_size) { if(!(*dst = *src++)) return (dst-begin); ++dst; }
    *dst = 0;
    return dst - begin;
}

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

S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

примерные результаты тестирования по сравнению с strncpy и ap_cpystrn(Apache):

test results (strlen = 20, buf size = 128, count = 10000000):
strncpy: 734 msec
ap_cpystrn: 531 msec
my_strncpy: 219 msec

S>Интересуют предложения по оптимизации.

В свой время Крис Касперски оптимизировал memcpy за счет периодического чтения "вперед".
За счет этого уменьшались простои самого внутреннего кэша процессора, который, кстати, разного размера для разных CPU.

Он приводил очень убедительные результаты сравнения разных реализаций memcpy в свою пользу.

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

S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

Ты выравниваешь по sizeof(size_t), а не по sizeof(int). Но именно int является наиболее родным типом данных для процессора.
Есть платформы, на которых sizeof(size_t) > sizeof(int), получишь некоторую просадку производительности.

Ну а в остальном — всякие мелочи:
— register никому особо не нужно, компилятор (если только это не диалект для микроконтроллеров) проигнорирует его
— дефайн haszero и копи-паст src_pad, dst_pad вместо инлайновых функций
— код с многочисленными автоинкрементами внутри выражений трудно читать человеку

... << RSDN@Home 1.2.0 alpha rev. 655>>

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

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

S>>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

К>Ты выравниваешь по sizeof(size_t), а не по sizeof(int). Но именно int является наиболее родным типом данных для процессора.
К>Есть платформы, на которых sizeof(size_t) > sizeof(int), получишь некоторую просадку производительности.

К>Ну а в остальном — всякие мелочи:
К>- register никому особо не нужно, компилятор (если только это не диалект для микроконтроллеров) проигнорирует его
К>- дефайн haszero и копи-паст src_pad, dst_pad вместо инлайновых функций
К>- код с многочисленными автоинкрементами внутри выражений трудно читать человеку

не, для 64 битных как раз size_t будет более родным.

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

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

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

S>>>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

К>>Ты выравниваешь по sizeof(size_t), а не по sizeof(int). Но именно int является наиболее родным типом данных для процессора.
К>>Есть платформы, на которых sizeof(size_t) > sizeof(int), получишь некоторую просадку производительности.

К>>Ну а в остальном — всякие мелочи:
К>>- register никому особо не нужно, компилятор (если только это не диалект для микроконтроллеров) проигнорирует его
К>>- дефайн haszero и копи-паст src_pad, dst_pad вместо инлайновых функций
К>>- код с многочисленными автоинкрементами внутри выражений трудно читать человеку

S>не, для 64 битных как раз size_t будет более родным.

ну и, извиняюсь... комментарии:

// макрос для проверки наличия нулевого байта в слове
#define haszero(x) (((x)-~0UL/255)&~(x)&~0UL/255*128)
// функция копирования строк с ограничением по размеру буфера (аналог strncpy)
size_t my_strncpy(register char* dst, register const char* src, register size_t dst_size)
{
    if(!dst_size) return 0;
    register const char* begin = dst; // запоминаем начало, чтобы потом посчитать длину
    if(dst_size > sizeof(size_t)) 
    {
        // вычисляем выравнивание источника и назначения по size_t
        register size_t src_pad = (size_t)(src)%sizeof(size_t);
        register size_t dst_pad = (size_t)(dst)%sizeof(size_t);
        // если выравнивания источника и назначения относительно size_t равны
        if(dst_pad == src_pad) 
        {
            // сначала при необходимости копируем побайтово кусок строки до границы слова
            // dst_size используем как размер остатка буфера
            if(src_pad)
            {
                src_pad = sizeof(size_t)-src_pad;
                do { if(!(*dst = *src++)) return (dst-begin); ++dst; --dst_size; } while(--src_pad);
            }
            // дальше копируем строку пословно - 32 или 64 битными кусками
            // макрос haszero проверяет слово на наличие нулевого байта
            while(dst_size > sizeof(size_t) && !haszero(*((const size_t*)src)))
            {
                *((size_t*&)dst)++ = *((const size_t*&)src)++; // слово в слово
                dst_size -= sizeof(size_t);
            }
        }
    }
    // копируем остаток строки посимвольно
    while(--dst_size) { if(!(*dst = *src++)) return (dst-begin); ++dst; }
    // исходная строка не влезла в буфер:
    *dst = 0;
    return dst - begin;
}

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

S>>Интересуют предложения по оптимизации.

MS>В свой время Крис Касперски оптимизировал memcpy за счет периодического чтения "вперед".
MS>За счет этого уменьшались простои самого внутреннего кэша процессора, который, кстати, разного размера для разных CPU.

MS>Он приводил очень убедительные результаты сравнения разных реализаций memcpy в свою пользу.

На самом деле, strncpy — вполне насущная проблема, с которой сразу сталкиваешься при реализации, например, собственного класса строки. Во первых, хочется получать хотя бы размер копируемой строки, раз уж он всё равно неявно вычисляется, а не использовать strlen. Во вторых, чем большего запаса буфер и чем меньше строки, тем больше времени тратится на бесполезное заполнение остатка нулями при копировании. В третьих, просто раздражает то, что результатом строковой по сути функции может быть вообще не строка.

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

К>>Ты выравниваешь по sizeof(size_t), а не по sizeof(int). Но именно int является наиболее родным типом данных для процессора.
К>>Есть платформы, на которых sizeof(size_t) > sizeof(int), получишь некоторую просадку производительности.

S>не, для 64 битных как раз size_t будет более родным.

Если брать во внимание только IA32 — IA64, тогда можно long.
Если же "вообще", то, может быть, завести какой-нибудь пользовательский typedef ..... int_register_t. Чтобы совсем не зависеть от прихотей разработчиков компилятора.

А для сегментных моделей памяти всё-таки size_t не влезает в регистр данных (потому что тащит с собой селектор сегмента).

... << RSDN@Home 1.2.0 alpha rev. 655>>

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

S>

S>#define haszero(x) (((x)-~0UL/255)&~(x)&~0UL/255*128)

S>size_t my_strncpy(register char* dst, register const char* src, register size_t dst_size)
S>{
S>}
S>

Я думаю что компилятор не разберется в "С" циклах с под-условиями и просто сделает циклы на ASM-е вместо того, чтобы вставить один REPNZ. Вероятно, REPNZ быстрее и компактнее чем прямые циклы.

вот так сделано у MS: (strncpy.c)


        char *start = dest;

        while (count && (*dest++ = *source++))    /* copy string */
                count--;

        if (count)                              /* pad out with zeroes */
                while (--count)
                        *dest++ = '\0';

        return(start);

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

        if (count)  
             *dest++ = '\0';

        return dest - start; // count of symbols

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

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

К>>>Ты выравниваешь по sizeof(size_t), а не по sizeof(int). Но именно int является наиболее родным типом данных для процессора.
К>>>Есть платформы, на которых sizeof(size_t) > sizeof(int), получишь некоторую просадку производительности.

S>>не, для 64 битных как раз size_t будет более родным.

К>Если брать во внимание только IA32 — IA64, тогда можно long.
К>Если же "вообще", то, может быть, завести какой-нибудь пользовательский typedef ..... int_register_t. Чтобы совсем не зависеть от прихотей разработчиков компилятора.

К>А для сегментных моделей памяти всё-таки size_t не влезает в регистр данных (потому что тащит с собой селектор сегмента).

А как насчет выравнивания, например, по sizeof(void*). Сегментная модель вряд ли понадобится, этож прошлый век.

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

S>может просто подправить последний фрагмен чтобы не забивать нулями и вернуть количество?

S>

S>        if (count)  
S>             *dest++ = '\0';

S>        return dest - start; // count of symbols
S>

Именно так сделано в Apache:

char* ap_cpystrn(char *dst, const char *src, size_t dst_size)
{
    char *d, *end;
    if (!dst_size)
        return (dst);
    d = dst;
    end = dst + dst_size - 1;

    for (; d < end; ++d, ++src)
        if (!(*d = *src))
            return (d);
    *d = '\0';      /* always null terminate */
    return (d);
}

Но здесь работает оптимизация за счет пословного копирования строки, опять таки, вот результаты теста (тест на выровненных строках):

test results (strlen = 20, buf size = 128, count = 10000000):
strncpy: 734 msec
ap_cpystrn: 531 msec
my_strncpy: 219 msec

Microsoft Windows XP [Версия 5.1.2600]
(С) Корпорация Майкрософт, 1985-2001.

C:\Documents and Settings\.........\Test\Release>test
strncpy: 640 msec
my_strncpy: 641 msec

C:\Documents and Settings\.........\Test\Release>test
strncpy: 641 msec
my_strncpy: 640 msec

C:\Documents and Settings\.........\Test\Release>test
strncpy: 641 msec
my_strncpy: 640 msec

C:\Documents and Settings\.........\Test\Release>test
strncpy: 625 msec
my_strncpy: 641 msec

C:\Documents and Settings\.........\Test\Release>test
strncpy: 640 msec
my_strncpy: 625 msec

Все это на VC++ 7.1 (2003), PIV 3 GHz, 1024 MB

Хм. В чем преимущество — в упор не понимаю....

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

S>вот так сделано у MS: (strncpy.c)

Вот только в реальности этот код не используется, а используется либо intrinsic-реализация, либо реализация из \intel\strncpy.asm

--
Sergey Chadov

... << RSDN@Home 1.2.0 alpha rev. 685>>

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

S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

1. __forceinline. Очень помогает против недальновидности компилятора. Правда MS-specific
2. Убрать register. Смущает

3. Сделать более читабельным код.
вот это:

while(src_pad--){ if(!(*dst = *src++)) return (dst-begin); ++dst; --dst_size; }

не способствует.

--
Sergey Chadov

... << RSDN@Home 1.2.0 alpha rev. 685>>

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

К>Ты выравниваешь по sizeof(size_t), а не по sizeof(int). Но именно int является наиболее родным типом данных для процессора.

Извините, а разве size_t не есть просто целочисленный define или typedef соотв. типа для данной платформы?
Т.е. где-то он будет 4 байта, где-то 16, а где-то даже и 20 бит (2,5 байта)?
Или вы что-то иное имете ввиду?

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

V_S>Microsoft Windows XP [Версия 5.1.2600]
V_S>(С) Корпорация Майкрософт, 1985-2001.

V_S>C:\Documents and Settings\.........\Test\Release>test
V_S>strncpy: 640 msec
V_S>my_strncpy: 641 msec

V_S>C:\Documents and Settings\.........\Test\Release>test
V_S>strncpy: 641 msec
V_S>my_strncpy: 640 msec

V_S>C:\Documents and Settings\.........\Test\Release>test
V_S>strncpy: 641 msec
V_S>my_strncpy: 640 msec

V_S>C:\Documents and Settings\.........\Test\Release>test
V_S>strncpy: 625 msec
V_S>my_strncpy: 641 msec

V_S>C:\Documents and Settings\.........\Test\Release>test
V_S>strncpy: 640 msec
V_S>my_strncpy: 625 msec

V_S>Все это на VC++ 7.1 (2003), PIV 3 GHz, 1024 MB

V_S>Хм. В чем преимущество — в упор не понимаю....

попробуй размер буфера побольше сделать, strncpy будет работать медленней, поскольку будет заполнять остаток нулями

char* src = "1234567890123456789012345678901234567890";
char dst[256];
int test_count = 10000000;
int main(int argc, char* argv[]) 
{
    int i;
    clock_t t1,t2;
    printf("test results (strlen = %lu, buf size = %lu, count = %d):\n", strlen(src), sizeof(dst), test_count);
    t1 = clock();
    for(i=0;i<test_count;++i)strncpy(dst, src, sizeof(dst));
    t2 = clock();
    printf("   strncpy: %d\n", (int)(t2-t1));
    t1 = clock();
    for(i=0;i<test_count;++i)my_strncpy(dst, src, sizeof(dst));
    t2 = clock();
    printf("my_strncpy: %d\n", (int)(t2-t1));
    return 0;
}
test results (strlen = 40, buf size = 256, count = 10000000):
   strncpy: 1203
my_strncpy: 390

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

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

S>>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

SC>1. __forceinline. Очень помогает против недальновидности компилятора. Правда MS-specific
SC>2. Убрать register. Смущает

SC>3. Сделать более читабельным код.
SC> вот это:
SC>

while(src_pad--){ if(!(*dst = *src++)) return (dst-begin); ++dst; --dst_size; }

SC> не способствует.

1. MS-specific не надо. Да и функцию такого размера как haszero любой компилятор заинлайнит без вопросов.
2. убрал

3. так лучше?:

// функция проверки наличия нулевого байта в слове
inline bool haszero(size_t x) { return (((x)-~0UL/255)&~(x)&~0UL/255*128) != 0; }
// функция копирования строк с ограничением по размеру буфера (аналог strncpy)
size_t dtl_strncpy(char* dst, const char* src, size_t dst_size)
{
    if(!dst_size) return 0;
    const char* begin = dst; // запоминаем начало, чтобы потом посчитать длину
    if(dst_size > sizeof(size_t)) 
    {
        // вычисляем выравнивание источника и назначения по size_t
        size_t src_pad = (size_t)(src)%sizeof(size_t);
        // если выравнивания источника и назначения относительно size_t равны
        if(src_pad == (size_t)(dst)%sizeof(size_t)) 
        {
            // сначала при необходимости копируем побайтово кусок строки до границы слова
            // dst_size используем как размер остатка буфера
            if(src_pad)
            {
                src_pad = sizeof(size_t)-src_pad;
                dst_size -= src_pad;
                do 
                { 
                    *dst = *src;
                    if(!*src) return (dst-begin); 
                    ++dst; ++src;
                } 
                while(--src_pad);
            }
            // дальше копируем строку пословно - 32 или 64 битными кусками
            while(dst_size > sizeof(size_t) && !haszero(*((const size_t*)src)))
            {
                *((size_t*&)dst)++ = *((const size_t*&)src)++; // слово в слово
                dst_size -= sizeof(size_t);
            }
        }
    }
    // копируем остаток строки посимвольно
    while(--dst_size) 
    { 
        *dst = *src;
        if(!*src) return (dst-begin); 
        ++dst; ++src;
    }
    // исходная строка не влезла в буфер:
    *dst = 0;
    return dst - begin;
}

S>

S>// функция проверки наличия нулевого байта в слове
S>inline bool haszero(size_t x) { return (((x)-~0UL/255)&~(x)&~0UL/255*128) != 0; }
S>

Мои три копейки:
~0UL при компиляции 64 битного кода на разных компиляторах будет разным
0xFFFFFFFF — на Microsoft/Intel компиляторах
0xFFFFFFFFFFFFFFFF — на gcc
size_t — соответственно 64 бита в обоих случаях

Я бы заменил ~0UL на (size_t)(-1)

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

S>>

S>>// функция проверки наличия нулевого байта в слове
S>>inline bool haszero(size_t x) { return (((x)-~0UL/255)&~(x)&~0UL/255*128) != 0; }
S>>

MS>Мои три копейки:
MS>~0UL при компиляции 64 битного кода на разных компиляторах будет разным
MS>0xFFFFFFFF — на Microsoft/Intel компиляторах
MS>0xFFFFFFFFFFFFFFFF — на gcc
MS>size_t — соответственно 64 бита в обоих случаях

MS>Я бы заменил ~0UL на (size_t)(-1)

Ага, спсибо. Просто на Win64 не было возможности проверить.

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

S>попробуй размер буфера побольше сделать, strncpy будет работать медленней, поскольку будет заполнять остаток нулями

Да нет, не влияет.
Microsoft Windows XP [Версия 5.1.2600]
(С) Корпорация Майкрософт, 1985-2001.

C:\Documents and Settings\.........\Test\Release>test
strncpy: 656 msec
my_strncpy: 657 msec

C:\Documents and Settings\.........\Test\Release>test
strncpy: 640 msec
my_strncpy: 657 msec

буфер — 1024 (даже не 256), все остальное — твой код.

Увеличил буфер до 32 К:
Microsoft Windows XP [Версия 5.1.2600]
(С) Корпорация Майкрософт, 1985-2001.

C:\Documents and Settings\...............\Test\Release>test
strncpy: 36656 msec
my_strncpy: 36844 msec

C:\Documents and Settings\...............\Test\Release>test
strncpy: 36703 msec
my_strncpy: 36875 msec

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

V_S>Увеличил буфер до 32 К:
V_S>Microsoft Windows XP [Версия 5.1.2600]
V_S>(С) Корпорация Майкрософт, 1985-2001.

V_S>C:\Documents and Settings\...............\Test\Release>test
V_S>strncpy: 36656 msec
V_S>my_strncpy: 36844 msec

V_S>C:\Documents and Settings\...............\Test\Release>test
V_S>strncpy: 36703 msec
V_S>my_strncpy: 36875 msec

а можно код теста? каков размер копируемой строки относительно буфера?

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

S>>Интересуют предложения по оптимизации.

MS>В свой время Крис Касперски оптимизировал memcpy за счет периодического чтения "вперед".
MS>За счет этого уменьшались простои самого внутреннего кэша процессора, который, кстати, разного размера для разных CPU.

MS>Он приводил очень убедительные результаты сравнения разных реализаций memcpy в свою пользу.

Эти оптимизации перестали работать, начиная с 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 без нужды — неоправданно.

... << RSDN@Home 1.2.0 alpha rev. 655>>

> К>Я имею в виду, что int и size_t — это родные для компилятора типы. Да, они платформенно-зависимы.
> К>int — тип, наиболее удобный для целочисленной арифметики; size_t и ptrdiff_t — достаточные для адресной.
>
> Только вот я не встречал компилятора где sizeof(int) != 4.

Не так давно таких компиляторов было полно

Posted via RSDN NNTP Server 2.1 beta

S>Только вот я не встречал компилятора где sizeof(int) != 4.

На многих сигнальных процессорах (например для TS201) sizeof(int) = 1

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

S>Только вот я не встречал компилятора где sizeof(int) != 4. Та же реализация strncpy с выравниванием по int на 64-битной платформе занчительно уступает реализации с выравниванием по size_t.

Вот упёрся же ты рогом в size_t.
Для IA64 с сегментной моделью sizeof(size_t) должен быть не менее 10. (8 байт — смещение, хранимое в регистрах общего назначения, и 2 байта — селектор сегмента).
Плоская модель — это всего лишь подарок микрософта благодарным прикладным программистам.

Форум-то называется "С++", а не "Intel Pentium"?

... << RSDN@Home 1.2.0 alpha rev. 655>>

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

К>>Плоская модель — это всего лишь подарок микрософта благодарным прикладным программистам.
S>Не подарок микрософта, а механизм страничной трансляции. А сегментная модель памяти, это как раз для форума "Intel Pentium".

Ну раз уж спускаемся до этого уровня — то процессоры с сегментно-страничной памятью — это не только интелы (макинтоши, VAXы, что там ещё было).
А подарок микрософта состоит в том, что прикладных программистов освободили, во-первых, от секса с ручным управлением сегментами, и во-вторых, от недо-гарвардской архитектуры (когда стек, данные и код лежат в разных сегментах). Хорошо известной ещё под досом.

Вот не помню, какую модель предлагает OS/2 warp. Там, кажется, как раз рукоделия приветствовались.

... << RSDN@Home 1.2.0 alpha rev. 655>>

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

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

К>>>Плоская модель — это всего лишь подарок микрософта благодарным прикладным программистам.
S>>Не подарок микрософта, а механизм страничной трансляции. А сегментная модель памяти, это как раз для форума "Intel Pentium".

К>Ну раз уж спускаемся до этого уровня — то процессоры с сегментно-страничной памятью — это не только интелы (макинтоши, VAXы, что там ещё было).
К>А подарок микрософта состоит в том, что прикладных программистов освободили, во-первых, от секса с ручным управлением сегментами, и во-вторых, от недо-гарвардской архитектуры (когда стек, данные и код лежат в разных сегментах). Хорошо известной ещё под досом.

К>Вот не помню, какую модель предлагает OS/2 warp. Там, кажется, как раз рукоделия приветствовались.

Ладно, не суть. В общем, size_t я выбрал потому что этот тип определяет возможности адресации и, как правило, покрывает разрядность процессора, соответственно, оптимален для пословного копирования. А двухкомпонентная адресация и сегментная модель памяти, как я думал, просто наследие 286-х и 16-битной адресации, что упоминается, например, здесь или здесь.

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

S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

Тогда уж можно попробовать поэкспериментировать с
такой штукойтакой штукой

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

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

S>>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

_>Тогда уж можно попробовать поэкспериментировать с
_>такой штукойтакой штукой

_>-)

экспериментировал, бесполезно.

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

S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

Конструктивную критику принимаете? Может Вы где-нибудь уже ответили, но когда пишут "fast strncpy" приводят относительно чего fast? Никаких таблиц сравнения не заметил. В классических изложениях также перед кодом алгоритма дают его основную идею.

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

S>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

Если речь идет о версиях компилятора от
Microsoft VC 8+, то в стандартных библиотеках появился целый набор функций с постфиксом "_s".
В частности, имеется функция strncpy_s, которая описанного выше недостатка не имеет.
Однако есть небольшая понкость — в Debug версии она все же заполняет буффер данными (0xfd).
Это значительно помогает искать многие трудновыявляемые баги. В релизе же работает как и положено — без лишних операций по заполнению.

Здравствуйте, 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 в конец буфера.

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

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

S>>Интересуют предложения по оптимизации.

R>Оптимизация таких вещей — это всегда платформенно-зависимая вещь.
R>Во-первых, тебе надо определиться, для чего ты хочешь применять эту функцию. Варианты: для копирования маленьких областей, для копирования очень больших областей, для всего подряд.
R>Например для копирования очень больших областей на x86 тебе надо применять non-temporal сохранения + non-temporal предвыборку в L1$ + барьер на запись. Смотри описание и гугли по инструкциям MOVNTQ, PREFETCHNTA, SFENCE.

А потом, когда все сделаешь, надо замерить время выполнения приложения, и увидеть что твоя ф-ия копирования занимает меньше 1% времени. и выкинуть ее.

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

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

S>>Предлагаю на растерзание функцию копирования строк, аналог strncpy, без недостатков оной. Не заполняет остаток нулями, всегда в конце вставляет 0. На входе принимает размер буфера назначения, на выходе дает число скопированных символов. Интересуют предложения по оптимизации.

N>Прокомментирую не только по оптимизации

N>Во-первых, интерфейс strncpy() действительно немного неадекватен обычному использованию — дело в том, что эта функция была придумана в Unix именно для заполнения полей фиксированного размера так, чтобы они потом были пригодны для memcmp (а не с ограничением по размеру), поэтому там доливание нулями. Поэтому все тесты, в которых размер приёмника больше размера источника, заведомо неадекватны; сравнивать надо не с классической strncpy(), а с, лучше всего, strcpy_s() или strncpy_s() (ISO drafts, из платформ — последние MSVC). Если же смотреть на приведённые дальше сравнения скоростей, Ваша strncpy заметно проигрывает штатной memcpy(), а это показывает, что таки старания на Си не дают достаточного результата, и ассемблер тут таки прогрессивнее. (Разумеется, если надо так делать. Я не премину повторить, что NUL-terminated strings — зло, и от них надо избавляться при любой возможности.)

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

N>Во-вторых, если strlen(src)>=dst_size, я бы делал не так — буфер заполняется полностью, \0 в него не дописывается, а возвращается dst_size. (Кстати, оригинальная strncpy делает именно так.) Это позволяет немедленно проверять на переполнение; у Вас же не отличить переполнения от полного заполнения буфера. Если кому нужна в таком случае урезанная строка, он может и вручную дописать \0 в конец буфера.

Проверить на переполнение просто — достаточно сравнить с нулем источник, по возвращенному смещению. А если такая проверка не нужна, то надо постоянно дописывать 0, то есть писать в конец буфера, который может быть довольно большим, опять таки cache latency.

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

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

S>>Интересуют предложения по оптимизации.

R>Оптимизация таких вещей — это всегда платформенно-зависимая вещь.
R>Во-первых, тебе надо определиться, для чего ты хочешь применять эту функцию. Варианты: для копирования маленьких областей, для копирования очень больших областей, для всего подряд.
R>Например для копирования очень больших областей на x86 тебе надо применять non-temporal сохранения + non-temporal предвыборку в L1$ + барьер на запись. Смотри описание и гугли по инструкциям MOVNTQ, PREFETCHNTA, SFENCE.
R>Во-вторых, погляди, не можешь ли ты наложить какие-то дополнительные ограничения на входные данные.
R>Например ты можешь потребовать, что бы обе области были выровнены на 16 байт + размер памяти под области тоже кратен 16 байтам. Тогда ты можешь не обрабатывать отдельным образом начало и конец области, а сразу и до конца шпарить по 16 байт. Я думаю, это должно дать выигрыш для маленьких областей, т.к. функция будет маленькой и простой и без дополнительных ветвлений.
R>Если же ты хочешь функцию портируемую, для всех размеров областей и без дополнительных ограничений на входные данные, то тут и никакого простора для оптимизаций нет. Остаётся только оставить функцию как есть и надеяться на оптимизатор компилятора. Но тут ты скорее всего всегда будешь отставать от библиотечной memcpy() и от intrinsic'а компилятора.

R>

Нужна была именно портируемая функция для любых размеров. Оптимизация интересна в плане С. memcpy конечно быстрей, но тут речь всё таки о строках, memcpy на 0 не проверяет. А вот дополнительные реализации, не требующие проверки на выравнивание источника и/или назначения — хорошая мысль.

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

N>>Во-вторых, если strlen(src)>=dst_size, я бы делал не так — буфер заполняется полностью, \0 в него не дописывается, а возвращается dst_size. (Кстати, оригинальная strncpy делает именно так.) Это позволяет немедленно проверять на переполнение; у Вас же не отличить переполнения от полного заполнения буфера. Если кому нужна в таком случае урезанная строка, он может и вручную дописать \0 в конец буфера.
S>Проверить на переполнение просто — достаточно сравнить с нулем источник, по возвращенному смещению.

Это значительно более громоздко писать, чем проверку вида if(strlcpy(dst,src,size)>=size){типа всё плохо;}

S> А если такая проверка не нужна, то надо постоянно дописывать 0, то есть писать в конец буфера, который может быть довольно большим, опять таки cache latency.

"Если такая проверка не нужна" — случай, когда надо просто усечь строку без всяких других последствий — крайне редок. Даже если пишешь отладочный лог (а я с ходу что-то не найду другое применение такому усечению), надо как-то указать, что строка закончилась раньше, чем допустимое место в записи в логе. А вот нормальная проверка — нужна постоянно.

	От:	Сергей Мухин
	Дата:	15.01.08 09:32
	Оценка:	1 (1)

От:	Critical Error	ICQ: 123736611
Дата:	18.01.08 13:31
Оценка:	1 (1)

	От:	sokel
	Дата:	15.01.08 11:42
	Оценка:	-1

	От:	sokel
	Дата:	15.01.08 15:33
	Оценка:	-1

От:	remark	http://www.1024cores.net/
Дата:	19.01.08 13:55
Оценка:	+1

От:	netch80	http://netch80.dreamwidth.org/
Дата:	19.01.08 14:02
Оценка:

	От:	MShura
	Дата:	14.01.08 12:23
	Оценка:

	От:	Кодт
	Дата:	14.01.08 12:24
	Оценка:

	От:	Кодт
	Дата:	14.01.08 14:25
	Оценка:

	От:	shrecher
	Дата:	14.01.08 14:41
	Оценка: