Re: Мой эксперимент (strncpy, my_strncpy, memcpy) - C/C++

Предлагаю на растерзание функцию копирования строк, аналог 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;
}

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>>

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>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
	Дата:	14.01.08 10:38
	Оценка:

	От:	sokel
	Дата:	14.01.08 11:59
	Оценка:

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

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

	От:	sokel
	Дата:	14.01.08 12:37
	Оценка:

	От:	djs_
	Дата:	15.01.08 01:01
	Оценка:

	От:	Vlad_SP
	Дата:	15.01.08 08:18
	Оценка: