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

Groups > comp.lang.java.programmer > #30400 > unrolled thread

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

Back to article view | Back to comp.lang.java.programmer

Contents

  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

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

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?

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

[toc] | [next] | [standalone]

#30401

On 11/24/2014 3: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?

     Beats me.  Have you measured a difference?  (Or tried to;
micro-measurements of Java performance are notoriously hard to
do well.)

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

     Since the immediately preceding line is

	q = i / 100;

... and since `i' is known to be positive, I'd expect an immediately
following `r = i % 100;' to be recognizable by most optimizers as
"Divide once, getting quotient and remainder, use both outputs."

     Andreas, I think you've spotted a certifiable Oddity.  I will
instruct the Secretary to make a notation in the record books.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#30416

Eric Sosman <esosman@comcast-dot-net.invalid> wrote:
> On 11/24/2014 3: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?
>      Beats me.  Have you measured a difference?  (Or tried to;

Nope, not even tried. It was more of a fun finding for me,
than a scientific task :)

>      Andreas, I think you've spotted a certifiable Oddity.  I will
> instruct the Secretary to make a notation in the record books.

https://www.flickr.com/photos/76992789@N02/6967641276/ ;-)

[toc] | [prev] | [next] | [standalone]

#30410

On 24.11.14 21.58, 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?

I tend to agree: it is an anachronism.
It makes absolutely no sense with respect to performance, especially in 
case of Java or other JIT languages, where an important goal is that the 
JIT optimizer /understands/ your code to do platform specific 
optimizations. And I am pretty sure that multiplication by a constant is 
understood by the JIT.

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

Exactly. And if you put hand optimized code for a single platform into 
the JIT it is likely to fail sadly on other platforms. Especially if the 
target platform is not optimized for the rarely used shift operations 
and does not have a barrel shifter.

However, there might be another subtile difference. The above code does 
an /unsigned/ multiplication rather than a signed one. So it effectively 
can handle a wider range of input numbers. Don't know whether this 
counts in your context.


Marcel

[toc] | [prev] | [next] | [standalone]

#30411

On 11/25/2014 5:11 PM, Marcel Mueller wrote:
> On 24.11.14 21.58, 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));
>>  [...]
> However, there might be another subtile difference. The above code does
> an /unsigned/ multiplication rather than a signed one. So it effectively
> can handle a wider range of input numbers. Don't know whether this
> counts in your context.

     As it happens, no: Thanks to surrounding code, it is known that
`65536 <= i && i <= Integer.MAX_VALUE && q == i / 100'.  No minus
signs nor overflow to worry about.

     I'm wondering, though, about the distinction you draw between
signed and unsigned multiplication.  Given that Java (unlike C, say)
demands two's complement arithmetic, what's the difference?  Is
there *any* integer `q' for which shift-and-add and times-100 produce
different outcomes?

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#30413

On 11/25/2014 4:45 PM, Eric Sosman wrote:
>      I'm wondering, though, about the distinction you draw between
> signed and unsigned multiplication.  Given that Java (unlike C, say)
> demands two's complement arithmetic, what's the difference?  Is
> there *any* integer `q' for which shift-and-add and times-100 produce
> different outcomes?

In two's complement arithmetic, signed and unsigned multiplication are 
exactly identical. Replacing a multiplication with a series of 
shifts-and-adds is therefore completely legal for both signed and 
unsigned multiplies. It's division where the conversion between division 
and shifts is extremely laden with pitfalls.

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

[toc] | [prev] | [next] | [standalone]

#30412

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

[toc] | [prev] | [next] | [standalone]

#30415

Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> wrote:
> 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[]).
>> [...]
>> 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.

Thanks for throwing in this information of current state of cpu-timings.

Last book I had mentioning those was about 8088/86 processors :-)
And latest hearsay was, that on sufficiently new cpus even a floating
point operations took one mere cpu-cycle - not so sure about that anymore.

I'm not very knowing about modern cpu feature names, but not-requiring
a "superlane" sure sounds like an advantage in the lowest levels.

> 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.

I haven't looked into the (presumed) Long.getChars(...) method, yet.

>> 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.

Thanks for confirming that.
  (If it were different, I'd have thanked for correction, of course :-)

[toc] | [prev] | [next] | [standalone]

#30418

On 11/26/2014 2:53 AM, Andreas Leitgeb wrote:
> Last book I had mentioning those was about 8088/86 processors :-)
> And latest hearsay was, that on sufficiently new cpus even a floating
> point operations took one mere cpu-cycle - not so sure about that anymore.

Eh..... modern processors are heavily pipelined, so "taking one 
cpu-cycle" is a bit of a misnomer. The latencies of an SSE floating 
point add is 3, but it has a throughput of 1 per cycle.

Although I should point out that x86 processors have something like 
10-15 stages of "fetch" and "decode" due to the complex nature of their 
instruction set... which means the most painful thing you can do is 
mispredict a branch and have to flush the pipeline.

> I'm not very knowing about modern cpu feature names, but not-requiring
> a "superlane" sure sounds like an advantage in the lowest levels.

A modern desktop x86 processor is an out-of-order, superscalar 
processor. Effectively, this means that the "execute instruction" stage 
is basically a step where the processor ignores the order of 
instructions you listed in the assembly but rather throws them in 
several execution units as they become available. The Haswell 
microarchitecture (the latest as of this writing) has 8 execution units 
or ports: Two for loads, two for stores, one for branches, one for 
vectors, two for floating point or vectors. Basic integer operations can 
operate in any of the last four ports.

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

[toc] | [prev] | [next] | [standalone]

#30420

On Wed, 26 Nov 2014 08:10:18 -0600, Joshua Cranmer ������ wrote:

> Although I should point out that x86 processors have something like 
> 10-15 stages of "fetch" and "decode" due to the complex nature of their 
> instruction set... which means the most painful thing you can do is 
> mispredict a branch and have to flush the pipeline.

That is a low level detail that I always stumbled over and was surprised.
While I had always avoided branching in my OpenGL/GLES code because I knew
about the issues there, I would have never thought there to be any point in
considering branches carefully on desktop.

Liebe Gruesse,
		Joerg

-- 
Ich lese meine Emails nicht, replies to Email bleiben also leider
ungelesen.

[toc] | [prev] | [next] | [standalone]

#30419

On Tue, 25 Nov 2014 18:30:41 -0600, Joshua Cranmer ������ wrote:

> MUL is 5 cycle latency on Silvermont but 3

Can you reword that sentence part (I think it stood on its own) ? I'm a bit
confused by the wording.

Liebe Gruesse,
		Joerg

-- 
Ich lese meine Emails nicht, replies to Email bleiben also leider
ungelesen.

[toc] | [prev] | [next] | [standalone]

#30435

On 11/26/2014 10:25 AM, Joerg Meier wrote:
> On Tue, 25 Nov 2014 18:30:41 -0600, Joshua Cranmer ������ wrote:
>
>> MUL is 5 cycle latency on Silvermont but 3
>
> Can you reword that sentence part (I think it stood on its own) ? I'm a bit
> confused by the wording.

Oops, I forgot a few words (and transposed the architectures!). It 
should be 5 cycles on Atom but 3 on Silvermont.

P.S. Your newsgroup client appears to have a few chokes on Unicode 
characters. :-)

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

[toc] | [prev] | [next] | [standalone]

#30436

In article <slrnm7770k.uoi.avl@login.logic.tuwien.ac.at>,
 Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> 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?
> 
> PS: even if it *is* still faster, I'd expect the JIT/hotspot
>   to do that optimization on its own...

I've found that ints and floats have the same performance on x86, as do 
longs and doubles.  A mix of the two seems to perform even better.  This 
actually worked out well for me.  I replaced some fixed-point int with 
float and the code ran significantly faster.  The very slight difference 
in output wasn't an issue so it was a win for performance and 
readability.

-- 
I will not see posts from astraweb, theremailer, dizum, or google
because they host Usenet flooders.

[toc] | [prev] | [next] | [standalone]

#30442

Kevin McMurtrie <mcmurtrie@pixelmemory.us> wrote:
> I've found that ints and floats have the same performance on x86, as do 
> longs and doubles.  A mix of the two seems to perform even better.  This 
> actually worked out well for me.  I replaced some fixed-point int with 
> float and the code ran significantly faster.

I'd already be very curious about a test case to allow for a reliable
measurement of these differences.

If that microoptimization actually improved execution speed for a real world
task, odds are unfortunately much higher that some subtle semantic difference
between integral and fp math merely caused different paths in the code.  If
that was the case, and the "other" path was still providing a "close enough"
result, then you're just lucky :-)

> The very slight difference 
> in output wasn't an issue so it was a win for performance and 
> readability.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web