Сравнение массивов больших размеров

[e2e4]

ewert в сообщении #250419 писал(а):

e2e4 в сообщении #250412 писал(а):

я не ожидал что с strncmp все так плохо,

Так она ведь делает в цикле не одну проверку, как memcmp (на счётчик цикла), а три -- в дополнение ещё и проверяет, не наткнулись ли мы на конец хотя бы одной из двух строк.

А, ну да, точно. Забыл .

[Maslov]

e2e4 в сообщении #250412 писал(а):

я не ожидал что с strncmp все так плохо

Исходный код strncmp интеловского процессора выглядит просто пугающе

Используется синтаксис C

/***
*int strncmp(first, last, count) - compare first count chars of strings
*
*Purpose:
*   Compares two strings for lexical order.  The comparison stops
*   after: (1) a difference between the strings is found, (2) the end
*   of the strings is reached, or (3) count characters have been
*   compared.
*
*Entry:
*   char *first, *last - strings to compare
*   unsigned count - maximum number of characters to compare
*
*Exit:
*   returns <0 if first < last
*   returns  0 if first == last
*   returns >0 if first > last
*
*Exceptions:
*
*******************************************************************************/

int __cdecl strncmp (
    const char * first,
    const char * last,
    size_t count
)
{
    size_t n = 0;

    if (!count)
        return(0);

    if( count >= 4 )
    {
        /* unroll by four */
        for (; n < count-4; n += 4)
        {
            first += 4;
            last += 4;

            if (*(first - 4) == 0 || *(first - 4) != *(last - 4))
            {
                return (*(unsigned char *)(first - 4) - *(unsigned char *)(last - 4));
            }

            if (*(first - 3) == 0 || *(first - 3) != *(last - 3))
            {
                return (*(unsigned char *)(first - 3) - *(unsigned char *)(last - 3));
            }

            if (*(first - 2) == 0 || *(first - 2) != *(last - 2))
            {
                return (*(unsigned char *)(first - 2) - *(unsigned char *)(last - 2));
            }

            if (*(first - 1) == 0 || *(first - 1) != *(last - 1))
            {
                return (*(unsigned char *)(first - 1) - *(unsigned char *)(last - 1));
            }
        }
    }

    /* residual loop */
    for (; n < count; ++n)
    {
        if (*first == 0 || *first != *last)
        {
            return (*(unsigned char *)first - *(unsigned char *)last);
        }
        ++first;
        ++last;
    }

    return 0;
}
 

-- Пт окт 09, 2009 16:28:42 --

А memcmp сразу дергает RtlCompareMemory, а она простенькая совсем:

507 /******************************************************************************
508  *  RtlCompareMemory   [NTDLL.@]
509  *
510  * Compare one block of memory with another
511  *
512  * PARAMS
513  *  Source1 [I] Source block
514  *  Source2 [I] Block to compare to Source1
515  *  Length  [I] Number of bytes to compare
516  *
517  * RETURNS
518  *  The length of the first byte at which Source1 and Source2 differ, or Length
519  *  if they are the same.
520  */
521 SIZE_T WINAPI RtlCompareMemory( const VOID *Source1, const VOID *Source2, SIZE_T Length)
522 {
523     SIZE_T i;
524     for(i=0; (i<Length) && (((const BYTE*)Source1)[i]==((const BYTE*)Source2)[i]); i++);
525     return i;
526 }

[e2e4]

e2e4 писал(а):

1. Пускай каждая строка содержит по 256 символов
2. Пускай расхождение находится (если находится) всегда на последнем символе строки (уж невезет, так невезет ).
3. Размер первого массива: 6,4 Мб; Размер второго массива: 4 Мб. Легко помещаются в ОЗУ, а на современных процессорах еще и большая их часть поместится в L2 - кеше процессора. Таким образом, временем доступа пренебрегаем.
4. Считаем кол-во операций сравнения: .
5. Берем относительно современный (но и не топовый) одноядерный процессор Intel Pentium IV@3.2 GHz и смотрим, что у него около 10 MIPS, т.е. около 10 миллионов целочисленных операций в сек. Предполагаем, что операция сравнения не займет более 1-й целочисленной операции,

e2e4 писал(а):

Итого имеем 11 сек для исходной задачи (прикидочно)

e2e4 писал(а):

Результаты:
2. Массив 26 000 х 16 000 выполняется за 3,3 мин

Хотелось бы пояснить результат. Конечно, мой процессор послабее, чем Intel Pentium IV@3.2 GHz на 35%. Но это все ерунда. Основная моя ошибка - конечно, не был сделан учет на выполнение операций закгрузки в регистры, записи результатов обратно в память, индексацию строк. Плюс некоторые операции выполняются дольше, чем за 1 такт. Плюс прочие накладные расходы. Итого имеем $\cfrac{3,3[min] * 60[\frac{sec}{min}]}{11[sec]*\frac{10[MIPS]}{7.4[MIPS]} } = 13,3$ в среднем операций требуется на сравнение одного символа на данной архитектуре компьютера.

-- Пн окт 12, 2009 11:30:24 --

Maslov писал(а):

Исходный код strncmp интеловского процессора выглядит просто пугающе

Вопрос: а разве библиотечные функции, входящие в поставки си-компилятора, не пишутся обычно сразу на асссемблере?
Предложение: если есть желание, можно завести отдельную тему и попробовать написать более удачную функцию strncmp на Си (challenge Микрософту так сказать), только обязательно сначала выработать критерии оценки "оптимальности" функции и методику тестирования. Что-то мне подсказывает, что более оптимально вряд ли получится, разве что последний "остаточный" цикл тоже развернуть.

[Lotos]

Мне нравится развитие этой темы в область Си. А если все-таки не Си, у меня C# на платформе .Net.

[Maslov]

e2e4 в сообщении #251074 писал(а):

Вопрос: а разве библиотечные функции, входящие в поставки си-компилятора, не пишутся обычно сразу на асссемблере?

Что-то на ассемблере пишется, что-то на C/C++. В Visual Studio в каталоге VC\crt\src можно посмотреть что и как.

e2e4 в сообщении #251074 писал(а):

Что-то мне подсказывает, что более оптимально вряд ли получится

Я тоже так думаю.

[e2e4]

Lotos писал(а):

Мне нравится развитие этой темы в область Си. А если все-таки не Си, у меня C# на платформе .Net.

А Вы еще не решили эту простецкую задачу? .