Re: Impact of code difference in Collection#contains() worth improving?

Much thanks for your comments John. The in bug 6984886 mentioned isHigh/LowSurrogate methods are frequently used in small loops of charset de/encoders, so I expect a measurable performance improvement there. -Ulf Am 06.09.2014 um 01:25 schrieb John Rose: On Aug 30, 2014, at 7:17 AM, Ulf Zib

Re: Impact of code difference in Collection#contains() worth improving?

Hi Martin, why you didn't include Mike's suggestion into the fix? -Ulf Am 02.09.2014 um 19:04 schrieb Mike Duigou: Looks fine (bug updated with noreg-perf). I do think we should consider promoting a copy of this method to AbstractList as it generally allows for a much better implementation t

Re: Impact of code difference in Collection#contains() worth improving?

On Aug 30, 2014, at 10:58 AM, Doug Lea wrote: > In the present case, I'm with Martin about short-circuiting > this with a simple approximate answer: Rather than flip a coin > choosing between solutions A and B, pick the one with smaller bytecode. > This has a decent enough correlation with actual

Re: Impact of code difference in Collection#contains() worth improving?

On Aug 30, 2014, at 7:17 AM, Ulf Zibis wrote: > Am 30.08.2014 um 01:33 schrieb John Rose: >> On Aug 29, 2014, at 1:05 PM, Ulf Zibis > > wrote: >> >>> Thanks for explaining this, but a very little nit: the immediate (I.e. -1) >>> uses additional 32/64 bits in code whi

Re: Impact of code difference in Collection#contains() worth improving?

On Fri, Aug 29, 2014 at 7:53 PM, Guy Steele wrote: > > But I cannot resist recalling that one of the earliest pieces of software > in the implementation of EMACS (back when the implementation language was > TECO, a text-editing language) was a routine that, when it loaded TECO > macros from a fil

Re: Impact of code difference in Collection#contains() worth improving?

Looks fine (bug updated with noreg-perf). I do think we should consider promoting a copy of this method to AbstractList as it generally allows for a much better implementation than AbstractCollection's contains(). Mike On Aug 29 2014, at 14:56 , Martin Buchholz wrote: > Just think - one whole

Re: Impact of code difference in Collection#contains() worth improving?

Hi Fabian; This has been an excellent discussion and thank you for starting it! Even if there is disagreement on various aspects I don't believe that anyone is upset or angry. Mike On Aug 30 2014, at 10:04 , Fabian Lange wrote: > Hello dear list, > > it was not my intention to steal precio

Re: Impact of code difference in Collection#contains() worth improving?

Somewhat off topic. The linked implementation of android lacks integer overflow on size. That might be actually irrelevant on android due to OOM happening earlier than integer overflow. The latter that made me check the JDK impl. I know most concurrent collections handle integer overflow (CLQ, CHM

Re: Impact of code difference in Collection#contains() worth improving?

Stepping back from this just a little... Potential OpenJDK contributors wonder whether, all other things being equal, they should choose construction A because it is faster than construction B. And they'd like a better answer than "it's complicated". Usually, the answer IS complicated, so it's

Re: Impact of code difference in Collection#contains() worth improving?

Hello dear list, it was not my intention to steal precious developer time by annoying you guys with my finding. I really wanted to understand why there is a source difference. So I went ahead and looked at it from the only aspect I could estimate contributing to it. I am well aware of the fact tha

Re: Impact of code difference in Collection#contains() worth improving?

Am 29.08.2014 um 23:56 schrieb Martin Buchholz: Just think - one whole byte saved for each individual change! I have a webrev! http://cr.openjdk.java.net/~martin/webrevs/openjdk9/pico-optimize-contains/ https://bugs

Re: Impact of code difference in Collection#contains() worth improving?

Am 30.08.2014 um 01:33 schrieb John Rose: On Aug 29, 2014, at 1:05 PM, Ulf Zibis mailto:ulf.zi...@cosoco.de>> wrote: Thanks for explaining this, but a very little nit: the immediate (I.e. -1) uses additional 32/64 bits in code which must be loaded from memory and wastes space in CPU cache or a

Re: Impact of code difference in Collection#contains() worth improving?

On Aug 29, 2014, at 7:33 PM, John Rose wrote: > . . . > Changing source code on based on the difference between 0 and -1 is almost as > pointless as removing whitespace and comments . . . Well said, John! But I cannot resist recalling that one of the earliest pieces of software in the impleme

Re: Impact of code difference in Collection#contains() worth improving?

On Aug 29, 2014, at 5:27 PM, Martin Buchholz wrote: > I agree that the benefit is very small, but I am coming at this from source > code consistency and bytecode size (not jitted code performance), and I think > bytecode size is at least one of the problems with assert. We agree about JDK-6445

Re: Impact of code difference in Collection#contains() worth improving?

Hi John, I agree that the benefit is very small, but I am coming at this from source code consistency and bytecode size (not jitted code performance), and I think bytecode size is at least one of the problems with assert. ... I filed that bug long ago, but no action yet https://bugs.openjdk

Re: Impact of code difference in Collection#contains() worth improving?

On Aug 29, 2014, at 1:05 PM, Ulf Zibis wrote: > Thanks for explaining this, but a very little nit: the immediate (I.e. -1) > uses additional 32/64 bits in code which must be loaded from memory and > wastes space in CPU cache or am I wrong? This could be saved with >= 0. I have to say you're mo

Re: Impact of code difference in Collection#contains() worth improving?

Refactoring the hierarchy should be separate (and much more controversial) change. This change is a clean win, just very small. Refactoring runs into space/time tradeoffs. On Fri, Aug 29, 2014 at 3:23 PM, Vitaly Davidovich wrote: > :) so if you're going to do this, is there no base class in t

Re: Impact of code difference in Collection#contains() worth improving?

:) so if you're going to do this, is there no base class in the hierarchy where this can be placed (I don't have source in front of me)? That way there's a higher likelihood that the pattern will stay consistent (with new implementations at least). Sent from my phone On Aug 29, 2014 5:56 PM, "Mart

Re: Impact of code difference in Collection#contains() worth improving?

Just think - one whole byte saved for each individual change! I have a webrev! http://cr.openjdk.java.net/~martin/webrevs/openjdk9/pico-optimize-contains/ https://bugs.openjdk.java.net/browse/JDK-8056951 Can haz review please? On Fri, Aug 29, 2014 at 1:05 PM, Ulf Zibis wrote: > > Am 28.08.2014

Re: Impact of code difference in Collection#contains() worth improving?

Yes, the immediate is part of the instruction encoding, so takes up space. However, I believe the CMP instruction allows comparison of an immediate with a wider register (e.g. cmp $-1, %eax), in which case the immediate takes up 1 byte and is then sign extended to the size of the register. But ag

Re: Impact of code difference in Collection#contains() worth improving?

Am 28.08.2014 um 19:46 schrieb Vitaly Davidovich: There's no register pressure - the immediate (I.e. -1) is encoded directly into the instruction, just like 0 would be. The time when 0 is particularly useful is when you test for it in the zero bit of the flags register (e.g. dec followed by

Re: Impact of code difference in Collection#contains() worth improving?

Am 28.08.2014 um 19:30 schrieb Louis Wasserman: Comparator is spec'd to be allowed to return any number, positive, negative, or zero, but indexOf is specifically spec'd to return -1. Yes, I know. I wanted to say, that from this knowing some developer might assume the same for indexOf when suc

Re: Impact of code difference in Collection#contains() worth improving?

Right, and people take advantage of Comparable spec to avoid branches (when over/underflow isn't a concern). Sent from my phone On Aug 28, 2014 1:30 PM, "Louis Wasserman" wrote: > Comparator is spec'd to be allowed to return any number, positive, > negative, or zero, but indexOf is specifically

Re: Impact of code difference in Collection#contains() worth improving?

Also, micro optimization conversations at this scale would have a leg to stand on if we were talking about a tight loop with very simple instructions around it with no memory chasing; this is LinkedList traversal with equality checking we're talking about. Sent from my phone On Aug 28, 2014 1:46 P

Re: Impact of code difference in Collection#contains() worth improving?

There's no register pressure - the immediate (I.e. -1) is encoded directly into the instruction, just like 0 would be. The time when 0 is particularly useful is when you test for it in the zero bit of the flags register (e.g. dec followed by jz, such as when counting a loop down to 0). Otherwise,

Re: Impact of code difference in Collection#contains() worth improving?

Am 27.08.2014 um 17:51 schrieb Martin Buchholz: The ArrayList version saves one byte of bytecode, and is therefore very slightly better. We should bless that version and use it consistently. +1 Additional argument: The LinkedList code requires to load 32/64-Bit -1 into CPU. This may take some

Re: Impact of code difference in Collection#contains() worth improving?

On Aug 27, 2014, at 6:48 AM, Fabian Lange wrote: > Hi all, > I have been involved recently in some theoretical or nonsensical > discussions about microbenchmarking, jit compiling assemblies and so fort. > One example was LinkedList vs ArrayList. > > What I noticed is that those two have a differ

Re: Impact of code difference in Collection#contains() worth improving?

Hi Fabian; The correct mailing list for this discussion would be core-libs-dev@openjdk.java.net The difference between these two implementations is probably of not much consequence though it seems that one or the other could be promoted to AbstractList. This implementation would be marginally

Re: Impact of code difference in Collection#contains() worth improving?

The ArrayList version saves one byte of bytecode, and is therefore very slightly better. We should bless that version and use it consistently. javap -c -private java.util.ArrayList | grep -A10 'boolean.*contains' public boolean contains(java.lang.Object); Code: 0: aload_0 1:

Re: Impact of code difference in Collection#contains() worth improving?

As far as I know, hotspot jit will favor cmov only when the branch appears to be unpredictable (or conversely, not strongly predictable); otherwise, jmp is used. To get feedback on predictability, the code needs to run in the interpreter, which you've not done by using -Xcomp. Generally, if you'r

Re: Impact of code difference in Collection#contains() worth improving?

Hi Vitaly, The code comes from a single invocation of a contains(1) on an empty list. I forced -Xcomp to get a compilation result. But as stated in the initial mail, this was just curiosity. If the >=0 and !=-1 checks are 100% equal in performance and optimization, then it does not matter. If one o

Re: Impact of code difference in Collection#contains() worth improving?

There's no clear winner between cmov and jmp in the general case. When you looked at the generated assembly, what code did you run to warm it up? Were most instances found in the list or not or some mix? Using 0 as a test does have benefits in some places (e.g. when flags register can be used from

Impact of code difference in Collection#contains() worth improving?

Hi all, I have been involved recently in some theoretical or nonsensical discussions about microbenchmarking, jit compiling assemblies and so fort. One example was LinkedList vs ArrayList. What I noticed is that those two have a different implementation for contains(): ArrayList: public bool