Реализация memcmp

Question

Ниже приводится реализация memcmp для Microsoft CRT:

int memcmp(const void* buf1,
           const void* buf2,
           size_t count)
{
    if(!count)
        return(0);

    while(--count && *(char*)buf1 == *(char*)buf2 ) {
        buf1 = (char*)buf1 + 1;
        buf2 = (char*)buf2 + 1;
    }

    return(*((unsigned char*)buf1) - *((unsigned char*)buf2));
}

Он в основном выполняет побайтовое сравнение.

Мой вопрос состоит из двух частей:

1. Есть ли причина не менять это на int путем сравнения int, пока count < sizeof(int), а затем сделать побайтовое сравнение для того, что остается?
2. Если бы я сделал 1, есть ли потенциальные / очевидные проблемы?

Примечания: я вообще не использую ЭЛТ, поэтому мне все равно нужно реализовать эту функцию. Я просто ищу совет о том, как правильно его реализовать.

Answer 1

При желании вы можете сделать это как сравнение по типу int или как еще более широкий тип данных.

Две вещи, которых вы должны остерегаться (как минимум), это выступ в начале, а также в конце, и то, отличаются ли выравнивания между двумя областями.

Некоторые процессоры работают медленнее, если вы обращаетесь к значениям, не следуя их правилам выравнивания (некоторые даже вылетают, если вы попробуете это).

Таким образом, ваш код может сделать char сравнения до int область выравнивания, то int сравнения, то char Снова сравнения, но, опять же, выравнивание обеих областей, вероятно, будет иметь значение.

Стоит ли такая дополнительная сложность кода для экономии, которую вы получите, зависит от многих факторов, находящихся вне вашего контроля. Один из возможных методов - обнаружить идеальный случай, когда обе области выровнены одинаково, и сделать это быстрым способом, в противном случае просто сделать это посимвольно.

Answer 2

Оптимизация, которую вы предлагаете, очень распространена. Самая большая проблема будет в том случае, если вы попытаетесь запустить его на процессоре, который не допускает выравниваемый доступ для чего-либо, кроме одного байта, или медленнее в этом режиме; Семейство x86 не имеет этой проблемы.

Это также более сложно, и, следовательно, более вероятно, содержит ошибку.

Answer 3

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

Answer 4

Другая идея состоит в том, чтобы оптимизировать процессорный кеш и выборку. Процессоры любят извлекать большие куски, а не отдельные байты в случайное время. Хотя внутренняя работа уже может объяснить это, в любом случае это было бы хорошим упражнением. Всегда профиль, чтобы определить наиболее эффективное решение.

Код Псуэдо:

while bytes remaining > (cache size) / 2 do // Half the cache for source, other for dest.
  fetch source bytes
  fetch destination bytes
  perform comparison using fetched bytes
end-while
perform byte by byte comparison for remainder.

Для получения дополнительной информации поищите в Интернете "Data Driven Design" и "Data ориентированное программирование".

Некоторые процессоры, такие как семейство ARM, допускают условное выполнение инструкций (в 32-битном режиме, не для большого пальца). Процессор извлекает инструкции, но выполняет их только при соблюдении условий. В этом случае попробуйте перефразировать сравнение в терминах логических назначений. Это также может уменьшить количество используемых веток, что повышает производительность.

Смотрите также раскрутка петли.
Смотрите также ассемблер.

Вы можете получить большую производительность, адаптируя алгоритм к конкретному процессору, но потеряв в области переносимости.

Answer 5

Если вы сравниваете как int, вам нужно будет проверить выравнивание и проверить, делится ли count на sizeof(int) (чтобы сравнить последние байты как char).

Answer 6

Это действительно их реализация? У меня есть другие проблемы, кроме как не делать это интуитивно:

• отбрасывать константу.
• этот возвратный оператор работает? char без знака - без знака char = со знаком int?

int за раз работает только в том случае, если указатели выровнены, или если вы можете прочитать несколько байтов с начала каждого, и они оба все еще выровнены, поэтому, если оба равны 1 до границы выравнивания, вы можете прочитать один символ каждого из них, затем перейти int-at-a-time, но если они выровнены по-разному, например, один выровнен, а другой нет, то сделать это невозможно.

memcmp наиболее неэффективен (то есть занимает больше всего времени), когда они действительно сравнивают (он должен идти до конца), а данные длинные.

Я бы не стал писать свои собственные, но если вы собираетесь сравнивать большие порции данных, вы можете сделать такие вещи, как обеспечение выравнивания и даже заполнение концов, а затем делать пословные слова, если хотите.

Answer 7

Код, который вы нашли, является просто отладочной реализацией memcmpОн оптимизирован для простоты и удобочитаемости, а не для производительности.

Реализация встроенного компилятора является специфичной для платформы и достаточно умной, чтобы генерировать инструкции процессора, которые сравнивают dwords или qwords (в ​​зависимости от целевой архитектуры) по возможности сразу. Кроме того, внутренняя реализация может немедленно вернуться, если оба буфера имеют одинаковый адрес (buf1 == buf2), Эта проверка также отсутствует в реализации отладки.

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

• Каково минимальное гарантированное выравнивание буфера?
• Можете ли вы прочитать какие-либо байты заполнения после конца буфера, не вызывая нарушения прав доступа?
• Могут ли параметры буфера быть идентичными?
• Может ли размер буфера быть 0?
• Вам нужно только сравнить содержимое буфера на равенство? Или вам также нужно знать, какой из них больше (возвращаемое значение < 0 или> 0)?
• ...

Если производительность вызывает беспокойство, я предлагаю написать процедуру сравнения в сборке. Большинство компиляторов дают вам возможность увидеть список сборок, которые они генерируют для источника. Вы можете взять этот код и адаптировать его под свои нужды.

Answer 8

Многие процессоры реализуют это как одну инструкцию. Если вы можете гарантировать работающий на нем процессор, он может быть реализован с помощью одной строки встроенного ассемблера.