Реализация 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 или int или, если хотите, еще более широкий тип данных.

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

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

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

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

Answer 5

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

Код Psuedo:

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 6

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

Answer 7

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

• отбрасывает константу.
• работает ли этот оператор возврата?unsigned char - unsigned char = signature int?

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

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

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

Answer 8

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