Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Hi, took me some time to setup Maven/JMH and learn the basics. (two tools in a day, phew, that's more than I usually do in a year! :) >JIT can sometimes optimize the code so aggressively I was trying to bench this aggressively optimized version of the code, with the idea that: - If the JVM th

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Hi Jeff, Home grown loops are not the best way of micro-benchmarking (have done it myself and learned it). JIT can sometimes optimize the code so aggressively that performance differences you obtain from such benchmarks just show that your concrete program can be optimized better and not that

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Hi been watching this fascinating discussion - seeing Jeff's benchmark today, was wondering if there isn't already at least one benchmark written with JMH? Wouldn't it make sense to make that part of the submission, as a standard practice in refactoring like this? Regards, Patrick On Mon, Jul

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

>Can you post the benchmark source? Before the source, here are the time ranges runs were stabilizing in for lucky executions (using 1.7 for compiler compliance level, and win7 / core i7) : | original | peter7   | peter7   | peter8   | peter8   | |  |  | no loo

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/13/2014 12:41 AM, Peter Levart wrote: On 07/12/2014 10:46 PM, Ivan Gerasimov wrote: Peter, seems you need to fix capacity(): int capacity = Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1)); does not necessarily produces a negative number in the case of overflow. Good cat

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/13/2014 01:24 PM, Jeff Hain wrote: On 07/08/2014 10:07 PM, Martin Buchholz wrote: I updated my webrev and it is again "feature-complete". http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 10:07 PM, Martin Buchholz wrote: > I updated my webrev and it is again "feature-complete". > http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/ > > (old webrev at > http://cr

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/12/2014 10:46 PM, Ivan Gerasimov wrote: Peter, seems you need to fix capacity(): int capacity = Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1)); does not necessarily produces a negative number in the case of overflow. Good catch. You're right. Why don't you want to use

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Peter, seems you need to fix capacity(): int capacity = Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1)); does not necessarily produces a negative number in the case of overflow. Why don't you want to use the variant that from the latest Martin's webrev? It seems to work correctl

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/12/2014 08:12 PM, Peter Levart wrote: (3 * size < 2 * highestOneBit(3*size)) is true for any size, so IHM will never be resized if filled with size elements and table was preallocated with length = 2 * highestOneBit(3*size) even if condition for resizing is changed from (3*size > length)

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/12/2014 08:12 PM, Peter Levart wrote: If we're willing to pay the price of special-casing the non-power-of-2 MAX_CAPACITY = (1 << 29) + (1 << 28), which amounts to approx. 4% of performance, The cause of performance drop is of course the conditional in: 297 private static int hash

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/12/2014 05:47 PM, Peter Levart wrote: If we're willing to pay the price of special-casing the non-power-of-2 MAX_CAPACITY = (1 << 29) + (1 << 28), which amounts to approx. 4% of performance, Then here's a possible solution: http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/w

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/11/2014 09:08 PM, Doug Lea wrote: I've been content to just observe Martin and Peter's nice efforts on this, but one note: On 07/11/2014 03:00 PM, Martin Buchholz wrote: On Wed, Jul 9, 2014 at 3:17 PM, Peter Levart wrote: IMH resizing is arranged so that the table is always 33% ...

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 11.07.2014 23:07, Martin Buchholz wrote: Ivan, feel free to submit your latest webrev. We have consensus that changes being made are progress. Yes, I was going to do that during the weekend after control rebuild. What is the right way to form the commit message here? Would it be ok if t

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

I've been content to just observe Martin and Peter's nice efforts on this, but one note: On 07/11/2014 03:00 PM, Martin Buchholz wrote: On Wed, Jul 9, 2014 at 3:17 PM, Peter Levart wrote: IMH resizing is arranged so that the table is always 33% ... 66% full (if nothing is ever removed from

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 11:30 PM, Martin Buchholz wrote: Benchmarks welcome. I have run your latest webrev with the following benchamrk: @State(Scope.Thread) public class IHMBench { Map map = new IdentityHashMap(); @Benchmark public void putNewObject(Blackhole bh) { Object o = new

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/09/2014 06:36 PM, Martin Buchholz wrote: OK, I think we're down to the smallest possible bug: I wouldn't call it a bug, since it's not present. if size == MAX_CAPACITY - 1 and we putAll a concurrent map with greater size, but the concurrent map shrinks while we're adding it, and no a

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

OK, I think we're down to the smallest possible bug: if size == MAX_CAPACITY - 1 and we putAll a concurrent map with greater size, but the concurrent map shrinks while we're adding it, and no actual elements get added to the IHM (but each element put takes ~ 2**28 probes), then an ISE is thrown w

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/09/2014 09:23 AM, Peter Levart wrote: On 07/09/2014 02:46 AM, Martin Buchholz wrote: Let me understand - you're worried that when size is MAX_CAPACITY - 1, then a call to putAll that does not actually add any elements might throw? This is not possible, because resize() is only called

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/09/2014 02:46 AM, Martin Buchholz wrote: Let me understand - you're worried that when size is MAX_CAPACITY - 1, then a call to putAll that does not actually add any elements might throw? This is not possible, because resize() is only called from putAll(map) if argument map.size() > thi

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 09.07.2014 4:46, Martin Buchholz wrote: Let me understand - you're worried that when size is MAX_CAPACITY - 1, then a call to putAll that does not actually add any elements might throw? Well, I'm having a hard time considering that corner case a bug, given how unusable the map is at this p

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Here's the same final webrev by Martin. I only shortened the comment before capacity() and moved the check in resize() upper. http://cr.openjdk.java.net/~igerasim/6904367/4/webrev/ Sincerely yours, Ivan On 09.07.2014 4:25, Ivan Gerasimov wrote: On 09.07.2014 3:20, Martin Buchholz wrote: I

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 09.07.2014 3:20, Martin Buchholz wrote: I agree with Peter that we do not need to increment modCount on resize. My latest webrev is again "done". Ivan, feel free to take over. Yes, thanks! The fix is much much better now. I think I see yet another very minor glitch, though. If the table

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Ah, yes, sure. I overlooked the reference to the table :-) On 09.07.2014 2:42, Peter Levart wrote: On 07/09/2014 12:06 AM, Ivan Gerasimov wrote: On 09.07.2014 1:44, Peter Levart wrote: On 07/08/2014 11:39 PM, Ivan Gerasimov wrote: Might be worth to add modCount++ before this line: 487

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/09/2014 12:06 AM, Ivan Gerasimov wrote: On 09.07.2014 1:44, Peter Levart wrote: On 07/08/2014 11:39 PM, Ivan Gerasimov wrote: Might be worth to add modCount++ before this line: 487 table = newTable; 488 return true; Not quite, I think. The map has just been resize

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 09.07.2014 1:44, Peter Levart wrote: On 07/08/2014 11:39 PM, Ivan Gerasimov wrote: Might be worth to add modCount++ before this line: 487 table = newTable; 488 return true; Not quite, I think. The map has just been resized, but it's contents has not changed yet logica

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Looks pretty good. I like the additional comments as well. Could you document the return conditions of resize()? A "since we're there already" suggestion for readObject: if (size < 0) throw new InvalidObjectException("Illegal mappings count: " + size); Mike On Jul 8 2014, at 13:07 , Martin B

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 11:39 PM, Ivan Gerasimov wrote: Might be worth to add modCount++ before this line: 487 table = newTable; 488 return true; Not quite, I think. The map has just been resized, but it's contents has not changed yet logically. Regards, Peter On 09.07.2014 0:07

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Might be worth to add modCount++ before this line: 487 table = newTable; 488 return true; On 09.07.2014 0:07, Martin Buchholz wrote: I updated my webrev and it is again "feature-complete". http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

If size == MAXIMUM_CAPACITY - 1 and you're in resize, presumably you're about to fill that last empty slot after returning, so you want to throw instead of returning false? Benchmarks welcome. On Tue, Jul 8, 2014 at 2:15 PM, Peter Levart wrote: > > On 07/08/2014 10:07 PM, Martin Buchholz wrote

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 10:07 PM, Martin Buchholz wrote: I updated my webrev and it is again "feature-complete". http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/ (old webrev at http://cr.openjd

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Given the table size if a power of two, another possible optimization would be private static int nextKeyIndex(int i, int len) { -return (i + 2 < len ? i + 2 : 0); +return (i + 2) & (len - 1); } Or even +int m = len - 1; while ( (item = tab[i]) != null)

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 03:56 PM, Martin Buchholz wrote: On Tue, Jul 8, 2014 at 5:30 AM, Peter Levart wrote: On 07/08/2014 02:20 PM, Peter Levart wrote: That's right. Not in put(). But in putAll() it can overflow, since the argument Map can be of any size that fits in int... I took another look at

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 03:00 PM, Ivan Gerasimov wrote: I took your latest version of the patch and modified it a little: http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.01/ But isn't it post-insert-resize vs pre-insert-resize problem Doug mentioned above? I've tested a similar fix

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 08.07.2014 4:44, Martin Buchholz wrote: On Mon, Jul 7, 2014 at 9:41 AM, Martin Buchholz > wrote: I'd like to offer an alternative version of this change. webrev coming soon. Here's the promised webrev. http://cr.openjdk.java.net/~martin/webrevs/open

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 08.07.2014 14:41, Peter Levart wrote: On 07/08/2014 12:12 PM, Peter Levart wrote: On 07/08/2014 09:33 AM, Martin Buchholz wrote: I've updated the webrev http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/ It now has all my TODOs done. The test case has been test

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 02:20 PM, Peter Levart wrote: That's right. Not in put(). But in putAll() it can overflow, since the argument Map can be of any size that fits in int... So here's my 3rd variation of Martin's latest version: http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.03/

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 01:53 PM, Ivan Gerasimov wrote: On 08.07.2014 15:25, Peter Levart wrote: Hi again, Here's a version with (3*size > len) replaced with (size > len/3) as suggested by Ivan Gerasimov to avoid overflow and also fixed if block if put() that enclosed too much code (in my changed versi

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 08.07.2014 15:25, Peter Levart wrote: Hi again, Here's a version with (3*size > len) replaced with (size > len/3) as suggested by Ivan Gerasimov to avoid overflow and also fixed if block if put() that enclosed too much code (in my changed version of Martin's latest webrev): It shouldn'

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Hi again, Here's a version with (3*size > len) replaced with (size > len/3) as suggested by Ivan Gerasimov to avoid overflow and also fixed if block if put() that enclosed too much code (in my changed version of Martin's latest webrev): http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHa

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 12:12 PM, Peter Levart wrote: On 07/08/2014 09:33 AM, Martin Buchholz wrote: I've updated the webrev http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/ It now has all my TODOs done. The test case has been testng-ified. Hi Martin, What happened to th

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/08/2014 09:33 AM, Martin Buchholz wrote: I've updated the webrev http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/ It now has all my TODOs done. The test case has been testng-ified. Hi Martin, What happened to the desire that when OOME is thrown on resizing, I

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Thank you Martin for the enhancement! It's a good idea to get rid of threshold variable! When the table grows large, it will start to try to resize the table on every single put(). Though it shouldn't matter much, as in such situation everything is already slow. On 08.07.2014 4:44, Martin B

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 08.07.2014 4:47, Martin Buchholz wrote: I think this code has an off-by-factor-of-2 bug. +if (expectedMaxSize > MAXIMUM_CAPACITY / 3) +return MAXIMUM_CAPACITY; No, even though it looks like a bug. (MAXIMUM_CAPACITY / 3) * (3 / 2) == MAXIMUM_CAPACITY / 2. if expected

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Thanks for suggestion Jeff! I've tried it, but it doesn't seem to make a difference on my machine. Here are the numbers. I measured the time of a single put in nanoseconds. --- | vanila | fix1 | fix2 client | 8292 | 8220 | 8304 server | 8197 | 8198 | 8221 interpreter |

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

>So, I reverted this change to the original code, but added a single >check of the current table size before doing any modifications to the map. >This is to address the issue #4, and this doesn't seem to introduce any >significant penalty. > >Would you please help review the updated webrev: >

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Thank you Doug for your comment! On 04.07.2014 23:38, Doug Lea wrote: On 07/04/2014 01:33 PM, Ivan Gerasimov wrote: On 04.07.2014 8:14, David Holmes wrote: Hi Ivan, I find the change to capacity somewhat obfuscating and I can't see what the actual bug was. The bug was in rounding in the ex

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Ivan, Fields like MAXIMUM_CAPACITY are compile-time constants. Their values are placed directly into the code that uses them - there is no associated getField to load it. Hence changing the field via reflection has no affect on any existing code that references the field. I'm still uncomfort

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

>Here is the updated webrev: >http://cr.openjdk.java.net/~igerasim/6904367/2/webrev/ There is another bug with the initial implementation: if put throws, the element is still put (and the size incremented accordingly), and if putting a new mapping after the throwing one, the table gets full and

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

On 07/04/2014 01:33 PM, Ivan Gerasimov wrote: On 04.07.2014 8:14, David Holmes wrote: Hi Ivan, I find the change to capacity somewhat obfuscating and I can't see what the actual bug was. The bug was in rounding in the expression minCapacity = (3 * expectedMaxSize)/2. Suppose, we want the expe

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Thanks David for looking at the change! On 04.07.2014 8:14, David Holmes wrote: Hi Ivan, I find the change to capacity somewhat obfuscating and I can't see what the actual bug was. The bug was in rounding in the expression minCapacity = (3 * expectedMaxSize)/2. Suppose, we want the expected

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Hi Ivan, I find the change to capacity somewhat obfuscating and I can't see what the actual bug was. The recursive call to put after a resize seems very sub-optimal as you will re-search the map for the non-existent key. Can you not just recompute the correct indices and do the store? Alte

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

>http://cr.openjdk.java.net/~igerasim/6904367/1/webrev/ My test now terminates (exception on MAX_CAPACITY-th put). Maybe where MAX_CAPACITY is defined you could indicate that you can actually have at most MAX_CAPACITY-1 mappings, to ensure that the table always contains some null key-spot (I do

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Thank you Jeff! On 03.07.2014 23:07, Jeff Hain wrote: Hi. >WEBREV: http://cr.openjdk.java.net/~igerasim/6904367/0/webrev/ The "while" loop in put(...) supposes that there is at least one free slot, which was the case before (tha

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Hi. >WEBREV: http://cr.openjdk.java.net/~igerasim/6904367/0/webrev/ The "while" loop in put(...) supposes that there is at least one free slot, which was the case before (that could be added as comment). Now if you try to go past max capacity, instead of getting an IllegalStateException, y

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Thanks Martin! On 03.07.2014 21:12, Martin Buchholz wrote: Martin's law of expanding capacity: Always grow by using the form newCapacity = oldCapacity + oldCapacity >> n for some suitable constant n. This will be efficient and more overflow resistant than the alternative newCapacity = old

Re: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Martin's law of expanding capacity: Always grow by using the form newCapacity = oldCapacity + oldCapacity >> n for some suitable constant n. This will be efficient and more overflow resistant than the alternative newCapacity = oldCapacity * (2**n + 1) / (2**n) Here n == 1. On Thu, Jul 3, 20

RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

Hello! IdentityHasMap has a couple of small issues. The first one is a performance issue: If you create a map, specifying 42 as the expected number of element, you'll be able to insert only 41 elements into the preallocated table. Inserting the 42th element will trigger resizing of the storage