[ProfileData] Sort FuncData before iteration to remove non-determinism

[mgrang]

tools/llvm-profdata/instr-remap.test is failing in the reverse iteration bot. See http://lab.llvm.org:8011/builders/reverse-iteration/builds/10546/steps/check_all/logs/stdio.

This is because FunctionData is iterated in InstrProfWriter to output function counts, etc. But for two functions with the same name the iteration order is not defined if we use a DenseMap. Changing this to MapVector resolves this.

Note: We can also sort FunctionData before iteration to fix this issue. But that would mean we would need to sort every time we iterate in order to print. Using a MapVector instead is a better option IMO.

[mgrang]

Ping for reviews please.

[vsk]

I think this could roughly double the memory utilization of the writer, which might be problematic because the number of records to write can be high. (@dblaikie did some work on reducing memory usage in this area, he might have hard data about this.)

As the write should only occur once, maybe the better tradeoff would be to sort?

[dblaikie]

In D57986#1398271, @vsk wrote:

I think this could roughly double the memory utilization of the writer, which might be problematic because the number of records to write can be high. (@dblaikie did some work on reducing memory usage in this area, he might have hard data about this.)

As the write should only occur once, maybe the better tradeoff would be to sort?

Yeah, unless I'm missing something (quite possibly) this seems like the sort of place where "do a bunch of processing, then sort, then iterate" is a valid strategy.

@mgrang - does it look like any use case is emitting more than once & modifying in between? I would find that pretty surprising. I think it's just "build build build, stop building, emit" and adding a sort-before-emit would be OK there.

[Hahnfeld]

I think this patch is right in also sorting the function names: AFAICS StringMap doesn't provide that guarantee.

lib/ProfileData/InstrProfWriter.cpp

393–403

Please run clang-format, the lambda should only be indented by two additional spaces. Also can you put the explicit types for nameA et al.? That should be StringRef and uint64_t for the hashes.

[dblaikie]

lib/ProfileData/InstrProfWriter.cpp

390–398

I guess you could write this as:

return std::tie(A.first, A.second.first) < std::tie(B.first, B.second.first);

perhaps?

[dblaikie]

lib/ProfileData/InstrProfWriter.cpp

399–400

Inconsistent variable naming? (some start with upper case, some with lower case)

Currently I think the LLVM style says upper case is required.

Naming the types here might be reasonable for readability, but I'm not sure.

[mgrang]

Addressed comments.

lib/ProfileData/InstrProfWriter.cpp

void InstrProfWriter::writeRecordInText(StringRef Name, uint64_t Hash,
 
   OS << "\n";
 }
 
 Error InstrProfWriter::writeText(raw_fd_ostream &OS) {
   if (ProfileKind == PF_IRLevel)
     OS << "# IR level Instrumentation Flag\n:ir\n";
   InstrProfSymtab Symtab;
-  for (const auto &I : FunctionData)
-    if (shouldEncodeData(I.getValue()))
+
+  using FuncPair = detail::DenseMapPair<uint64_t, InstrProfRecord>;
+  using RecordType = std::pair<StringRef, FuncPair>;
+
+  SmallVector<RecordType, 4> OrderedFuncData;
+  for (const auto &I : FunctionData) {
+    if (shouldEncodeData(I.getValue())) {
       if (Error E = Symtab.addFuncName(I.getKey()))
         return E;
-
-  for (const auto &I : FunctionData)
-    if (shouldEncodeData(I.getValue()))
       for (const auto &Func : I.getValue())
-        writeRecordInText(I.getKey(), Func.first, Func.second, Symtab, OS);
+        OrderedFuncData.push_back(std::make_pair(I.getKey(), Func));
+    }
+  }
+
+  llvm::sort(OrderedFuncData, [](const RecordType &A, const RecordType &B) {
+                                 auto nameA = A.first;
+                                 auto nameB = B.first;
+                                 int comp = nameA.compare(nameB);
+                                 if (comp)
+                                   return comp < 0;
+
+                                 auto hashA = A.second.first;
+                                 auto hashB = B.second.first;
+                                 return hashA < hashB;
+                              });
+
+  for (const auto &record : OrderedFuncData) {
+    const auto &name = record.first;
+    const auto &Func = record.second;
+    writeRecordInText(name, Func.first, Func.second, Symtab, OS);
+  }
+
   return Error::success();
 }