Skip to content

Improve worst-case bounds #24

@treeowl

Description

@treeowl

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.

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions