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
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
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
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/
http://cr.openjdk.java.net/%7Emartin/webrevs/openjdk9/IdentityHashMap-capacity/
(old webrev at
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/
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
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
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 peter.lev...@gmail.com
wrote:
IMH resizing is arranged so that the
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:
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
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)
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 correctly
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
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 peter.lev...@gmail.com wrote:
IMH resizing is arranged so that the table is always 33% ... 66% full (if
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 {
MapObject, Object map = new IdentityHashMapObject, Object();
@Benchmark
public void putNewObject(Blackhole
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()
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
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
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
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,
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
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):
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't
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
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/
On 08.07.2014 4:44, Martin Buchholz wrote:
On Mon, Jul 7, 2014 at 9:41 AM, Martin Buchholz marti...@google.com
mailto:marti...@google.com wrote:
I'd like to offer an alternative version of this change. webrev
coming soon.
Here's the promised webrev.
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
On 07/08/2014 03:56 PM, Martin Buchholz wrote:
On Tue, Jul 8, 2014 at 5:30 AM, Peter Levart peter.lev...@gmail.com 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...
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)
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/
http://cr.openjdk.java.net/%7Emartin/webrevs/openjdk9/IdentityHashMap-capacity/
(old webrev at
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 peter.lev...@gmail.com wrote:
On 07/08/2014 10:07 PM,
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/
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
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
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
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
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
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
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
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
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
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
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:
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 |
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
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
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
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
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
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,
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 =
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,
you
Thank you Jeff!
On 03.07.2014 23:07, Jeff Hain wrote:
Hi.
WEBREV: http://cr.openjdk.java.net/~igerasim/6904367/0/webrev/
http://cr.openjdk.java.net/%7Eigerasim/6904367/0/webrev/
The while loop in put(...) supposes that there is at least one free
slot,
which was the case before (that
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
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?
55 matches
Mail list logo