Подбор паролей на 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

[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]

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