<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Jan 24, 2014 at 12:41 PM, Anton Korobeynikov <span dir="ltr"><<a href="mailto:anton@korobeynikov.info" target="_blank">anton@korobeynikov.info</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Jasper,<br>
<br>
As it was stated before - all these are pretty fine theoretical<br>
arguments. However, without real numbers of benchmarking it's hard to<br>
say anything definite about whether this approach is preferable.<br>
<br>
There are plenty of switches in LLVM and clang itself. Can't you<br>
provide some statistics how the stuff was lowered before and after?</blockquote><div><br></div><div>Sounds like it's worth implementing in tree, off by default, and then doing some benchmarking.</div><div><br></div><div>
FWIW, I don't think sparse switches are very common in LLVM, so it's not clear how often this optimization would fire.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5">
On Fri, Jan 24, 2014 at 11:51 PM, Jasper Neumann <<a href="mailto:jn@sirrida.de">jn@sirrida.de</a>> wrote:<br>
> Hi folks,<br>
><br>
> here is a short RFC regarding hashing for the implementation of switch<br>
> statements and my preliminary patch.<br>
> I posted this patch on 2014-01-16 21:58 at <a href="mailto:llvm-commits@cs.uiuc.edu">llvm-commits@cs.uiuc.edu</a>. You can<br>
> find a copy e.g. on<br>
> <a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140113/201782.html" target="_blank">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140113/201782.html</a>.<br>
><br>
> Best regards<br>
> Jasper<br>
><br>
> ===<br>
><br>
> Preliminary: Special identifiers<br>
><br>
> n number of given switch labels<br>
> N size of the (intermediate) hash range, usually n rounded up to the next<br>
> power of 2<br>
> x the value to be switch upon<br>
><br>
><br>
> Why (perfect) hashing?<br>
><br>
> Hashing enables a jump table like approach even for sparse label sets.<br>
> Let's concentrate on perfect hashing in order to keep the code smaller and<br>
> faster.<br>
> Hashing is faster than a decision tree provided there are enough labels,<br>
> i.e. O(1) vs. O(log n). For x86 the break-even point is about 6..8 labels<br>
> assuming random values of x.<br>
> The memory consumption of the hashing tables is comparable to the memory<br>
> footage of the code of a decision tree.<br>
> A decision tree consumes a lot of branch prediction resources.<br>
> For minimal perfect hashing the jump table does not need to contain dummy<br>
> labels and therefore has n instead of (almost) N elements.<br>
> "Switch-to-lookup tables": If all jump targets are sufficiently similar<br>
> hashing opens the possibility to use table which contain the differences.<br>
> Thereby the indirect jump is eliminated and we get a huge performance gain.<br>
><br>
><br>
> Why not hashing?<br>
><br>
> A decision tree or even an else-if chain is faster than hashing for very few<br>
> labels.<br>
> The branch prediction logic usually does not work as satisfactorily as for<br>
> decision trees if fed with cyclical access patterns; i.e. the break-even<br>
> point in this scenario is higher.<br>
> Hashing can not deal with large label ranges since very single label is<br>
> treated. A possible compromise/solution might be to first catch all single<br>
> labels and sufficiently short ranges by hashing and then treat the remaining<br>
> ranges in a decision tree.<br>
><br>
><br>
> Why reversible hashing?<br>
><br>
> Reversible hashing does not need a value table and a simple range check of<br>
> the calculated hash value is sufficient.<br>
> Reversible hashing is very simple to implement.<br>
> The usual jump table approach is a special case of reversible hashing.<br>
><br>
><br>
> Why simple hashing?<br>
><br>
> A comparison against a value table is sufficient.<br>
> Simple hashing does not need an extra table.<br>
><br>
><br>
> Why not simple hashing?<br>
><br>
> Simple hashing needs a lot of hash function candidates to be tested until a<br>
> suitable is found; this costs time in the compiler.<br>
> For large label sets the chance to find such a function is very small; the<br>
> applicability is therefore reduced to quite small sets.<br>
> Minimal perfect hashing is usually not achievable.<br>
><br>
><br>
> Why Jenkins' hashing?<br>
><br>
> Jenkins' hashing produces very fast and compact code and needs one extra<br>
> table (BTable) with usually less elements than n; the elements itself are<br>
> unsigned integers which can become as high N-1.<br>
> The code first generates two hash values h1=f1(x) and h2=f2(x) where f1 and<br>
> f2 limit their range by shifting or masking, then the final hash as h = h1 ^<br>
> BTable[h1].<br>
> Minimal perfect hashing is achievable, albeit often at the cost of larger<br>
> tables.<br>
> For sufficiently high N the table memory can optionally be reduced by<br>
> introducing an extra scrambling table (STable); BTable then consists of<br>
> bytes whereas STable contains 256 words or DWords. Obviously this reduction<br>
> of memory costs another indirection in the resulting code.<br>
> As far as I tested Jenkins' hashing can be used for label sets of several<br>
> thousand elements; often even one million labels can be treated.<br>
> The application in a compiler is to lower switch statements. Switch<br>
> statements with much more than 1000 labels are almost never present in<br>
> practice.<br>
> Jenkins' hashing usually is sufficiently fast.<br>
> By the way: You will find the following remark in lib/Target/README.txt:<br>
> ==><br>
> Investigate lowering of sparse switch statements into perfect hash tables:<br>
> <a href="http://burtleburtle.net/bob/hash/perfect.html" target="_blank">http://burtleburtle.net/bob/hash/perfect.html</a><br>
> <==<br>
><br>
><br>
> Why not Jenkins' hashing?<br>
><br>
> The search time of Jenkins' hashing might become unacceptably long for<br>
> extraordinary large label sets.<br>
> In practice this should never happen, however in this case the label set<br>
> will be split in two parts are the process of lowering switches will be<br>
> repeated.<br>
> An alternative (for very large label sets) could be a different perfect hash<br>
> algorithm such as CHM.<br>
><br>
><br>
> Why CHM?<br>
><br>
> CHM is extraordinarily fast at generating the extra table with a runtime of<br>
> O(1).<br>
> CHM can be used to hash almost arbitrarily many labels.<br>
> CHM produces an ordered minimal perfect hashing function.<br>
><br>
><br>
> Why not CHM?<br>
><br>
> CHM needs extra table space of 2.09 * n elements; this is larger compared to<br>
> Jenkins' method.<br>
> CHM (in the implementation of cmph-2.0) is much more complicated than the<br>
> code of Jenkins' hashing:<br>
> h1 = f1(x) % N;<br>
> h2 = f2(x) % N;<br>
> if (h1 == h2 && ++h2 >= N) h2 = 0;<br>
> h = (Table[h1] + Table[h2]) % n;<br>
> By enlarging N to a power of 2 and other tweaking we might replace the 3<br>
> modulo operations by shifting or masking at the cost of more table space. We<br>
> might also eliminate the conditional statement if in this case we choose<br>
> different hash functions and retry the calculation.<br>
> There is at least one more table access compared to Jenkins' method.<br>
><br>
> ===<br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
<br>
<br>
</div></div><span class="HOEnZb"><font color="#888888">--<br>
With best regards, Anton Korobeynikov<br>
Faculty of Mathematics and Mechanics, Saint Petersburg State University<br>
</font></span><div class="HOEnZb"><div class="h5">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</div></div></blockquote></div><br></div></div>