lspitzner / pqueue

Haskell priority queue package
Other
15 stars 13 forks source link

Improve worst-case bounds #24

Closed treeowl closed 2 years ago

treeowl commented 3 years ago

Some operations are lazier than they need to be, which seems to lead to linear worst-case bounds rather than logarithmic ones, presumably to the detriment of cache utilization. In particular, when an insertion cascades (carries), it should first force the tail that it's about to carry into. So in particular, we should have at least

incr :: LEq a -> BinomTree rk a -> BinomForest rk a -> BinomForest rk a
incr le t f0 = t `seq` case f0 of
  Nil  -> Cons t Nil
  Skip f     -> Cons t f
  Cons t' f' -> f' `seq` Skip (incr le (t `cat` t') f')
  where  cat = joinBin le

but probably actually

incr :: LEq a -> BinomTree rk a -> BinomForest rk a -> BinomForest rk a
incr le t f0 = t `seq` case f0 of
  Nil  -> Cons t Nil
  Skip f     -> Cons t f
  Cons t' f' -> let blah = t `cat` t' in f' `seq` blah `seq` Skip (incr le blah f')
  where  cat = joinBin le

On deletion, we probably want to be sure to force the entire result spine; I'm not sure what's involved in making that happen.

treeowl commented 3 years ago

A simpler approach is to make a Cons strict in its cdr (leaving the Skips lazy). That's actually more eager than necessary, but it would be a better starting point than gratuitous laziness.

treeowl commented 3 years ago

The fundamental rule: we should never, ever produce a thunk chain. Another rule of thumb that's served me very well: never suspend O(1) work. And another good guideline with some exceptions: don't suspend work if you can do it immediately without breaking the amortized bounds.

treeowl commented 3 years ago

I'm putting together a PR for this. I've finished the plain version and am working on the key-value one. It's almost all straightforward; the main complication is that I also want to calculate the minimum for extraction on the way down instead of on the way up, to avoid building chains of thunks that may eventually be forced to rebuild the forest. Nothing too terrible.