Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
On 25/02/2013 04:06, Mike Duigou wrote: I have created an issue for fixing the introduced regression and created a regression test that would have caught the error (fix a bug, write a test...). 8008785: IdentityHashMap.values().toArray(V[]) broken by JDK-8008167 http://cr.openjdk.java.net/~mduigou/JDK-8008785/0/webrev Mike The fix to IdentityHashMap looks good. It is surprising that it wasn't caught by tests in the jdk repository so a reminder that we always need to check that we have good test coverage when doing performance fixes. The webrev suggests you've replaced Map/Collisions.java and assume that is not the intention. Otherwise the new test looks okay, an alternative would have been to expand MOAT. -Alan.
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
On Feb 25 2013, at 01:51 , Alan Bateman wrote: On 25/02/2013 04:06, Mike Duigou wrote: I have created an issue for fixing the introduced regression and created a regression test that would have caught the error (fix a bug, write a test...). 8008785: IdentityHashMap.values().toArray(V[]) broken by JDK-8008167 http://cr.openjdk.java.net/~mduigou/JDK-8008785/0/webrev Mike The fix to IdentityHashMap looks good. It is surprising that it wasn't caught by tests in the jdk repository so a reminder that we always need to check that we have good test coverage when doing performance fixes. Yes, I should have checked not just that the existing tests passed but that there was a specific test for what was being changed. I was very surprised to discover after the fact that there was no test at all for ToArray. The webrev suggests you've replaced Map/Collisions.java and assume that is not the intention. Otherwise the new test looks okay, an alternative would have been to expand MOAT. Webrev doesn't properly recognize 'hg copy' and sees it as a rename. I started ToArray.java by copying Collisions.java Mike -Alan.
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
On Feb 25 2013, at 01:51 , Alan Bateman wrote: On 25/02/2013 04:06, Mike Duigou wrote: I have created an issue for fixing the introduced regression and created a regression test that would have caught the error (fix a bug, write a test...). 8008785: IdentityHashMap.values().toArray(V[]) broken by JDK-8008167 http://cr.openjdk.java.net/~mduigou/JDK-8008785/0/webrev Mike The fix to IdentityHashMap looks good. It is surprising that it wasn't caught by tests in the jdk repository so a reminder that we always need to check that we have good test coverage when doing performance fixes. The webrev suggests you've replaced Map/Collisions.java and assume that is not the intention. Otherwise the new test looks okay, an alternative would have been to expand MOAT. Ouch! The patch generated by webrev gets it wrong too: --- old/test/java/util/Map/Collisions.java 2013-02-24 19:47:40.491333191 -0800 +++ /dev/null 2013-02-24 18:12:51.832474922 -0800 --- /dev/null 2013-02-24 18:12:51.832474922 -0800 +++ new/test/java/util/Map/ToArray.java 2013-02-24 19:47:40.319333199 -0800 vs diff on source repo: diff --git a/test/java/util/Map/Collisions.java b/test/java/util/Map/ToArray.java copy from test/java/util/Map/Collisions.java copy to test/java/util/Map/ToArray.java --- a/test/java/util/Map/Collisions.java +++ b/test/java/util/Map/ToArray.java
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
On 25/02/2013 15:55, Mike Duigou wrote: : The webrev suggests you've replaced Map/Collisions.java and assume that is not the intention. Otherwise the new test looks okay, an alternative would have been to expand MOAT. Webrev doesn't properly recognize 'hg copy' and sees it as a rename. I started ToArray.java by copying Collisions.java Are you sure you want to do hg copy here? This means that hg will track the copy and I assume we don't want that here. -Alan.
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
On Feb 25 2013, at 10:13 , Alan Bateman wrote: On 25/02/2013 15:55, Mike Duigou wrote: : The webrev suggests you've replaced Map/Collisions.java and assume that is not the intention. Otherwise the new test looks okay, an alternative would have been to expand MOAT. Webrev doesn't properly recognize 'hg copy' and sees it as a rename. I started ToArray.java by copying Collisions.java Are you sure you want to do hg copy here? This means that hg will track the copy and I assume we don't want that here. Some people would just do a plain shell copy of the file and then hg add the new file. I prefer to use an actual SCM copy because I am re-using portions of the original file. If it turns out there is a bug in the boilerplate that I copied the hg copy does leave a tenuous link back to the source which would still have the same bug. If I just used regular copy and then hg add then that link is broken completely. Mike
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
I made one additional change to the regression test so that the keys and values
aren't in the same range. It didn't produce any failures but I think it is a
good addition to catch future bugs.
Mike
diff --git a/test/java/util/Map/ToArray.java b/test/java/util/Map/ToArray.java
--- a/test/java/util/Map/ToArray.java
+++ b/test/java/util/Map/ToArray.java
@@ -67,7 +67,7 @@ public class ToArray {
static {
for (int each = 0; each TEST_SIZE; each++) {
KEYS[each] = Integer.valueOf(each);
-VALUES[each] = Long.valueOf(each);
+VALUES[each] = Long.valueOf(each + TEST_SIZE);
}
}
On Feb 25 2013, at 01:51 , Alan Bateman wrote:
On 25/02/2013 04:06, Mike Duigou wrote:
I have created an issue for fixing the introduced regression and created a
regression test that would have caught the error (fix a bug, write a
test...).
8008785: IdentityHashMap.values().toArray(V[]) broken by JDK-8008167
http://cr.openjdk.java.net/~mduigou/JDK-8008785/0/webrev
Mike
The fix to IdentityHashMap looks good. It is surprising that it wasn't caught
by tests in the jdk repository so a reminder that we always need to check
that we have good test coverage when doing performance fixes.
The webrev suggests you've replaced Map/Collisions.java and assume that is
not the intention. Otherwise the new test looks okay, an alternative would
have been to expand MOAT.
-Alan.
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
On 25/02/2013 20:24, Mike Duigou wrote: I made one additional change to the regression test so that the keys and values aren't in the same range. It didn't produce any failures but I think it is a good addition to catch future bugs. Mike Looks okay. -Alan
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
On 14/02/2013 17:55, mike.dui...@oracle.com wrote: Changeset: e57019d2f34a Author:mduigou Date: 2013-02-13 14:50 -0800 URL: http://hg.openjdk.java.net/jdk8/tl/jdk/rev/e57019d2f34a 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up Reviewed-by: mduigou, martin Contributed-by: Peter Levartpeter.lev...@gmail.com ! src/share/classes/java/util/IdentityHashMap.java A belated comment on this is that CME will now be thrown for cases where it wasn't previously. We need to make sure this behavior change is tracked (for release notes, etc.). -Alan
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
Hi Alan, I think ConcurrentModificationException could be thrown previously too, if the Map was modified from other thread while iterating using iterator (fail-fast iterator). Will check this in detail when I'm back at screen... Regards, Peter On Feb 24, 2013 2:25 PM, Alan Bateman alan.bate...@oracle.com wrote: On 14/02/2013 17:55, mike.dui...@oracle.com wrote: Changeset: e57019d2f34a Author:mduigou Date: 2013-02-13 14:50 -0800 URL: http://hg.openjdk.java.net/**jdk8/tl/jdk/rev/e57019d2f34ahttp://hg.openjdk.java.net/jdk8/tl/jdk/rev/e57019d2f34a 8008167: IdentityHashMap.[keySet|**values|entrySet].toArray speed-up Reviewed-by: mduigou, martin Contributed-by: Peter Levartpeter.lev...@gmail.com ! src/share/classes/java/util/**IdentityHashMap.java A belated comment on this is that CME will now be thrown for cases where it wasn't previously. We need to make sure this behavior change is tracked (for release notes, etc.). -Alan
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
Hi Alan, I checked and it seems all 3 IHM views [keySet|values|entrySet] have a fail-fast iterator implementation (IdentityHashMap.IdentityHashMapIterator) and all 3 are (were) using the iterator for .toArray implementations. So this patch tries to preserve the behavior when there is a concurrent modification (which is only possible from other thread and is illegal usage anyway since IHM is not thread-safe) while executing the toArray methods on the views... Do you see something I don't see? Regards, Peter On 02/24/2013 03:42 PM, Peter Levart wrote: Hi Alan, I think ConcurrentModificationException could be thrown previously too, if the Map was modified from other thread while iterating using iterator (fail-fast iterator). Will check this in detail when I'm back at screen... Regards, Peter On Feb 24, 2013 2:25 PM, Alan Bateman alan.bate...@oracle.com mailto:alan.bate...@oracle.com wrote: On 14/02/2013 17:55, mike.dui...@oracle.com mailto:mike.dui...@oracle.com wrote: Changeset: e57019d2f34a Author:mduigou Date: 2013-02-13 14:50 -0800 URL: http://hg.openjdk.java.net/jdk8/tl/jdk/rev/e57019d2f34a 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up Reviewed-by: mduigou, martin Contributed-by: Peter Levartpeter.lev...@gmail.com mailto:peter.lev...@gmail.com ! src/share/classes/java/util/IdentityHashMap.java A belated comment on this is that CME will now be thrown for cases where it wasn't previously. We need to make sure this behavior change is tracked (for release notes, etc.). -Alan
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
On 24/02/2013 15:49, Peter Levart wrote:
Hi Alan,
I checked and it seems all 3 IHM views [keySet|values|entrySet] have a
fail-fast iterator implementation
(IdentityHashMap.IdentityHashMapIterator) and all 3 are (were) using
the iterator for .toArray implementations. So this patch tries to
preserve the behavior when there is a concurrent modification (which
is only possible from other thread and is illegal usage anyway since
IHM is not thread-safe) while executing the toArray methods on the
views...
Do you see something I don't see?
My apologies, I see it does check the modification count in
IdentityHashMapIterator.nextIndex.
However, as this forced me to looks at the changes-set again then the
copy loop in Values.toArray has caught by eye:
for (int si = 0; si tab.length; si += 2) {
if (tab[si++] != null) { // key present ?
// more elements than expected - concurrent
modification from other thread
if (ti = size) {
throw new ConcurrentModificationException();
}
a[ti++] = (T) tab[si]; // copy value
}
}
Looks like si is incrementing by 3 rather than 2 (which ironically will
cause a CME later because there will be fewer elements copied than
expected).
Do you concur? If so then we can create a bug to change this to test
tab[si] and copy in tab[si+1].
-Alan
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
Ouch, this would have been introduced by me.
I will check to see how this could have passed the pre-commit regression
testing. I suspect that a regression test needs to be improved.
Mike
On Feb 24 2013, at 10:48 , Alan Bateman wrote:
On 24/02/2013 15:49, Peter Levart wrote:
Hi Alan,
I checked and it seems all 3 IHM views [keySet|values|entrySet] have a
fail-fast iterator implementation (IdentityHashMap.IdentityHashMapIterator)
and all 3 are (were) using the iterator for .toArray implementations. So
this patch tries to preserve the behavior when there is a concurrent
modification (which is only possible from other thread and is illegal usage
anyway since IHM is not thread-safe) while executing the toArray methods on
the views...
Do you see something I don't see?
My apologies, I see it does check the modification count in
IdentityHashMapIterator.nextIndex.
However, as this forced me to looks at the changes-set again then the copy
loop in Values.toArray has caught by eye:
for (int si = 0; si tab.length; si += 2) {
if (tab[si++] != null) { // key present ?
// more elements than expected - concurrent modification
from other thread
if (ti = size) {
throw new ConcurrentModificationException();
}
a[ti++] = (T) tab[si]; // copy value
}
}
Looks like si is incrementing by 3 rather than 2 (which ironically will cause
a CME later because there will be fewer elements copied than expected).
Do you concur? If so then we can create a bug to change this to test tab[si]
and copy in tab[si+1].
-Alan
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
Hi Mike,
I thought I saw that too when you commited the change, but then
re-examinig the whole source in detail, I couldn't spot it again. I must
have stared at the wrong third of change...
Regards, Peter
On 02/24/2013 07:53 PM, Mike Duigou wrote:
Ouch, this would have been introduced by me.
I will check to see how this could have passed the pre-commit regression
testing. I suspect that a regression test needs to be improved.
Mike
On Feb 24 2013, at 10:48 , Alan Bateman wrote:
On 24/02/2013 15:49, Peter Levart wrote:
Hi Alan,
I checked and it seems all 3 IHM views [keySet|values|entrySet] have a
fail-fast iterator implementation (IdentityHashMap.IdentityHashMapIterator) and
all 3 are (were) using the iterator for .toArray implementations. So this patch
tries to preserve the behavior when there is a concurrent modification (which
is only possible from other thread and is illegal usage anyway since IHM is not
thread-safe) while executing the toArray methods on the views...
Do you see something I don't see?
My apologies, I see it does check the modification count in
IdentityHashMapIterator.nextIndex.
However, as this forced me to looks at the changes-set again then the copy loop
in Values.toArray has caught by eye:
for (int si = 0; si tab.length; si += 2) {
if (tab[si++] != null) { // key present ?
// more elements than expected - concurrent modification
from other thread
if (ti = size) {
throw new ConcurrentModificationException();
}
a[ti++] = (T) tab[si]; // copy value
}
}
Looks like si is incrementing by 3 rather than 2 (which ironically will cause a
CME later because there will be fewer elements copied than expected).
Do you concur? If so then we can create a bug to change this to test tab[si]
and copy in tab[si+1].
-Alan
Re: hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
I have created an issue for fixing the introduced regression and created a
regression test that would have caught the error (fix a bug, write a test...).
8008785: IdentityHashMap.values().toArray(V[]) broken by JDK-8008167
http://cr.openjdk.java.net/~mduigou/JDK-8008785/0/webrev
Mike
On Feb 24 2013, at 12:27 , Peter Levart wrote:
Hi Mike,
I thought I saw that too when you commited the change, but then re-examinig
the whole source in detail, I couldn't spot it again. I must have stared at
the wrong third of change...
Regards, Peter
On 02/24/2013 07:53 PM, Mike Duigou wrote:
Ouch, this would have been introduced by me.
I will check to see how this could have passed the pre-commit regression
testing. I suspect that a regression test needs to be improved.
Mike
On Feb 24 2013, at 10:48 , Alan Bateman wrote:
On 24/02/2013 15:49, Peter Levart wrote:
Hi Alan,
I checked and it seems all 3 IHM views [keySet|values|entrySet] have a
fail-fast iterator implementation
(IdentityHashMap.IdentityHashMapIterator) and all 3 are (were) using the
iterator for .toArray implementations. So this patch tries to preserve the
behavior when there is a concurrent modification (which is only possible
from other thread and is illegal usage anyway since IHM is not
thread-safe) while executing the toArray methods on the views...
Do you see something I don't see?
My apologies, I see it does check the modification count in
IdentityHashMapIterator.nextIndex.
However, as this forced me to looks at the changes-set again then the copy
loop in Values.toArray has caught by eye:
for (int si = 0; si tab.length; si += 2) {
if (tab[si++] != null) { // key present ?
// more elements than expected - concurrent
modification from other thread
if (ti = size) {
throw new ConcurrentModificationException();
}
a[ti++] = (T) tab[si]; // copy value
}
}
Looks like si is incrementing by 3 rather than 2 (which ironically will
cause a CME later because there will be fewer elements copied than
expected).
Do you concur? If so then we can create a bug to change this to test
tab[si] and copy in tab[si+1].
-Alan
Re: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
Hello Mike, On 02/13/2013 09:21 PM, Mike Duigou wrote: This looks like excellent contribution Peter! I will proceed with the testing needed to integrate your improved toArray()/toArray(T[]) implementations. I have created an issue, JDK-8008167, for this patch. I am surprised that this didn't get more attention back in December as it does seem to offer significant benefits for size and performance. It would if IdentityHashMap was used instead of HashMap for annotations caching. But that's something that should be done on the global basis (there are various places where Maps of annotations are constructed: reflection classes, AnnotationParser, ...). There's also opportunity to use IdentityHashMap instead of LinkedHashMap (totally unnecessary, since it is never iterated !!??) for holding member values of annotation instances (the Map is keyed by String objects, but they could be interned at map creation time - the same string values are interned already, since they are equal to names of methods of the annotation interfaces and retrieval is already using the interned Strings: Method.getName() - see AnnotationInvocationHandler)... Let me know if testing finds anything or if there's anything I can do (regarding coding style, etc). Regards, Peter Thanks, Mike On Dec 12 2012, at 01:07 , Peter Levart wrote: Hi all, I propose a patch to java.util.IdentityHashMap to speed-up toArray methods of it's keySet, values and entrySet views: http://dl.dropbox.com/u/101777488/jdk8-tl/IdentityHashMap/webrev.01/index.html I toyed with the possibility to replace HashMap-s, that are used in java.lang.Class and java.lang.reflect.[Field|Method|Constructor] to hold cached annotations, with IdentityHashMap-s. They are a perfect replacement, since keys in these maps are java.lang.Class objects. They are more compact then HashMap-s. This is the comparison of allocated heap bytes between HashMap and IdentityHashMap for various sizes and corresponding capacities which takes into account the size of the Map object, the size of allocated array and the size of Map.Entry-s in case of HM (IHM doesn't have them) and the size of associated values Collection view (allocated when dumping annotations to array). HM-s for annotations are currently allocated with default initial capacity (16). I propose to allocate IHM-s with initial capacity 8 that fits to hold 5 entries which is enough for typical annotation use cases on one hand and still makes improvement for any case on the other: 32 bit JVM: | HashMap | IdentityHashMap | size|capacitybytes|capacitybytes|IHM.bytes-HM.bytes +-+-+-- 0| 16 144| 8 136| -8 1| 16 168| 8 136| -32 2| 16 192| 8 136| -56 3| 16 216| 8 136| -80 4| 16 240| 8 136|-104 5| 16 264| 8 136|-128 6| 16 288| 16 200| -88 7| 16 312| 16 200|-112 8| 16 336| 16 200|-136 9| 16 360| 16 200|-160 10| 16 384| 16 200|-184 11| 16 408| 16 200|-208 12| 16 432| 32 328|-104 13| 32 520| 32 328|-192 14| 32 544| 32 328|-216 15| 32 568| 32 328|-240 16| 32 592| 32 328|-264 17| 32 616| 32 328|-288 18| 32 640| 32 328|-312 19| 32 664| 32 328|-336 20| 32 688| 32 328|-360 40| 64 1296| 64 584|-712 60| 128 2032| 128 1096|-936 80| 128 2512| 128 1096| -1416 100| 256 3504| 256 2120| -1384 120| 256 3984| 256 2120| -1864 140| 256 4464| 256 2120| -2344 160| 256 4944| 256 2120| -2824 180| 256 5424| 512 4168| -1256 64 bit JVM: | HashMap | IdentityHashMap | size|capacitybytes|capacitybytes|IHM.bytes-HM.bytes +-+-+-- 0| 16 248| 8 240| -8 1| 16 296| 8 240| -56 2| 16 344| 8 240|-104 3| 16 392| 8 240|-152 4| 16 440| 8 240|-200 5| 16 488| 8 240|-248 6| 16 536| 16 368|-168 7| 16 584| 16 368|-216 8| 16 632| 16 368|-264 9| 16 680|
Re: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
On Feb 14 2013, at 05:24 , Peter Levart wrote: Hello Mike, On 02/13/2013 09:21 PM, Mike Duigou wrote: This looks like excellent contribution Peter! I will proceed with the testing needed to integrate your improved toArray()/toArray(T[]) implementations. I have created an issue, JDK-8008167, for this patch. I am surprised that this didn't get more attention back in December as it does seem to offer significant benefits for size and performance. It would if IdentityHashMap was used instead of HashMap for annotations caching. But that's something that should be done on the global basis (there are various places where Maps of annotations are constructed: reflection classes, AnnotationParser, ...). There's also opportunity to use IdentityHashMap instead of LinkedHashMap (totally unnecessary, since it is never iterated !!??) for holding member values of annotation instances (the Map is keyed by String objects, but they could be interned at map creation time - the same string values are interned already, since they are equal to names of methods of the annotation interfaces and retrieval is already using the interned Strings: Method.getName() - see AnnotationInvocationHandler)... Let me know if testing finds anything or if there's anything I can do (regarding coding style, etc). I have made the style changes (method brackets placement, while-for) suggested by Martin but didn't make any other changes. Build farm regression testing passed with flying colours so I will integrate the patch today. I encourage you to pursue the replacement of LinkedHashMap and HashMap with IdentityHashMap for annotations. Mike Regards, Peter Thanks, Mike On Dec 12 2012, at 01:07 , Peter Levart wrote: Hi all, I propose a patch to java.util.IdentityHashMap to speed-up toArray methods of it's keySet, values and entrySet views: http://dl.dropbox.com/u/101777488/jdk8-tl/IdentityHashMap/webrev.01/index.html I toyed with the possibility to replace HashMap-s, that are used in java.lang.Class and java.lang.reflect.[Field|Method|Constructor] to hold cached annotations, with IdentityHashMap-s. They are a perfect replacement, since keys in these maps are java.lang.Class objects. They are more compact then HashMap-s. This is the comparison of allocated heap bytes between HashMap and IdentityHashMap for various sizes and corresponding capacities which takes into account the size of the Map object, the size of allocated array and the size of Map.Entry-s in case of HM (IHM doesn't have them) and the size of associated values Collection view (allocated when dumping annotations to array). HM-s for annotations are currently allocated with default initial capacity (16). I propose to allocate IHM-s with initial capacity 8 that fits to hold 5 entries which is enough for typical annotation use cases on one hand and still makes improvement for any case on the other: 32 bit JVM: | HashMap | IdentityHashMap | size|capacitybytes|capacitybytes|IHM.bytes-HM.bytes +-+-+-- 0| 16 144| 8 136| -8 1| 16 168| 8 136| -32 2| 16 192| 8 136| -56 3| 16 216| 8 136| -80 4| 16 240| 8 136|-104 5| 16 264| 8 136|-128 6| 16 288| 16 200| -88 7| 16 312| 16 200|-112 8| 16 336| 16 200|-136 9| 16 360| 16 200|-160 10| 16 384| 16 200|-184 11| 16 408| 16 200|-208 12| 16 432| 32 328|-104 13| 32 520| 32 328|-192 14| 32 544| 32 328|-216 15| 32 568| 32 328|-240 16| 32 592| 32 328|-264 17| 32 616| 32 328|-288 18| 32 640| 32 328|-312 19| 32 664| 32 328|-336 20| 32 688| 32 328|-360 40| 64 1296| 64 584|-712 60| 128 2032| 128 1096|-936 80| 128 2512| 128 1096| -1416 100| 256 3504| 256 2120| -1384 120| 256 3984| 256 2120| -1864 140| 256 4464| 256 2120| -2344 160| 256 4944| 256 2120| -2824 180| 256 5424| 512 4168| -1256 64 bit JVM: | HashMap | IdentityHashMap | size|capacitybytes|capacitybytes|IHM.bytes-HM.bytes +-+-+-- 0| 16 248| 8 240| -8 1| 16
hg: jdk8/tl/jdk: 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
Changeset: e57019d2f34a Author:mduigou Date: 2013-02-13 14:50 -0800 URL: http://hg.openjdk.java.net/jdk8/tl/jdk/rev/e57019d2f34a 8008167: IdentityHashMap.[keySet|values|entrySet].toArray speed-up Reviewed-by: mduigou, martin Contributed-by: Peter Levart peter.lev...@gmail.com ! src/share/classes/java/util/IdentityHashMap.java
Re: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
This looks like excellent contribution Peter! I will proceed with the testing needed to integrate your improved toArray()/toArray(T[]) implementations. I have created an issue, JDK-8008167, for this patch. I am surprised that this didn't get more attention back in December as it does seem to offer significant benefits for size and performance. Thanks, Mike On Dec 12 2012, at 01:07 , Peter Levart wrote: Hi all, I propose a patch to java.util.IdentityHashMap to speed-up toArray methods of it's keySet, values and entrySet views: http://dl.dropbox.com/u/101777488/jdk8-tl/IdentityHashMap/webrev.01/index.html I toyed with the possibility to replace HashMap-s, that are used in java.lang.Class and java.lang.reflect.[Field|Method|Constructor] to hold cached annotations, with IdentityHashMap-s. They are a perfect replacement, since keys in these maps are java.lang.Class objects. They are more compact then HashMap-s. This is the comparison of allocated heap bytes between HashMap and IdentityHashMap for various sizes and corresponding capacities which takes into account the size of the Map object, the size of allocated array and the size of Map.Entry-s in case of HM (IHM doesn't have them) and the size of associated values Collection view (allocated when dumping annotations to array). HM-s for annotations are currently allocated with default initial capacity (16). I propose to allocate IHM-s with initial capacity 8 that fits to hold 5 entries which is enough for typical annotation use cases on one hand and still makes improvement for any case on the other: 32 bit JVM: | HashMap | IdentityHashMap | size|capacitybytes|capacitybytes|IHM.bytes-HM.bytes +-+-+-- 0| 16 144| 8 136| -8 1| 16 168| 8 136| -32 2| 16 192| 8 136| -56 3| 16 216| 8 136| -80 4| 16 240| 8 136|-104 5| 16 264| 8 136|-128 6| 16 288| 16 200| -88 7| 16 312| 16 200|-112 8| 16 336| 16 200|-136 9| 16 360| 16 200|-160 10| 16 384| 16 200|-184 11| 16 408| 16 200|-208 12| 16 432| 32 328|-104 13| 32 520| 32 328|-192 14| 32 544| 32 328|-216 15| 32 568| 32 328|-240 16| 32 592| 32 328|-264 17| 32 616| 32 328|-288 18| 32 640| 32 328|-312 19| 32 664| 32 328|-336 20| 32 688| 32 328|-360 40| 64 1296| 64 584|-712 60| 128 2032| 128 1096|-936 80| 128 2512| 128 1096| -1416 100| 256 3504| 256 2120| -1384 120| 256 3984| 256 2120| -1864 140| 256 4464| 256 2120| -2344 160| 256 4944| 256 2120| -2824 180| 256 5424| 512 4168| -1256 64 bit JVM: | HashMap | IdentityHashMap | size|capacitybytes|capacitybytes|IHM.bytes-HM.bytes +-+-+-- 0| 16 248| 8 240| -8 1| 16 296| 8 240| -56 2| 16 344| 8 240|-104 3| 16 392| 8 240|-152 4| 16 440| 8 240|-200 5| 16 488| 8 240|-248 6| 16 536| 16 368|-168 7| 16 584| 16 368|-216 8| 16 632| 16 368|-264 9| 16 680| 16 368|-312 10| 16 728| 16 368|-360 11| 16 776| 16 368|-408 12| 16 824| 32 624|-200 13| 32 1000| 32 624|-376 14| 32 1048| 32 624|-424 15| 32 1096| 32 624|-472 16| 32 1144| 32 624|-520 17| 32 1192| 32 624|-568 18| 32 1240| 32 624|-616 19| 32 1288| 32 624|-664 20| 32 1336| 32 624|-712 40| 64 2552| 64 1136| -1416 60| 128 4024| 128 2160| -1864 80| 128 4984| 128 2160| -2824 100| 256 6968| 256 4208| -2760 120| 256 7928| 256 4208| -3720 140| 256
Re: IdentityHashMap.[keySet|values|entrySet].toArray speed-up
Seems pretty good overall. Thanks for doing this.
Style: put your open braces at the end of the line.
---
+int si = 0;
+while (si tab.length) {
why not the more readable:
for (int i = 0, len = tab.length; i len; i += 2) {
Object key = tab[i];
if (key != null) { ...
IdentityHashMap.[keySet|values|entrySet].toArray speed-up
Hi all, I propose a patch to java.util.IdentityHashMap to speed-up toArray methods of it's keySet, values and entrySet views: http://dl.dropbox.com/u/101777488/jdk8-tl/IdentityHashMap/webrev.01/index.html I toyed with the possibility to replace HashMap-s, that are used in java.lang.Class and java.lang.reflect.[Field|Method|Constructor] to hold cached annotations, with IdentityHashMap-s. They are a perfect replacement, since keys in these maps are java.lang.Class objects. They are more compact then HashMap-s. This is the comparison of allocated heap bytes between HashMap and IdentityHashMap for various sizes and corresponding capacities which takes into account the size of the Map object, the size of allocated array and the size of Map.Entry-s in case of HM (IHM doesn't have them) and the size of associated values Collection view (allocated when dumping annotations to array). HM-s for annotations are currently allocated with default initial capacity (16). I propose to allocate IHM-s with initial capacity 8 that fits to hold 5 entries which is enough for typical annotation use cases on one hand and still makes improvement for any case on the other: 32 bit JVM: | HashMap | IdentityHashMap | size|capacitybytes|capacitybytes|IHM.bytes-HM.bytes +-+-+-- 0| 16 144| 8 136| -8 1| 16 168| 8 136| -32 2| 16 192| 8 136| -56 3| 16 216| 8 136| -80 4| 16 240| 8 136|-104 5| 16 264| 8 136|-128 6| 16 288| 16 200| -88 7| 16 312| 16 200|-112 8| 16 336| 16 200|-136 9| 16 360| 16 200|-160 10| 16 384| 16 200|-184 11| 16 408| 16 200|-208 12| 16 432| 32 328|-104 13| 32 520| 32 328|-192 14| 32 544| 32 328|-216 15| 32 568| 32 328|-240 16| 32 592| 32 328|-264 17| 32 616| 32 328|-288 18| 32 640| 32 328|-312 19| 32 664| 32 328|-336 20| 32 688| 32 328|-360 40| 64 1296| 64 584|-712 60| 128 2032| 128 1096|-936 80| 128 2512| 128 1096| -1416 100| 256 3504| 256 2120| -1384 120| 256 3984| 256 2120| -1864 140| 256 4464| 256 2120| -2344 160| 256 4944| 256 2120| -2824 180| 256 5424| 512 4168| -1256 64 bit JVM: | HashMap | IdentityHashMap | size|capacitybytes|capacitybytes|IHM.bytes-HM.bytes +-+-+-- 0| 16 248| 8 240| -8 1| 16 296| 8 240| -56 2| 16 344| 8 240|-104 3| 16 392| 8 240|-152 4| 16 440| 8 240|-200 5| 16 488| 8 240|-248 6| 16 536| 16 368|-168 7| 16 584| 16 368|-216 8| 16 632| 16 368|-264 9| 16 680| 16 368|-312 10| 16 728| 16 368|-360 11| 16 776| 16 368|-408 12| 16 824| 32 624|-200 13| 32 1000| 32 624|-376 14| 32 1048| 32 624|-424 15| 32 1096| 32 624|-472 16| 32 1144| 32 624|-520 17| 32 1192| 32 624|-568 18| 32 1240| 32 624|-616 19| 32 1288| 32 624|-664 20| 32 1336| 32 624|-712 40| 64 2552| 64 1136| -1416 60| 128 4024| 128 2160| -1864 80| 128 4984| 128 2160| -2824 100| 256 6968| 256 4208| -2760 120| 256 7928| 256 4208| -3720 140| 256 | 256 4208| -4680 160| 256 9848| 256 4208| -5640 180| 25610808| 512 8304| -2504 I hope I've got that tables right. This is the program to compute them: https://raw.github.com/plevart/jdk8-tl/JEP-149.2/test/src/test/IHMvsHMsizes.java IHM is also more performant when retrieving the values by keys. The only area in which it lags behind HashMap and is important for accessing
