Add multikey_qsort to STLExtras.h

[ruiu]

Summary

So this is a generalized version of the function I added to
StringTableBuilder before. I'm not sure this is really an "STLExtra".
Is this the right place to add this function?

[grosbach]

Not 100% sure it's the best place, either; it's just what came to mind since the function we're replacing the invocation of is also there.

include/llvm/ADT/STLExtras.h

376

Does the compiler not auto-recognize the tail call pattern here? If not, it seems like it should.

[ruiu]

include/llvm/ADT/STLExtras.h

376

Unlike Scheme we cannot assume that the tail call optimization is always in place. If a compiler does tail call optimization only in -O2 and not in -O0, this code could cause SEGV only in -O0 for some input. That would be confusing. So I think this is needed.

[grosbach]

include/llvm/ADT/STLExtras.h

376

I'm not sure I agree. -O0 vs. -O2 (or -Os) builds of the compiler (and Debug vs. Release in general) already have radically different memory usage patterns and algorithmic behavior (various +asserts stuff has n^2 algorithms, e.g.).

Is this a theoretical concern, or are you seeing crashes on real examples with a debug build of the compiler?

[dblaikie]

include/llvm/ADT/STLExtras.h

376

Eh, I think we tend not to write recursive algorithms where there aren't nice/known/low bounds, even if the compiler can optimize them away (same reason we write ++i instead of i++, etc).

That said, I wouldn't write it with goto if I could help it - I'd rather find a more natural iterative expression of the issue. (even just a simple "while (true) / return" thing I'd prefer over a raw goto, but a do/while loop seems plausible here)

[ruiu]

include/llvm/ADT/STLExtras.h

376

test/MC/COFF/section-name-encoding.s fails if this is not tail-optimized. But as long as it is tail-optimized, everything should be fine. So this is kind of theoretical.

[grosbach]

include/llvm/ADT/STLExtras.h

376

That's fair. To be clear, it's the "goto" I'm having trouble swallowing. A do/while would be totally reasonable.

[silvas]

I'd really like to see sanity check performance numbers vs. std::sort to make sure that this function is worth it.

[ruiu]

Rewrite it with for(;;) to remove goto. (I was taught to think that a tail call is a jump as opposed to a call, so it was natural for me to use goto instead of for(;;) here, but I'm totally OK with for(;;) if this is more readable for others.)

[dblaikie]

include/llvm/ADT/STLExtras.h

351

This could become the loop condition? (while (End - Start > 1) ?)

It'd be possible to contort this so that the late return could be part of the loop condition too, but that might be awkward. When does getKey return a null pivot? (when does that trailing conditional return fire)

[ruiu]

• Updated as per David's comment.
• Add a comment.

include/llvm/ADT/STLExtras.h

inline void array_pod_sort(
   // Don't inefficiently call qsort with one element or trigger undefined
   // behavior with an empty sequence.
   auto NElts = End - Start;
   if (NElts <= 1) return;
   qsort(&*Start, NElts, sizeof(*Start),
         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 }
 
+template <class IteratorTy, class ValueTy>
+inline void multikey_qsort(
+    IteratorTy Start, IteratorTy End,
+    const ValueTy *(*getKey)(IteratorTy, size_t Pos),
+    int (*Compare)(const ValueTy *, const ValueTy *),
+    size_t Pos = 0) {
+  while (End - Start >= 2) {
+    // Partition items. Items in [Start, P) are less than the pivot, [P, Q)
+    // are the same as the pivot, and [Q, End) are greater than the pivot.
+    const ValueTy *Pivot = getKey(Start, Pos);
+    IteratorTy P = Start;
+    IteratorTy Q = End;
+    for (IteratorTy R = Start + 1; R < Q;) {
+      int Comp = Compare(Pivot, getKey(R, Pos));
+      if (Comp < 0)
+        std::swap(*P++, *R++);
+      else if (Comp > 0)
+        std::swap(*--Q, *R);
+      else
+        R++;
+    }
+
+    multikey_qsort(Start, P, getKey, Compare, Pos);
+    multikey_qsort(Q, End, getKey, Compare, Pos);
+
+    // Pivot is null if (*Start)'s size is shorter than Pos.
+    // If we are sorting strings, that means Pos is beyond end of *Start.
+    // In that's the case, we have already sorted all items in [P, Q).
+    if (!Pivot)
+      return;
+
+    // Repeat again with a new range. This is equivalent to
+    // multikey_qsort(P, Q, getKey, Compare, Pos + 1) but does not consume
+    // the stack.
+    Start = P;
+    End = Q;
+    ++Pos;
+  }
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <algorithm>
 //===----------------------------------------------------------------------===//
 
 /// For a container of pointers, deletes the pointers and then clears the
 /// container.
 template<typename Container>
 void DeleteContainerPointers(Container &C) {

lib/MC/StringTableBuilder.cpp

 #include "llvm/Support/Endian.h"
 
 #include <vector>
 
 using namespace llvm;
 
 StringTableBuilder::StringTableBuilder(Kind K) : K(K) {}
 
-typedef std::pair<StringRef, size_t> StringPair;
-
 // Returns the character at Pos from end of a string.
-static int charTailAt(StringPair *P, size_t Pos) {
-  StringRef S = P->first;
+static const char *charTailAt(
+    std::vector<std::pair<StringRef, size_t> *>::iterator It, size_t Pos) {
+  StringRef S = (*It)->first;
   if (Pos >= S.size())
-    return -1;
-  return (unsigned char)S[S.size() - Pos - 1];
+    return nullptr;
+  return S.data() + S.size() - Pos - 1;
 }
 
-// Three-way radix quicksort. This is much faster than std::sort with strcmp
-// because it does not compare characters that we already know the same.
-static void qsort(StringPair **Begin, StringPair **End, int Pos) {
-tailcall:
-  if (End - Begin <= 1)
-    return;
-
-  // Partition items. Items in [Begin, P) are greater than the pivot,
-  // [P, Q) are the same as the pivot, and [Q, End) are less than the pivot.
-  int Pivot = charTailAt(*Begin, Pos);
-  StringPair **P = Begin;
-  StringPair **Q = End;
-  for (StringPair **R = Begin + 1; R < Q;) {
-    int C = charTailAt(*R, Pos);
-    if (C > Pivot)
-      std::swap(*P++, *R++);
-    else if (C < Pivot)
-      std::swap(*--Q, *R);
-    else
-      R++;
-  }
-
-  qsort(Begin, P, Pos);
-  qsort(Q, End, Pos);
-  if (Pivot != -1) {
-    // qsort(P, Q, Pos + 1), but with tail call optimization.
-    Begin = P;
-    End = Q;
-    ++Pos;
-    goto tailcall;
-  }
-}
+static int compare(const char *A, const char *B) {
+  int X = A ? (unsigned char)*A : -1;
+  int Y = B ? (unsigned char)*B : -1;
+  return X - Y;
+};
 
 void StringTableBuilder::finalize() {
   std::vector<std::pair<StringRef, size_t> *> Strings;
   Strings.reserve(StringIndexMap.size());
   for (std::pair<StringRef, size_t> &P : StringIndexMap)
     Strings.push_back(&P);
 
-  if (!Strings.empty())
-    qsort(&Strings[0], &Strings[0] + Strings.size(), 0);
+  // Sort strings by suffix so that strings with the same common suffix
+  // are next to each other in the vector.
+  multikey_qsort(Strings.begin(), Strings.end(), charTailAt, compare);
 
   switch (K) {
   case RAW:
     break;
   case ELF:
   case MachO:
     // Start the table with a NUL byte.
     StringTable += '\x00';