Hello Anton! > Some of the behavior seen there was for a purpose, > like the heuristics to overcome different problems. > I have to remember all the details :) I have read your article "Improving Switch Lowering for The LLVM Compiler System" and thought that the selection mechanism works out well; by chance however I found that this mechanism does not work as designed if labels are sufficiently sparse and can effectively create an else-if chain because separated (single) marginal (i.e. first and last) labels have a too high weight. The central point might be: What is the density of a single label? It might also be that the logarithmic metric is not always working well. My simple modification however seems to be a solution to this special problem; until now I have not found any malicious secondary effects (collateral damages). By the way: I have submitted the patch to llvm-commits at cs.uiuc.edu few minutes ago; perhaps you are the person with the best knowledge for this problem. I'm currently working on switch lowering using hashing which can fully replace the jump table method. It works quite good by now but I will have to prepare a ton of documentation and test stuff. Some of the remaining problems can easily be solved later. Is anybody interested in beta-testing my patches therefor? Best regards Jasper Neumann
> I'm currently working on switch lowering using hashing which can fully > replace the jump table method. It works quite good by now but I will have to > prepare a ton of documentation and test stuff. Some of the remaining > problems can easily be solved later.Is it somehow similar to MRST (multi-way radix search trees) technique? -- With best regards, Anton Korobeynikov Faculty of Mathematics and Mechanics, Saint Petersburg State University
I'd be interested in giving it a shot if you'd like some performance testing done. -eric On Sat Jan 11 2014 at 8:56:18 AM, Jasper Neumann <jasper.neumann at web.de> wrote:> Hello Anton! > > > Some of the behavior seen there was for a purpose, > > like the heuristics to overcome different problems. > > I have to remember all the details :) > > I have read your article "Improving Switch Lowering for The LLVM > Compiler System" and thought that the selection mechanism works out > well; by chance however I found that this mechanism does not work as > designed if labels are sufficiently sparse and can effectively create an > else-if chain because separated (single) marginal (i.e. first and last) > labels have a too high weight. > The central point might be: What is the density of a single label? > It might also be that the logarithmic metric is not always working well. > > My simple modification however seems to be a solution to this special > problem; until now I have not found any malicious secondary effects > (collateral damages). > > By the way: I have submitted the patch to llvm-commits at cs.uiuc.edu few > minutes ago; perhaps you are the person with the best knowledge for this > problem. > > I'm currently working on switch lowering using hashing which can fully > replace the jump table method. It works quite good by now but I will > have to prepare a ton of documentation and test stuff. Some of the > remaining problems can easily be solved later. > Is anybody interested in beta-testing my patches therefor? > > Best regards > Jasper Neumann > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140111/9923fe49/attachment.html>
Hello Anton,>> I'm currently working on switch lowering using hashing which can fully >> replace the jump table method. It works quite good by now but I will have to >> prepare a ton of documentation and test stuff. Some of the remaining >> problems can easily be solved later.> Is it somehow similar to MRST (multi-way radix search trees) technique?Well, yes and no. The idea is to catch all switch labels with a single perfect hash function which transforms the label values into a small range of numbers. One test follows and thereafter we can dispatch with a jump table. This is especially effective if the switch labels are sparse. The normal jump table approach is a special case thereof. The MRST technique can be seen as an imperfect hashing approach. Larger ranges ought to be treated later by MRST or a decision tree; unfortunately I could not yet get this running. A detailed discussion can be found in http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf ("A Superoptimizer Analysis of Multiway Branch Code Generation" by Roger Anthony Sayle, 2008). Best regards Jasper Neumann