-
Notifications
You must be signed in to change notification settings - Fork 71
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Switch from pqueue
to psqueues
or heaps
?
#214
Comments
Updated benchmark code shows somewhat similar memory usage by all 3 libraries
Benchmark code{- cabal:
build-depends: base, chronos-bench, heaps, pqueue, psqueues, random, random-shuffle, weigh
ghc-options: -O
-}
{-# LANGUAGE BlockArguments #-}
import qualified Chronos.Bench as Chronos
import Control.Monad
import Data.Foldable
import Data.Function
import qualified Data.Heap as Heaps
import qualified Data.IntPSQ as Psqueues
import qualified Data.PQueue.Prio.Min as Pqueue
import System.Random (randomIO, randomRIO)
import System.Random.Shuffle (shuffleM)
import qualified Weigh
type Level = Int
type Node = Int
main :: IO ()
main = do
benchmarkMemory
benchmarkTime
benchmarkMemory :: IO ()
benchmarkMemory = do
let n = 1000000
nodes <- randomNodes n
Weigh.mainWith do
Weigh.func ("pqueue " ++ show n) (pqueueDrain . pqueueFromList) nodes
Weigh.func ("psqueues " ++ show n) (psqueuesDrain . psqueuesFromList) nodes
Weigh.func ("heaps " ++ show n) (heapsDrain . heapsFromList) nodes
benchmarkTime :: IO ()
benchmarkTime = do
let n = 100
nodes <- randomNodes n
Chronos.defaultMain
[ Chronos.bench ("pqueue insert/pop x" ++ show n) (pqueueDrain . pqueueFromList) nodes,
Chronos.bench ("psqueues insert/pop x" ++ show n) (psqueuesDrain . psqueuesFromList) nodes,
Chronos.bench ("heaps insert/pop x" ++ show n) (heapsDrain . heapsFromList) nodes
]
randomNodes :: Int -> IO [(Node, Level)]
randomNodes n =
zip
<$> (shuffleM =<< replicateM n randomIO)
<*> replicateM n (randomRIO (1, 10))
pqueueDrain :: Pqueue.MinPQueue Level Node -> ()
pqueueDrain q =
case Pqueue.minView q of
Nothing -> ()
Just (_, q') -> pqueueDrain q'
psqueuesDrain :: Psqueues.IntPSQ Level Node -> ()
psqueuesDrain q =
case Psqueues.minView q of
Nothing -> ()
Just (_, _, _, q') -> psqueuesDrain q'
heapsDrain :: Heaps.Heap (Heaps.Entry Level Node) -> ()
heapsDrain q =
case Heaps.viewMin q of
Nothing -> ()
Just (_, q') -> heapsDrain q'
pqueueFromList :: [(Node, Level)] -> Pqueue.MinPQueue Level Node
pqueueFromList =
foldl' (\acc (node, level) -> Pqueue.insert level node acc) Pqueue.empty
psqueuesFromList :: [(Node, Level)] -> Psqueues.IntPSQ Level Node
psqueuesFromList =
fst . foldl' step (Psqueues.empty, 1)
where
step (acc, counter) (node, level) =
let counter' = counter + 1
in counter' `seq` (Psqueues.insert counter level node acc, counter')
heapsFromList :: [(Node, Level)] -> Heaps.Heap (Heaps.Entry Level Node)
heapsFromList =
foldl'
(\acc (node, level) -> Heaps.insert (Heaps.Entry level node) acc)
Heaps.empty |
Hm. I would also prefer to switch to a more maintained library, but the problem is that these libraries offer slightly different APIs that are subtly incompatible.
In the worst case, that is if |
Ah, interesting! Yes, I ran into that pecularity in Also, perhaps relevant, the last And finally, about |
Yes, that would be clumsy. The very existence of the
It appears that
Ah, I missed that the structures permits duplicates. Still, in this case, I think that the (PS: With "for all intents and purposes", I mean that "as far as the public API is concerned, no distinction can be made". For example, if two maps from |
Fyi, |
As |
pqueue
does not seem to be very actively maintained at the moment, and lspitzner/pqueue#40 is blocking GHC 9 support over here.Just out of curiosity, I did a little bit of quick & dirty time benchmarking of the insert/pop performance of
![2021-06-01-183520_964x200_scrot](https://user-images.githubusercontent.com/1074598/120398447-46358780-c308-11eb-8e68-a25d16bfb368.png)
pqueue
vs.psqueues
vs.heaps
:Benchmark code
The text was updated successfully, but these errors were encountered: