GCC 3.3 compile speed regression - AN ANSWER

[Lars Segerlund]

  Not necessarily that simple,

   The thing is when you build a datastructure such as a tree, make it 
lean and still able to contain all the information that you will ned 
later, many times you keep on regenerating information which you have 
thrown away.

   As an example, a searching algorithm such as a djikstra ( breadth 
first ) can be made furiously fast ba adding backward pointers to 
'nodes' already traversed. Marching a tree this way is FAST ! ( however 
getting rid of loops is interesting :-) ).

   I think that the tree -> ssa -> rtl is a quite sound strategy, but 
greater care have to be made as for the locality and 
deallocation/allocation of data. The used structures must be tuned to 
the algoritms used.

   You *really* want ssa .... trust me on this one ;-) ...

   Check out the O(1) scheduler in the linux kernel, from what I can see 
a large part of it's performance is tuning the data representation to 
the algoritm ( or rather making it possible in O(1) ).

  ( btw. is the timing for the mouse driver in 2.5.60 still wiolating 
spec ? ;-) ).

  / regards, and thanks for linux ! , Lars Segerlund.

Linus Torvalds wrote:
> In article <Pine.LNX.4.33.0302112331070.27761-100000@kern.srcf.societies.cam.ac.uk> you write:
> 
>>On Tue, 11 Feb 2003, Michael S. Zick wrote:
>>
>>
>>>1) Give the problem/solution the recognition it deserves in the form of
>>>a separate branch, solely for this specific purpose.
>>
>>We *have* the faster-compiler-branch, created at the same time as
>>gcc-3_4-basic-improvements-branch
>><http://gcc.gnu.org/ml/gcc/2002-08/msg01575.html>.  It just hasn't been
>>used, whereas BIB was extensively used.
> 
> 
> I bet the reason it didn't get used is simply that making the compile
> faster is a hell of a lot harder than just adding a few improvements.
> 
> The thing is, if you want to make gcc faster, you have to bite the
> bullet and throw out code that doesn't perform well.  And you have to
> _remove_ phases of optimization, instead of adding new ones.  Having
> different phases where you operate on different kinds of data structures
> (ie tree -> ssa -> rtl) is just fundamentally slow, as you have to
> marshall the data into the right format for the next phase (which is
> likely bad for caches too). 
> 
> And I don't think anybody is really interested enough to do it. And as
> long as it doesn't get done, the rest of the performance improvements
> are going to be completely hidden in the noise.
> 
> The CPP rewrite is a good example of better performance by just getting
> rid of code, not by massaging it. Make the thing more integrated, so
> that the next "phase" of the compiler can use the data structures
> in-place.
> 
> I bet that people working on the recursive-descent parser will get quite
> noticeable speeups, _especially_ if the parser can build up the parse
> tree in a format where the tree is directly usable for the tree
> optimization phase and doesn't need any more munging.
> 
> Then the next step would likely be to jump over the SSA and RTL phases,
> and generate code directly from the same tree-based thing.  That's how
> most historical compilers used to work, afaik. For well-written C, you
> don't need much else anyway.
> 
> 			Linus
>