This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [patch] sort and group case labels

On May 26, 2004 01:01 PM, Joern Rennecke <> wrote:

> > 	(gimplify_switch_expr): Sort case labels, and make sure the
> > 	last label in the label vector is the default case.

[ Note that the patch has a missing line to update base_high after grouping.
  I attached the wrong file.  ]

> That's an O(N^2) sort - that performs rather poorly when you compile
> a yacc grammer or an interpreter.

It is _worst_case_ O(N^2) but in practice it is O(N log N).
(And quicksort is typically faster than algorithms with a worst-case 
O(N log N) time complexity).

I had an implementation before this one that would build an AVL tree,
but using qsort turned out to be faster for a gcc bootstrap.
Actually I tried quicksort because rth suggested that.  When I asked
if that wouldn't be too slow, he asked back if that was sarcasm, so I
decided to just try and see...

> We parse the case labels into an AVL tree or a splay tree, so where do
> the trees loose their order?  I would consider this to be a bug.

They don't "loose" their order, they're just never ordered at all.  The trees
are only used to make sure there are no overlapping cases.  The front ends
cannot easily sort the labels because control flow is not lowered that early,
so it would require far more rechaining than such (because the case labels
are still chained in the statement list), than just sorting the label vector for


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]