Сразу скажу, что в начале псотика будет много воды, самое интересное в последних N абзацах.

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

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

За 40 минут был написан текст программы:

Сорс также доступен по https://gist.github.com/1340356 , если у кого не вставилось.

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

• uniDistr делает пару нормально распределенных чисел из пары равномерно распределенных, и возвращает остаток бесконечного списка этих равномерно распределенных. Для преобразования используется преобразование Бокса-Мюллера.
• unis дергает uniDistr, чтобы преобразовать бесконечный список равномерно распределенных случайных чисел в случайно распределенные.
• makeDoc по списку слов из словаря, требуемому размеру в символах и списку заранее сгенеренных случайных величин делает документ, используя makeDoc' как рекурсивно вызываемую «рабочую лошадку».
• genSingle получает список слов из словаря, рандомный генератор и пару чисел — число документов и размер одного документа в символах. Дергает makeDoc, чтобы сгенерить каждый из документов. Результатом является список из пар (ИмяДокумента, СодержаниеДокумента).
• gen делает примерно то же самое, что и genSingle, но только принимает не одну пару «размер-число документов», а их список, и для каждой такой пары дергает genSingle.
• gs делает из одного случайного генератора бесконечный список случайных генераторов применяя unfoldr со сплитом.

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

По памяти могу сказать, что для массива слов в первом приближении использовался банальный список, и поэтому в строке 26 на операции индексации все адово тормозило — профайлер показал, что в этом месте жралось 97% процессорного времени, а скорость генерации была такой, что нужный мне объем текстов породился бы по моим прикидкам за пару суток. Впрочем, это довольно очевидное место — списки не очень круто использовать для случайного доступа, поэтому список был заменен на Data.Array, что существенно увеличило скорость генерации. Почти на три порядка, кажется, сейчас точно не вспомню.

Затем, рекурсивная makeDoc' сначала была написана не так оптимально. В первом приближении просто создавался список слов, запоминалось, какова их суммарная длина, и если длина превышала требуемую, делалось intercalate " " по этому списку слов. Тормозило, гадина, поэтому вызов был переписан на вот такой, хвосто-рекурсивный. Стало еще побыстрее.

И вот после этой пары оптимизаций (и еще пары совсем незначительных) я уперся в сам процесс генерации текстов. И тут мы подступаем к самому интересному: любой внимательный читатель заметит, что это просто отличный кандидат на распараллеливание! Пусть один тред генерит себе один текст, другой тред — другой, и так далее.

Лирическое отступление: ленивость хаскеля подразумевает, что в памяти хранится не сам результат вычислений, а некоторая отсылка к этому результату: запись о том, что должно быть вычислено и как. Только тогда, когда результат вычисления действительно понадобится, этот thunk будет вычислен. Такая запись называется thunk'ом, и подобная ленивость позволяет делать кучу интересных вещей, типа простого оперирования бесконечными списками. В программе, о которой этот псотик, бесконечные списки используются, например, для того, чтобы функция-генератор текстов вообще не парилась о природе случайных чисел и их генерации, а просто брала следующее число из списка. Для нее этот список бесконечный — из него можно будет достать любое количество элементов, а следующее случайное число вычислится как раз тогда, когда это будет нужно. На практике, конечно же, все всегда будет конечным — наши тексты конечны, в конце концов.

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

Для вычисления в нужном треде используются вещи из Control.Parallel.Strategies, в частности, parMap и parListChunk Последний позволяет задавать количество элементов, которые уйдут каждому треду, а это полезно, чтобы, например, наплодить не 1000 мелких заданий, а 8 крупных, так как у меня все же не 1000, а всего 8 ядер. Есть несколько разных стратегий вычисления, используемых с parMap/parListChunk. Нужная нам — rdeepseq. Эта стратегия позволяет проходить по всему списку thunk'ов, убеждаясь, что каждый из них вычислится там, где надо, а не в основном треде.

Окей, написали parListChunk, отлично, параллельно, но... Блин, жрет память как не в себя, гигабайтами на сколь значимо больших объемах данных. А почему? А потому, что теперь, как мы и просили, все санки действительно вычисляются сразу. До добавления этого parListChunk было просто: при записи на файл оказывается, что строку-то надо вычислить, а так как запись идет блоками, а не сразу вся, то и вычисляется, например, первые 16 килобайт. Или пусть даже 16 мегабайт, не суть, все равно мало. Вычислилось, записалось, больше не нужно, Garbage Collector за нами прибрал, память освободилась. Все отлично, много памяти в один момент времени не жрется, и ваще. А теперь каждый документ вычисляется сразу и весь держится в памяти до тех пор, пока не будет записан на диск, поэтому все логично и разумно.

Тем не менее, решение есть, причем достаточно тривиальное — использовать вместо parListChunk другой подход, с forkIO. В таком случае можно спокойно запустить несколько тредов, в каждом из которых вычислять по-старому, лениво и без насильного вычисления.