gmane.comp.java.openjdk.core-libs.devel

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

Ulf Zibis — 2012-05-24T01:03:15

Am 24.05.2012 02:22, schrieb Mike Duigou:
And as improvement for the following:
   58             int k1 = (data[offset] & 0x0FF)
   59                     | (data[offset + 1] & 0x0FF) << 8
   60                     | (data[offset + 2] & 0x0FF) << 16
   61                     | data[offset + 3] << 24;
See:
Bug 6914113 <http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6914113> - Copy int to byte[] in 1 step

-Ulf

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

Ulf Zibis — 2012-05-24T00:46:31

Am 24.05.2012 02:22, schrieb Mike Duigou:
Oh, these are good news.
But I don't think all Maps need such a method, e.g. TreeMap.

I didn't think about saving the cashing, I thought about cashing the new hash in the existing old 
field in context of my upper question. Maybe we could drop caching the legacy one, if now rarely used.

I was one of those, who objected the compile time hashes O:-)

-Ulf

P.S.: have you seen my question + suggestion on the very bottom ...

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

Mike Duigou — 2012-05-24T00:22:53

On May 23 2012, at 16:58 , Ulf Zibis wrote:


It is possible for JDK 8. One option is to provide the hash() method as a virtual extension method on Map allowing implementations to override it. 


Interesting idea. The description specifically avoids defining the behaviour so implementations can do this kind of optimization. For 7u6, unless there are technical problems, the proposed. implementation is sufficient. The important message though is that it can be changed later.


Compatibility (which is of paramount importance). Part of the difficulty is that the String.hashCode() calculation method is part of the specification. Changing the specification is possible but probably not practical.


Performance without caching the hash code result is unacceptable. (I've tried it).


Yes, there other other reasons as well.

Mike

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

Ulf Zibis — 2012-05-23T23:58:07

Hi,

What about making this approach a little bit more general?
See: Bug <http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6812862>6812862 
<http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6812862> - provide customizable hash() algorithm 
in HashMap for speed tuning
      + all later comments.
Then you additionally could save:
     if ((0 != h) && (k instanceof String))

Looking at the codes of many charsets, the main variance seems to be in the lower 8 bits of a 
character, especially if the strings belong to the same language. So if we would compose the initial 
32-bit values from 4 chars then the murmur3 algorithm could perform almost twice faster.

If you alter all hash maps in JDK to use a new hash value, which noteworthy use cases remain to use 
the legacy hashcode()? Do we really need 2 hash fields in String?

In project coin, we have set in stone to use compile time hashes for Strings_in_switch extension. So 
it never can't profit from the murmur3 optimization. IMO: what a pity!
(Prominent people have said, it will never make sense to change the String's hash algorithm.)
See: http://markmail.org/message/ig3nzmfinfuvgbwz
      http://markmail.org/message/h3nlhhae5qlmf37a


Am 23.05.2012 21:03, schrieb Mike Duigou:
Wouldn' t
     return (h ^= (h>>>  7) ^ (h>>>  4));
have the same effect ?

Anyway, please add a comment for later readers.

-Ulf

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

David Holmes — 2012-05-23T23:31:44

Is it worth using:

&& (k instanceof String || k instanceof Hash32)

to deal with that. What would be the penalty on non-String Hash32's?

David

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

Mike Duigou — 2012-05-23T19:03:03

Hi Remi;

As always, thank you for the valuable feedback.

On May 23 2012, at 03:42 , Rémi Forax wrote:

It was temporary and should no longer be needed. There was skew between my patch and the java.utils warnings cleanup for a while. I will make sure that this change can be removed. I won't commit without making sure that the Makefile change is not required.

These are different seeds. The zero value is a signal that alternative hashing is disabled.

I will fix this.

I responded to this issue to Mike Skells question. Repeating that response: The problem with using instanceof Hashable32 is that is much slower (often more than 25X) than instanceof String. It's slow enough that we won't reasonably consider using instanceof Hashable32 in JDK 8. We have considered making Object implement Hashable32 and add a virtual extension method to Object for hash32(). The extension method would just call hashCode(). A compiler that supports extension methods is not yet part of the JDK mainline repo yet (It is still in the Lambda repo). This approach would mean that we can avoid an instanceof check but there is a *lot* of entirely reasonable reservations about having Object implement an interface and gain a new method. The actually solution which will be used in Java 8 is TBD. Using instanceof String is interim solution.

I will fix this.

I did microbenchmarking early in the development of this patch which showed that getForNullKey() was not needed.

Habit. I still accidentally use 'if (e = null)' once every year or so and hate myself when I discover that was the problem. I know that some people hate these "Yoda" style expressions checks. (http://wiert.me/2010/05/25/yoda-conditions-from-stackoverflow-new-programming-jargon-you-coined/)

I am not sure how they can be unified except to put the field into AbstractMap which would be unacceptable.

The location of the resize check moved slightly.

Mis-port from JDK 7 version which needs it to be non-final for rehashing. It can be final in the JDK 8 version.

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

Mike Duigou — 2012-05-23T16:24:28

Hi Mike;

The problem with using instanceof Hashable32 is that is much slower (often more than 25X) than instanceof String. It's slow enough that we won't reasonably consider using instanceof Hashable32 in JDK 8. We have considered making Object implement Hashable32 and add a virtual extension method to Object for hash32(). The extension method would just call hashCode(). A compiler that supports extension methods is not yet part of the JDK mainline repo yet (It is still in the Lambda repo). This approach would mean that we can avoid an instanceof check but there is a *lot* of entirely reasonable reservations about having Object implement an interface and gain a new method.

Opinions and insights welcome,

Mike

On May 23 2012, at 00:38 , Mike Skells wrote:

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

Rémi Forax — 2012-05-23T10:42:31

Hi Mike,
these comments are for jdk8, I have no time currently to take a look to 
jdk7 counterpart.

First, why do you change make/java/java/Makefile ?

In java.lang.String, when you compute the HASHING_SEED in the static block,
you should ensure that it's never zero in the static block instead of 
doing it
in hash32().

In HashMap, the class Holder should not declare the static final fields 
'private'
because the compiler will generate an accessor in that case,
again musn.misc.Hashing.makeHashMask should never return 0 to avoid
the check in hashObject().

I suppose that the cast to j.l.String in hashObject() should be a cast 
to Hashable32
otherwise I don't see the purpose to introduce such interface
(note that WeakHashMap used Hashable32 correctly).

Also, this change

-        return h ^ (h>>>  7) ^ (h>>>  4);
+        h ^= (h>>>  7) ^ (h>>>  4);
+
+        return h;

will make the compiler generates an additional iload/istore pair.
While the Jitted code will be the same, it may bother the inlining 
heuristic.

I think the code in get() was explicitly hand-inlined to avoid perf glitch,
that's why the current code is not

Entry<K,V>  entry = getEntry(key);
return null == entry ? null : entry.getValue();

but may be this is not needed anymore. i don't know.

In transfer, we are not in C++, you can write

   while(e != null)

instead of

   while(null != e)

with no fear :)

I've a kind of meta-question, why you have one HASHMASK_OFFSET by hash map
implementations instead of one to rule them all.

Can you explain why you don't need to resize anymore in 
LinkedHashMap.addEntry(),
I'm too lazy to figure this out by myself.

In WeakHashMap.Entry, why hash is not declared 'final' anymore ?

cheers,
Rémi

On 05/23/2012 07:16 AM, Mike Duigou wrote:

Re: Code Review Request: 7170169: (props)System.getProperty("os.name")should return "Windows 8" when run on Windows 8

Chris Hegarty — 2012-05-23T08:56:35

Looks fine to me.

-Chris.

On 23/05/2012 02:32, Kurchi Hazra wrote:

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

Paul Sandoz — 2012-05-23T08:27:51

Hi Mike,

On May 23, 2012, at 7:16 AM, Mike Duigou wrote:

Can the private method HashMap.getForNullKey be removed?

Paul.

Re: Code Review Request: 7170169: (props)System.getProperty("os.name")should return "Windows 8" when run on Windows 8

Alan Bateman — 2012-05-23T07:49:32

The changes look fine to me.

David - I'm sure that Windows 8 will bring surprises but so far the only 
one that we know of for the "core" area is:

7096436: (sc) SocketChannel.connect fails on Windows 8 when channel 
configured non-blocking

Kurchi pushed a fix for that a few weeks ago. I'm sure other issues 
(client area in particular) will be found once folks start to run tests 
and use Windows 8 in anger.

-Alan.

Re: Review Request CR#7118743 : Alternative Hashing for String withHash-based Maps

Mike Skells — 2012-05-23T07:38:39

Hi Mike,

I have a query, why is this implementation limitted to String?
Is this by intent?

in HashMap the patch for hash calculation is 
 290     final int hash(Object k) {
 291         int h = hashMask;
 292         if ((0 != h) && (k instanceof String)) {
 293             return h ^ ((String)k).hash32();
....
whereas I would have thought that it should be 
 290     final int hash(Object k) {
 291         int h = hashMask;
 292         if ((0 != h) && (k instanceof Hash32)) {
 293             return h ^ ((Hash32)k).hash32();
....

As a more flexible improvement could you supply a HashCode and Equals delegate, and then the user can supply either a custom delegate, suitable for that application (e.g.one that iterates through array content, or any other application data structure that needs to be handled differently like c# uses http://msdn.microsoft.com/en-us/library/system.collections.iequalitycomparer )

Regards

Mike

Re: Code Review Request: 7170169: (props)System.getProperty("os.name")should return "Windows 8" when run on Windows 8

David Holmes — 2012-05-23T03:04:57

I would think AWT/Swing is the place most likely to have version 
specific workarounds.

David

Re: Code Review Request: 7170169: (props)System.getProperty("os.name")should return "Windows 8" when run on Windows 8

Kurchi Subhra Hazra — 2012-05-23T03:02:30

I ran the tests in jdk/test/java/lang and they all pass. Let me know if 
you think some other tests should also
be run.

- Kurchi

On 5/22/12 7:33 PM, David Holmes wrote:

Re: Code Review Request: 7170169: (props)System.getProperty("os.name")should return "Windows 8" when run on Windows 8

David Holmes — 2012-05-23T02:33:48

Is there any windows version specific code that might also need updating 
to allow for Windows 8 aka 6.2?

David

Re: Code Review Request: 7170169: (props)System.getProperty("os.name")should return "Windows 8" when run on Windows 8

Joseph Darcy — 2012-05-23T01:57:28

Hi Kurchi,

Looks fine,

-Joe

On 5/22/2012 6:32 PM, Kurchi Hazra wrote:

Code Review Request: 7170169: (props) System.getProperty("os.name")should return "Windows 8" when run on Windows 8

Kurchi Hazra — 2012-05-23T01:32:23

Hi,

   This is a minor change to java_props_md.c to return "Windows 8" as 
the "os.name" for Windows version 6.2.

Bug: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7170169
Webrev: http://cr.openjdk.java.net/~khazra/7170169/webrev.00/

Thanks,
Kurchi

Long standing String.trim() bug

Paulo Levi — 2012-05-21T07:13:04

Just hit me now, from a utf-8 document

http://closingbraces.net/2008/11/11/javastringtrim/

Anyway, any plans to deprecate trim() and add a new one?
I for one would refactor all my projects with it.

Re: Please review (EZ): 7170087: tools/launcher/Arrghs.java test haswrong bugID for 7151434

Kelly O'Hair — 2012-05-18T23:39:31

Change looks fine to me.

-kto

On May 18, 2012, at 3:04 PM, Kumar Srinivasan wrote:

Please review (EZ): 7170087: tools/launcher/Arrghs.java test haswrong bugID for 7151434

Kumar Srinivasan — 2012-05-18T22:04:14

Hi,

Fixed CR reference in test.

http://cr.openjdk.java.net/~ksrini/7170087/

The original changset for reference.
http://hg.openjdk.java.net/jdk8/tl/jdk/rev/f68c854fa584

Thanks in advance.

Kumar

Re: Code Review Request: 7164636: (prefs) Cleanupsrc/macosx/classes/java/util/prefs

Chris Hegarty — 2012-05-15T18:00:24

This looks fine to me.

-Chris.