sml-redprl icon indicating copy to clipboard operation
sml-redprl copied to clipboard

Consider using lists instead of splay trees for contexts

Open favonia opened this issue 6 years ago • 4 comments

In what real-life situations we will have >10 variables in a context? See #239.

favonia avatar Nov 24 '17 17:11 favonia

Yes, the profiling I've done so far suggests that splay trees are not providing us a performance benefit over lists for our application.

jonsterling avatar Nov 24 '17 22:11 jonsterling

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%

favonia avatar Feb 12 '18 03:02 favonia

@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 avatar Feb 12 '18 06:02 favonia

@favonia I think the majority of the culprits lie in sml-typed-abts and maybe sml-dependent-lcf.

jonsterling avatar Feb 12 '18 13:02 jonsterling