Proposal: Better HashMap.resize() when memory is tight

[Martin Buchholz]

Hi Peter,

It's true that under low memory conditions your code would
allow execution to continue under some circumstances.
However, I'm not sure this would be an improvement to the JDK.
Recovery from OOME is fraught with hazards.  We do occasionally
try, but an application becomes much less reliable once OOMEs
start appearing.  Perhaps it's better to fail than to pretend
that the JDK has been bullet-proofed against OOME.
OOME recovery code is rarely executed and hard to test.
The new code would have to be maintained indefinitely,
making future maintenance just a little bit harder for
the maintainers.

If the hashmap is fully populated, most of the memory is tied
up in the Entry objects themselves, not in the table array.
Each Entry object should be about 5 words of memory, while
there's approximately one word used within the table array.
So I don't think we'll see anything close to the factor of
two max memory saving that we might expect.

I would prefer to see engineering work go into something
like auto-reduction of the table array when many elements
have been removed, but that's a hard problem.

Martin

Peter Arrenbrecht wrote:
> Hi all,
> 
> I recently thought about how to resize hashmaps. When looking at the
> JDK 6 source, I saw that java.util.HashMap always transfers old
> entries from the old table. When memory is tight, it might be better
> to first concatenate the entry lists into one big list, throw away the
> old table, allocate the new one, and then fill it from the
> concatenated list. So:
> 
> 	@Override
> 	void resize( int _newCapacity )
> 	{
> 		try {
> 			fastResize( _newCapacity ); // This would be the current resize code.
> 		}
> 		catch (OutOfMemoryError e) {
> 			tightResize( _newCapacity );
> 		}
> 	}
> 
> 	@SuppressWarnings( "unchecked" )
> 	private void tightResize( int newCapacity )
> 	{
> 		Entry head = joinLists();
> 		table = new Entry[ newCapacity ];
> 		threshold = (int) (newCapacity * loadFactor);
> 		transfer( head, table );
> 	}
> 
> 	@SuppressWarnings("unchecked")
> 	private Entry joinLists()
> 	{
> 		final Entry[] src = table;
> 		final int n = src.length;
> 		Entry head = null;
> 		int i = 0;
> 		while (i < n && null == head) {
> 			head = src[ i++ ];
> 		}
> 		Entry tail = head;
> 		assert i >= n || null != tail;
> 		while (i < n) {
> 			Entry e = src[ i++ ];
> 			if (null != e) {
> 				tail.next = e;
> 				do {
> 					tail = e;
> 					e = e.next;
> 				} while (null != e);
> 			}
> 		}
> 		return head;
> 	}
> 
> 	@SuppressWarnings("unchecked")
> 	private void transfer( Entry head, Entry[] tgt )
> 	{
> 		int n = capacity();
> 		while (head != null) {
> 			Entry e = head;
> 			head = head.next;
> 			int i = indexFor( e.hash, n );
> 			e.next = tgt[ i ];
> 			tgt[ i ] = e;
> 		}
> 	}
> 
> 
> What do you think?
> -peo
-------------- next part --------------
An embedded message was scrubbed...
From: Peter Arrenbrecht <peter.arrenbrecht at gmail.com>
Subject: Re: Proposal: Better HashMap.resize() when memory is tight
Date: Wed, 21 Nov 2007 16:51:28 +0100
Size: 10453
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20071121/19ab2972/AttachedMessage.mht>