--------------------------------------- > Date: Tue, 10 Mar 2015 11:20:07 +0100 > Subject: Re: Proposal for adding splay_tree_find (to find elements without > updating the nodes). > From: richard.guent...@gmail.com > To: stevenb....@gmail.com > CC: hiradi...@msn.com; gcc@gcc.gnu.org > > On Mon, Mar 9, 2015 at 11:59 PM, Steven Bosscher <stevenb....@gmail.com> > wrote: >> On Mon, Mar 9, 2015 at 7:59 PM, vax mzn wrote: >>> w.r.t, https://gcc.gnu.org/wiki/Speedup_areas where we want to improve the >>> performance of splay trees. >>> >>> The function `splay_tree_node splay_tree_lookup (splay_tree, >>> splay_tree_key);' >>> updates the nodes every time a lookup is done. >>> >>> IIUC, There are places where we call this function in a loop i.e., we >>> lookup different elements every time. >>> e.g., >>> In this exaple we are looking for a different `t' in each iteration. >> >> >> If that's really true, then a splay tree is a horrible choice of data >> structure. The splay tree will simply degenerate to a linked list. The >> right thing to do would be, not to "break" one of the key features of >> splay trees (i.e. the latest lookup is always on top), but to use >> another data structure. > > I agree with Steven here and wanted to say the same. If you don't > benefit from splay trees LRU scheme then use a different data structure. > > Richard. > >> Ciao! >> Steven
Thanks Richard and Steven for the feedback. I tried to replace the use of splay
tree with std::map, and got it to bootstrap.
The compile time on a few runs shows improvement but I wont trust those data
because it is too good to be true.
Maybe, I dont have enough data points and this machine runs other things too.
1
Baseline: 1426175470 (SHA:7386c9d)
Patch:1426258562 (SHA:592c06f)
2 Program
| CC_Time CC_Real_Time
CC_Time CC_Real_Time
3 MultiSource/Applications/ALAC/decode/alacconvert-decode
| 4.2605 4.9840 2.6455 3.0826
4 MultiSource/Applications/ALAC/encode/alacconvert-encode
| 4.3124 4.9600 2.7138 3.0725
5 MultiSource/Applications/Burg/burg
| 5.6053 6.4204
3.5663 4.0837
6 MultiSource/Applications/JM/ldecod/ldecod
| 33.3773 35.9444 20.7180
22.4260
7 MultiSource/Applications/JM/lencod/lencod
| 74.2836 78.6588 47.3016
50.0484
8 MultiSource/Applications/SIBsim4/SIBsim4
| 5.5832 5.8932
3.0524 3.2456
9 MultiSource/Applications/SPASS/SPASS
| 67.4992 72.1056
43.2258 45.7996
10 MultiSource/Applications/aha/aha
| 0.5019 0.5894
0.3860 0.4406
11 MultiSource/Applications/d/make_dparser
| 13.4930 14.5575
8.5084 9.2331
12 MultiSource/Applications/hbd/hbd
| 4.7727 5.9225
2.9896 3.8366
13 MultiSource/Applications/hexxagon/hexxagon
| 3.1735 3.6957 1.8297
2.2171
14 MultiSource/Applications/kimwitu++/kc
| 29.6117 31.8364
18.0744 19.5862
15 MultiSource/Applications/lambda-0.1.3/lambda
| 4.5274 4.9125
2.7136 2.9241
I have attached my patch. Please give feedback/suggestions for improvement.
Thanks
-Aditya
splay.patch
Description: Binary data
