RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees (original) (raw)
Paul Sandoz paul.sandoz at oracle.com
Tue Jun 4 07:56:50 UTC 2013
- Previous message: RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees
- Next message: hg: jdk8/tl/langtools: 8010737: javac, known parameter's names should be copied to automatically generated constructors for inner classes
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
I forgot to say please don't let this hold up getting the patch into TL. I think it more important to get the code in then iterate on it.
Paul.
On Jun 4, 2013, at 9:45 AM, Paul Sandoz <paul.sandoz at oracle.com> wrote:
Hi,
On Jun 4, 2013, at 1:34 AM, Brent Christian <brent.christian at oracle.com> wrote:
Hi, Paul
If a HashMap is created via serialization or clone(), we don't check if the table needs resizing when adding entries, but still need to check if a bin should be converted to a TreeBin. In this case, putForCreate() calls createEntry() directly, instead of addEntry(). But putForCreate calculates "checkIfNeedTree": 1161 if (table[i] instanceof Entry) { 1162 int listSize = 0; 1163 Entry<K,V> e = (Entry<K,V>) table[i]; 1164 for (; e != null; e = (Entry<K,V>)e.next) { 1165 Object k; 1166 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 1167 e.value = value; 1168 return; 1169 } 1170 listSize++; 1171 } 1172 // Didn't find, fall through to createEntry(). 1173 // Check for conversion to TreeBin done via createEntry(). 1174 checkIfNeedTree = listSize >= TreeBin.TREETHRESHOLD; 1175 } else if (table[i] != null) { ... 1186 1187 createEntry(hash, key, value, i, checkIfNeedTree); 1188 } So the call to createEntry is just recalculating the same "listSize" value: 2232 void createEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) { ... 2239 if (checkIfNeedTree) { 2240 int listSize = 0; 2241 for (e = (Entry<K,V>) table[bucketIndex]; e != null; e = (Entry<K,V>)e.next) { 2242 listSize++; 2243 if (listSize >= TreeBin.TREETHRESHOLD) { // Convert to TreeBin 2244 if (comparableClassFor(key) != null) { 2245 TreeBin t = new TreeBin(); 2246 t.populate((Entry)table[bucketIndex]); 2247 table[bucketIndex] = t; 2248 } 2249 break; 2250 } 2251 } 2252 } Paul. Thanks, -Brent On 6/3/13 12:56 AM, Paul Sandoz wrote: Hi Brent,
A minor thing: take it or leave it :-) In HashMap: 2207 void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) { 2208 // assert key != null; 2209 if ((size >= threshold) && (null != table[bucketIndex])) { 2210 resize(2 * table.length); 2211 hash = hash(key); 2212 bucketIndex = indexFor(hash, table.length); 2213 } 2214 createEntry(hash, key, value, bucketIndex, checkIfNeedTree); 2215 } You could re-verify the bucket size if the table is resized rather than in createEntry, since that AFAICT is the only case where conditions after the call to addEntry might change. Pau.
- Previous message: RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees
- Next message: hg: jdk8/tl/langtools: 8010737: javac, known parameter's names should be copied to automatically generated constructors for inner classes
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]