This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] sort and group case labels
- From: Joern Rennecke <joern dot rennecke at superh dot com>
- To: stevenb at suse dot de (Steven Bosscher)
- Cc: joern dot rennecke at superh dot com (Joern Rennecke), stevenb at suse dot de (Steven Bosscher), gcc-patches at gcc dot gnu dot org
- Date: Wed, 26 May 2004 12:47:48 +0100 (BST)
- Subject: Re: [patch] sort and group case labels
> 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).
+ for (i = 0; i < old_size - 2; i++)
+ {
+ tree base_case, base_high, base_label, type;
+
+ base_case = TREE_VEC_ELT (old_labels, i);
+ if (! base_case)
+ abort ();
+
+ type = TREE_TYPE (CASE_LOW (base_case));
+ base_label = CASE_LABEL (base_case);
+ base_high = CASE_HIGH (base_case) ?
+ CASE_HIGH (base_case) : CASE_LOW (base_case);
+
+ for (j = i; j < old_size - 2; j++)
That looks solidly O(n^2) to me.
>
> 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...
case labels often come pre-sorted, so here you are relying on using a qsort
implementation that uses a strategy that avoids pathological behaviour on
sorted input. (e.g. 'mid-array value is pivot' or 'look at values of start,
mid-array and end value, and pick the middle one for the pivot' .)