[ProfileData] Sort ProfilingData by hash

[Hahnfeld]

Summary

This is expected by instr-remap.test and currently fails when building
LLVM with reverse-iteration: Use std::map instead of SmallDenseMap
which has no guarantees about ordering.

[davidxl]

lgtm

[lebedev.ri]

This does look better than the D58385.
But i wonder if this is too strict and is notably slower?
Have you considered only imposing the ordering/sorting where it matters,
i.e. i think where FunctionData is used in InstrProfWriter::writeImpl() and InstrProfWriter::writeText()?

[davidxl]

The number of functions with name conflicts (and requires) using secondary map is very few, so the performance should not be affected.

[Hahnfeld]

In D58787#1413840, @lebedev.ri wrote:

Have you considered only imposing the ordering/sorting where it matters,
i.e. i think where FunctionData is used in InstrProfWriter::writeImpl() and InstrProfWriter::writeText()?

No. But AFAICS you cannot sort a SmallDenseMap, so we'd need to create another std::map just for sorting?

[davidxl]

The secondary map 'ProfileData' is needed occasionally (to use cfg hash). doing sorting with std::map is not needed strictly speaking, but it has the nice property of having fixed order.

[Hahnfeld]

In D58787#1413869, @davidxl wrote:

The secondary map 'ProfileData' is needed occasionally (to use cfg hash). doing sorting with std::map is not needed strictly speaking, but it has the nice property of having fixed order.

Yeah I know, the other approach is making the test resilient against such changes in ordering: D58385

[mgrang]

Sorry, I just saw this now. I had a patch to fix this issue (but I didn't get time to follow-up on it). See D57986.

instr-remap.test is failing 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. One way to resolve this is to use an ordered container like MapVector.

Another way to resolve this is to sort FunctionData before iteration. In fact, that is what the reviwers of D57986 suggested.

[mgrang]

llvm/include/llvm/ProfileData/InstrProfWriter.h

36

I think llvm prefers not to rely on external/STL containers. I would use a MapVector here.

[Hahnfeld]

I don't care how this is solved, but it needs to be solved! And it's not getting easier with everyone saying something different

llvm/include/llvm/ProfileData/InstrProfWriter.h

36

$ git grep "std::map" -- llvm/include/ llvm/lib/ | wc -l
426

[dblaikie]

How about we keep the discussion on the original patch (D57986)? I think we explored the problem space a fair bit there & I'll advocate for the same thing here as I did there: Sorting before emission is likely more efficient than keeping a continuously sorted container, if there's a separate "build" and "iterate" phase you can sort between. At least that's my understanding. std::map and MapVector would both grow memory usage, probably not prohibitively, but a fair bit.

Especially if these are just small clusters of collisions - they can be put in a small container, sorted, emitted, then thrown away - better than changing the whole long-lived/larger data structure.

[mgrang]

In D58787#1414176, @dblaikie wrote:

How about we keep the discussion on the original patch (D57986)? I think we explored the problem space a fair bit there & I'll advocate for the same thing here as I did there: Sorting before emission is likely more efficient than keeping a continuously sorted container, if there's a separate "build" and "iterate" phase you can sort between. At least that's my understanding. std::map and MapVector would both grow memory usage, probably not prohibitively, but a fair bit.

Especially if these are just small clusters of collisions - they can be put in a small container, sorted, emitted, then thrown away - better than changing the whole long-lived/larger data structure.

I have added sort-before-iteration for FuncData in D57986.

llvm/include/llvm/ProfileData/InstrProfWriter.h

 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <cstdint>
+#include <map>
 #include <memory>
 
 namespace llvm {
 
 /// Writer for instrumentation based profile data.
 class InstrProfRecordWriterTrait;
 class ProfOStream;
 class raw_fd_ostream;
 
 class InstrProfWriter {
 public:
-  using ProfilingData = SmallDenseMap<uint64_t, InstrProfRecord>;
+  using ProfilingData = std::map<uint64_t, InstrProfRecord>;
   enum ProfKind { PF_Unknown = 0, PF_FE, PF_IRLevel };
 
 private:
   bool Sparse;
   StringMap<ProfilingData> FunctionData;
   ProfKind ProfileKind = PF_Unknown;
   // Use raw pointer here for the incomplete type object.
   InstrProfRecordWriterTrait *InfoObj;