Уменьшить выделение сортировки большого списка (или вектора)

Question

Я пытаюсь сократить время GC в моей программе. Основным подозреваемым является следующий фрагмент кода:

Data.Vector.Unboxed.fromList . take n . List.sortBy (flip $ Ord.comparing id) 
 $ [ ( sum [ (c + a) * wsum z | (z,c) <- IntMap.toList zt_d ] , d)
   | d <- IntMap.keys $ m
   , let zt_d = IntMap.findWithDefault IntMap.empty d $ m ]

Сортируемый список обычно содержит несколько тысяч элементов. Я думаю, что сортировка списка является виновником, потому что, если я заменю take n . List.sortBy (flip $ Ord.comparing id) на return . List.maximum, моя производительность повысится с 60% до 95%.

Есть ли что-нибудь, что я могу сделать, чтобы сократить распределение?

Обновление

Как рекомендовано, я заменил List.sort на сортировку по месту с vector-algorithms. Возможно, я делаю это неправильно, но я вижу, что нет выделения (производительность 97%, а не 63% со списками), но программа во много раз медленнее: она выполняется за 85 секунд с List.sortBy ; с сортировкой на месте я убил его после жду 7 минут. Я пробовал оба вида Intro и Merge. Вот мой код:

import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Algorithms.Merge as Sort
import qualified Data.Vector.Fusion.Stream as Stream
import Control.Monad.ST   

sortBy :: (Ord a, U.Unbox a) => (a -> a -> Ordering) -> [a] -> U.Vector a
sortBy cmp xs = runST $ do
  mv  <- GM.unstream . Stream.fromList $ xs
  Sort.sortBy cmp mv
  G.unsafeFreeze mv

Answer 1

Сортировка действительно выглядит так, как будто она вызовет много выделений. Хотя сортировка выполняется по списку, ее нельзя полностью изменить, поскольку сортировка списков приводит к созданию множества промежуточных списков. При необходимости вы можете попробовать выполнить сортировку на MVector, используя, например, пакет vector-алгоритмы , который обеспечивает эффективные алгоритмы сортировки.

Однако есть и другие недостатки, которые вызывают большее выделение, чем необходимо в

Data.Vector.Unboxed.fromList . take n . List.sortBy (flip $ Ord.comparing id) 
 $ [ ( sum [ (c + a) * wsum z | (z,c) <- IntMap.toList zt_d ] , d)
   | d <- IntMap.keys $ m
   , let zt_d = IntMap.findWithDefault IntMap.empty d $ m ]

Когда вы пишете

d <- IntMap.keys m, let zt_d = IntMap.findWithDefault IntMap.empty d m
-- The '$' are unnecessary, I left them out

вы: 1) пересекаете всю карту, чтобы собрать список ключей, и 2) затем ищите каждый ключ самостоятельно. Поскольку вы просматриваете только ключи, присутствующие на карте, вы никогда не используете значение по умолчанию. Гораздо эффективнее создать список пар ключ / значение в одном обходе карты:

(d,zt_d) <- IntMap.assocs m

Тогда, если id в flip $ Ord.comparing id действительно является тождественной функцией, это было бы более читабельным (и, возможно, более эффективным), как sortBy (flip compare).

В зависимости от типа суммируемых элементов (и, возможно, уровня оптимизации), может быть лучше использовать Data.List.foldl' (+) 0 вместо sum.