8:42 a.m.
Manik Surtani wrote:
On 5 Aug 2008, at 01:31, Jason T. Greene wrote:
>
> Manik Surtani wrote:
>> Guys,
>> I have created 3 new collection impls in trunk - ImmutableListCopy,
>> ImmutableSetCopy and ImmutableMapCopy. I have also ported the first
>> 2 to branch 2.2.x (the reason why I didnt port the third is because
>> the MapCopy which it replaces can get serialized and I don't want to
>> break binary compat).
>
> I took a look at adjusting these to be more efficient with the
> FastCopyHashMap. After doing some analysis and sanity benchmarks, I
> have determined that we should switch to unmodifiableXXX(obj.clone()
> or copy constructor) in all cases, for the following reasons:
>
> 1. There is no performance advantage with lists.
Agreed, this part was just convenience and perhaps removing a little bit
of superfluous object instantiation.
> 2. While the construction time in the Map and Set variants is faster,
> since it doesn't use hashing, it sacrifices way too much (O(n) lookup
> times). I did verify that the performance difference will be the same
> with just about every map implementation, since it's mostly allocation
> that is being measured here.
These were originally optimised for iteration only, but I expected
lookups to be a problem - hence my comment below.
> 3. It prevents the copy optimization in FastCopyHashMap, so removing
> usage of ImmutableMapCopy will improve copy performance of anything
> using FastCopyHashMap.
Thats what I suspected, and hence my thoughts on extending
FastCopyHashMap to an ImmutableFastCopyHashMap - so we have fast
construction, decent lookup times, immutability as well as reduce
unnecessary object construction/wrapping.
I measured this, and there is *no difference* between FastCopyHashMap
and HashMap when it comes to copying a different map. So all a
ImmutableFastCopyHashMap would do, is save the creation of the
unmodifiableXXX wrapper, which also ends up not making a difference (see
below).
> 4. The construction of the immutable wrapper is barely noticeable, and
> it's done per call, so the value is likely temporary.
Depends. This does happen in many different places, for different reasons:
- retrieval of collections from Node or Cache - which means the
reference goes into userland and may not be temporary
- used to pass data values into cache listeners. Again, may not be
temporary.
- Other internal uses are likely to be temporary though, such as
retrieving of invocation or transaction locks. These *may* not be
immutable if code written around it is careful, but for the sake of
correctness and thoroughness I have made these immutable.
What I meant was that the Collections.unmodifiableXXX object is very
short lived, so doesn't impact our memory footprint much. It also made
practically no difference when measuring the construction time.
> Also I noticed that we have some duplicate copying going on. For
> example , CacheInvocationDelegate copies a set that is constructed by
> the command, per call.
It makes sense for CID to provide a wrapIfNecessary transformation,
which only defensively copies/wraps the collection to be returned if it
has not already been wrapped/copied elsewhere in the chain, e.g., in the
command.
>
>
> What I would like to do, provided everyone is ok with this, is switch
> this code to static factory methods like so:
>
> Immutables.immutableCopy(Map map);
> Immutables.immutableCopy(List list);
> Immutables.immutableCopy(Set set);
>
> These will then just call clone and Collections.unmodifiableXXX as
> appropriate. We can then add optimizations later if they become
> available.
Would these be more generic, to suit any collection implementation?
Remember that not all Maps, for example, implement Cloneable or have a
copy constructor. And wrapping any Map passed in as a FastCopyHashMap
may break correctness, for example, if a SortedMap were passed in.
Right, they would use instanceof to check all the known map types as a
fast-path optimization. After that it would check for cloneable, and use
reflection to invoke clone. It would then look for a copy constructor,
and failing that it would then create a different collection type. We
could for example, in the case of a non-copyable SortedMap, use a
TreeMap, and order is maintained.
-Jason
--
Jason T. Greene
JBoss, a division of Red Hat