Почему `(карта digitToInt) . шоу` так быстро?

Поскольку я пока не могу добавлять комментарии, я немного поработаю и просто проанализирую их все. Я ставлю анализ вверху; однако соответствующие данные приведены ниже. (Примечание: все это сделано и в 6.12.3 — пока без магии GHC 7.)

Анализ:

Версия 1: show довольно хорошо подходит для целых чисел, особенно таких коротких, как у нас. Создание строк на самом деле имеет тенденцию быть приличным в GHC; однако чтение в строки и запись больших строк в файлы (или stdout, хотя вы бы не хотели этого делать) — это то, где ваш код может абсолютно сканировать. Я подозреваю, что многие детали, объясняющие, почему это так быстро, связаны с умной оптимизацией в рамках шоу для Ints.

Версия 2: эта версия была самой медленной при компиляции. Некоторые проблемы: reverse является строгим в своем аргументе. Это означает, что вы не получаете выгоды от возможности выполнять вычисления для первой части списка, пока вы вычисляете следующие элементы; вы должны вычислить их все, перевернуть их, а затем выполнить свои вычисления (а именно (`mod` 10)) над элементами списка. Хотя это может показаться небольшим, это может привести к большему использованию памяти (обратите внимание на выделенные здесь 5 ГБ памяти кучи) и замедлению вычислений. (Короче говоря: не используйте реверс.)

Версия 3. Помните, я только что сказал не использовать реверс? Оказывается, если вы уберете его, общее время выполнения упадет до 1,79 с — чуть медленнее, чем базовый уровень. Единственная проблема здесь заключается в том, что по мере того, как вы углубляетесь в число, вы строите костяк списка в неправильном направлении (по сути, вы входите «в» список с помощью рекурсии, а не «на». список).

Версия 4: это очень умная реализация. Вы получаете выгоду от нескольких приятных вещей: во-первых, quotRem должен использовать алгоритм Евклида, который является логарифмическим по большему аргументу. (Возможно, это быстрее, но я не верю, что есть что-то большее, чем постоянный множитель, быстрее, чем Евклид.) Кроме того, вы используете cons в списке, как обсуждалось в прошлый раз, так что вам не нужно разрешать какие-либо преобразователи списка, когда вы go - список уже полностью построен, когда вы возвращаетесь, чтобы проанализировать его. Как видите, производительность от этого выигрывает.

Этот код был, вероятно, самым медленным в GHCi, потому что многие оптимизации, выполненные с флагом -O3 в GHC, связаны с более быстрым созданием списков, тогда как GHCi не делал ничего из этого.

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

Данные:

Я просто взял все четыре функции, поместил их в один файл .hs, а затем изменил по мере необходимости, чтобы отразить используемую функцию. Кроме того, я увеличил ваш лимит до 5e6, потому что в некоторых случаях скомпилированный код будет выполняться менее чем за полсекунды на 1e6, и это может начать вызывать проблемы с детализацией при измерениях, которые мы делаем.

Параметры компилятора: используйте ghc --make -O3 [имя файла].hs, чтобы GHC выполнил некоторую оптимизацию. Мы выведем статистику в стандартную ошибку, используя цифры +RTS -sstderr.

Сброс в -sstderr дает нам вывод, который выглядит следующим образом, в случае digits1:

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 МБ означает, что эта версия очень компактна.
2. Общее время: 1,61 с сейчас ничего не значит, но посмотрим, как оно будет выглядеть на фоне других реализаций.
3. Производительность: Это просто 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

Итак, мы наблюдаем интересную закономерность.

1. Тот же объем используемой памяти. Это означает, что это довольно хорошая реализация, хотя это может означать, что нам нужно протестировать входные данные с большим количеством выборок, чтобы увидеть, сможем ли мы найти разницу.
2. Это занимает в два раза больше времени. Мы вернемся к некоторым предположениям о том, почему это произошло позже.
3. На самом деле это немного более продуктивно, но, учитывая, что 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. Мы не совсем в цифрах 1, но у нас есть цифры 2, которые довольно легко обыгрываются.
3. Очень мало ГК. (Имейте в виду, что производительность выше 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

Вауза! Давайте разберем это:

1. У нас все еще 1 МБ. Почти наверняка это особенность этих реализаций, поскольку они остаются на уровне 1 МБ при вводе 5e5 и 5e7. Свидетельство лени, если хотите.
2. Мы сократили около 32% нашего исходного времени, что довольно впечатляет.
3. Я подозреваю, что проценты здесь отражают степень детализации в мониторинге -sstderr, а не какие-либо расчеты сверхсветовых частиц.

Отвечая на вопрос "почему rem вместо mod?" в комментариях. При работе с положительными значениями rem x y === mod x y единственным соображением является производительность:

> import Test.QuickCheck
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y)

Итак, какова производительность? Если у вас нет веской причины не делать этого (и лень не является веской причиной, как и незнание критерия), тогда используйте хороший инструмент для тестирования, я использовал критерий:

$ cat useRem.hs 
import Criterion
import Criterion.Main

list :: [Integer]
list = [1..10000]

main = defaultMain
        [ bench "mod" (nf (map (`mod` 7)) list)
        , bench "rem" (nf (map (`rem` 7)) list)
        ]

Выполнение этого показывает, что rem заметно лучше, чем mod (скомпилировано с -O2):

$ ./useRem 
...
benchmarking mod
...
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950

benchmarking rem
...
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950