Подбор паролей на D
Apr. 9th, 2015 07:17 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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'ов (индентификаторов потоков), запустив нужное число воркеров, а потом раскидывает им задания:
$ внутри [] означает длину массива, так номер задачки i мапится на номер рабочего. Встречающиеся в коде .idup и .dup создают иммутабельную и мутабельную копии массива соответственно (посылать между потоками без глубокого копирования разрешается лишь иммутабельные данные).
У каждого потока свой почтовый ящик, откуда он полученные сообщения достает функцией receive, передавая ей разные функции-обработчики, receive по типу этих обработчиков выбирает подходящий, кому отдать данные из сообщения. Соответственно, главный цикл рабочего потока, по мотивам гошного варианта, выглядит
Как и в гошном варианте, когда главный поток получает сообщение с ответом, он его выводит и завершается. Как я понял, в Go остальные потоки при этом тут же умирают в мучениях. В D при завершении главного потока потоки-воркеры продолжают свою работу. При таком бесконечном цикле ожидания сообщений, как здесь, в какой-то момент мэйлбокс потока оказывается пуст, и в этот момент если receive видит, что родительский поток помер, эта функция бросает определенное исключение. На него можно при желании осмысленно реагировать, но в моем случае я просто говорю тихонько завершиться:
Такое вот баловство.
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;
Такое вот баловство.
