search

JuliaServices / TreeTransform.jl

A Julia package to transform the nodes of a tree until it reaches a fixed point.
Other
3 stars 1 forks source link

Accidentally Quadratic #13

Open gafter opened 1 year ago

gafter commented 1 year ago

Apparently this package is (accidentally) quadratic. See https://gist.github.com/gafter/a231febe5a7ec09bfa4968b46d97a970

We should figure out why and fix it. It might be the equality relation used in a hash table.

gafter commented 1 year ago

Ah, TreeTransform is quadratic because comparing trees for equality is linear in the size of the tree. I'm working on an option for @auto_hash_equals where it will make the type a reference type and make all of the fields const so it can write a much more efficient == implementation. That appears to solve the problem for TreeTransform (but not for innermost)