Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #30412

Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)"

Show key headers only | View raw

On 11/24/2014 2:58 PM, Andreas Leitgeb wrote:
> Out of idle curiosity I stepped into StringBuilder.append(int),
> and reached non-public Integer.getChars(int,int,char[]).
>
> "    // really: r = i - (q * 100);
> "    r = i - ((q << 6) + (q << 5) + (q << 2));
>
> Is this some relict from early early days, or are 5 operations
> (3 "<<" and 2 "+") still faster than one multiplication on
> modern cpus?   Or did just no one ever care to revise it?

According to Agner's timing tables, a Nehalem processor has latency 3 
for MUL, and it can only execute in one of the superscalar lanes.  Sandy 
Bridge, Ivy Bridge, and Haswell don't do better here. Adds and shifts 
both have latency 1, and can execute in any of the two or three lanes 
for integer operations. The numbers for AMD chips seem comparable, but I 
understand their internal microarchitecture less well.

On the Atom and Silvermont (mobile) architectures, it looks like shifts 
only get one port. MUL is 5 cycle latency on Silvermont but 3 (both for 
32-bit), adds and shifts are of course 1.

I don't have timings for ARM, but my recollection was that multiply 
times sucked there.

In summary: replacing a multiply with a single shift is always better; 
replacing it with two shifts is also always better (it uses fewer ports, 
even if it takes as long as a multiply); and replacing it with three 
shifts is no overall improvement, probably, but it may allow for better 
instruction scheduling in a big block, since the instructions are finer 
granularity and can be spread out more.

Note that all of these assume word-sized multiplies. If you're doing a 
64-bit multiply on 32-bit hardware, shifts are much faster since a 
64-bit shift is 4 operations with a critical path of 2 whereas a 64-bit 
multiply is 3 multiplies and two adds with a critical path length of 3. 
And multiplies generally cannot be done in parallel.

> PS: even if it *is* still faster, I'd expect the JIT/hotspot
>    to do that optimization on its own...

Quite frankly, yes. Optimizing constant multiplies/divisions is one of 
the more fundamental optimizations in a toolkit.

-- 
Beware of bugs in the above code; I have only proved it correct, not 
tried it. -- Donald E. Knuth

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> - 2014-11-24 20:58 +0000
  Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Eric Sosman <esosman@comcast-dot-net.invalid> - 2014-11-24 16:31 -0500
    Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> - 2014-11-26 12:39 +0000
  Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Marcel Mueller <news.5.maazl@spamgourmet.org> - 2014-11-25 23:11 +0100
    Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Eric Sosman <esosman@comcast-dot-net.invalid> - 2014-11-25 17:45 -0500
      Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2014-11-25 18:39 -0600
  Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2014-11-25 18:30 -0600
    Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> - 2014-11-26 08:53 +0000
      Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2014-11-26 08:10 -0600
        Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Joerg Meier <joergmmeier@arcor.de> - 2014-11-26 17:30 +0100
    Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Joerg Meier <joergmmeier@arcor.de> - 2014-11-26 17:25 +0100
      Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2014-11-27 12:17 -0600
  Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Kevin McMurtrie <mcmurtrie@pixelmemory.us> - 2014-11-27 16:39 -0800
    Re: just for fun: JSL: "q*100" hand-optimized to "(q<<6)+(q<<5)+(q<<2)" Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> - 2014-11-29 15:17 +0000

csiph-web