On Thu, Jun 29, 2017 at 7:03 PM Xinliang David Li <davidxl at google.com> wrote:> On Thu, Jun 29, 2017 at 6:27 PM, David Blaikie <dblaikie at gmail.com> wrote: > >> I haven't tested it, but it looks to me like llvm-profdata merge (well, >> InstrProfWriter specifically) would not have deterministic output. >> >> Certainly the textual output iterates over FunctionData which is a >> StringMap of SmallDenseMaps, neither of which has deterministic iteration >> > > Does the iteration order of these maps depend on the order of hashes (of > strings for StringMap)? >Right - that's my understanding. (Some folks have started adding interesting things to LLVM to try to help weed out these sort of issues (ENABLE_REVERSE_ITERATION - though it's only been implemented in one of LLVM's containers so far))> Anyway, text dump is for debugging purpose only. >Sure, though even test cases written against this should be deterministic, but yeah - less of a concern, for sure.> . >> >> The binary writing looks like it'd have similar issues - looping through >> these unordered maps & writing output (eg: >> InstrProfRecordWriterTrait::EmitData loops through the data in the same >> SmallDenseMap and writes content in that order so far as I can tell. >> >> > 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. >Ah, so you mean the loop in InstrProfRecordWriterTrait::EmitData that inserts into the SummaryBuilder - the SummaryBuilder itself doesn't depend on the order of 'addRecord' calls - ah, I see, addRecord -> addEntryCount -> addCount -> CountFrequencies, a std::map (thus, ordered by value, independent of call order of addRecord). But inside that loop, it also starts writing directly to 'Out' based on the order of the SmallDenseMap, doesn't it? I don't immediately see anywhere that seeks within 'Out' to ensure that the loop there doesn't affect the ordering of the bytes written within it.> 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. >> > >> >> 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? >> >> > For the binary output, we definitely need deterministic behavior. For > debug output, we can relax that requirement. > > >> 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). >> >> 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) >> >> How's all that sound? >> > > 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. > > David > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170630/9b8e2f8a/attachment.html>
On Thu, Jun 29, 2017 at 7:26 PM, David Blaikie <dblaikie at gmail.com> wrote:> > > On Thu, Jun 29, 2017 at 7:03 PM Xinliang David Li <davidxl at google.com> > wrote: > >> On Thu, Jun 29, 2017 at 6:27 PM, David Blaikie <dblaikie at gmail.com> >> wrote: >> >>> I haven't tested it, but it looks to me like llvm-profdata merge (well, >>> InstrProfWriter specifically) would not have deterministic output. >>> >>> Certainly the textual output iterates over FunctionData which is a >>> StringMap of SmallDenseMaps, neither of which has deterministic iteration >>> >> >> Does the iteration order of these maps depend on the order of hashes (of >> strings for StringMap)? >> > > Right - that's my understanding. > > (Some folks have started adding interesting things to LLVM to try to help > weed out these sort of issues (ENABLE_REVERSE_ITERATION - though it's only > been implemented in one of LLVM's containers so far)) > > >> Anyway, text dump is for debugging purpose only. >> > > Sure, though even test cases written against this should be deterministic, > but yeah - less of a concern, for sure. > > >> . >>> >>> The binary writing looks like it'd have similar issues - looping through >>> these unordered maps & writing output (eg: InstrProfRecordWriterTrait::EmitData >>> loops through the data in the same SmallDenseMap and writes content in that >>> order so far as I can tell. >>> >>> >> 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. >> > > Ah, so you mean the loop in InstrProfRecordWriterTrait::EmitData that > inserts into the SummaryBuilder - the SummaryBuilder itself doesn't depend > on the order of 'addRecord' calls - ah, I see, addRecord -> addEntryCount > -> addCount -> CountFrequencies, a std::map (thus, ordered by value, > independent of call order of addRecord). > > But inside that loop, it also starts writing directly to 'Out' based on > the order of the SmallDenseMap, doesn't it? I don't immediately see > anywhere that seeks within 'Out' to ensure that the loop there doesn't > affect the ordering of the bytes written within it. >The instrProf records are organized in this order: 1) function name hashing order; 2) for two functions with identical name/name hash, the hashing order of the function CFG hash. The loop in EmitData is only for 2). It does depend on the SmallDenseMap's entry order (with hash key being uint64). For majority of the cases, the map has only 1 entry (note the string uses MD5 checksum for hashing, so the collision rate is very low. For static functions, the compiler will add module id to differentiate. For practical purpose, we can consider the map is almost always size 1. In rare cases, it may contain > 1 (e.g, a small number such as 2) entries, do you see the possibility of their orders to be different from run to run (i.e, depending on memory address)? It seems unlikely, but I have not checked the map's implementation in details to be sure. David> > >> 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. >> > >> >> >>> >>> 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? >>> >>> >> For the binary output, we definitely need deterministic behavior. For >> debug output, we can relax that requirement. >> >> >>> 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). >>> >>> 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) >>> >>> How's all that sound? >>> >> >> 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. >> >> David >> >> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170629/dee0e066/attachment.html>
On Thu, Jun 29, 2017 at 8:10 PM Xinliang David Li <davidxl at google.com> wrote:> On Thu, Jun 29, 2017 at 7:26 PM, David Blaikie <dblaikie at gmail.com> wrote: > >> >> >> On Thu, Jun 29, 2017 at 7:03 PM Xinliang David Li <davidxl at google.com> >> wrote: >> >>> On Thu, Jun 29, 2017 at 6:27 PM, David Blaikie <dblaikie at gmail.com> >>> wrote: >>> >>>> I haven't tested it, but it looks to me like llvm-profdata merge (well, >>>> InstrProfWriter specifically) would not have deterministic output. >>>> >>>> Certainly the textual output iterates over FunctionData which is a >>>> StringMap of SmallDenseMaps, neither of which has deterministic iteration >>>> >>> >>> Does the iteration order of these maps depend on the order of hashes (of >>> strings for StringMap)? >>> >> >> Right - that's my understanding. >> >> (Some folks have started adding interesting things to LLVM to try to help >> weed out these sort of issues (ENABLE_REVERSE_ITERATION - though it's only >> been implemented in one of LLVM's containers so far)) >> >> >>> Anyway, text dump is for debugging purpose only. >>> >> >> Sure, though even test cases written against this should be >> deterministic, but yeah - less of a concern, for sure. >> >> >>> . >>>> >>>> The binary writing looks like it'd have similar issues - looping >>>> through these unordered maps & writing output (eg: >>>> InstrProfRecordWriterTrait::EmitData loops through the data in the same >>>> SmallDenseMap and writes content in that order so far as I can tell. >>>> >>>> >>> 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. >>> >> >> Ah, so you mean the loop in InstrProfRecordWriterTrait::EmitData that >> inserts into the SummaryBuilder - the SummaryBuilder itself doesn't depend >> on the order of 'addRecord' calls - ah, I see, addRecord -> addEntryCount >> -> addCount -> CountFrequencies, a std::map (thus, ordered by value, >> independent of call order of addRecord). >> >> But inside that loop, it also starts writing directly to 'Out' based on >> the order of the SmallDenseMap, doesn't it? I don't immediately see >> anywhere that seeks within 'Out' to ensure that the loop there doesn't >> affect the ordering of the bytes written within it. >> > > > The instrProf records are organized in this order: > > 1) function name hashing order; > 2) for two functions with identical name/name hash, the hashing order of > the function CFG hash. > > The loop in EmitData is only for 2). It does depend on the SmallDenseMap's > entry order (with hash key being uint64). For majority of the cases, the > map has only 1 entry (note the string uses MD5 checksum for hashing, so the > collision rate is very low. For static functions, the compiler will add > module id to differentiate. For practical purpose, we can consider the map > is almost always size 1. In rare cases, it may contain > 1 (e.g, a small > number such as 2) entries, do you see the possibility of their orders to be > different from run to run (i.e, depending on memory address)? It seems > unlikely, but I have not checked the map's implementation in details to be > sure. >Ah, sorry for the distraction - realized I conflated a few things. Generally the contract for hashing containers is that they have no ordering guarantees. This means even that they may change run-over-run, for the same inputs (not even pointers where the elements change run over run due to memory layout, etc). But this applies perhaps more firmly to the standard library - LLVM should be portable & deterministic between different standard library implementations (so any dependence on the ordering of std::unordered_map would be undesirable). Dependence on the ordering of LLVM's internal containers is less of an issue - since it doesn't create portability concerns, just a minor maintenance cost if these containers are modified/improved/etc. I'm not sure anyone's interested in making LLVM independent of changes to its own internal containers hash ordering, nor how close the project is today. So I'll leave this bit alone for now - thanks for talking it through with me (: - Dave> > David > > > > >> >> >>> 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. >>> >> >>> >>> >>>> >>>> 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? >>>> >>>> >>> For the binary output, we definitely need deterministic behavior. For >>> debug output, we can relax that requirement. >>> >>> >>>> 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). >>>> >>>> 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) >>>> >>>> How's all that sound? >>>> >>> >>> 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. >>> >>> David >>> >>> >>> >>-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170705/b373014d/attachment.html>