This is the mail archive of the
mailing list for the GCC project.
Re: [patch] sort and group case labels
- From: Steven Bosscher <stevenb at suse dot de>
- To: Joern Rennecke <joern dot rennecke at superh dot com>
- Cc: Steven Bosscher <stevenb at suse dot de>, gcc-patches at gcc dot gnu dot org
- Date: Wed, 26 May 2004 13:14:13 +0200 (CEST)
- Subject: Re: [patch] sort and group case labels
- Organization: SuSE Linux AG
- References: <200405261101.i4QB1AE07386@linsvr1.uk.superh.com>
On May 26, 2004 01:01 PM, Joern Rennecke <email@example.com> 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