?

Log in

No account? Create an account

Previous Entry | Next Entry

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

Увидел на днях у 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;

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

Tags:

Comments

( 44 comments — Leave a comment )
sober_space
Apr. 9th, 2015 01:27 pm (UTC)
Тут надо учесть, что все суслики пользуются go fmt, что резко увеличивает количество строк за счет форматирования. Если бы был аналогично устроенный d fmt, у Вас тоже строк было бы побольше.

Edited at 2015-04-09 01:27 pm (UTC)
thedeemon
Apr. 9th, 2015 03:29 pm (UTC)
Да, верно, у меня код плотнее напихан. Плюс еще угол срезал, не стал выносить генерацию заданий в отдельный поток/актор.
swizard
Apr. 9th, 2015 02:44 pm (UTC)
Я бы для этой задачи просто тупо завёл счётчик, который бы воркеры атомарно инкрементировали и из значения формировали бы себе пароль для подбора (5 символов из алфавита в 36 значений совсем немного получается).

Но раз предлагается померяться толщиной каналов, то щас попробую изобразить аналог на Rust с использованием mpsc, посмотрим, что получится.
thedeemon
Apr. 9th, 2015 04:14 pm (UTC)
В посте про Го было сразу показано, что каналы там не шибко толстые, поэтому в упомянутых тут вариантах передается совсем мало данных.
(no subject) - swizard - Apr. 9th, 2015 05:35 pm (UTC) - Expand
(no subject) - Yauheni Akhotnikau - Apr. 9th, 2015 06:11 pm (UTC) - Expand
(no subject) - thesz - Apr. 13th, 2015 03:56 pm (UTC) - Expand
(no subject) - Yauheni Akhotnikau - Apr. 9th, 2015 06:30 pm (UTC) - Expand
(no subject) - swizard - Apr. 9th, 2015 07:54 pm (UTC) - Expand
(no subject) - Yauheni Akhotnikau - Apr. 9th, 2015 07:58 pm (UTC) - Expand
(no subject) - swizard - Apr. 9th, 2015 08:59 pm (UTC) - Expand
(no subject) - swizard - Apr. 9th, 2015 09:01 pm (UTC) - Expand
(no subject) - Yauheni Akhotnikau - Apr. 10th, 2015 04:29 am (UTC) - Expand
(no subject) - Yauheni Akhotnikau - Apr. 10th, 2015 08:25 am (UTC) - Expand
(no subject) - swizard - Apr. 10th, 2015 12:10 pm (UTC) - Expand
(no subject) - Yauheni Akhotnikau - Apr. 10th, 2015 12:34 pm (UTC) - Expand
(no subject) - swizard - Apr. 10th, 2015 01:56 pm (UTC) - Expand
(no subject) - Yauheni Akhotnikau - Apr. 10th, 2015 02:04 pm (UTC) - Expand
(no subject) - swizard - Apr. 10th, 2015 02:56 pm (UTC) - Expand
(no subject) - Yauheni Akhotnikau - Apr. 11th, 2015 07:37 am (UTC) - Expand
(no subject) - swizard - Apr. 11th, 2015 11:40 am (UTC) - Expand
(no subject) - thedeemon - Apr. 10th, 2015 01:32 am (UTC) - Expand
(no subject) - thedeemon - Apr. 10th, 2015 02:56 am (UTC) - Expand
(no subject) - swizard - Apr. 10th, 2015 12:00 pm (UTC) - Expand
Yauheni Akhotnikau
Apr. 9th, 2015 03:12 pm (UTC)
Флэш-моб, так флэш-моб :)
Т.к. мое вчерашнее решение было сделано с несколько другим прицелом, то вот более близкие к вашему варианту: eao197.blogspot.com/2015/04/progsobjectizer-md5bruteforce.html
simsun
Apr. 9th, 2015 05:24 pm (UTC)
На плюсах то сколько шустрит?:)
Yauheni Akhotnikau
Apr. 9th, 2015 07:27 pm (UTC)
На моей машине go-ный вариант отрабатывает за 8.1s, плюсовый -- за 6.7s.
Правда в go я не копенгаген, может компилятору какие-то хитрые ключики для оптимизации можно подставить...
Плюсовый вариант собран MSVS2013 Express с ключиком -02.
Go -- версии 1.4.2 (amd64).
(no subject) - simsun - Apr. 9th, 2015 10:19 pm (UTC) - Expand
sleepy_drago
Apr. 9th, 2015 06:20 pm (UTC)
интереснее было бы если бы обсуждались кластерные варианты. мол на 7 машинках по 8 цпу 4секунды.
kodt_rsdn
Apr. 9th, 2015 07:20 pm (UTC)
pastebin.com забанен в России
http://minjust.ru/ru/extremist-materials?field_extremist_content_value=pastebin.com

Конечно, поставлю себе проксю ради любопытства, но всё же... :\
thedeemon
Apr. 10th, 2015 01:29 am (UTC)
Не знал. Там в постах были альтернативные ссылки, вроде.
(no subject) - _slw - Apr. 10th, 2015 03:21 pm (UTC) - Expand
(no subject) - kodt_rsdn - Apr. 11th, 2015 09:09 am (UTC) - Expand
(no subject) - _slw - Apr. 11th, 2015 09:15 am (UTC) - Expand
(no subject) - kodt_rsdn - Apr. 11th, 2015 10:59 am (UTC) - Expand
(no subject) - _slw - Apr. 11th, 2015 11:02 am (UTC) - Expand
109
Apr. 10th, 2015 07:43 am (UTC)
ubyte[] ourHash = hashString.chunks(2).map!text.map!(s => ofHex(s[0])*16 + ofHex(s[1])).map!(to!ubyte).array;
auto workers = iota(totalCPUs).map!(i => spawn(&worker, thisTid, cast(immutable)ourHash)).array;

в таком стиле я на C# берусь в десять строчек написать. ну в 11 точно.

а вообще честнее число символов считать.

и непонятно, какое отношение к задаче имеет bandwidth обмена между тредами. задача же полностью параллелится с самого начала.
thedeemon
Apr. 10th, 2015 09:32 am (UTC)
Да, есть у меня пристрастие такие выражения в одну строчку писать.
Впрочем, в окошко гитхаба влезает, в редактор тоже, не вижу смысла делать существенно короче.
Вариант на С# тоже было бы интересно увидеть и потестить для сравнения. Необязательно в 11 строк (они уйдут на using'и), можно и в 12. :)

Число символов:
Go 1434
C++ 3377 исходный вариант, 2859 обновленный
D - 1345
Rust 2057

bandwidth обмена тут не при чем действительно.
afiskon
Apr. 10th, 2015 08:25 am (UTC)
Спасибо, интересно.

С интересом посматриваю на D. Скажите, а какая IDE для D в это время суток считается наиболее продвинутой?
thedeemon
Apr. 10th, 2015 09:38 am (UTC)
Вероятно, Mono-D (на базе XamarinStudio/MonoDevelop), хотя своим опытом подтвердить не могу, у меня с ней как-то не сложилось.
Сам использую VisualD (плагин для Visual Studio, сильно продвинутым сложно назвать) под виндой и Vim в линуксе.
В народе популярнее всего Vim, похоже.
fluidz123
Apr. 10th, 2015 10:44 am (UTC)
Вариант на scala+akka: https://gist.github.com/romangrebennikov/60eaee612bc37715d87a

У меня отрабатывает за 3.9с
thedeemon
Apr. 12th, 2015 07:22 am (UTC)
Занятно, спасибо. А зачем samehash вручную реализован, штатное сравнение массивов такое медленное что-ли?
livejournal
Apr. 12th, 2015 07:10 pm (UTC)
Весёлые приключения одной аллокации
Пользователь swizard сослался на вашу запись в своей записи «Весёлые приключения одной аллокации» в контексте: [...] и форкнувшегося здесь [...]
livejournal
Apr. 13th, 2015 10:19 am (UTC)
Разделяй и властвуй
Пользователь a_jelly сослался на вашу запись в своей записи «Разделяй и властвуй» в контексте: [...] Прочел вот тут [...]
( 44 comments — Leave a comment )