[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [really patch] Re: HashMap putAll/putAllInternal bug
From: |
Eric Blake |
Subject: |
Re: [really patch] Re: HashMap putAll/putAllInternal bug |
Date: |
Thu, 16 Oct 2003 06:42:35 -0600 |
User-agent: |
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 |
Here's an implementation idea that might work for an accurate size() for your
case - maintain a single combined hash map which contains modified elements,
with the submaps being views into the giant map, rather than maintaining the
two submaps and having the combined map be a view.
Instead of key->value, you would have key->valueWrapper, where valueWrapper is
something like:
class valueWrapper {
private static final Object UNUSED = new Object();
Object front; // UNUSED if not in front
Object back; // UNUSED if not in back
}
The big map is maintains all three maps with independent size counts for the
three views, and the small maps would just need to be custom implementations
of AbstractMap that wrap the big map to provide the appropriate view,
modifying their particular size count as appropriate.
Of course, having the small maps as wrappers of the big adds another layer of
indirection, which may affect your performance, but at least size() would be
O(1) for all three maps.
Stuart Ballard wrote:
David Holmes wrote:
Sure, I can calculate the size. The problem is that doing so requires a
full iteration over the elements of both sets: you can't just sum the
sizes, because you have to correctly account for elements that are in
both sets.
That makes this "optimization" of just looping size() times actually a
pessimization, because you have to iterate over the elements twice
instead of once. I didn't provide a correct implementation of size() for
exactly this reason: I was afraid that it would get called a lot on the
assumption that it's fast, when it's not.
As for why I need this implementation: it's being used for a language
interpreter and provides an implementation of nested scoping of
variables. Performance is important because it gets used a LOT. I wanted
to make sure that creating a new scope was cheap and didn't affect the
parent scope (it does caching to make sure that gets are cheap too). The
reasons why both the front and back scope need to be able to change
directly are complicated but (as far as I've found so far) unavoidable.
--
Someday, I might put a cute statement here.
Eric Blake address@hidden
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, (continued)
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, Bryce McKinlay, 2003/10/09
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, Stuart Ballard, 2003/10/10
- RE: [really patch] Re: HashMap putAll/putAllInternal bug, David Holmes, 2003/10/12
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, Stephen Crawley, 2003/10/12
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, Stuart Ballard, 2003/10/13
- RE: [really patch] Re: HashMap putAll/putAllInternal bug, David Holmes, 2003/10/13
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, Eric Blake, 2003/10/16
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, Stuart Ballard, 2003/10/22
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, Stuart Ballard, 2003/10/27
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, Stuart Ballard, 2003/10/13
- Re: [really patch] Re: HashMap putAll/putAllInternal bug,
Eric Blake <=
- Re: [really patch] Re: HashMap putAll/putAllInternal bug, Bryce McKinlay, 2003/10/13