Priority Queue based on Heap causes a lot of garbage collection in Haskell

user_7430178 0
Viewed 260

I am trying to develop a Heuristic Search library in Haskell, and one of the main things that make the algorithm behave in a way or another is the data structure; so I declared the class:

class DataStructure ds where  
  add :: Eq a => Node a -> ds a -> ds a
  addList :: Eq a => [Node a] -> ds a -> ds a
  next :: Eq a => ds a -> (ds a, Node a)
  isEmpty :: Eq a => ds a -> Bool

And then, instances of this class are used in a general search algorithm that expands nodes like this:

generalSearch :: (DataStructure ds, Eq a, Hashable a)
  => ProblemSpace a   -- ^ 'ProblemSpace' to be solved
  -> Cost a           -- ^ 'Cost' function to use
  -> Heuristic a      -- ^ 'Heuristic' function to use
  -> ds a             -- ^ 'DataStructure' that manages the node expansion
  -> [Node a]         -- ^ Returns the infinite list of final nodes (solutions)

generalSearch problem g h open
  | isEmpty open                    = []
  | getGoalF problem (getState n)   = n : generalSearch problem g h open'
  | otherwise                       = generalSearch problem g h open''
  where (open', n) = next open
        expanded = expand n g h (getActions problem)
        open'' = addList expanded open'

This last snippet of code is quite hard to understand without the full context of the module, but the important part is the last line: it uses the the DataStructure method addList to merge together the just expanded nodes with the rest of the open list that the execution is carrying.

Some of the algorithms require that the open list is sorted in some way: ascending cost, ascending heuristic... For which I used the heap package to build a PriorityQueue implementation like this:

data PriorityQueue a =
  PriorityQueue { priorityQueueToHeap :: MinPrioHeap Double (Node a)
                , valueFunction :: Node a -> Double }

So this queue stores the Nodes in ascending order depending on the valueFunction. The relevant method for this problem, addList, is implemented like:

addList :: Eq a => [Node a] -> PriorityQueue a -> PriorityQueue a
addList xs (PriorityQueue h f) = PriorityQueue (union h xs') f
  where xs' = fromList $ map (\n -> (f n, n)) xs

From my inexperience in Haskell this seemed like a good approach, but it turns out that when testing it, the execution is super slow. After some profiling I was able to spot that the problem was a lot of pause due to Garbage Collection, and the cost centers revealed that the union method in addList is the most expensive one in time (which I can understand, due to the sorting) but also in space (it is the one allocating by far the most).

COST CENTRE   MODULE             SRC                                     %time %alloc

union         Data.Heap.Internal Data/Heap/Internal.hs:(134,1)-(141,79)   42.8   32.7
visited       Search.General     src/Search/General.hs:77:43-53           14.6    0.0
expand        Search.General     src/Search/General.hs:(70,40)-(76,78)    13.6   14.0
cost          Search.General     src/Search/General.hs:74:70-81            7.8    7.9
generalSearch Search.General     src/Search/General.hs:(52,1)-(58,37)      6.7   13.6
fromList      Data.Heap          Data/Heap.hs:137:1-34                     4.7   11.7
size          Data.Heap.Internal Data/Heap/Internal.hs:(98,1)-(99,23)      3.4    8.3
rank          Data.Heap.Internal Data/Heap/Internal.hs:(93,1)-(94,23)      2.7    8.0
expand        Search.General     src/Search/General.hs:(69,1)-(77,53)      1.4    3.4

The time problems appear to happen only when the list of open nodes is big, so I guess that it is related to the inmutability of the Heap, being written and erased in each new expansion. Is there a way to prevent this behavior, and reduce the garbage collection? Should I use a different type of data structure to build the priority queue?

haskell
0 Answers
Related