Подбор паролей на D

[thedeemon]

Увидел на днях у afiskon'a гостевой пост с реализацией на Go игрушечной задачки про подбор пароля по его MD5 хэшу. По условию в пароле 5 символов из алфавита 0..9a..z, перебор надо распараллелить по ядрам. Там же есть ссылки на предыдущие инкарнации (на хаскеле и эрланге), в них я сейчас не вчитывался. А еще тот же пост увидел eao197 и сделал свой вариант на C++ с использованием его любимого SObjectizer'a. Я решил присоединиться к флэшмобу и сделал вариант на D. Варианты на С++ и D - прямые переводы с Го, поэтому за объяснением рекомендую смотреть пост про гошный вариант, там подробно расписано. Полные исходники:
Go (84 lines)
C++ (155 lines)
D (48 lines)

На моем ноуте с i3 и двумя ядрами по два гипертреда вариант на Go отрабатывает за 13 секунд, вариант на D - за 6 секунд. Оба грузят проц под 100%, имеют по 5 потоков и памяти едят меньше 2 мегов. Что занятно, на этом примере получился очень резкий контраст между компиляторами D: при сборке LDC получается вдвое быстрее Го, а при сборке DMD - вдвое медленнее.

Что касается кода, в варианте на С++ просто почерк очень размашистый, при другом форматировании было бы заметно компактнее, но и синтаксического шума, конечно, тоже заметно больше чем в остальных вариантах. В Го рабочие потоки получают задания и посылают ответ через каналы, которые они шарят меж собой. В D использован модуль из стандартной библиотеки std.concurrency, где нет в явном виде каналов, а вместо этого потоки могут посылать друг другу сообщения аки процессы в эрланге. В частности, у меня тут главный поток создает массив Tid'ов (индентификаторов потоков), запустив нужное число воркеров, а потом раскидывает им задания:

workers[i % $].send( Part( pass.idup, b ) );

$ внутри [] означает длину массива, так номер задачки i мапится на номер рабочего. Встречающиеся в коде .idup и .dup создают иммутабельную и мутабельную копии массива соответственно (посылать между потоками без глубокого копирования разрешается лишь иммутабельные данные).

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

while(true)	
  receive( (Part p) { 
    ... тут вложенная функция, вызывающаяся при получении структуры Part

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

scope(failure) return;

Такое вот баловство.

Comments

[swizard.livejournal.com]

Так, добрался до задачки, получается как-то так для раста (переписал твой алгоритм с D): https://gist.github.com/swizard0/6f4df8bdea0db32833fd

70 строк, но по-сути один хрен, я придерживался стиля, но можно и сжать, это непринципиально. На моём ноуте получается 4.5 сек на подбор.

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

[yauheni akhotnikau (from livejournal.com)]

Вообще да, в таком виде это больше соревнование на скорость реализации md5. Если в реализации есть адаптация под особенности процессора (или архитектуры), то это большой плюс, т.к. основное время тратится внутри md5.

[thesz.livejournal.com]

Вот.

И тут мог бы победить тот, кто сделает векторную MD5. Или, даже, bit sliced SSE-vectorized MD5.

[yauheni akhotnikau (from livejournal.com)]

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

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

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

[swizard.livejournal.com]

А ещё тогда надо чтоб воркеры имели тенденцию падать с ошибкой в рандомный момент, и чтоб мастер мог эти моменты отлавливать, логгировать ошибку и респавнить процесс :) Я всецело за, только чур я тогда эрланг за собой застолбил! =)

[yauheni akhotnikau (from livejournal.com)]

А с чего бы воркерам здесь падать? :)

[swizard.livejournal.com]

Эмуляция реальных условий типа! Допустим, воркеры не просто md5 считают, а натурально ходят к какой-то веб-форме логина и подбирают пароль :)

[swizard.livejournal.com]

...или спам рассылают, или капчу распознают =)

[yauheni akhotnikau (from livejournal.com)]

Понятно. Но хотелось бы, чтобы падения были как-то детерминированы, а не рандомно возникали. Чтобы сценарий падений не зависел от языка реализации.

[yauheni akhotnikau (from livejournal.com)]

Придумался такой сценарий. Есть N тасков (где N > 10, чило можно подобрать). Каждый таск -- это md5-хеш и диапазон возможных значений. Например {"c4ca4238a0b923820dcc509a6f75849b", ["0","9")} или {"698d51a19d8a121ce581499d7b701668", ["000","zzz")}.
Менеджер раздает таски воркерам когда воркеры освобождаются. Воркер получает таск, пытается подобрать значение из указанного в таске диапазона, которое даст такой же md5-хеш. Такое значение может быть, а может и не быть. О результате воркер сообщает менеджеру. Получение результата менеджером означает, что воркер освободился и может получить следующий таск (если таковые еще есть).

Диапазоны могут быть заданы некорректно. Например, ["zzz", "000") -- нарушение правила start меньше end. Или ["0000", "zz") -- в end меньше символов, чем в start. Или ["aaaa", "aaAz") -- символ A не входит в разрешенный алфавит.

Столкнувшись с некорректным диапазоном воркер должен "упасть". Эту ситуацию должен отловить менеджер и запустить вместо упавшего воркера нового. Сбойный таск при этом выбрасывается.

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

[swizard.livejournal.com]

Ага, вроде получилась интересная постановка задачи, готов попробовать изобразить на rust.

Я бы тогда ещё чуток модифицировал:

• чтобы программа интервалы получала на stdin, и запуск чтоб производился как % ./program < intervals.txt
• чтоб на stderr программа логгировала некорректные интервалы с причиной ошибки из мастер-потока

[yauheni akhotnikau (from livejournal.com)]

А вот читать stdin нужно сразу при старте, или в процессе работы?

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

На счет вывода в stderr согласен.

[swizard.livejournal.com]

Там данные вполне простые, можно что-нибудь вроде "<md5><пробел><начало интервала><пробел><конец интервала><\n>" на каждой строке.

Чтоб можно было просто сделать сплит по пробелам и нормально (соответственно, пробел и перенос строки не должны входить в алфавит).

[yauheni akhotnikau (from livejournal.com)]

Ok. Не уверен, что смогу заняться завтра. Скорее это будет понедельник-вторник на следующей неделе.

[swizard.livejournal.com]

Окей, а я, видимо, сегодня вечерком что-нибудь накидаю.

[yauheni akhotnikau (from livejournal.com)]

Предлагаю, для простоты, диапазоны для поиска задавать так, чтобы и левая и правая граница входили в поиск. Т.е. в виде [l,r], а не [l,r).

В этом случае проще задавать файлы заданий:

95ebc3c7b3b9f1d2c40fec14415d3cb8 yyyyy zzzzz

Вместо

95ebc3c7b3b9f1d2c40fec14415d3cb8 yyyyy 100000

[swizard.livejournal.com]

ага, согласен

[thedeemon.livejournal.com]

Так это и не бенчмарк вовсе, а флэшмоб по показу того, как код с конкаренси на разных языках выглядит.

[thedeemon.livejournal.com]

У, там зависимости внешние. :(
На одной стандартной библиотеке нельзя выехать?

Попробовал с такими зависимостями:
[dependencies]
rust-crypto = "0.2.31"
sys-info = "0.3.3"
rustc-serialize = "0.3.12"

Но один из пакетов, от которых они зависят, не собрался, чего-то в моем mingw не хватило.

[swizard.livejournal.com]

У меня написано просто вот так:

[dependencies]
rust-crypto = "*"
rustc-serialize = "*"
sys-info = "*"

Что касается выехать на стандартной библиотеке -- уже нет :) Там щас новая политика партии: всё по-максимуму вынести из stdlib в crates.io. Вот эти crypto, serialize, и даже rand -- всё это раньше было в стандартной библиотеке.

Не сказал бы, что меня радует такой порядок вещей, но сейчас вот так вот.