Использование 64-битных типов? - PullRequest
1 голос
/ 12 января 2011

Я пишу некоторые хеш-функции для компилятора и часто использую тип данных __int64.Компилятор предназначен для поддержки (и пока поддерживается) в разных ОС.Я знаю, что __int64 - это тип, который может быть скомпилирован большинством основных компиляторов C ++ для моих целевых систем, так что это не проблема.Я использую хеш-функции, чтобы сделать большие строки символов меньше и быстрее сравнивать, и они чудесно работают на 64-битных ОС;но будет ли достаточно значительное снижение производительности на 32-битных ОС, чтобы отменить преимущества?Я мог бы использовать 32-битные целые числа, но тогда это значительно уменьшило бы эффективность хеш-функций.

Редактировать: Это пользовательский код и очень простой.Первая хеш-функция генерирует уникальный 64-разрядный тип int из 12 буквенно-цифровых (включая подчеркивание) символов.Затем класс обрабатывает хэши более 12 символов, создавая связанные с адресами списки 64-битных хэшей и перегружая операторы сравнения.Перегруженные сравнения замыкаются и сравниваются по списку адресов.Я провел тесты на своей машине, чтобы сравнить скорость случайного генерирования больших хешей (100–300 символов) по сравнению с самими собой (наихудший случай), и она оказалась быстрее, чем сравнение строкЧтобы лучше имитировать накладные расходы на генерацию хэшей, я также провел сравнительные тесты предварительно сгенерированных больших хэшей, сравнивающих их с собой.Это все работает с отключенной оптимизацией кода.С ~ 1 млрд сравнений хешей против ~ 1 млрд сравнений строк хеш занимал около 16% времени.Это было все в среде 64, хотя.У меня нет 32-битной машины для запуска тестов с

Ответы [ 4 ]

2 голосов
/ 12 января 2011
Целые числа размером

64 бита существенно не медленнее в 32-битной архитектуре x86.Они не такие быстрые, как 32-битные, очевидно, но не намного медленнее.Нельзя безрассудно использовать 64-битное int для хэшей, независимо от x86 или x64.Дополнительные издержки, вероятно, будут минимальными по сравнению, скажем, с парой ненужных динамических распределений или неудачных алгоритмов.

1 голос
/ 12 января 2011

Я не думаю, что сравнение четырех 32-битных переменных будет быстрее, чем сравнение двух 64-битных переменных, так как я предполагаю, что компилятор сгенерирует самый быстрый код: если ваш процессор не поддерживает 64-битные операции, ваш Компилятор сгенерирует код, который сравнивает его в два этапа, как вы это делаете вручную.
Это, конечно, зависит от вашего компилятора.


В любом случае, есть другие инструменты, которые сделают ваши сравнения еще быстрее, но которые не везде доступны, например, векторные операции (предоставляемые расширениями SSE), которые позволяют сравнивать даже 8 * 4 байта одновременно.

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

0 голосов
/ 12 января 2011

Все хеш-функции, которые я использовал, возвращают значение в массиве байтов (uchar), чтобы избежать вашей проблемы.

0 голосов
/ 12 января 2011

Вы уверены, что это значительно уменьшит эффективность хэш-функции?Вы проводили тесты?Конечно, 64-битный хэш лучше, чем 32-битный, если (i) количество хэшированных элементов значительно больше 2 ^ 16 и (ii) вычисление 64-битного хеша обходится дешево.Какой из (i) или (ii) (или оба) верен в вашем случае?Если важна производительность, вы можете использовать различные хеш-функции в зависимости от базовой операционной системы.В противном случае я бы сказал: написать 32-разрядную версию и 64-разрядную версию;опробуйте оба в 64-битной и 32-битной системах;и ты увидишь, стоит ли перебивать кишку.

...