sml-redprl
sml-redprl copied to clipboard
Consider using lists instead of splay trees for contexts
In what real-life situations we will have >10 variables in a context? See #239.
Yes, the profiling I've done so far suggests that splay trees are not providing us a performance benefit over lists for our application.
For the current semi-simplicial.prl
:
<gc> 21.9%
SplayTree.findAndSplay 8.9%
_res_Abt.abtRec 6.1%
_res_Abt.renameVars.fn.fn 4.3%
SplayTree.splay 4.2%
_res_Abt.eq 4.2%
_res_LnScope.eq 3.5%
_res_LnScope.liftTraversal 2.9%
_res_Abt.scopeReadAnn 2.5%
List.foldl.loop 2.2%
One.use 2.2%
_res_SplayRDict.foldl 1.8%
ListPair.allEq.loop 1.7%
@jonsterling I tried replacing many Splay
with List
in the RedPRL main code but SplayTree.findAndSplay
still takes significant time. I think it is coming from the libs.
@favonia I think the majority of the culprits lie in sml-typed-abts
and maybe sml-dependent-lcf
.