Самая эффективная хеш-функция Unicode для Delphi 2009
Используйте это, это работает для меня
<integer name="custom_wrap_content">-2</integer>
<dimen name="horizontal_border_height">@integer/custom_wrap_content</dimen>
4 ответа
ASM output is not a good indication of algorithm speed. Also, from what I can see, the two pieces of code are doing almost the identical work. The biggest difference seem to be the memory access strategy and the first is using roll-left instead of the equivalent set of instructions (shl | shr -- most higher-level programming languages leave out the "roll" operators). The latter may pipeline better than the former.
ASM optimization is black magic and sometimes more instructions execute faster than fewer.
To be sure, benchmark both and pick the winner. If you like the output of the second but the first is faster, plug the second's values into the first.
rol edx,5 { edx := (edx shl 5) or (edx shr 27)... }
Note that different machines will run the code in different ways, so if speed is REALLY of the essence then benchmark it on the hardware that you plan to run the final application on. I'm willing to bet that over megabytes of data the difference will be a matter of milliseconds -- which is far less than the operating system is taking away from you.
PS. I'm not convinced this algorithm creates even distribution, something you explicitly called out (have you run the histograms?). You may look at porting this hash function to Delphi. It may not be as fast as the above algorithm but it appears to be quite fast and also gives good distribution. Again, we're probably talking on the order of milliseconds of difference over megabytes of data.
There has been a bit of discussion in the Delphi/BASM forum that may be of interest to you. Have a look at the following:
http://forums.embarcadero.com/thread.jspa?threadID=13902&tstart=0
Некоторое время назад мы провели небольшое красивое соревнование, улучшив хэш под названием " MurmurHash "; Цитата из Википедии:
Он известен тем, что является исключительно быстро, часто в два-четыре раза быстрее чем сопоставимые алгоритмы, такие как FNV, поиск Дженкинса3 и Хси SuperFastHash с отличным распределение, лавинное поведение и общая устойчивость к столкновениям.
Вы можете загрузить материалы для этого конкурса здесь .
Мы узнали, что иногда оптимизации не улучшают результаты на каждом процессоре. Мой вклад был изменен так, чтобы он хорошо работал на AMD, но работал не так хорошо на Intel. Случилось и обратное (оптимизации Intel работают неоптимально на AMD).
Итак, как сказал Таллджо: измеряйте свои оптимизации, так как они могут действительно нанести ущерб вашей производительности!
В качестве примечания: I не согласен с Ли; Delphi - хороший компилятор и все такое, но иногда я вижу, что он генерирует неоптимальный код (даже при компиляции со всеми включенными оптимизациями). Например, я регулярно вижу, как он очищает регистры, которые уже были очищены всего двумя или тремя операторами ранее. Или EAX помещается в EBX, только для того, чтобы его сдвинуть и вернуть в EAX. Что-то в этом роде. Я просто догадываюсь, но ручная оптимизация такого кода наверняка поможет в трудных местах.
Но прежде всего; Сначала проанализируйте свое узкое место, затем посмотрите, можно ли использовать лучший алгоритм или структуру данных, затем попробуйте оптимизировать код паскаля (например: уменьшить выделение памяти, избежать подсчета ссылок, финализации, попробовать / наконец, попробовать / исключить блоки и т. Д.), а затем, только в качестве последнего средства, оптимизируйте ассемблерный код.
Я написал две ассемблерные "оптимизированные" функции в Delphi или несколько реализовал известные быстрые алгоритмы хеширования как в точно настроенном паскале, так и в Borland Assembler. Первая была реализацией SuperFastHash , а вторая была реализацией MurmurHash2, вызванной запросом Томми Прами в моем блоге о переводе моей версии C # в реализацию Pascal. Это породило обсуждение, продолжившееся на форумах Embarcadero Discussion BASM , что в итоге привело к примерно 20 реализациям (проверьте последний набор тестов ), которые в конечном итоге показали, что выбрать будет сложно. лучшая реализация из-за большой разницы в времени цикла на инструкцию между Intel и AMD.
Итак, попробуйте один из них, но помните, получение максимальной скорости каждый раз, вероятно, означало бы изменение алгоритма на более простой, что повредило бы вашему дистрибутиву. На точную настройку реализации уходит много времени, и лучше создать хороший набор для проверки и тестирования, чтобы проверить ваши реализации.