Another round of updates for Java 7 [1] and Java 8 [2] implementations. This revision incorporates Remi's suggestions and some feedback from Doug Lea regarding applying the per-instance seed to the result of String.hash32()
[1] althashing "7" webrev : http://cr.openjdk.java.net/~mduigou/althashing7/10/webrev/ [2] althashing "8" webrev : http://cr.openjdk.java.net/~mduigou/althashing8/10/webrev/ Barring any emergencies this will be integrated to both Java 7 and Java 8 on Wednesday May 30th, 2012. Thanks to all who provided feedback! Mike On May 25 2012, at 10:38 , Rémi Forax wrote: > On 05/24/2012 09:34 PM, Mike Duigou wrote: >> Hello All; >> >> I have updated the webrevs for alternative hashing for String with feedback >> from Remi, Doug, Ulf and internal reviewers. >> >> Additional feedback is welcome. >> >> Mike >> >> [1] althashing "7" webrev : >> http://cr.openjdk.java.net/~mduigou/althashing7/9/webrev/ >> [2] althashing "8" webrev : >> http://cr.openjdk.java.net/~mduigou/althashing8/9/webrev/ > > Hello Mike, > just two small issues. > > In WeakHashMap.hash(), the null check should be done at callsite, It's not even needed at the callsite as it always follows a maskNull call. > the call to hash32() should be directly returned like in HashMap. Fixed. > Is Hashable32 is used anymore ? It's the "source" of the hash32 method that String now implements and hopefully more later. This bit is sort of unfinished in this patch but I would like to leave it in for now. Mike > Rémi > >> >> On May 22 2012, at 22:16 , Mike Duigou wrote: >> >>> Dear OpenJDK CoreLibs community, >>> >>> A significant enhancement to the Java SE hashing-based Map implementations >>> in planned for inclusion in Java SE 7u6. All of the hashing based Map >>> implementations: HashMap, Hashtable, LinkedHashMap, WeakHashMap and >>> ConcurrentHashMap will now use an enhanced hashing algorithm for string >>> keys when the capacity of the hash table has ever grown beyond 512 entries. >>> The enhanced hashing implementation uses the murmur3 hashing algorithm[1] >>> along with random hash seeds and index masks. These enhancements mitigate >>> cases where colliding String hash values could result in a performance >>> bottleneck. >>> >>> In order to provide the greatest opportunity for developers to test >>> compatibility with their applications this change will be incorporated into >>> JDK7u6 build 12 and JDK8 build 39. Both builds are planned for release next >>> week. ***For 7u6 build 12 only, the alternative hashing will be >>> unconditionally enabled (always on).*** The threshold default will be reset >>> to the intended release default (512) for 7u6 build 13. >>> >>> The quick promotion of this change into builds with limited opportunity for >>> public review and the special behaviour for build 12 is intended to make it >>> easier for developers to test their application compatibility. Feedback on >>> the approach, implementation, compatibility and performance is eagerly >>> sought and encouraged both before *and after* this change is incorporated >>> into the OpenJDK repositories. >>> >>> A new system property, jdk.map.althashing.threshold, allows adjustment of >>> the threshold for enabling the enhanced hashing algorithm. If changed from >>> the default value of 512, the enhanced hashing will be invoked any time >>> after map capacity exceeds the value of jdk.map.althashing.threshold. To >>> completely disable the enhanced hashing (not recommended), set >>> jdk.map.althashing.threshold to -1 or a very large number such as 2^31 -1 >>> (Integer.MAX_VALUE). >>> >>> The iteration order of keys, values and entries for hash-based maps where >>> the new algorithm has been invoked will vary for each HashMap instance. >>> While the Java SE Map documentation makes no promises that iteration order >>> of items returned from Maps will be consistent, developers should check if >>> their applications have incorrectly created a dependency on the iteration >>> order of Map entries, keys or values. >>> >>> Webrevs for the Java 7u6 and 8 changes are available for download at [2] >>> and [3] for your review. There are some important differences between the >>> Java 7 and 8 implementations of this enhancement. Most specifically in the >>> Java 8 implementation alternative string hashing is always enabled--no >>> threshold is used for enablement and alternative hashing cannot be >>> disabled. (The Java 8 implementation completely ignores the >>> jdk.map.althashing.threshold system property). The Java 8 implementation is >>> also subject to additional refinement as Java 8 develops. >>> >>> If you have any questions or concerns with this planned enhancement, please >>> use the corelibs development mailing >>> list,<mailto:core-libs-dev@openjdk.java.net>, or you may also respond >>> privately to me if you prefer. >>> >>> Thanks, >>> >>> Mike >>> >>> [1] Murmur3 : https://code.google.com/p/smhasher/wiki/MurmurHash3 >>> [2] althashing "7" webrev : >>> http://cr.openjdk.java.net/~mduigou/althashing7/8/webrev/ >>> [3] althashing "8" webrev : >>> http://cr.openjdk.java.net/~mduigou/althashing8/8/webrev/ >
