<div dir="ltr">This looks (not closely checked) like it's implementing the first part of pop1() combined with the last part of pop3(). Which is suggested in the comment just after pop1().<div><br></div><div><a href="http://www.hackersdelight.org/hdcodetxt/pop.c.txt">http://www.hackersdelight.org/hdcodetxt/pop.c.txt</a><br></div><div><br></div><div>And then anding with 1, obviously.</div><div><br></div><div>I wonder if division is good enough on modern machines to make pop2() faster.</div><div><br></div><div>XORing down to a byte and then using the x86 built in parity flag is obviously better if you are on an x86, of course. Other machines don't usually have that.</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jul 20, 2018 at 11:02 AM, via cfe-dev <span dir="ltr"><<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="#0563C1" vlink="#954F72"><div class="m_-5226560529932248255WordSection1"><p class="MsoNormal">Hello all!<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">I’ve been mucking around in an old codebase at work looking for easy performance wins. One avenue involves replacing a switch-based variable assignment with something derived from the parity of an input variable. I was pretty surprised when I saw the generated assembly, and I’m wondering about the reasoning behind it.<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">In short, it boils down to the assembly <span style="font-family:Consolas">__builtin_parity()</span> produces. Clang 6.0.1 (and trunk on Godbolt) produces:<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal"><span style="font-family:Consolas">parity(int): <wbr> # @parity(int)<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> mov eax, edi<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> shr eax<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> and eax, 1431655765<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> sub edi, eax<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> mov eax, edi<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> and eax, 858993459<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> shr edi, 2<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> and edi, 858993459<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> add edi, eax<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> mov eax, edi<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> shr eax, 4<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> add eax, edi<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> and eax, 17764111<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> imul eax, eax, 16843009<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> shr eax, 24<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> and eax, 1<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> ret<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"><u></u> <u></u></span></p><p class="MsoNormal">While GCC 8.1.0 (and trunk on Godbolt) produces<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal"><span style="font-family:Consolas">parity(int):<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> mov eax, edi<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> shr edi, 16<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> xor eax, edi<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> xor al, ah<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> setnp al<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> movzx eax, al<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"> ret<u></u><u></u></span></p><p class="MsoNormal"><span style="font-family:Consolas"><u></u> <u></u></span></p><p class="MsoNormal">I know a popcnt followed by an and would be better, but unfortunately some of my users don’t have computers that support the popcnt instruction, so I can’t use a newer -march flag.<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">Could someone explain why the difference between Clang and GCC here, and whether it should make a difference? The code in question is in a hot loop in my code, so I’d imagine the size difference could impact unrolling (and result in icache differences too), but I haven’t finished poking around with benchmarks.<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">Thanks,<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">Alex <u></u><u></u></p></div></div><br>______________________________<wbr>_________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/cfe-dev</a><br>
<br></blockquote></div><br></div>