<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jun 29, 2017 at 6:27 PM, David Blaikie <span dir="ltr"><<a href="mailto:dblaikie@gmail.com" target="_blank">dblaikie@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I haven't tested it, but it looks to me like llvm-profdata merge (well, InstrProfWriter specifically) would not have deterministic output.<br><br>Certainly the textual output iterates over FunctionData which is a StringMap of SmallDenseMaps, neither of which has deterministic iteration</div></blockquote><div><br></div><div>Does the iteration order of these maps depend on the order of hashes (of strings for StringMap)?    Anyway, text dump is for debugging purpose only.</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">.<br><br>The binary writing looks like it'd have similar issues - looping through these unordered maps & writing output (eg: InstrProfRecordWriterTrait::<wbr>EmitData loops through the data in the same SmallDenseMap and writes content in that order so far as I can tell.<br><br></div></blockquote><div><br></div><div>Binary dump does not have the problem. The binary format  of the indexed profile data is on-disk hashtable. Before serializing into the disk, the instProfRecord is first inserted into the in memory hashtable and the hashtable is then dumped into the disk. The entry order of the hashtable only depends on the string hashes and in case of conflicts, the function content hash.  </div><div><br></div><div>If you do see case of non-determinism, then we have a bug there which should be fixed, but there is no need to change the iteration order of the IntrProfWriter.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br>Generally it's important that the compiler (& I believe related tools) have deterministic output. Is there a reason that wouldn't be the case for llvm-profdata? Or have I misunderstood how the output is determined?<br><br></div></blockquote><div><br></div><div>For the binary output, we definitely need deterministic behavior.  For debug output, we can relax that requirement.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br>Ensuring deterministic output may be expensive in terms of memory usage, though perhaps not prohibitive. The usual approach is to use some of LLVM's deterministic maps (like MapVector), though they're not exactly tuned for memory usage. An alternative might be to take the data in each SmallDenseMap and sort it by the hash as a key - it's unique after all, and doing each map separately won't do crazy bad things to memory usage (a small constant overhead).<br><br>Handling the StringMap, I'm not sure about - it might be cheap enough to make a separate vector of StringMapEntry*s, sorting based on the strings and iterating over that instead of the StringMap itself? (I guess the same approach could be taken with the SmallDenseMaps, rather than duplicating anything)<br><br>How's all that sound?</div></blockquote><div><br></div><div>See above -- I don't think we have a need to change the use of StringMap.  If we see a case where the non-determinism happens, we need to root-cause it first.</div><div><br></div><div>David</div><div><br></div><div> </div></div><br></div></div>