You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@harmony.apache.org by "Jimmy,Jing Lv" <fi...@gmail.com> on 2007/06/27 12:10:30 UTC
Performance improvement of java.util.HashMap (Was Re: [jira] Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Hi,
As currently focus on performance, I find this JIRA(4064) and do
some investigation on it.
The Performance improvement of java.util.HashMap is about two
aspects: one is hash algorithm that make hashcode randomly distributed
enough, just as Tim's fix/comments in Harmony-4064, the other is about
to make hash algorithm itself perform fast enough. HashMap is so
widely used so that both two aspects may be very important.
I strongly agree with Tim that hash algorithm that make hashcode
randomly distributed is very important, for HashMap.put(), get(), etc,
depends on it and it should perform better if the hash algorithm can
make it randomly distributed. On the other hand, the hash algorithm
should perform very fast as every HashMap.put and get method call this
hash algorithm, if it is slow itself, then its benfits on randomly
distribution became meaningless.
I do a lot of benchmark and micro-benchmarks, it shows that (a &
b) is much faster than (a % b). And if b is Math.pow(2,n)-1, the two
operations just get the same result. That's why if we choose
"&(Math.pow(2,n)-1)" (here Math.pow(2,n) is the size of bucket of a
hashmap)to replace "%", by this way we improve performance greatly at
least 2% ~ 3% in some benchmarks . This shows if we avoid slow
operation like mod(%), multiply(*), division(/) and so forth, we can
get performance improvement.
Yes, I do think to randomly distrubute the hashcode is very
important and I suggest we can use other machnisms other than mod
prime to make it happen. One thought is right-shift the hashcode and
combine bits together (by AND or OR or Exclusive Or operation) into
low order(e.g, (a & (a >> 8) ^ (a >> 16) | (a >> 24)) &
(bucketSize-1), a small test on it shows that it does distributed more
randomly, but it may be better algorithms. In this way the hashcode
may be more random destributed and performs fast. And in this way we
may keep a balance of a both fast and good hash algorithm.
Any comments/suggestions? Thanks!
2007/6/6, Tim Ellison (JIRA) <ji...@apache.org>:
>
> [ https://issues.apache.org/jira/browse/HARMONY-4064?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12501905 ]
>
> Tim Ellison commented on HARMONY-4064:
> --------------------------------------
>
> Robert. You patch undoes the change I made to make the length of the elements array a prime number, so that it is now always a power of two. The problem is that identity hash codes are not randomly distributed, they typically reflect object address alignments which will be factors of two, so we don't get a good distribution across all the possible buckets.
>
> You can see the effect in this simple 'simulation':
>
> public class HashingTest {
>
> public static void main(String[] args) {
> int numBuckets = 16;
>
> int[] distrib = new int[numBuckets];
> for (int i = 0; i < distrib.length; i++) {
> distrib[i] = 0;
> }
>
> for (int i = 0; i < 1000; i++) {
> int hashCode = new Object().hashCode();
> int bucket = hashCode & (numBuckets - 1);
> distrib[bucket] = distrib[bucket] + 1;
> }
>
> System.out.println("Bucket\tList_length");
> for (int i = 0; i < distrib.length; i++) {
> System.out.println(i + "\t" + distrib[i]);
> }
> }
> }
>
> I suggest that we have to ensure the elements array length is chosen more carefully, or that we modify the hashCodes to avoid these collisions.
>
> > [classlib][luni] Performance improvement of java.util.HashMap
> > -------------------------------------------------------------
> >
> > Key: HARMONY-4064
> > URL: https://issues.apache.org/jira/browse/HARMONY-4064
> > Project: Harmony
> > Issue Type: Improvement
> > Components: Classlib
> > Reporter: Robert Hu
> > Assignee: Tim Ellison
> > Attachments: HARMONY-4064.diff
> >
> >
> > The performance of HashMap can be improved, the hash method is improved.
> > By running the following test code, our HashMap can be improved from 110% time cost (compared by RI) to 90% time cost (compared by RI).
> > public class TestHashMap {
> > public static void main(String[] args) {
> > Random ran = new Random();
> > HashMap map = new HashMap();
> > int elementNum = 500;
> > int times = 10000;
> > int[] rans = new int[elementNum];
> > for (int i = 0; i < elementNum; i++)
> > rans[i] = ran.nextInt(Integer.MAX_VALUE);
> > long start = System.currentTimeMillis();
> > for (int i = 0; i < elementNum; i++)
> > map.put(rans[i], "b");
> > System.out.println(System.currentTimeMillis() - start);
> > start = System.currentTimeMillis();
> > for (int i = 0; i < elementNum; i++)
> > for(int j = 0; j< times; j++){
> > map.get(rans[i]);
> > }
> > System.out.println(System.currentTimeMillis() - start);
> > }
> > }
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
>
--
Best Regards!
Jimmy, Jing Lv
China Software Development Lab, IBM
Re: Performance improvement of java.util.HashMap (Was Re: [jira] Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by "Jimmy,Jing Lv" <fi...@gmail.com>.
Properly our function is not good enough, perhaps we may find some
operater other than '|' and '^', e.g, '+', '-' or something? Though I
guess '|' and '^' are the fastest.
2007/6/29, Yuri Dolgov <do...@gmail.com>:
> Hi Jimmy,
>
> I've done couple of experiments with different hash functions (including all
> the functions proposed in this mail thread), but none of them worked
> satisfactorily for hashmap with small number of elemts (32-64) when I've
> changed only upper bits. Do you have any progress so far?
>
>
> Thanks,
> Yuri
>
> On 6/28/07, Jimmy,Jing Lv <fi...@gmail.com> wrote:
> >
> > 2007/6/28, Tim Ellison <t....@gmail.com>:
> > > Jimmy,Jing Lv wrote:
> > > > 2007/6/28, Tim Ellison <t....@gmail.com>:
> > > >> Jimmy,Jing Lv wrote:
> > > >> > One thought is right-shift the hashcode and combine bits together
> > (by
> > > >> > AND or OR or Exclusive Or operation) into low order(e.g, (a & (a >>
> > > >> > 8) ^ (a >> 16) | (a >> 24)) & (bucketSize-1), a small test on it
> > > >> > shows that it does distributed more randomly, but it may be better
> > > >> > algorithms.
> > > >>
> > > >> Why so complex bit shifting? How did you settle on this?
> > > >>
> > > >> If you are optimizing for the identity hashcode case then you can
> > > >> probably ignore the bottom 'y' bits due to object alignment (and top
> > 'z'
> > > >> bits for address range limits), so just do (a >> 8) & (bucketSize -
> > 1)
> > > >> assuming the objects are 8-bit aligned.
> > > >
> > > > It sounds interesting and reasonable :)
> > > > But I'm afraid not all hashcode() returns the object's memory
> > > > address,
> > >
> > > Understood. The hashCode() can return any int value, so in principle
> > > you have a random set of 32 bits an no bit manipulation is required.
> > >
> > > However, in practice I think we can optimize for typical hashcode
> > > values. The debate is what is 'typical'? What is the most common type
> > > of HashMap key? (then we can look at it's hashCode implementation).
> > >
> >
> > Ah yes I hope someone may know what is 'typical' or common hashcode? :)
> > But i'm afraid everyone who program in java may define his own
> > hashcode. After all, the basic principle of hashcode is to make it as
> > dispersive as possible, that's why I think we may use all 32 bits to
> > find the bucket.
> >
> > > > in some other cases, the difference of hashcodes may remain
> > > > in buttom 'y' bits or top 'z' bits, at that time our HashMap will
> > > > perform very slow.
> > >
> > > You are right, I should not have thrown away those top bits. So how
> > > about a *rotate* right by eight bits operation?
> > >
> > > > So the best way is to use all 32 bit of a hashcode, and take extra
> > > > operator '|' and '^' does not cost much time.( though I'm not sure if
> > > > the the right-shift paramter '8' is proper)
> > >
> > > The operation you suggested was
> > > a & (a >> 8) ^ (a >> 16) | (a >> 24)
> > >
> > > can you please explain how you came up with this?
> > >
> >
> > If we make it small, like 4, we have to spend much more time like:
> > a & (a >> 4) ^ (a >> 8) | (a >> 12)^(a >> 16) ^ (a >> 20) | (a >> 24)...
> > and if make it bigger, we may still lose the information after the
> > operation &(2^n-1) if the parameter is a bit bigger than n, so I'm try
> > to find a balance here, though the parameter '8' may be not best.
> > As you know, the basic bucket of HashMap is 16( that is 2^4), and I
> > have no idea what is the most commen size of the hashMap bucket? Or we
> > may still use the size of the bucket as the parameter? As a result:
> > a & (a >> n) ^ (a >> n*2) | (a >> n*3), here bucket size is 2^n
> >
> > I have no idea what is better, I'll try to benckmark and find some
> > hash theory if any. Thanks to Yuri, I take a glance of two papers he
> > offered, though one is copyright-ed, the other offered many classic
> > hash algorithm, I may study and find out a best way by myself (of
> > cource, avoid copying the code :) )
> >
> > > Regards,
> > > Tim
> > >
> >
> >
> > --
> >
> > Best Regards!
> >
> > Jimmy, Jing Lv
> > China Software Development Lab, IBM
> >
>
--
Best Regards!
Jimmy, Jing Lv
China Software Development Lab, IBM
Re: Performance improvement of java.util.HashMap
Posted by Tim Ellison <t....@gmail.com>.
Yuri Dolgov wrote:
> I've done couple of experiments with different hash functions
> (including all the functions proposed in this mail thread), but none
> of them worked satisfactorily for hashmap with small number of elemts
> (32-64) when I've changed only upper bits. Do you have any progress
> so far?
What usecase does this represent? I agree with Sergey that we probably
don't want to spend much time 'improving' the incoming hashCode() inside
the hashMap, but should just ensure we don't suck for the most common
range of values.
Regards,
Tim
Re: Performance improvement of java.util.HashMap (Was Re: [jira] Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by Yuri Dolgov <do...@gmail.com>.
Hi Jimmy,
I've done couple of experiments with different hash functions (including all
the functions proposed in this mail thread), but none of them worked
satisfactorily for hashmap with small number of elemts (32-64) when I've
changed only upper bits. Do you have any progress so far?
Thanks,
Yuri
On 6/28/07, Jimmy,Jing Lv <fi...@gmail.com> wrote:
>
> 2007/6/28, Tim Ellison <t....@gmail.com>:
> > Jimmy,Jing Lv wrote:
> > > 2007/6/28, Tim Ellison <t....@gmail.com>:
> > >> Jimmy,Jing Lv wrote:
> > >> > One thought is right-shift the hashcode and combine bits together
> (by
> > >> > AND or OR or Exclusive Or operation) into low order(e.g, (a & (a >>
> > >> > 8) ^ (a >> 16) | (a >> 24)) & (bucketSize-1), a small test on it
> > >> > shows that it does distributed more randomly, but it may be better
> > >> > algorithms.
> > >>
> > >> Why so complex bit shifting? How did you settle on this?
> > >>
> > >> If you are optimizing for the identity hashcode case then you can
> > >> probably ignore the bottom 'y' bits due to object alignment (and top
> 'z'
> > >> bits for address range limits), so just do (a >> 8) & (bucketSize -
> 1)
> > >> assuming the objects are 8-bit aligned.
> > >
> > > It sounds interesting and reasonable :)
> > > But I'm afraid not all hashcode() returns the object's memory
> > > address,
> >
> > Understood. The hashCode() can return any int value, so in principle
> > you have a random set of 32 bits an no bit manipulation is required.
> >
> > However, in practice I think we can optimize for typical hashcode
> > values. The debate is what is 'typical'? What is the most common type
> > of HashMap key? (then we can look at it's hashCode implementation).
> >
>
> Ah yes I hope someone may know what is 'typical' or common hashcode? :)
> But i'm afraid everyone who program in java may define his own
> hashcode. After all, the basic principle of hashcode is to make it as
> dispersive as possible, that's why I think we may use all 32 bits to
> find the bucket.
>
> > > in some other cases, the difference of hashcodes may remain
> > > in buttom 'y' bits or top 'z' bits, at that time our HashMap will
> > > perform very slow.
> >
> > You are right, I should not have thrown away those top bits. So how
> > about a *rotate* right by eight bits operation?
> >
> > > So the best way is to use all 32 bit of a hashcode, and take extra
> > > operator '|' and '^' does not cost much time.( though I'm not sure if
> > > the the right-shift paramter '8' is proper)
> >
> > The operation you suggested was
> > a & (a >> 8) ^ (a >> 16) | (a >> 24)
> >
> > can you please explain how you came up with this?
> >
>
> If we make it small, like 4, we have to spend much more time like:
> a & (a >> 4) ^ (a >> 8) | (a >> 12)^(a >> 16) ^ (a >> 20) | (a >> 24)...
> and if make it bigger, we may still lose the information after the
> operation &(2^n-1) if the parameter is a bit bigger than n, so I'm try
> to find a balance here, though the parameter '8' may be not best.
> As you know, the basic bucket of HashMap is 16( that is 2^4), and I
> have no idea what is the most commen size of the hashMap bucket? Or we
> may still use the size of the bucket as the parameter? As a result:
> a & (a >> n) ^ (a >> n*2) | (a >> n*3), here bucket size is 2^n
>
> I have no idea what is better, I'll try to benckmark and find some
> hash theory if any. Thanks to Yuri, I take a glance of two papers he
> offered, though one is copyright-ed, the other offered many classic
> hash algorithm, I may study and find out a best way by myself (of
> cource, avoid copying the code :) )
>
> > Regards,
> > Tim
> >
>
>
> --
>
> Best Regards!
>
> Jimmy, Jing Lv
> China Software Development Lab, IBM
>
Re: Performance improvement of java.util.HashMap (Was Re: [jira] Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by "Jimmy,Jing Lv" <fi...@gmail.com>.
2007/6/28, Tim Ellison <t....@gmail.com>:
> Jimmy,Jing Lv wrote:
> > 2007/6/28, Tim Ellison <t....@gmail.com>:
> >> Jimmy,Jing Lv wrote:
> >> > One thought is right-shift the hashcode and combine bits together (by
> >> > AND or OR or Exclusive Or operation) into low order(e.g, (a & (a >>
> >> > 8) ^ (a >> 16) | (a >> 24)) & (bucketSize-1), a small test on it
> >> > shows that it does distributed more randomly, but it may be better
> >> > algorithms.
> >>
> >> Why so complex bit shifting? How did you settle on this?
> >>
> >> If you are optimizing for the identity hashcode case then you can
> >> probably ignore the bottom 'y' bits due to object alignment (and top 'z'
> >> bits for address range limits), so just do (a >> 8) & (bucketSize - 1)
> >> assuming the objects are 8-bit aligned.
> >
> > It sounds interesting and reasonable :)
> > But I'm afraid not all hashcode() returns the object's memory
> > address,
>
> Understood. The hashCode() can return any int value, so in principle
> you have a random set of 32 bits an no bit manipulation is required.
>
> However, in practice I think we can optimize for typical hashcode
> values. The debate is what is 'typical'? What is the most common type
> of HashMap key? (then we can look at it's hashCode implementation).
>
Ah yes I hope someone may know what is 'typical' or common hashcode? :)
But i'm afraid everyone who program in java may define his own
hashcode. After all, the basic principle of hashcode is to make it as
dispersive as possible, that's why I think we may use all 32 bits to
find the bucket.
> > in some other cases, the difference of hashcodes may remain
> > in buttom 'y' bits or top 'z' bits, at that time our HashMap will
> > perform very slow.
>
> You are right, I should not have thrown away those top bits. So how
> about a *rotate* right by eight bits operation?
>
> > So the best way is to use all 32 bit of a hashcode, and take extra
> > operator '|' and '^' does not cost much time.( though I'm not sure if
> > the the right-shift paramter '8' is proper)
>
> The operation you suggested was
> a & (a >> 8) ^ (a >> 16) | (a >> 24)
>
> can you please explain how you came up with this?
>
If we make it small, like 4, we have to spend much more time like:
a & (a >> 4) ^ (a >> 8) | (a >> 12)^(a >> 16) ^ (a >> 20) | (a >> 24)...
and if make it bigger, we may still lose the information after the
operation &(2^n-1) if the parameter is a bit bigger than n, so I'm try
to find a balance here, though the parameter '8' may be not best.
As you know, the basic bucket of HashMap is 16( that is 2^4), and I
have no idea what is the most commen size of the hashMap bucket? Or we
may still use the size of the bucket as the parameter? As a result:
a & (a >> n) ^ (a >> n*2) | (a >> n*3), here bucket size is 2^n
I have no idea what is better, I'll try to benckmark and find some
hash theory if any. Thanks to Yuri, I take a glance of two papers he
offered, though one is copyright-ed, the other offered many classic
hash algorithm, I may study and find out a best way by myself (of
cource, avoid copying the code :) )
> Regards,
> Tim
>
--
Best Regards!
Jimmy, Jing Lv
China Software Development Lab, IBM
Re: Performance improvement of java.util.HashMap (Was Re: [jira]
Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by Tim Ellison <t....@gmail.com>.
Jimmy,Jing Lv wrote:
> 2007/6/28, Tim Ellison <t....@gmail.com>:
>> Jimmy,Jing Lv wrote:
>> > One thought is right-shift the hashcode and combine bits together (by
>> > AND or OR or Exclusive Or operation) into low order(e.g, (a & (a >>
>> > 8) ^ (a >> 16) | (a >> 24)) & (bucketSize-1), a small test on it
>> > shows that it does distributed more randomly, but it may be better
>> > algorithms.
>>
>> Why so complex bit shifting? How did you settle on this?
>>
>> If you are optimizing for the identity hashcode case then you can
>> probably ignore the bottom 'y' bits due to object alignment (and top 'z'
>> bits for address range limits), so just do (a >> 8) & (bucketSize - 1)
>> assuming the objects are 8-bit aligned.
>
> It sounds interesting and reasonable :)
> But I'm afraid not all hashcode() returns the object's memory
> address,
Understood. The hashCode() can return any int value, so in principle
you have a random set of 32 bits an no bit manipulation is required.
However, in practice I think we can optimize for typical hashcode
values. The debate is what is 'typical'? What is the most common type
of HashMap key? (then we can look at it's hashCode implementation).
> in some other cases, the difference of hashcodes may remain
> in buttom 'y' bits or top 'z' bits, at that time our HashMap will
> perform very slow.
You are right, I should not have thrown away those top bits. So how
about a *rotate* right by eight bits operation?
> So the best way is to use all 32 bit of a hashcode, and take extra
> operator '|' and '^' does not cost much time.( though I'm not sure if
> the the right-shift paramter '8' is proper)
The operation you suggested was
a & (a >> 8) ^ (a >> 16) | (a >> 24)
can you please explain how you came up with this?
Regards,
Tim
Re: Performance improvement of java.util.HashMap (Was Re: [jira] Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by "Jimmy,Jing Lv" <fi...@gmail.com>.
2007/6/28, Tim Ellison <t....@gmail.com>:
> Jimmy,Jing Lv wrote:
> > As currently focus on performance, I find this JIRA(4064) and do
> > some investigation on it.
>
> Great.
>
> > The Performance improvement of java.util.HashMap is about two
> > aspects: one is hash algorithm that make hashcode randomly distributed
> > enough, just as Tim's fix/comments in Harmony-4064, the other is about
> > to make hash algorithm itself perform fast enough. HashMap is so
> > widely used so that both two aspects may be very important.
>
> Just to be clear, you are talking about computing the hash 'bucket'
> index for a given key's hashcode.
>
> > I strongly agree with Tim that hash algorithm that make hashcode
> > randomly distributed is very important, for HashMap.put(), get(), etc,
> > depends on it and it should perform better if the hash algorithm can
> > make it randomly distributed.
>
> Of course, you make a bet based upon the range of keys' hashcode values.
>
> The more we know about the hashcode values the better we can design the
> function to evenly distribute the keys across the available buckets. We
> used to perform badly for objects' identity hashcodes by dividing it by
> 2^n, which didn't give a good distribution.
>
> > On the other hand, the hash algorithm should perform very fast as
> > every HashMap.put and get method call this hash algorithm, if it is
> > slow itself, then its benfits on randomly distribution became
> > meaningless.
>
> Agreed, a fast bucket index computation that gives an even distribution
> is the ideal.
>
> > I do a lot of benchmark and micro-benchmarks, it shows that (a &
> > b) is much faster than (a % b).
>
> where 'a' is the key's hashcode and 'b' is the number of buckets...
>
> > And if b is Math.pow(2,n)-1, the two operations just get the same
> > result. That's why if we choose "&(Math.pow(2,n)-1)" (here
> > Math.pow(2,n) is the size of bucket of a hashmap)to replace "%", by
> > this way we improve performance greatly at least 2% ~ 3% in some
> > benchmarks . This shows if we avoid slow operation like mod(%),
> > multiply(*), division(/) and so forth, we can get performance
> > improvement.
>
> Agreed, so if we limit the number of buckets to always be a power of
> two, then you can use the fast bit operation for computing a bucket index.
>
> So now you have the problem that identity hashcodes are often the
> object's memory address at some point in time, and many implementations
> align the objects on boundaries that won't give a good even distribution
> when divided by 2^n.
>
> > Yes, I do think to randomly distrubute the hashcode is very important
> > and I suggest we can use other machnisms other than mod prime to make
> > it happen.
>
> For which set of hashcodes? Those that are typically an object's
> identity hashcode? I guess that is the most popular key hashcode, but I
> don't know for sure.
>
> > One thought is right-shift the hashcode and combine bits together (by
> > AND or OR or Exclusive Or operation) into low order(e.g, (a & (a >>
> > 8) ^ (a >> 16) | (a >> 24)) & (bucketSize-1), a small test on it
> > shows that it does distributed more randomly, but it may be better
> > algorithms.
>
> Why so complex bit shifting? How did you settle on this?
>
> If you are optimizing for the identity hashcode case then you can
> probably ignore the bottom 'y' bits due to object alignment (and top 'z'
> bits for address range limits), so just do (a >> 8) & (bucketSize - 1)
> assuming the objects are 8-bit aligned.
>
It sounds interesting and reasonable :)
But I'm afraid not all hashcode() returns the object's memory
address, in some other cases, the difference of hashcodes may remain
in buttom 'y' bits or top 'z' bits, at that time our HashMap will
perform very slow.
So the best way is to use all 32 bit of a hashcode, and take extra
operator '|' and '^' does not cost much time.( though I'm not sure if
the the right-shift paramter '8' is proper)
> > In this way the hashcode may be more random destributed and performs
> > fast. And in this way we may keep a balance of a both fast and good
> > hash algorithm.
>
> An honorable goal!
>
> Regards,
> Tim
>
>
--
Best Regards!
Jimmy, Jing Lv
China Software Development Lab, IBM
Re: Performance improvement of java.util.HashMap (Was Re: [jira]
Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by Tim Ellison <t....@gmail.com>.
Jimmy,Jing Lv wrote:
> As currently focus on performance, I find this JIRA(4064) and do
> some investigation on it.
Great.
> The Performance improvement of java.util.HashMap is about two
> aspects: one is hash algorithm that make hashcode randomly distributed
> enough, just as Tim's fix/comments in Harmony-4064, the other is about
> to make hash algorithm itself perform fast enough. HashMap is so
> widely used so that both two aspects may be very important.
Just to be clear, you are talking about computing the hash 'bucket'
index for a given key's hashcode.
> I strongly agree with Tim that hash algorithm that make hashcode
> randomly distributed is very important, for HashMap.put(), get(), etc,
> depends on it and it should perform better if the hash algorithm can
> make it randomly distributed.
Of course, you make a bet based upon the range of keys' hashcode values.
The more we know about the hashcode values the better we can design the
function to evenly distribute the keys across the available buckets. We
used to perform badly for objects' identity hashcodes by dividing it by
2^n, which didn't give a good distribution.
> On the other hand, the hash algorithm should perform very fast as
> every HashMap.put and get method call this hash algorithm, if it is
> slow itself, then its benfits on randomly distribution became
> meaningless.
Agreed, a fast bucket index computation that gives an even distribution
is the ideal.
> I do a lot of benchmark and micro-benchmarks, it shows that (a &
> b) is much faster than (a % b).
where 'a' is the key's hashcode and 'b' is the number of buckets...
> And if b is Math.pow(2,n)-1, the two operations just get the same
> result. That's why if we choose "&(Math.pow(2,n)-1)" (here
> Math.pow(2,n) is the size of bucket of a hashmap)to replace "%", by
> this way we improve performance greatly at least 2% ~ 3% in some
> benchmarks . This shows if we avoid slow operation like mod(%),
> multiply(*), division(/) and so forth, we can get performance
> improvement.
Agreed, so if we limit the number of buckets to always be a power of
two, then you can use the fast bit operation for computing a bucket index.
So now you have the problem that identity hashcodes are often the
object's memory address at some point in time, and many implementations
align the objects on boundaries that won't give a good even distribution
when divided by 2^n.
> Yes, I do think to randomly distrubute the hashcode is very important
> and I suggest we can use other machnisms other than mod prime to make
> it happen.
For which set of hashcodes? Those that are typically an object's
identity hashcode? I guess that is the most popular key hashcode, but I
don't know for sure.
> One thought is right-shift the hashcode and combine bits together (by
> AND or OR or Exclusive Or operation) into low order(e.g, (a & (a >>
> 8) ^ (a >> 16) | (a >> 24)) & (bucketSize-1), a small test on it
> shows that it does distributed more randomly, but it may be better
> algorithms.
Why so complex bit shifting? How did you settle on this?
If you are optimizing for the identity hashcode case then you can
probably ignore the bottom 'y' bits due to object alignment (and top 'z'
bits for address range limits), so just do (a >> 8) & (bucketSize - 1)
assuming the objects are 8-bit aligned.
> In this way the hashcode may be more random destributed and performs
> fast. And in this way we may keep a balance of a both fast and good
> hash algorithm.
An honorable goal!
Regards,
Tim
Re: Performance improvement of java.util.HashMap
Posted by "Jimmy,Jing Lv" <fi...@gmail.com>.
2007/6/29, Tim Ellison <t....@gmail.com>:
> Jimmy,Jing Lv wrote:
> > 2007/6/29, Sergey Kuksenko <se...@gmail.com>:
> >> The first solution has one advantage - it can be done only in
> >> classlib. The second variant should be implemented in all VMs which
> >> are based on Harmony's classlib. But this way has other advantages
> >> - Well-formed IdentityHashCode will helps not only for HashMap, but
> >> for Hashtable, IdentityHashMap and moreover for all hashing
> >> implemented by users.
> >
> > Ah, I never think of it, so you mean IdentityHashCode can be
> > implemented in vm?
>
> It always will be in Harmony, since it is obtained by
> System#identityHashCode(Object), which is in the kernel class set.
>
> > Doesn't vm return directly the address as the
> > IdentityHashCode?(it is easiest and fastest way)
>
> It is typical for the implementation to return the object address at the
> point was first asked for it's identityHashCode, but that is not
> required by the spec.
>
Interesting, got it :)
> >> In the second variant we don't add rehashing function into HashMap. It is
> >> common practice when advanced Java developers tune their HashCode
> >> functions.
> >> If we add rehashing function into HashMap we may break their tuning,
> >> without
> >> knowledge of internal rehashing functions it is impossible to tune
> >> HashCode
> >> function.
> >> From my opinion we should think about the last argument against adding
> >> rehashing into HashMap and move rehashing into VM.
> >>
> >
> > Yes, the improved identityHashCode may help, but usually users also
> > define their own hashcode, then the identityHashCode may not help,
> > while rehash in classlib still works, that's why I guess improvement
> > in classlib is better :)
>
> Since the developer is defining the hashCode() I don't see how you would
> know the best way to improve their value? I think we just rely on them
> to do their job properly or suffer the consequences :-)
>
I think we never try to make an improvement for all hashcode :) I
think we can only make a hypothesis that programmer can define a
hashcode that is distributed randomly, in that way we can rehash it
into buckets and in this hypothesis we can improve our Hash-relasted
classes.
After all, Harmony is open-source and everyone can modify the code
into his own style or for special use/performance improvement (it is
really coooool! :) ). Our discuss here may help them on tuning
HashMap. And we harmony guys just try to find a more typical way ;)
> Regards,
> Tim
>
--
Best Regards!
Jimmy, Jing Lv
China Software Development Lab, IBM
Re: Performance improvement of java.util.HashMap
Posted by Tim Ellison <t....@gmail.com>.
Jimmy,Jing Lv wrote:
> 2007/6/29, Sergey Kuksenko <se...@gmail.com>:
>> The first solution has one advantage - it can be done only in
>> classlib. The second variant should be implemented in all VMs which
>> are based on Harmony's classlib. But this way has other advantages
>> - Well-formed IdentityHashCode will helps not only for HashMap, but
>> for Hashtable, IdentityHashMap and moreover for all hashing
>> implemented by users.
>
> Ah, I never think of it, so you mean IdentityHashCode can be
> implemented in vm?
It always will be in Harmony, since it is obtained by
System#identityHashCode(Object), which is in the kernel class set.
> Doesn't vm return directly the address as the
> IdentityHashCode?(it is easiest and fastest way)
It is typical for the implementation to return the object address at the
point was first asked for it's identityHashCode, but that is not
required by the spec.
>> In the second variant we don't add rehashing function into HashMap. It is
>> common practice when advanced Java developers tune their HashCode
>> functions.
>> If we add rehashing function into HashMap we may break their tuning,
>> without
>> knowledge of internal rehashing functions it is impossible to tune
>> HashCode
>> function.
>> From my opinion we should think about the last argument against adding
>> rehashing into HashMap and move rehashing into VM.
>>
>
> Yes, the improved identityHashCode may help, but usually users also
> define their own hashcode, then the identityHashCode may not help,
> while rehash in classlib still works, that's why I guess improvement
> in classlib is better :)
Since the developer is defining the hashCode() I don't see how you would
know the best way to improve their value? I think we just rely on them
to do their job properly or suffer the consequences :-)
Regards,
Tim
Re: Performance improvement of java.util.HashMap (Was Re: [jira] Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by "Jimmy,Jing Lv" <fi...@gmail.com>.
2007/6/29, Sergey Kuksenko <se...@gmail.com>:
> Hi All,
>
> I wish to include myself into discussion and express some my thought in this
> area.
> I am absolutely agree with the idea of using bitwise operations & (or power
> of two remainder) instead of % (arbirary remainder) because of power of two
> remainder is really faster and was proved by my tests and etc...
>
> First of all I wish to note that if HashMap works with user-defined HashCode
> it doesn't matter which reminder is used: power fo two (&) or prime(or
> arbitrary) number reminder (%). In case if user defined HashCode we can't
> predict hash and the hash can be suitable as for & and for %.
> But prime number reminder has one disadavntages (except speed of operation).
> When HashMap uses prime number (or some irreglar) we get negative effect of
> unused part of memory page. Size of memory pages is power of two and it is
> better to fill it completely. Espesially it is visible on large hash maps.
> Unfortunately I can privide any numbers at the moment.
> Thus in my opinion power of two reminder gives boost in time of operation
> plus benefits from more natural memory usage (layouts etc.)
>
> As to default hashCode which is IdentityHashCode.
> There are two ways here:
> 1. Add new hashing function (additional hashing) inside HashMap. As was
> suggested here.
> 2. Change IdentityHashCode implementation. There are no rules that
> IdentityHashCode should return exactly address of object. And last zero bits
> from IdentityHashCode (which caused by object alignment) can be removed
> inside IdentityHashCode. Other words - to add additional hashing inside
> IdentityHashCode.
>
> The first solution has one advantage - it can be done only in classlib. The
> second variant should be implemented in all VMs which are based on Harmony's
> classlib. But this way has other advantages - Well-formed IdentityHashCode
> will helps not only for HashMap, but for Hashtable, IdentityHashMap and
> moreover for all hashing implemented by users.
Ah, I never think of it, so you mean IdentityHashCode can be
implemented in vm? Doesn't vm return directly the address as the
IdentityHashCode?(it is easiest and fastest way)
> In the second variant we don't add rehashing function into HashMap. It is
> common practice when advanced Java developers tune their HashCode functions.
> If we add rehashing function into HashMap we may break their tuning, without
> knowledge of internal rehashing functions it is impossible to tune HashCode
> function.
> From my opinion we should think about the last argument against adding
> rehashing into HashMap and move rehashing into VM.
>
Yes, the improved identityHashCode may help, but usually users also
define their own hashcode, then the identityHashCode may not help,
while rehash in classlib still works, that's why I guess improvement
in classlib is better :)
>
>
>
> On 6/27/07, Jimmy,Jing Lv <fi...@gmail.com> wrote:
> >
> > Hi,
> >
> > As currently focus on performance, I find this JIRA(4064) and do
> > some investigation on it.
> >
> > The Performance improvement of java.util.HashMap is about two
> > aspects: one is hash algorithm that make hashcode randomly distributed
> > enough, just as Tim's fix/comments in Harmony-4064, the other is about
> > to make hash algorithm itself perform fast enough. HashMap is so
> > widely used so that both two aspects may be very important.
> >
> > I strongly agree with Tim that hash algorithm that make hashcode
> > randomly distributed is very important, for HashMap.put(), get(), etc,
> > depends on it and it should perform better if the hash algorithm can
> > make it randomly distributed. On the other hand, the hash algorithm
> > should perform very fast as every HashMap.put and get method call this
> > hash algorithm, if it is slow itself, then its benfits on randomly
> > distribution became meaningless.
> >
> > I do a lot of benchmark and micro-benchmarks, it shows that (a &
> > b) is much faster than (a % b). And if b is Math.pow(2,n)-1, the two
> > operations just get the same result. That's why if we choose
> > "&(Math.pow(2,n)-1)" (here Math.pow(2,n) is the size of bucket of a
> > hashmap)to replace "%", by this way we improve performance greatly at
> > least 2% ~ 3% in some benchmarks . This shows if we avoid slow
> > operation like mod(%), multiply(*), division(/) and so forth, we can
> > get performance improvement.
> >
> > Yes, I do think to randomly distrubute the hashcode is very
> > important and I suggest we can use other machnisms other than mod
> > prime to make it happen. One thought is right-shift the hashcode and
> > combine bits together (by AND or OR or Exclusive Or operation) into
> > low order( e.g, (a & (a >> 8) ^ (a >> 16) | (a >> 24)) &
> > (bucketSize-1), a small test on it shows that it does distributed more
> > randomly, but it may be better algorithms. In this way the hashcode
> > may be more random destributed and performs fast. And in this way we
> > may keep a balance of a both fast and good hash algorithm.
> >
> > Any comments/suggestions? Thanks!
> >
> >
> > 2007/6/6, Tim Ellison (JIRA) <ji...@apache.org>:
> > >
> > > [ https://issues.apache.org/jira/browse/HARMONY-4064?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12501905
> > ]
> > >
> > > Tim Ellison commented on HARMONY-4064:
> > > --------------------------------------
> > >
> > > Robert. You patch undoes the change I made to make the length of the
> > elements array a prime number, so that it is now always a power of two. The
> > problem is that identity hash codes are not randomly distributed, they
> > typically reflect object address alignments which will be factors of two, so
> > we don't get a good distribution across all the possible buckets.
> > >
> > > You can see the effect in this simple 'simulation':
> > >
> > > public class HashingTest {
> > >
> > > public static void main(String[] args) {
> > > int numBuckets = 16;
> > >
> > > int[] distrib = new int[numBuckets];
> > > for (int i = 0; i < distrib.length; i++) {
> > > distrib[i] = 0;
> > > }
> > >
> > > for (int i = 0; i < 1000; i++) {
> > > int hashCode = new Object().hashCode();
> > > int bucket = hashCode & (numBuckets - 1);
> > > distrib[bucket] = distrib[bucket] + 1;
> > > }
> > >
> > > System.out.println("Bucket\tList_length");
> > > for (int i = 0; i < distrib.length; i++) {
> > > System.out.println(i + "\t" + distrib[i]);
> > > }
> > > }
> > > }
> > >
> > > I suggest that we have to ensure the elements array length is chosen
> > more carefully, or that we modify the hashCodes to avoid these collisions.
> > >
> > > > [classlib][luni] Performance improvement of java.util.HashMap
> > > > -------------------------------------------------------------
> > > >
> > > > Key: HARMONY-4064
> > > > URL:
> > https://issues.apache.org/jira/browse/HARMONY-4064
> > > > Project: Harmony
> > > > Issue Type: Improvement
> > > > Components: Classlib
> > > > Reporter: Robert Hu
> > > > Assignee: Tim Ellison
> > > > Attachments: HARMONY-4064.diff
> > > >
> > > >
> > > > The performance of HashMap can be improved, the hash method is
> > improved.
> > > > By running the following test code, our HashMap can be improved from
> > 110% time cost (compared by RI) to 90% time cost (compared by RI).
> > > > public class TestHashMap {
> > > > public static void main(String[] args) {
> > > > Random ran = new Random();
> > > > HashMap map = new HashMap();
> > > > int elementNum = 500;
> > > > int times = 10000;
> > > > int[] rans = new int[elementNum];
> > > > for (int i = 0; i < elementNum; i++)
> > > > rans[i] = ran.nextInt(Integer.MAX_VALUE );
> > > > long start = System.currentTimeMillis();
> > > > for (int i = 0; i < elementNum; i++)
> > > > map.put(rans[i], "b");
> > > > System.out.println (System.currentTimeMillis() - start);
> > > > start = System.currentTimeMillis();
> > > > for (int i = 0; i < elementNum; i++)
> > > > for(int j = 0; j< times; j++){
> > > > map.get(rans[i]);
> > > > }
> > > > System.out.println(System.currentTimeMillis() - start);
> > > > }
> > > > }
> > >
> > > --
> > > This message is automatically generated by JIRA.
> > > -
> > > You can reply to this email to add a comment to the issue online.
> > >
> > >
> >
> >
> > --
> >
> > Best Regards!
> >
> > Jimmy, Jing Lv
> > China Software Development Lab, IBM
> >
>
>
>
> --
> Best regards,
> ---
> Sergey Kuksenko.
> Intel Enterprise Solutions Software Division.
>
--
Best Regards!
Jimmy, Jing Lv
China Software Development Lab, IBM
Re: Performance improvement of java.util.HashMap
Posted by Tim Ellison <t....@gmail.com>.
Sergey Kuksenko wrote:
> I wish to include myself into discussion and express some my thought
> in this area.
Great -- the more input the better!
> I am absolutely agree with the idea of using bitwise operations & (or
> power of two remainder) instead of % (arbirary remainder) because of
> power of two remainder is really faster and was proved by my tests
> and etc...
>
> First of all I wish to note that if HashMap works with user-defined
> HashCode it doesn't matter which reminder is used: power fo two (&)
> or prime(or arbitrary) number reminder (%). In case if user defined
> HashCode we can't predict hash and the hash can be suitable as for &
> and for %.
Right, I think we pretty much have to ignore the user defined hashCode()
since we have no insight into its characteristics, other than the
obvious ones like it being a 32-bit value.
> But prime number reminder has one disadavntages (except speed of
> operation). When HashMap uses prime number (or some irreglar) we get
> negative effect of unused part of memory page. Size of memory pages
> is power of two and it is better to fill it completely. Espesially it
> is visible on large hash maps. Unfortunately I can privide any
> numbers at the moment. Thus in my opinion power of two reminder gives
> boost in time of operation plus benefits from more natural memory
> usage (layouts etc.)
Good point, for the memory page occupancy of the contiguous
'elementData' array of map entries.
In a somewhat related thought, it may be worth experimenting with
pre-allocating a number of Entries, to get better memory locality for
the whole hash map, but I digress...
> As to default hashCode which is IdentityHashCode.
I don't know what object types are the most common for hashmap keys.
For example, if it turns out that keys are usually Strings then the
hashCode() values' characteristics would be different. But I agree that
we should do well for identityHashCode values since that probably
represents the biggest set of key types we want to accommodate.
> There are two ways here:
> 1. Add new hashing function (additional hashing) inside HashMap. As was
> suggested here.
> 2. Change IdentityHashCode implementation. There are no rules that
> IdentityHashCode should return exactly address of object. And last
> zero bits from IdentityHashCode (which caused by object alignment)
> can be removed inside IdentityHashCode. Other words - to add
> additional hashing inside IdentityHashCode.
There is no rule that identityHashCode should be the address, you are
right - but I think that is a common implementation. We would like the
class library code to work well on multiple-VM implementations.
> The first solution has one advantage - it can be done only in
> classlib. The second variant should be implemented in all VMs which
> are based on Harmony's classlib. But this way has other advantages -
> Well-formed IdentityHashCode will helps not only for HashMap, but for
> Hashtable, IdentityHashMap
Well we could use whatever technique we settle on in all our hashed
collections<g>
> and moreover for all hashing implemented by users.
how so? unless they query the object identityhashCode, which I think is
not usually the case when overriding hashCode().
> In the second variant we don't add rehashing function into HashMap.
> It is common practice when advanced Java developers tune their
> HashCode functions. If we add rehashing function into HashMap we may
> break their tuning, without knowledge of internal rehashing functions
> it is impossible to tune HashCode function.
I agree that only applying a very simple transformation would be
appropriate so as not to 'break' users' hash functions. Plus it has the
advantage of not taking a long time in our code<g>. That's why I had
suggested a simple rotate right operation (to help with the common
implementation of identityHashCode situation).
> From my opinion we should think about the last argument against adding
> rehashing into HashMap and move rehashing into VM.
So you would recommend using the key.hashCode() unmodified?
Regards,
Tim
Re: Performance improvement of java.util.HashMap (Was Re: [jira] Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by Sergey Kuksenko <se...@gmail.com>.
Hi All,
I wish to include myself into discussion and express some my thought in this
area.
I am absolutely agree with the idea of using bitwise operations & (or power
of two remainder) instead of % (arbirary remainder) because of power of two
remainder is really faster and was proved by my tests and etc...
First of all I wish to note that if HashMap works with user-defined HashCode
it doesn't matter which reminder is used: power fo two (&) or prime(or
arbitrary) number reminder (%). In case if user defined HashCode we can't
predict hash and the hash can be suitable as for & and for %.
But prime number reminder has one disadavntages (except speed of operation).
When HashMap uses prime number (or some irreglar) we get negative effect of
unused part of memory page. Size of memory pages is power of two and it is
better to fill it completely. Espesially it is visible on large hash maps.
Unfortunately I can privide any numbers at the moment.
Thus in my opinion power of two reminder gives boost in time of operation
plus benefits from more natural memory usage (layouts etc.)
As to default hashCode which is IdentityHashCode.
There are two ways here:
1. Add new hashing function (additional hashing) inside HashMap. As was
suggested here.
2. Change IdentityHashCode implementation. There are no rules that
IdentityHashCode should return exactly address of object. And last zero bits
from IdentityHashCode (which caused by object alignment) can be removed
inside IdentityHashCode. Other words - to add additional hashing inside
IdentityHashCode.
The first solution has one advantage - it can be done only in classlib. The
second variant should be implemented in all VMs which are based on Harmony's
classlib. But this way has other advantages - Well-formed IdentityHashCode
will helps not only for HashMap, but for Hashtable, IdentityHashMap and
moreover for all hashing implemented by users.
In the second variant we don't add rehashing function into HashMap. It is
common practice when advanced Java developers tune their HashCode functions.
If we add rehashing function into HashMap we may break their tuning, without
knowledge of internal rehashing functions it is impossible to tune HashCode
function.
>From my opinion we should think about the last argument against adding
rehashing into HashMap and move rehashing into VM.
On 6/27/07, Jimmy,Jing Lv <fi...@gmail.com> wrote:
>
> Hi,
>
> As currently focus on performance, I find this JIRA(4064) and do
> some investigation on it.
>
> The Performance improvement of java.util.HashMap is about two
> aspects: one is hash algorithm that make hashcode randomly distributed
> enough, just as Tim's fix/comments in Harmony-4064, the other is about
> to make hash algorithm itself perform fast enough. HashMap is so
> widely used so that both two aspects may be very important.
>
> I strongly agree with Tim that hash algorithm that make hashcode
> randomly distributed is very important, for HashMap.put(), get(), etc,
> depends on it and it should perform better if the hash algorithm can
> make it randomly distributed. On the other hand, the hash algorithm
> should perform very fast as every HashMap.put and get method call this
> hash algorithm, if it is slow itself, then its benfits on randomly
> distribution became meaningless.
>
> I do a lot of benchmark and micro-benchmarks, it shows that (a &
> b) is much faster than (a % b). And if b is Math.pow(2,n)-1, the two
> operations just get the same result. That's why if we choose
> "&(Math.pow(2,n)-1)" (here Math.pow(2,n) is the size of bucket of a
> hashmap)to replace "%", by this way we improve performance greatly at
> least 2% ~ 3% in some benchmarks . This shows if we avoid slow
> operation like mod(%), multiply(*), division(/) and so forth, we can
> get performance improvement.
>
> Yes, I do think to randomly distrubute the hashcode is very
> important and I suggest we can use other machnisms other than mod
> prime to make it happen. One thought is right-shift the hashcode and
> combine bits together (by AND or OR or Exclusive Or operation) into
> low order( e.g, (a & (a >> 8) ^ (a >> 16) | (a >> 24)) &
> (bucketSize-1), a small test on it shows that it does distributed more
> randomly, but it may be better algorithms. In this way the hashcode
> may be more random destributed and performs fast. And in this way we
> may keep a balance of a both fast and good hash algorithm.
>
> Any comments/suggestions? Thanks!
>
>
> 2007/6/6, Tim Ellison (JIRA) <ji...@apache.org>:
> >
> > [ https://issues.apache.org/jira/browse/HARMONY-4064?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12501905
> ]
> >
> > Tim Ellison commented on HARMONY-4064:
> > --------------------------------------
> >
> > Robert. You patch undoes the change I made to make the length of the
> elements array a prime number, so that it is now always a power of two. The
> problem is that identity hash codes are not randomly distributed, they
> typically reflect object address alignments which will be factors of two, so
> we don't get a good distribution across all the possible buckets.
> >
> > You can see the effect in this simple 'simulation':
> >
> > public class HashingTest {
> >
> > public static void main(String[] args) {
> > int numBuckets = 16;
> >
> > int[] distrib = new int[numBuckets];
> > for (int i = 0; i < distrib.length; i++) {
> > distrib[i] = 0;
> > }
> >
> > for (int i = 0; i < 1000; i++) {
> > int hashCode = new Object().hashCode();
> > int bucket = hashCode & (numBuckets - 1);
> > distrib[bucket] = distrib[bucket] + 1;
> > }
> >
> > System.out.println("Bucket\tList_length");
> > for (int i = 0; i < distrib.length; i++) {
> > System.out.println(i + "\t" + distrib[i]);
> > }
> > }
> > }
> >
> > I suggest that we have to ensure the elements array length is chosen
> more carefully, or that we modify the hashCodes to avoid these collisions.
> >
> > > [classlib][luni] Performance improvement of java.util.HashMap
> > > -------------------------------------------------------------
> > >
> > > Key: HARMONY-4064
> > > URL:
> https://issues.apache.org/jira/browse/HARMONY-4064
> > > Project: Harmony
> > > Issue Type: Improvement
> > > Components: Classlib
> > > Reporter: Robert Hu
> > > Assignee: Tim Ellison
> > > Attachments: HARMONY-4064.diff
> > >
> > >
> > > The performance of HashMap can be improved, the hash method is
> improved.
> > > By running the following test code, our HashMap can be improved from
> 110% time cost (compared by RI) to 90% time cost (compared by RI).
> > > public class TestHashMap {
> > > public static void main(String[] args) {
> > > Random ran = new Random();
> > > HashMap map = new HashMap();
> > > int elementNum = 500;
> > > int times = 10000;
> > > int[] rans = new int[elementNum];
> > > for (int i = 0; i < elementNum; i++)
> > > rans[i] = ran.nextInt(Integer.MAX_VALUE );
> > > long start = System.currentTimeMillis();
> > > for (int i = 0; i < elementNum; i++)
> > > map.put(rans[i], "b");
> > > System.out.println (System.currentTimeMillis() - start);
> > > start = System.currentTimeMillis();
> > > for (int i = 0; i < elementNum; i++)
> > > for(int j = 0; j< times; j++){
> > > map.get(rans[i]);
> > > }
> > > System.out.println(System.currentTimeMillis() - start);
> > > }
> > > }
> >
> > --
> > This message is automatically generated by JIRA.
> > -
> > You can reply to this email to add a comment to the issue online.
> >
> >
>
>
> --
>
> Best Regards!
>
> Jimmy, Jing Lv
> China Software Development Lab, IBM
>
--
Best regards,
---
Sergey Kuksenko.
Intel Enterprise Solutions Software Division.
Re: Performance improvement of java.util.HashMap (Was Re: [jira] Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by "Jimmy,Jing Lv" <fi...@gmail.com>.
Thanks so much Yuri !
But I'm a little concern before I click on these pages, I'm not sure
that we can touch that code/algorithm for Harmony development, is that
copyright-ed or patent-ed?
2007/6/27, Yuri Dolgov <do...@gmail.com>:
> Hi Jimmy,
> Here are couple of interesting links on hash functions implementation:
> http://burtleburtle.net/bob/hash/doobs.html
> http://www.azillionmonkeys.com/qed/hash.html
>
> In my point of view usage of shifts should give some benefit as in
> performance so in a distribution quality.
>
> Thanks,
> Yuri
>
>
>
> On 6/27/07, Jimmy,Jing Lv <fi...@gmail.com> wrote:
> >
> > Hi,
> >
> > As currently focus on performance, I find this JIRA(4064) and do
> > some investigation on it.
> >
> > The Performance improvement of java.util.HashMap is about two
> > aspects: one is hash algorithm that make hashcode randomly distributed
> > enough, just as Tim's fix/comments in Harmony-4064, the other is about
> > to make hash algorithm itself perform fast enough. HashMap is so
> > widely used so that both two aspects may be very important.
> >
> > I strongly agree with Tim that hash algorithm that make hashcode
> > randomly distributed is very important, for HashMap.put(), get(), etc,
> > depends on it and it should perform better if the hash algorithm can
> > make it randomly distributed. On the other hand, the hash algorithm
> > should perform very fast as every HashMap.put and get method call this
> > hash algorithm, if it is slow itself, then its benfits on randomly
> > distribution became meaningless.
> >
> > I do a lot of benchmark and micro-benchmarks, it shows that (a &
> > b) is much faster than (a % b). And if b is Math.pow(2,n)-1, the two
> > operations just get the same result. That's why if we choose
> > "&(Math.pow(2,n)-1)" (here Math.pow(2,n) is the size of bucket of a
> > hashmap)to replace "%", by this way we improve performance greatly at
> > least 2% ~ 3% in some benchmarks . This shows if we avoid slow
> > operation like mod(%), multiply(*), division(/) and so forth, we can
> > get performance improvement.
> >
> > Yes, I do think to randomly distrubute the hashcode is very
> > important and I suggest we can use other machnisms other than mod
> > prime to make it happen. One thought is right-shift the hashcode and
> > combine bits together (by AND or OR or Exclusive Or operation) into
> > low order(e.g, (a & (a >> 8) ^ (a >> 16) | (a >> 24)) &
> > (bucketSize-1), a small test on it shows that it does distributed more
> > randomly, but it may be better algorithms. In this way the hashcode
> > may be more random destributed and performs fast. And in this way we
> > may keep a balance of a both fast and good hash algorithm.
> >
> > Any comments/suggestions? Thanks!
> >
> >
> > 2007/6/6, Tim Ellison (JIRA) <ji...@apache.org>:
> > >
> > > [
> > https://issues.apache.org/jira/browse/HARMONY-4064?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12501905]
> > >
> > > Tim Ellison commented on HARMONY-4064:
> > > --------------------------------------
> > >
> > > Robert. You patch undoes the change I made to make the length of the
> > elements array a prime number, so that it is now always a power of two. The
> > problem is that identity hash codes are not randomly distributed, they
> > typically reflect object address alignments which will be factors of two, so
> > we don't get a good distribution across all the possible buckets.
> > >
> > > You can see the effect in this simple 'simulation':
> > >
> > > public class HashingTest {
> > >
> > > public static void main(String[] args) {
> > > int numBuckets = 16;
> > >
> > > int[] distrib = new int[numBuckets];
> > > for (int i = 0; i < distrib.length; i++) {
> > > distrib[i] = 0;
> > > }
> > >
> > > for (int i = 0; i < 1000; i++) {
> > > int hashCode = new Object().hashCode();
> > > int bucket = hashCode & (numBuckets - 1);
> > > distrib[bucket] = distrib[bucket] + 1;
> > > }
> > >
> > > System.out.println("Bucket\tList_length");
> > > for (int i = 0; i < distrib.length; i++) {
> > > System.out.println(i + "\t" + distrib[i]);
> > > }
> > > }
> > > }
> > >
> > > I suggest that we have to ensure the elements array length is chosen
> > more carefully, or that we modify the hashCodes to avoid these collisions.
> > >
> > > > [classlib][luni] Performance improvement of java.util.HashMap
> > > > -------------------------------------------------------------
> > > >
> > > > Key: HARMONY-4064
> > > > URL:
> > https://issues.apache.org/jira/browse/HARMONY-4064
> > > > Project: Harmony
> > > > Issue Type: Improvement
> > > > Components: Classlib
> > > > Reporter: Robert Hu
> > > > Assignee: Tim Ellison
> > > > Attachments: HARMONY-4064.diff
> > > >
> > > >
> > > > The performance of HashMap can be improved, the hash method is
> > improved.
> > > > By running the following test code, our HashMap can be improved from
> > 110% time cost (compared by RI) to 90% time cost (compared by RI).
> > > > public class TestHashMap {
> > > > public static void main(String[] args) {
> > > > Random ran = new Random();
> > > > HashMap map = new HashMap();
> > > > int elementNum = 500;
> > > > int times = 10000;
> > > > int[] rans = new int[elementNum];
> > > > for (int i = 0; i < elementNum; i++)
> > > > rans[i] = ran.nextInt(Integer.MAX_VALUE);
> > > > long start = System.currentTimeMillis();
> > > > for (int i = 0; i < elementNum; i++)
> > > > map.put(rans[i], "b");
> > > > System.out.println(System.currentTimeMillis() - start);
> > > > start = System.currentTimeMillis();
> > > > for (int i = 0; i < elementNum; i++)
> > > > for(int j = 0; j< times; j++){
> > > > map.get(rans[i]);
> > > > }
> > > > System.out.println(System.currentTimeMillis() - start);
> > > > }
> > > > }
> > >
> > > --
> > > This message is automatically generated by JIRA.
> > > -
> > > You can reply to this email to add a comment to the issue online.
> > >
> > >
> >
> >
> > --
> >
> > Best Regards!
> >
> > Jimmy, Jing Lv
> > China Software Development Lab, IBM
> >
>
--
Best Regards!
Jimmy, Jing Lv
China Software Development Lab, IBM
Re: Performance improvement of java.util.HashMap (Was Re: [jira] Commented: (HARMONY-4064) [classlib][luni] Performance improvement of java.util.HashMap)
Posted by Yuri Dolgov <do...@gmail.com>.
Hi Jimmy,
Here are couple of interesting links on hash functions implementation:
http://burtleburtle.net/bob/hash/doobs.html
http://www.azillionmonkeys.com/qed/hash.html
In my point of view usage of shifts should give some benefit as in
performance so in a distribution quality.
Thanks,
Yuri
On 6/27/07, Jimmy,Jing Lv <fi...@gmail.com> wrote:
>
> Hi,
>
> As currently focus on performance, I find this JIRA(4064) and do
> some investigation on it.
>
> The Performance improvement of java.util.HashMap is about two
> aspects: one is hash algorithm that make hashcode randomly distributed
> enough, just as Tim's fix/comments in Harmony-4064, the other is about
> to make hash algorithm itself perform fast enough. HashMap is so
> widely used so that both two aspects may be very important.
>
> I strongly agree with Tim that hash algorithm that make hashcode
> randomly distributed is very important, for HashMap.put(), get(), etc,
> depends on it and it should perform better if the hash algorithm can
> make it randomly distributed. On the other hand, the hash algorithm
> should perform very fast as every HashMap.put and get method call this
> hash algorithm, if it is slow itself, then its benfits on randomly
> distribution became meaningless.
>
> I do a lot of benchmark and micro-benchmarks, it shows that (a &
> b) is much faster than (a % b). And if b is Math.pow(2,n)-1, the two
> operations just get the same result. That's why if we choose
> "&(Math.pow(2,n)-1)" (here Math.pow(2,n) is the size of bucket of a
> hashmap)to replace "%", by this way we improve performance greatly at
> least 2% ~ 3% in some benchmarks . This shows if we avoid slow
> operation like mod(%), multiply(*), division(/) and so forth, we can
> get performance improvement.
>
> Yes, I do think to randomly distrubute the hashcode is very
> important and I suggest we can use other machnisms other than mod
> prime to make it happen. One thought is right-shift the hashcode and
> combine bits together (by AND or OR or Exclusive Or operation) into
> low order(e.g, (a & (a >> 8) ^ (a >> 16) | (a >> 24)) &
> (bucketSize-1), a small test on it shows that it does distributed more
> randomly, but it may be better algorithms. In this way the hashcode
> may be more random destributed and performs fast. And in this way we
> may keep a balance of a both fast and good hash algorithm.
>
> Any comments/suggestions? Thanks!
>
>
> 2007/6/6, Tim Ellison (JIRA) <ji...@apache.org>:
> >
> > [
> https://issues.apache.org/jira/browse/HARMONY-4064?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12501905]
> >
> > Tim Ellison commented on HARMONY-4064:
> > --------------------------------------
> >
> > Robert. You patch undoes the change I made to make the length of the
> elements array a prime number, so that it is now always a power of two. The
> problem is that identity hash codes are not randomly distributed, they
> typically reflect object address alignments which will be factors of two, so
> we don't get a good distribution across all the possible buckets.
> >
> > You can see the effect in this simple 'simulation':
> >
> > public class HashingTest {
> >
> > public static void main(String[] args) {
> > int numBuckets = 16;
> >
> > int[] distrib = new int[numBuckets];
> > for (int i = 0; i < distrib.length; i++) {
> > distrib[i] = 0;
> > }
> >
> > for (int i = 0; i < 1000; i++) {
> > int hashCode = new Object().hashCode();
> > int bucket = hashCode & (numBuckets - 1);
> > distrib[bucket] = distrib[bucket] + 1;
> > }
> >
> > System.out.println("Bucket\tList_length");
> > for (int i = 0; i < distrib.length; i++) {
> > System.out.println(i + "\t" + distrib[i]);
> > }
> > }
> > }
> >
> > I suggest that we have to ensure the elements array length is chosen
> more carefully, or that we modify the hashCodes to avoid these collisions.
> >
> > > [classlib][luni] Performance improvement of java.util.HashMap
> > > -------------------------------------------------------------
> > >
> > > Key: HARMONY-4064
> > > URL:
> https://issues.apache.org/jira/browse/HARMONY-4064
> > > Project: Harmony
> > > Issue Type: Improvement
> > > Components: Classlib
> > > Reporter: Robert Hu
> > > Assignee: Tim Ellison
> > > Attachments: HARMONY-4064.diff
> > >
> > >
> > > The performance of HashMap can be improved, the hash method is
> improved.
> > > By running the following test code, our HashMap can be improved from
> 110% time cost (compared by RI) to 90% time cost (compared by RI).
> > > public class TestHashMap {
> > > public static void main(String[] args) {
> > > Random ran = new Random();
> > > HashMap map = new HashMap();
> > > int elementNum = 500;
> > > int times = 10000;
> > > int[] rans = new int[elementNum];
> > > for (int i = 0; i < elementNum; i++)
> > > rans[i] = ran.nextInt(Integer.MAX_VALUE);
> > > long start = System.currentTimeMillis();
> > > for (int i = 0; i < elementNum; i++)
> > > map.put(rans[i], "b");
> > > System.out.println(System.currentTimeMillis() - start);
> > > start = System.currentTimeMillis();
> > > for (int i = 0; i < elementNum; i++)
> > > for(int j = 0; j< times; j++){
> > > map.get(rans[i]);
> > > }
> > > System.out.println(System.currentTimeMillis() - start);
> > > }
> > > }
> >
> > --
> > This message is automatically generated by JIRA.
> > -
> > You can reply to this email to add a comment to the issue online.
> >
> >
>
>
> --
>
> Best Regards!
>
> Jimmy, Jing Lv
> China Software Development Lab, IBM
>