Поскольку я пока не могу добавлять комментарии, я сделаю немного больше работы и просто проанализирую их все. Я ставлю анализ наверху; Тем не менее, соответствующие данные ниже. (Примечание: все это также сделано в 6.12.3 - магии GHC 7 пока нет.)
Анализ:
Версия 1: Шоу довольно неплохо для новичков, особенно таких коротких, как мы. Создание строк на самом деле имеет тенденцию быть приличным в GHC; однако чтение строк и запись больших строк в файлы (или stdout, хотя вы бы не хотели этого делать) - это то место, где ваш код может абсолютно сканировать. Я подозреваю, что многие детали, объясняющие, почему это так быстро, происходят из-за хитрой оптимизации в шоу для Ints.
Версия 2: Этот файл был самым медленным из всех при компиляции. Некоторые проблемы: обратное строгое в своем аргументе. Это означает, что вы не можете выполнять вычисления в первой части списка во время вычисления следующих элементов; Вы должны вычислить их все, перевернуть их, а затем выполнить свои вычисления (а именно (`mod` 10)) для элементов списка. Хотя это может показаться небольшим, это может привести к большему использованию памяти (обратите внимание, что здесь также выделено 5 ГБ памяти кучи) и более медленным вычислениям. (Короче говоря: не используйте реверс).
Версия 3: Помните, как я только что сказал, не используйте реверс? Оказывается, если вы возьмете его, это сокращает общее время выполнения до 1,79 с - чуть медленнее, чем базовая линия. Единственная проблема здесь в том, что когда вы углубляетесь в число, вы строите корешок списка в неправильном направлении (по сути, вы вводите «в» список с помощью рекурсии, а не «обращаетесь»). список).
Версия 4: Это очень умная реализация. Вы получаете выгоду от нескольких приятных вещей: во-первых, quotRem должен использовать евклидов алгоритм, логарифмический по большему аргументу. (Может быть, это быстрее, но я не верю, что есть что-то, что больше, чем постоянный фактор, быстрее, чем Евклид.) Кроме того, вы попадаете в список, как обсуждалось в прошлый раз, так что вам не нужно разрешать какие-либо списки по мере того, как вы go - список уже полностью создан, когда вы возвращаетесь, чтобы разобрать его. Как видите, от этого выигрывает производительность.
Этот код, вероятно, был самым медленным в GHCi, потому что многие оптимизации, выполняемые с флагом -O3 в GHC, связаны с ускорением создания списков, в то время как GHCi этого не делает.
Уроки: выбирает правильный путь в список, следите за промежуточной строгостью, которая может замедлить вычисления, и поработайте над просмотром детальной статистики производительности вашего кода. Также скомпилируйте с флагами -O3: всякий раз, когда вы этого не сделаете, все те люди, которые тратят много времени на то, чтобы сделать GHC сверхбыстрым, смотрят вам в глаза.
Данные:
Я просто взял все четыре функции, вставил их в один файл .hs, а затем изменил при необходимости, чтобы отразить используемую функцию. Кроме того, я увеличил ваш лимит до 5e6, потому что в некоторых случаях скомпилированный код будет выполняться менее чем за полсекунды на 1e6, и это может вызвать проблемы с гранулярностью при измерениях, которые мы проводим.
Параметры компилятора: используйте ghc --make -O3 [имя файла] .hs , чтобы GHC провел некоторую оптимизацию. Мы сбросим статистику в стандартную ошибку, используя цифры + RTS -sstderr .
Вывод в -sstderr дает нам вывод, который выглядит следующим образом, в случае цифр 1:
digits1 +RTS -sstderr
12000000
2,885,827,628 bytes allocated in the heap
446,080 bytes copied during GC
3,224 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 5504 collections, 0 parallel, 0.06s, 0.03s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.61s ( 1.66s elapsed)
GC time 0.06s ( 0.03s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.67s ( 1.69s elapsed)
%GC time 3.7% (1.5% elapsed)
Alloc rate 1,795,998,050 bytes per MUT second
Productivity 96.3% of total user, 95.2% of total elapsed
Здесь есть три ключевых статистики:
- Общее количество используемой памяти: только 1 МБ означает, что эта версия очень компактна.
- Общее время: 1,61 с сейчас ничего не значит, но посмотрим, как оно выглядит на фоне других реализаций.
- Производительность: это всего лишь 100% минус сборщик мусора; поскольку у нас 96,3%, это означает, что мы не создаем много объектов, которые оставляем в памяти.
Хорошо, давайте перейдем к версии 2.
digits2 +RTS -sstderr
12000000
5,512,869,824 bytes allocated in the heap
1,312,416 bytes copied during GC
3,336 bytes maximum residency (1 sample(s))
13,048 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 10515 collections, 0 parallel, 0.06s, 0.04s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 3.20s ( 3.25s elapsed)
GC time 0.06s ( 0.04s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 3.26s ( 3.29s elapsed)
%GC time 1.9% (1.2% elapsed)
Alloc rate 1,723,838,984 bytes per MUT second
Productivity 98.1% of total user, 97.1% of total elapsed
Хорошо, мы видим интересный паттерн.
- Тот же объем используемой памяти. Это означает, что это довольно хорошая реализация, хотя это может означать, что нам нужно протестировать более высокие входные данные выборки, чтобы увидеть, сможем ли мы найти разницу.
- Это занимает вдвое больше времени. Мы вернемся к некоторым предположениям о том, почему это позже.
- На самом деле это немного более продуктивно, но, учитывая, что GC не является огромной частью любой из этих программ, это не поможет нам ничего значительного.
Версия 3:
digits3 +RTS -sstderr
12000000
3,231,154,752 bytes allocated in the heap
832,724 bytes copied during GC
3,292 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 6163 collections, 0 parallel, 0.02s, 0.02s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 2.09s ( 2.08s elapsed)
GC time 0.02s ( 0.02s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 2.11s ( 2.10s elapsed)
%GC time 0.7% (1.0% elapsed)
Alloc rate 1,545,701,615 bytes per MUT second
Productivity 99.3% of total user, 99.3% of total elapsed
Хорошо, поэтому мы видим странные паттерны.
- Мы все еще используем 1 МБ общей памяти. Таким образом, мы не столкнулись с проблемой неэффективной памяти, что хорошо.
- Мы не совсем разбираемся с цифрами1, но у нас довольно легко бьют цифры2.
- Очень маленький GC. (Имейте в виду, что производительность более 95% очень хорошая, поэтому мы не имеем дело с чем-то слишком значительным.)
И, наконец, версия 4:
digits4 +RTS -sstderr
12000000
1,347,856,636 bytes allocated in the heap
270,692 bytes copied during GC
3,180 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 2570 collections, 0 parallel, 0.00s, 0.01s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.09s ( 1.08s elapsed)
GC time 0.00s ( 0.01s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.09s ( 1.09s elapsed)
%GC time 0.0% (0.8% elapsed)
Alloc rate 1,234,293,036 bytes per MUT second
Productivity 100.0% of total user, 100.5% of total elapsed
Wowza! Давайте разберемся с этим:
- Мы все еще на 1МБ. Это почти наверняка особенность этих реализаций, так как они остаются на 1 МБ на входах 5e5 и 5e7. Завещание лени, если хотите.
- Мы сократили около 32% нашего первоначального времени, что довольно впечатляюще.
- Я подозреваю, что проценты здесь отражают гранулярность в мониторинге -sstderr, а не какие-либо вычисления для сверхсветовых частиц.