Сверхбыстрое хэширование (hashing)

← →
textExpanser © (2007-08-12 17:02) [0]

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

ED2K (MD4) / MD5 / SHA-1 / CRC32 / Tiger-128 и Tiger-192 (TTH)

У меня уже есть эти библиотеки, но они не оптимизированы по скорости.
Думаю, что лучше что-то типа ASM/MMX/SSE/SSE2. Или на худой конец просто эффективная реализация алгоритма.

Посоветуйте библиотеки или компоненты для Delphi, или DLL / ActiveX. Можно и для C/С++ чтобы DLL сделать.

Если еще что посоветуете в связи с задачей ускорения, то тоже интересно.

← →
textExpanser © (2007-08-12 19:07) [1]

Не обязательно все-в-одном. Можно даже для каждого из хэшей отдельную библиотеку или компонент.

← →
Eraser © (2007-08-13 10:49) [2]

> textExpanser © (12.08.07 17:02)

а как насчет MS Crypto API?

← →
Котик Б (2007-08-13 11:05) [3]

А какой критерий быстрости ?
Есть колличественные показатели - или оперируем субъективными ощущениями ?

У меня дома StrongDC+ хеширует со скоростью 30-50Мб/с - это достаточно быстро ?

А из коммандной строки запускать утилитку md5hash пробовали ?

← →
textExpanser © (2007-08-14 09:14) [4]

Как можно быстрее - в идеале желательно такой уровень оптимизации, как ассемблер, MMX/SSE/SSE2. Я просто знаю, что те алгоритмы, которые у меня - они работают, но практически не оптимизировались. И все это занимает много времени.

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

MS Crypto API в каких версиях работает и какие жэши может вычислять из этих:
ED2K (MD4) / MD5 / SHA-1 / CRC32 / Tiger-128 и Tiger-192 (TTH) ?

Желательно встроенные библиотеки, чтобы по мере чтения файла, можно было _параллельно_ делать все вычислять и делать.

← →
@!!ex © (2007-08-14 09:24) [5]

А каким боком здесь SSE/SSE2/SSE3 - они же для чисел с плавающей точкой...
Да и MMX не представляю как можно здесь заюзать...

← →
tesseract © (2007-08-14 10:18) [6]

> Да и MMX не представляю как можно здесь заюзать...

Хз, всё можно заюзать, но нужно ли.

← →
homm © (2007-08-14 10:27) [7]

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

Свистите. Сорри.

← →
DrPass © (2007-08-14 10:57) [8]

> как насчет MS Crypto API?

Он, собссно, представляет собой API, а не алгоритмы шифрования/хеширования. Скорость работы будет целиком и полностью зависеть от используемого криптопровайдера, которых для CryptoAPI написано великое множество...

← →
bobby (2007-08-14 13:23) [9]

Сходи на форум к Касперскому, может там кто-нибудь подскажет:), они этим занимаются начиная с 5-й версии

← →
Eraser © (2007-08-14 16:00) [10]

> DrPass © (14.08.07 10:57) [8]

думаю для указанной задачи автору хватит тех, что начиная с 2k по-умолчанию поставляются. А на скороть работы стандартных криптопровайдеров не жалуюсь, в своё время тестировал разные библиотеки, криптоАпи оказался чуть ли не самым быстрым, да и реализация доверия вызывает больше, чем самопальные поделки.

← →
textExpanser © (2007-08-15 12:16) [11]

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

Eraser & DrPass:
А эти криптопровайдеры где взять? Они должны быть установлены на машине или мне нужно будет их самому инсталлировать и таскать с программой? Они в виде DLL или ActiveX? И если их нельзя с программой легко распространять, то как гарантировать, что на машине будет установлен нужный криптопровайдер, и что он будет оптимизирован по скорости? Спрашиваю не для того, чтобы поиронизировать, а потому, что не разбираюсь в MS Crypto API. Например, для вычисления ed2k есть?

← →
homm © (2007-08-15 12:19) [12]

> [11] textExpanser © (15.08.07 12:16)

Читаем дословно: «придется открывать файл, а это такая задержка будет». Пример, подтверждающую написаную здесь чушь можно? Открытие файла — очень быстрая операция.

← →
homm © (2007-08-15 12:23) [13]

> Вы хотя бы представляете себе разницу в скорости операций
> с диском и операций в памяти?

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

← →
Eraser © (2007-08-15 12:53) [14]

> textExpanser © (15.08.07 12:16) [11]

базовые криптопровайдеры есть в системе, начиная с win9x, но расширеный набор алгоритмов появился только начиная с 2k. Всё по-умолчанию присутствует в системе, никаких доп. библиотек не надо, если конечно не планируется использовать какие-либо экзотические алгоритмы.
http://rsdn.ru/article/crypto/cryptoapi.xml

← →
textExpanser © (2007-08-16 14:05) [15]

homm :
Открытие файла или чтение файла, как и все дисковые операции - ОЧЕНЬ МЕДЛЕННЫЕ операции. Стыдно этого не знать программисту. Для того и придумали кеш, кстати, если вы не в курсе. Но все равно, даже если файл уже закеширован ОС, то обращение к нему в разы медленнее, чем обращение к буферу в памяти или массиву байт.

Сейчас у меня реализовано так: файлы читаются последовательно в память большими кусками. Этот буфер с данными скармливается всем алгоритмам хэширования и обработки файла, которые получается работают параллельно (не в потоках, а просто по очереди обрабатывают одну порцию данных; ведь хеширующему алгоритму не обязательно сразу весь файл давать). За счет этого практически нет задержек и накладок из-за файловой системы (ну только скорость чтения файла). Чтение файла оптимизировано.

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

Eraser:
Спасибо. Мне конечно и под Win9x надо, но можно хотя-бы имеющиеся там алгоритмы использовать.

← →
homm © (2007-08-16 14:18) [16]

> Открытие файла или чтение файла

Открытие файла это не «или» чтение файла. Это разные вещи. Так что прежде чем говорить открытие файла, прожуй сам, и подумай, может ты хотел сказать чтение?

> ведь хеширующему алгоритму не обязательно сразу весь файл
> давать

Это от реализации хеширующей функции зависит.

← →
Котик Б (2007-08-16 14:45) [17]

Просто в шоке от таких специалистов как textExpanser © :(

После выхода W2K я повыкидывал практически все оптимизации по чтению файлов, оставив разве что MMF для слишком больших...

Оптимизация по кешированию файлов в нынешней винде настолько хорошая - что практически без разницы как читать файл:
что так
for i := 0 to FileSize-1 do Read(f, ch);
что так
BlockRead(f, FileSize);
Разница в большинстве случаев составляет не более 10% - иногда даже первый вариант быстрее... Про операцию ОТКРЫТИЯ файла вообще молчу...

Заметим, что гражданин textExpanser © не привёл НИ ОДНОЙ цифры желаемого быстродействия, и все его слова про тормознутость дисковых операций не подтвеждены НИЧЕМ. Судя по всему еще один великий теоретик.
Ассемблер ему подавай, да тот же древний С в данном случае ничуть не хуже. И рекомендуемая мной утилитка md5hash c размером около 50К думаю написана именно на С, а при использовании Intel C compiler тут вам и MMX и SSE :)

← →
homm © (2007-08-16 15:03) [18]

> [17] Котик Б (16.08.07 14:45)

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

← →
textExpanser © (2007-08-16 18:53) [19]

Котик Б:
10% - это много, но на самом деле еще больше. А о накладных расходах по вызову функций API ты подумал? ЗАЧЕМ несколько раз читать один и тот же файл, когда можно прочитать его 1 раз? И как ты будешь кешировать файл размером 1-5 гигабайт? Такой файл целиком в кеш не поместится.
Я вообще-то программирую еще с ДОСа и не надо мне рассказывать про чудеса технологий, я знаю как, что и с какой скоростью работает, включая кэш Windows.
А использование таких приемов как запуск внешней утилиты командной строки для - это один из самых кривых приемов программирования, за который нужно отрывать руки программисту.
Кстати, на Си можно написать так, что будет медленнее, чем на Basic. Не язык главное, а алгоритм. А уж писать на ассемблере не оптимизированный код, дающий преимущества перед c/pascal - просто глупо, поэтому я и упомянул про ассемблер, ты сам не додумался?

homm:
ну хоть ты понял
только к словам не придирайся ;)

← →
homm © (2007-08-16 21:41) [20]

> А использование таких приемов как запуск внешней утилиты
> командной строки для - это один из самых кривых приемов
> программирования, за который нужно отрывать руки программисту.

… писавшему в виндовс вызов этих самых утилит, потому как насколько мне известно, в линухе такие вещи делаются довольно часто, и дурным тоном не считаются. Хотя возможно и всем линуксойдом руки нужно оторвать :)

← →
textExpanser © (2007-08-17 01:30) [21]

Ну, там совсем другая концепция системы.
И скорость там не главное, а главное - красота врхитектуры. Которую можно понять ознакомившись с некоторыми элегантнейшими алгоритмами на Си. Так что Юникс - это порождение эстетов от Си.
Правда, из-за слишком уж большой гибкости, благодаря которой получаются такие академически элегантные решения алгоритмов, Си и страдает - награда за гибкость куча трудно выявляемых ошибок в программах, в чем Паскаль и выигрывает(-вал?) у C/C++.

← →
Котик Б (2007-08-17 15:42) [22]

> textExpanser © (16.08.07 18:53) [19]
> Котик Б:
> 10% - это много, но на самом деле еще больше. А о накладных
> расходах по вызову функций API ты подумал?

Подумал, подумал...

Как говорил наш преподаватель информатики: "Учитесь мыслить экономически"

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

По поводу ужаса, который вы испытываете при загрузке файла 1-5 гиг...
1. Современные материнки легко поддерживают до 16G.
2. Планка DDR2 6400 2G стоит сейчас $120. Четыре планки 4*$120=$480 соответственно...

В итоге примерно за $1000 получаем машинку, с лёгкостью жующую задачи по обработке таких больших файлов.
Для людей, работающих с файлами на 5G - $1000 обычно не проблема...

Так что думайте...

← →
homm © (2007-08-17 15:57) [23]

> Для людей, работающих с файлами на 5G - $1000 обычно не
> проблема...

А если ты сможешь написать программу, коотрая будет работать на компе за $400, 600 баксов пойдет тебе в карман.

Так что думайте...

← →
Котик Б (2007-08-17 16:08) [24]

> homm © (17.08.07 15:57) [23]
> > Для людей, работающих с файлами на 5G - $1000 обычно не
> > проблема...
>
> А если ты сможешь написать программу, коотрая будет работать
> на компе за $400, 600 баксов пойдет тебе в карман.

В одиночных случаях не пишеться программа а решается задача - чувствуешь разницу ?

А об чём можно говорить - если с 12.08.07 17:02 т.е. уже пятый день !!! автор ветки так и не озвучил конкретного быстродействия своей гениальной программы, работающей сразу со всеми алгоритмами хеширования...

Я думаю - если бы действительно была важна скорость - давно бы уже купили плату аппаратной акселерации хеш функций, с отдельным контроллером и возможностью прошивки микрокода. Такие к примеру применяются в системах безопасности...

Но проблема в том, что эти платы имеют конкретную спецификацию - а наш автор говорит о задаче абстрактно !!!

← →
Piter © (2007-08-17 16:14) [25]

textExpanser что-то гонит. Про открытие файла - это вообще шедевр.

Экономит на вызове функций для чтения, офигеть. Но при этом по десятку раз для разных кусков вызывает функции хеширования. Неэкономно, однако ;)

Что касается кусков - так у каждого алгоритма свой метод, надо их детально изучить, чтобы знать какого размера куски оптимально "скармливать". Иначе эти алгоритмы начинают что-то выравнивать, некоторые по-моему не считают каждый байт, а учитывают только каждый 10-ый байт (для скорости), ну и куча заморочек в таком роде. так что своим супер алгоритмом автор не исключено только сильно затормаживает процесс хеширования.

Ну и конечно никаких цифр не приведено, ничего не понятно, какая скорость нужна? Какую скорость достиг уже? Насколько эффективны примененные ходы - неизвестно.

Ну с таким подходом можно только удачи пожелать...

Сорри за off, но вот это
> homm © (17.08.07 15:57) [23]
> А если ты сможешь написать программу, коотрая будет работать
> на компе за $400, 600 баксов пойдет тебе в карман.

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

Котик Б :
Ну чего быть таким упрямым?.. ;)
По делу: где в задаче говорилось, что программа будет работать на какой-то выделенной под нее машине? Где говорилось, что она будет работать в пределах какой-то организации? Наборот - наличие хэша ed2k однозначно говорит, что программа связана с Интернет и p2p сетями.
Кстати, уже второй из наиболее отвратительных приемов программирования, за которые стоит отрывать руки - думать, что файл всегда может поместься в память, и закладываться под жесткие завышенные технические требования.

Piter :
Вот сразу видно человека, который всегда программировал только под Windows и никогда его программы не сталкивались с ограниченностью жестких дисков в скорости.
А что касается алгоритмов хэширования, которые работают через 10 байт - сильно сомневаюсь, хотя в алгоритмы эти не вникал. Иначе это уж очень ненадежное хэширование выйдет.
А про скорость - максимально возможная на любой машине (от, скажем, Pentium90/64MB/Win98). Нельзя сказать заранее какая будет скорость, но чем быстрее будет работать, тем лучше. Сейчас пока на 4-м пне работает не очень быстро (не так как хотелось бы в идеале, но все относительно). И глупо было бы требовать какой-то определенной скорости. Я ведь не аппаратно-программный комплекс разрабатываю (тем более, что на Delphi их не делают), а бесплатную программу.

textExpanser © (17.08.07 21:42) [27]
Вот сразу видно человека, который всегда

да тебе прямая дорогав доктора, диагнозы ставить

> хотя в алгоритмы эти не вникал.

Мля. Как народ любит рассуждать о том, в чем нифига не понимает.
Пот по вашему какая вероятность, что ддва разных файла размера идеентичного будут иметь одинаковый хэш при условии генерации его через 10 байт? ОООчень низкая вероятность. Я думаю сравнимая с вероятностью совпадения при генерации хэша на каждый байт.
Не надо рассуждать о том. чего не понимаете.

Маленькое imho в защиту "медленности" открытия файла.
Сразу оговорюсь, точно как внутри себя работает Windows не знаю, все сказанное - предположения.
Допустим, что мы еще не пробегались поиском файлов по диску.
(что там твориться после этой пробежки я не знаю :)
Для открытия файла, надо найти его запись.
Обзовем через "Коэф" некую поправку.
Для каждой директории она своя и зависит в том числе
и от кол-ва объектов в ней. Не Log(кол-во объектов), но что-то похожее :)
Т.е. нам надо обратиться к диску Коэф * Уровень_вложенности_имени раз.
Не думаю, что это можно назвать "быстрой операцией" для файла лежащего не в корне диска. :)

> Пот по вашему какая вероятность, что ддва разных файла размера
> идеентичного будут иметь одинаковый хэш при условии генерации
> его через 10 байт? ОООчень низкая вероятность.

Особенно, если их размер 9 байт. Ку?

> [29] @!!ex © (17.08.07 22:27)
> Мля. Как народ любит рассуждать о том, в чем нифига не понимает.

Я склонен пологать все-же, что это ты нифига не понимаешь, и что не один алгоритм хеширования так не работает.

textExpanser
Давай нормально поставим задачу.

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

ASM прирост по скорости дать может, при условии оптимизации под MMX/SSE/SSE2. Простое переписывание на ASM прироста не даст, или будет не значительным.

> А каким боком здесь SSE/SSE2/SSE3 - они же для чисел с плавающей
> точкой...
> Да и MMX не представляю как можно здесь заюзать...

Сам не представляю как, но ведь оптимизируют ;-).
SSE/SSE2 и с целыми числами работают.

> for i := 0 to FileSize-1 do Read(f, ch);
> что так
> BlockRead(f, FileSize);
> Разница в большинстве случаев составляет не более 10% -
> иногда даже первый вариант быстрее...

Взял померил чтенение по байтно состовляет от четения целиком файла
0,0114= 1,14% . В качестве подопытного был файл в 300МБ. Первый вариант не будет быстрее никогда.
Остальные высказывания этого человека не комментирую, но они из тойже оперы.

Правда как тут уже заметели целиком загонять файл в память не рентабельно лучше по несколько килобайт (16-32КБ можно и больше, сам пробовал разные размеры).

> 10 байт - сильно сомневаюсь, хотя в алгоритмы эти не вникал.
> Иначе это уж очень ненадежное хэширование выйдет.

Если считать что файлы обсолютно случайны. То обсолютно нет никакой разницы при больших файлах, при очень маленьких могут быть проблемы.

А то что в файле 9Байт ну значит возметься только первый байт, а вероятность встречи одинаковых хэший 2^72/2^8=2^64

> А то что в файле 9Байт ну значит возметься только первый
> байт, а вероятность встречи одинаковых хэший 2^72/2^8=2^64

а подумать? вероятность встречи одинаковых хэший = вероятности одинаковых первых байт, т.к. возметься только первый байт, а значит она равна 1/256.

← →
Черный Шаман (2007-08-18 04:03) [35]

> Котик Б (16.08.07 14:45) [17]
>
> Просто в шоке от таких специалистов как textExpanser © :
> (
>
> После выхода W2K я повыкидывал практически все оптимизации
> по чтению файлов, оставив разве что MMF для слишком больших.
> ..
>
> Оптимизация по кешированию файлов в нынешней винде настолько
> хорошая - что практически без разницы как читать файл:
> что так
> for i := 0 to FileSize-1 do Read(f, ch);

На Вызовы winapi уходит много тиков процессора, так что проще считать в буфер и там парсить.

> Я склонен пологать все-же, что это ты нифига не понимаешь,
> и что не один алгоритм хеширования так не работает.

Хм. А где я утверждал что хэширование работает именно так? :))
Говорил лишь о том, что вероятность совпадения хэшей при генерации на каждый байт и через 10 сравнима.
9 байт - частный случай и решаеться тупо тем самым "ка каждый байт", уже при сколь либо больших файлах выгоднее считать каждый 10 байт.

P.S.
Не надо читать между строк. Тем более, если там ничего не написано.

Сверхбыстрое хэширование (hashing) Найти похожие ветки