optimize KlassInfoTable size to power of 2

[Andrew Haley]

My observation is that when “jmap histo” iterating objects , the object’s klass
is identified and then hash idx in KlassInfoTable’s buckets[] is calculated by mod
of _num_bucktes, which would issue a heavy instruction idiv on x86 platform. It
means for every object scanned, a idiv instruction is issued, which lag the performance espically when
there are large number of objects in heap.

I'm surprised that GCC uses idiv in this case: it has an optimization for
constant modulo which doesn't use division. There is sometimes an
advantage for using hash tables of prime size. Is it that the size of
the table is not a constant that GCC can see?

[臧琳]

Our preliminary measurement show the patch introduced about ~5% speed up
for jmap šChisto when iterate ~13GB committed heap. ( with šCXX:+UseG1GC šCXmx180g configured)

Just FYI.

Cheers,
Lin

From: ê°ÁÕ
Sent: Monday, December 10, 2018 2:24 PM
To: serviceability-***@openjdk.java.net
Subject: optimize KlassInfoTable size to power of 2

Dear All,
I am investigating JMap utility for large heap (~200GB) and found that
the current KlassInfoTable¡¯s _num_buckets size(20011) may not be optimal.
My observation is that when ¡°jmap histo¡± iterating objects , the object¡¯s klass
is identified and then hash idx in KlassInfoTable¡¯s buckets[] is calculated by mod
of _num_bucktes, which would issue a heavy instruction idiv on x86 platform. It
means for every object scanned, a idiv instruction is issued, which lag the performance espically when
there are large number of objects in heap. Hence if the _num_buckets can be changed to
a pow of 2, (e.g. 65536) the idiv can be replaced with a faster instruction such as shl (left bit shift),
And I have prepared a patch for this change.
My question is that why 20011 is used now? is there any special reason? And is there
any potential problem if I change the value to 65536, or 32768?
Thanks!

BRs,
Lin

[臧琳]

Hi Andrew,
Thanks for your comments.
I think the reason that idiv is issued is that the constant _num_buckets is not used
directly for the hash idx calculation. It is the _size which is initialized to be _num_buckets.
And I am also puzzling about why the _size is necessary since there is no modification on
it after initialization.
I can try use _num_buckets directly to calculate idx and see what is the instruction
issued, and also do some measurement for comparing.
Would you like to give more details about the benefit of using hash table with prime
size? Thanks!

Cheers,
Lin


-----Original Message-----
From: Andrew Haley [mailto:***@redhat.com]
Sent: Monday, December 10, 2018 8:30 PM
To: 臧琳 <***@jd.com>; serviceability-***@openjdk.java.net
Subject: Re: optimize KlassInfoTable size to power of 2

My observation is that when “jmap histo” iterating objects , the object’s klass
is identified and then hash idx in KlassInfoTable’s buckets[] is
calculated by mod of _num_bucktes, which would issue a heavy
instruction idiv on x86 platform. It means for every object scanned, a
idiv instruction is issued, which lag the performance espically when there are large number of objects in heap.

I'm surprised that GCC uses idiv in this case: it has an optimization for constant modulo which doesn't use division. There is sometimes an advantage for using hash tables of prime size. Is it that the size of the table is not a constant that GCC can see?

[Andrew Haley]

Post by 臧琳
Would you like to give more details about the benefit of using hash table with prime
size?

Really? OK.

Imagine that your hash table is an exact power of two in size. Reducing the
index mod any power of two means using only the lower n bits of the hash
value.