RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).

[Aditya K <hiraditya at msn dot com>]

---------------------------------------
> 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.guenther@gmail.com
> To: stevenb.gcc@gmail.com
> CC: hiraditya@msn.com; gcc@gcc.gnu.org
>
> On Mon, Mar 9, 2015 at 11:59 PM, Steven Bosscher <stevenb.gcc@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

Attachment: splay.patch
Description: Binary data