Отладка узких мест производительности для алгоритма наиболее длинных общих подпоследовательностей

Ответ 1

Вы делаете огромный удар в

U.forM_ (U.fromList [0..ct-1])

в findSnakes. Я убежден, что это не должно произойти (билет?), Но он выделяет новый Vector для перемещения каждый раз, когда вызывается findSnakes. Если вы используете

Control.Monad.forM_ [0 .. ct-1]

время работы примерно вдвое, а распределение здесь примерно на 500. (GHC оптимизирует C.M.forM_ [0 :: Int .. limit] ну, список исключается, а остальное - это в основном цикл). Вы можете сделать немного лучше, написав цикл самостоятельно.

Некоторые вещи, которые вызывают беспорядочное размножение/размер кода, не повредив производительность, - это

• неиспользуемый аргумент Bool lcsh
• аргумент cmp для findSnakes и gridWalk; если они никогда не вызываются с другим сравнением, чем верхний уровень cmp, этот аргумент приводит к ненужному дублированию кода.
• общий тип while; специализируясь на используемом типе ST s Bool -> ST s () -> ST s (), уменьшает выделение (много), а также время работы (немного, но заметно здесь).

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

Например, ваш исходный код производит здесь

    total time  =        3.42 secs   (3415 ticks @ 1000 us, 1 processor)
    total alloc = 4,612,756,880 bytes  (excludes profiling overheads)

COST CENTRE MODULE    %time %alloc  ticks     bytes

gridWalk    Main       63.7   52.7   2176 2432608000
findSnakes  Main       20.0   27.8    682 1281440080
cmp         Main        9.2    0.0    313        16
findYP      Main        4.2   19.4    144 896224000
updateFP    Main        2.7    0.0     91         0

Просто добавление перехвата привязки len в gridWalk ничего не меняет в непрофилирующей версии, но для версии профилирования

    total time  =        2.98 secs   (2985 ticks @ 1000 us, 1 processor)
    total alloc = 3,204,404,880 bytes  (excludes profiling overheads)

COST CENTRE MODULE    %time %alloc  ticks     bytes

gridWalk    Main       63.0   32.0   1881 1024256000
findSnakes  Main       22.2   40.0    663 1281440080
cmp         Main        7.2    0.0    214        16
findYP      Main        4.7   28.0    140 896224000
updateFP    Main        2.7    0.0     82         0

это имеет большое значение. Для версии, включая упомянутые выше изменения (и перерыв на len в gridWalk), в профилирующей версии указано

total alloc = 1,923,412,776 bytes  (excludes profiling overheads)

но непрофилирующая версия

     1,814,424 bytes allocated in the heap
        10,808 bytes copied during GC
        49,064 bytes maximum residency (2 sample(s))
        25,912 bytes maximum slop
             1 MB total memory in use (0 MB lost due to fragmentation)

                                  Tot time (elapsed)  Avg pause  Max pause
Gen  0         2 colls,     0 par    0.00s    0.00s     0.0000s    0.0000s
Gen  1         2 colls,     0 par    0.00s    0.00s     0.0001s    0.0001s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    0.12s  (  0.12s elapsed)
GC      time    0.00s  (  0.00s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time    0.12s  (  0.12s elapsed)

говорит, что он выделяется в 1000 раз меньше, чем профилирующая версия.

Для кода Vector и друзей, более надежного для определения узких мест, чем профилирование (к сожалению, гораздо более трудоемкий и сложный процесс) изучает сгенерированное ядро ​​(или сборку, если вы владеете чтением этого).

Что касается обновления, C работает немного медленнее на моем ящике (gcc-4.7.2, -O3)

$ time ./miltest1

real    0m0.074s
user    0m0.073s
sys     0m0.001s

но Haskell о том же

$ time ./hsmiller
1

real    0m0.151s
user    0m0.149s
sys     0m0.001s

Это происходит немного быстрее при компиляции через бэкэнд LLVM:

$ time ./hsmiller1

real    0m0.131s
user    0m0.129s
sys     0m0.001s

И когда мы заменим forM_ на ручной цикл,

findSnakes a b fp !k !ct op = go 0
  where
    go x
        | x < ct    = gridWalk a b fp (op k x) >> go (x+1)
        | otherwise = return ()

он становится немного быстрее,

$ time ./hsmiller
1

real    0m0.124s
user    0m0.121s
sys     0m0.002s

соотв. через LLVM:

$ time ./hsmiller
1

real    0m0.108s
user    0m0.107s
sys     0m0.000s

В общем, сгенерированное ядро ​​выглядит прекрасно, одно небольшое раздражение было

Main.$wa
  :: forall s.
     GHC.Prim.Int#
     -> GHC.Types.Int
     -> GHC.Prim.State# s
     -> (# GHC.Prim.State# s, Main.MVI1 s #)

и немного окольной реализации. Это фиксируется, делая newVI1 strict во втором аргументе,

newVI1 n !x = do

Поскольку это часто не вызывается, влияние на производительность, конечно, незначительно.

Мясо является ядром для lcsh, и это выглядит не так уж плохо. Единственные вещи в коробке - это Int, читаемые/записываемые в STRef, и это неизбежно. Что не очень приятно, так это то, что ядро ​​содержит много дубликатов кода, но, по моему опыту, это редко является реальной проблемой производительности, и не все дублированные коды выживают при генерации кода.

и для того, чтобы он хорошо выполнялся, lcsh должен сократить цикл whileM_ до хорошего итеративного внутреннего цикла проверки состояния и вложенного кода findSnakes.

Вы получаете внутренний цикл, когда вы добавляете прагму INLINE в whileM_, но этот цикл не является приятным, и в этом случае он намного медленнее, чем whileM_ out-of-line (I "Не уверен, что это связано только с размером кода, но это может быть).