One class for both building and querying Immutables

[Russ Abbott]

I'm been using Guava for only a couple of week. In that time I've come to appreciate it a lot.  I hope it's ok if I make a suggestion. One slight irritation is that it takes two Classes, two variables, and two objects to build many Immutables.  Unless one can provide the complete contents of the Immutable when it is first created, you need both a Builder and the Immutable itself. Even though that's a minor inconvenience, I find that when I'm in a rush I don't want to think about both. 

Instead of

 ImmutableSet.Builder<T> builder = ImmutableSet.builder();

 ...

 buillder.add(...)

 ...

 ImmutableSet set = builder.build();

 ...

 if (set.contains(...)) ...

How about a single class with two modes of operation.

  ImmutableSet<X> set = ImmutableSet.of();

   ...

  set.add(...);

  ...

  set.build();

  ...

  if (set.contains( )) ...

The idea is that Immutables would in general be created in a build mode, during which only add or put operations are valid. After a build( ) operation, the object would be in a query mode during which add, put, etc. are not valid.

Although this wouldn't save significant typing, it would eliminate the .Builder classes, variables, and objects, which seem klunky to me. Somehow it feels nicer to be able to switch a single object from its build mode to its query mode rather than having to deal with two separate objects. 

One disadvantage of such a scheme is that the compiler wouldn't be able to determine when the various operations are valid unless it traced through the code to find the build() operation. An operation attempted when in the wrong phase wouldn't fail until runtime. I think it's take that trade-off.

[Tim Peierls]

No, no, no! That would rob ImmutableXxx of all of its wonderfulness. When something returns an ImmutableSet, I want to be able to trust that it will never, ever change on me. I don't want to have to test if build() has been called.

But there are many ways to obtain ImmutableXxx instances that don't involve a Builder. For small ImmutableXxx, you can provide the elements directly to the static of() method. If you have an existing Iterable, you can use static copyOf(). And there are methods from other classes that produce ImmutableXxx. FluentIterable has toImmutable{List/Set/SortedSet}.

--tim

--
guava-...@googlegroups.com
Project site: http://guava-libraries.googlecode.com
This group: http://groups.google.com/group/guava-discuss
 
This list is for general discussion.
To report an issue: http://code.google.com/p/guava-libraries/issues/entry
To get help: http://stackoverflow.com/questions/ask (use the tag "guava")

[Colin Decker]

Agreed with Tim. In general, I think classes where a single instance can switch between multiple modes that have significantly different behavior are a bad idea and make code more difficult to understand. The clean split between the mutable builder type and the immutable type solves that nicely.

Also, as I understand it the Builders are primarily there so that you can do stuff like this:

public static final ImmutableSet<String> SOME_SET = ImmutableSet.<String>builder()

    .add("FOO", "BAR")

    .addAll(someOtherStrings())

    .build();

Or just for building an immutable collection that's too big for any of the of(...) methods in one go like that. In other situations, if you want your builder to be a Collection so you can do more complex building, it would work just as well to create a HashSet and populate that and then use ImmutableSet.copyOf to create the immutable copy.

-- 

Colin

[Louis Wasserman]

Unless one can provide the complete contents of the Immutable when it is first created, you need both a Builder and the Immutable itself. 

Yep.  And for almost all interesting cases, you can provide its complete contents when it's created.

 

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[Osvaldo Doederlein]

Considering that the Builder objects are almost always local to a single method, and their structure and methods typically simple, I'd expect current VMs (at "server"/ C2 opt level) to stack-allocate the builders trough escape analysis. This should give use the best of two worlds, at least in hot code that gets full optimization.

But there's a more important problem: whether the final step of building--the handoff of builder data to the product collection--requires some extra data copy.  In ImmutableMap.Builder.build() for example, we can see this (for >1 elements):

          Entry<?, ?>[] entryArray

              = entries.toArray(new Entry<?, ?>[entries.size()]);

          return new RegularImmutableMap<K, V>(entryArray);

This is one example of inefficiency that could be avoided: the RegularImmutableMap(Entry...) constructor seems to be optimized for the various of(...) methods that pass a (varargs-implicit) array, but this is the wrong tradeoff, these methods will pass only a handful of objects so even if there's data copy the cost will be trivial.  The common-case of construction from the Builder with >1 elements, however, is the case we should optimize because somebody can pass a million objects, and copying that will have a huge cost.   So it seems that we could just change this constructor to receive a List. The code above would be replaced simply by: return new RegularImmutableMap<K, V>(entries).

And the funny thing is, there's no tradeoff: the of(...) methods won't be penalized, because they don't need to create a temporary array. Example:

  public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {

    ArrayList<K, V> list = new ArrayList<K, V>(3);

    list.add(entryOf(k1, v1));

    list.add(entryOf(k2, v2));

    list.add(entryOf(k3, v3));

    return new RegularImmutableMap<K, V>(list);

  }

A+

Osvaldo

[Louis Wasserman]

The overhead involved in the construction pipelines has been on my mind lately, and there are a few changes in progress.

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[eric.giese]

> Considering that the Builder objects are almost always local to a single
method, and their structure and methods typically simple, I'd expect
current VMs (at "server"/ C2 opt level) to stack-allocate the builders
trough escape analysis. This should give use the best of two worlds,
at
least in hot code that gets full optimization.

Escape analysis works like this:
http://docs.oracle.com/javase/7/docs/technotes/guides/vm/performance-enhancements-7.html#escapeAnalysis
It won't allocate objects on the stack, but it might skip unnecessary
instantiations.

However, this will never really work for builders: The builder
instance might be optimized away, but I doubt the jvm will ever be
able to remove non-fixed array or unlimited linked allocations.

Escape analysis is very useful to eliminate synchronized and to allow
for a more carefree instantiations of lightweigt wrappers and such.
Especially for scala, whose implicit conversions will likely always be
optimized away. :-)

[Raymond Rishty]

I would strongly recommend against a constructor that simply receives
a list without copying. Copying is the sine qua non here for the
immutability guarantee

[Osvaldo Doederlein]

On Thu, Apr 26, 2012 at 7:16 AM, Raymond Rishty <raymond...@gmail.com> wrote:

I would strongly recommend against a constructor that simply receives
a list without copying. Copying is the sine qua non here for the
immutability guarantee

1) These constructors are not public; classes like ImmutableMap.RegularImmutableMap are package-protected so there's no need for defensive copying for any reason.

2) Check the source code for that constructor: all it does with the input array (or list as I suggest) is iterating it in order to create the ImmutableEntry objects. This already has the effect of copying all the input, so there's no reason to do that twice.

[Emily Soldal]

-1, seems like a bad idea to me. 

[Osvaldo Doederlein]

On Thu, Apr 26, 2012 at 2:14 AM, eric.giese <eric...@googlemail.com> wrote:

> Considering that the Builder objects are almost always local to a single
method, and their structure and methods typically simple, I'd expect
current VMs (at "server"/ C2 opt level) to stack-allocate the builders
trough escape analysis. This should give use the best of two worlds,
at least in hot code that gets full optimization.

Escape analysis works like this:
http://docs.oracle.com/javase/7/docs/technotes/guides/vm/performance-enhancements-7.html#escapeAnalysis
It won't allocate objects on the stack, but it might skip unnecessary
instantiations.

The distinction is minor. HotSpot performs scalar displacement, i.e. instead of allocating some object X in the heap, it creates stack variables equivalent to X's fields (or at least the fields necessary at the use site), so [inlined] X's methods will operate on those stack vars.  The major difference between this and "stack allocation of X" is that you can't store references from heap fields into X, or pass X to non-inlined methods or JNI code that expects its regular memory layout and heap lifecycle.

 

However, this will never really work for builders: The builder
instance might be optimized away, but I doubt the jvm will ever be
able to remove non-fixed array or unlimited linked allocations.

True that it doesn't work now; but certainly not true that it can never work. Right now the JVM is not able to fully deconstruct builders--in part because these have some overhead that could be eliminated: indirection from ArrayList backing store; defensive copy to create the final immutable list that could be avoided with a hand-off protocol. I quickly experimented optimizing these things out, and the result was a speedup of a simple benchmark from 550ms to 400ms, which is very good (real-world perf will be better because the bench code is memory-bound). Still HotSpot was not able to drop all heap allocation for a code pattern like: "ImmutableList.<Integer>builder().add(0).add(0).add(0).add(0).add(0).build().get(0)". I expect that to be around the corner though, at least if the Builder implementation helps. For one thing, JRockit was way ahead of HotSpot in stack allocation, and they are porting that good stuff into HotSpot.

A+

Osvaldo

 

Escape analysis is very useful to eliminate synchronized and to allow
for a more carefree instantiations of lightweigt wrappers and such.
Especially for scala, whose implicit conversions will likely always be
optimized away. :-)

[Louis Wasserman]

True that it doesn't work now; but certainly not true that it can never work. Right now the JVM is not able to fully deconstruct builders--in part because these have some overhead that could be eliminated: indirection from ArrayList backing store; defensive copy to create the final immutable list that could be avoided with a hand-off protocol. 

There's always going to be some copying in the build() methods.  Two reasons:

1. The array backing the builder usually won't match the exact size of the result, and we don't want or need that extra space. 
2. Builders can be reused.

I'd be curious to see the change you were experimenting with, though.

[Osvaldo Doederlein]

On Thu, Apr 26, 2012 at 12:54 PM, Louis Wasserman <wasserm...@gmail.com> wrote:

True that it doesn't work now; but certainly not true that it can never work. Right now the JVM is not able to fully deconstruct builders--in part because these have some overhead that could be eliminated: indirection from ArrayList backing store; defensive copy to create the final immutable list that could be avoided with a hand-off protocol. 

There's always going to be some copying in the build() methods.  Two reasons:

1. The array backing the builder usually won't match the exact size of the result, and we don't want or need that extra space. 

This is true in the general case for common collections, but not for immutable collections. Immutability implies having all the input data at construction time; so you usually know the amount of data. And if you know that, then you can preallocate the builder with the exact space it needs for those elements.  Of course there's always the odd case where this preallocation is not possible or inefficient, e.g. when consuming an InputStream, or when populating the builder with a complex algorithm. But these are rare exceptions, at least my experience with Guava is that I can preallocate >95% of all immutable collections.

Also worth notice, slack space is only a problem for long-lived collections, and not all immutable collections are long-lived. If you check for example the Java code produced by protoc (protocol buffer compiler), it doesn't care to trim the collections used by its builders; the final immutable message classes will often have unused capacity. But nobody cares because protobuf objects are typically used for persistence or remoting, so their lifecycle is usually requiest/transaction-scoped at best. Making an extra data copy to prevent temporary use of extra memory for a couple milliseconds doesn't make any sense.  Even if we want to be conservative and not make the API more complex with extra methods like a build(boolean trim), the building logic could easily copy the backing array only conditionally, when used size != capacity.

1. Builders can be reused.

I'd be curious to see the change you were experimenting with, though.

Code for the reuse issue (omitting special cases for empty and singleton result). Had zero impact on my microbenchmark:

    private E[] contents;

    private int size;

    private boolean shared;

    private void ensureCapacity(int minCapacity) {

      if (minCapacity > contents.length || shared) {

          int newCapacity = (contents.length * 3)/2 + 1;

          if (newCapacity < minCapacity) newCapacity = minCapacity;

          contents = Arrays.copyOf(contents, newCapacity);

          shared = false;

      }

    }

    @Override public ImmutableList<E> build() {

      shared = true;

      return new RegularImmutableList<E>(contents, 0, size);

    }

All mutating methods need to call an ensureCapacity() method, which potentially grows the backing array. This results from implementing my own backing array instead of using an ArrayList.  So now I can take further advantage of that, and use the same method to also checks for buffer ownership; an extra variable tells if the backing array was handed off to an output collection, so any further update will automatically clone the array even if there's no need of extra capacity.  For the last ounce of perf, the shared variable can be avoided (just set size = -size, which costs using Math.abs() in a few places).  As a bonus, if a reused builder has build() called without any update since the last build(), the exact same backing array will be shared among all product collections, which is nice although real-world need should be rare.

If the build() method is further enhanced so it only copies the buffer when length != size (to avoid slack), then if this happens the shared flag doesn't need to be set to true, as the copy means we didn't share the buffer. This means no regression for the pessimist case of building without precise preallocation. Special cases for empty output or single-element output, which benefit from specialized result classes, won't set shared=true either.

A+

Osvaldo

[Louis Wasserman]

1. The array backing the builder usually won't match the exact size of the result, and we don't want or need that extra space. 

This is true in the general case for common collections, but not for immutable collections. Immutability implies having all the input data at construction time; so you usually know the amount of data. And if you know that, then you can preallocate the builder with the exact space it needs for those elements.  Of course there's always the odd case where this preallocation is not possible or inefficient, e.g. when consuming an InputStream, or when populating the builder with a complex algorithm. But these are rare exceptions, at least my experience with Guava is that I can preallocate >95% of all immutable collections.

I'm not sure we're talking about the same thing.  Builders don't know how many elements they'll have when build() gets called.  Their internal arrays have to have room for added elements.

 

Also worth notice, slack space is only a problem for long-lived collections, and not all immutable collections are long-lived. If you check for example the Java code produced by protoc (protocol buffer compiler), it doesn't care to trim the collections used by its builders; the final immutable message classes will often have unused capacity. But nobody cares because protobuf objects are typically used for persistence or remoting, so their lifecycle is usually requiest/transaction-scoped at best. Making an extra data copy to prevent temporary use of extra memory for a couple milliseconds doesn't make any sense.  

 

Minimizing memory usage for immutable collections is unquestionably a priority for us.  Even if they're not necessarily long-lived, they're used extremely widely across so many different services.  Indeed, I think we're inclined to pay the price at construction time of the additional copy, in exchange for those memory savings.

 

Even if we want to be conservative and not make the API more complex with extra methods like a build(boolean trim), the building logic could easily copy the backing array only conditionally, when used size != capacity.

But that said, builders can be reused.  Just because build() gets called once doesn't mean that more elements won't be added and build() won't be called again.

Additionally, the case that the backing array has exactly the right size is relatively rare, generally speaking.

[Tim Peierls]

On Thu, Apr 26, 2012 at 1:56 PM, Osvaldo Doederlein <opi...@google.com> wrote:

1. The array backing the builder usually won't match the exact size of the result, and we don't want or need that extra space. 

This is true in the general case for common collections, but not for immutable collections. Immutability implies having all the input data at construction time; so you usually know the amount of data. And if you know that, then you can preallocate the builder with the exact space it needs for those elements.  Of course there's always the odd case where this preallocation is not possible or inefficient, e.g. when consuming an InputStream, or when populating the builder with a complex algorithm. But these are rare exceptions, at least my experience with Guava is that I can preallocate >95% of all immutable collections.

It's precisely those cases for which I don't know the exact size of the collection in advance that I use Builders. It's not rare at all for me.

 

Also worth notice, slack space is only a problem for long-lived collections,

I'm not sure about this. If I have a Cache<String, ImmutableList<Foo>> with lots of turnover and average 25% slack, that could still be a lot of wasted space. 

 

and not all immutable collections are long-lived.

One of the most common uses I have for immutable maps is to hold long-lived indexes that are initialized from some stream (whose size I can't predict). I'm happy for a Builder to over-allocate during initialization, but I don't want that over-allocation to last past the call to build().

--tim

[Louis Wasserman]

One of the most common uses I have for immutable maps is to hold long-lived indexes that are initialized from some stream (whose size I can't predict). I'm happy for a Builder to over-allocate during initialization, but I don't want that over-allocation to last past the call to build().

 

Agreed.  A huge part of why I like the immutable collections is precisely because they reduce memory consumption to the bare minimum, without using any extra "slack space" for elements that might be added later -- because elements won't be added later.

Honestly, I'm generally inclined to pay increased up-front construction costs in exchange for reduced memory usage and fast query operations, as far as the immutable collections are concerned.  Yes, it can be improved.  Yes, we are improving it.  But I don't think added long-term memory usage is worth reduction in construction costs.

[Osvaldo Doederlein]

On Thu, Apr 26, 2012 at 2:19 PM, Louis Wasserman <wasserm...@gmail.com> wrote:

1. The array backing the builder usually won't match the exact size of the result, and we don't want or need that extra space. 

This is true in the general case for common collections, but not for immutable collections. Immutability implies having all the input data at construction time; so you usually know the amount of data. And if you know that, then you can preallocate the builder with the exact space it needs for those elements.  Of course there's always the odd case where this preallocation is not possible or inefficient, e.g. when consuming an InputStream, or when populating the builder with a complex algorithm. But these are rare exceptions, at least my experience with Guava is that I can preallocate >95% of all immutable collections.

I'm not sure we're talking about the same thing.  Builders don't know how many elements they'll have when build() gets called.  Their internal arrays have to have room for added elements.

I never meant that the builder would guess that automatically. What I need is simple, just give me a new method ImmutableMap.builder(int initialCapacity), and I will provide the number of elements when I know it.  This is a standard feature in Java SE's collections, so it's surprising that I don't have it in Guava (even with mitigations like the many factory methods like of(...) that do the correct preallocation).

 

 

Also worth notice, slack space is only a problem for long-lived collections, and not all immutable collections are long-lived. If you check for example the Java code produced by protoc (protocol buffer compiler), it doesn't care to trim the collections used by its builders; the final immutable message classes will often have unused capacity. But nobody cares because protobuf objects are typically used for persistence or remoting, so their lifecycle is usually requiest/transaction-scoped at best. Making an extra data copy to prevent temporary use of extra memory for a couple milliseconds doesn't make any sense.  

 

Minimizing memory usage for immutable collections is unquestionably a priority for us.  Even if they're not necessarily long-lived, they're used extremely widely across so many different services.  Indeed, I think we're inclined to pay the price at construction time of the additional copy, in exchange for those memory savings.

I agree with this tradeoff; was just trying to explore the design space. But the tradeoff to favor long-lived collections doesn't need to be extreme, I see no reason to not provide a builder(int) factory like suggested above. With respect to API simplicity, the current API already has 8 factories - build(), the six overloads of of(...), and copyOf() - seven of these to serve the special cases of very small collections or exact copy from an existing collection; so I don't think a ninth factory is a big deal even in terms of API footprint, even if its utility may be relatively rare.

Even if it's rare, when I need it, it's potentially a big deal and there is no workaround. I have for example a large stream of data (e.g. a file, or HTTP request etc.) with a million records that I need to import to an immutable collection, even if this stream has a header with the row count, I still have to pay two costs: (1) several reallocations of an internal buffer that starts with size 10, (2) buffer copy at build().  Total overhead is O(2*N), already considering the amortized reallocation of the internal ArrayList. These copying costs could be reduced in half to only O(N) if you only add the builder(int) factory, or to zero if you also implement non-copy handoff at build().

 

 

Even if we want to be conservative and not make the API more complex with extra methods like a build(boolean trim), the building logic could easily copy the backing array only conditionally, when used size != capacity.

But that said, builders can be reused.  Just because build() gets called once doesn't mean that more elements won't be added and build() won't be called again.

Additionally, the case that the backing array has exactly the right size is relatively rare, generally speaking.

It's a 100% hit when I know how many elements I will add beforehand so I can use the builder(int) constructor  ;-)

A+

Osvaldo

[Osvaldo Doederlein]

On Thu, Apr 26, 2012 at 2:20 PM, Tim Peierls <t...@peierls.net> wrote:

On Thu, Apr 26, 2012 at 1:56 PM, Osvaldo Doederlein <opi...@google.com> wrote:

1. The array backing the builder usually won't match the exact size of the result, and we don't want or need that extra space. 

This is true in the general case for common collections, but not for immutable collections. Immutability implies having all the input data at construction time; so you usually know the amount of data. And if you know that, then you can preallocate the builder with the exact space it needs for those elements.  Of course there's always the odd case where this preallocation is not possible or inefficient, e.g. when consuming an InputStream, or when populating the builder with a complex algorithm. But these are rare exceptions, at least my experience with Guava is that I can preallocate >95% of all immutable collections.

It's precisely those cases for which I don't know the exact size of the collection in advance that I use Builders. It's not rare at all for me.

YMMV, I also have these cases, but you can have the opposite case too.  For example I have a collection A and I need to build an immutable collection B with the same size as A but distinct elements, or maybe just copy a subset of A's elements.  Sounds like great candidates for methods like transform() or filter(), but sometimes--especially for long-lived collections!--I don't want to produce a lazy collection that will forever hold references for input data that I won't need anymore; or pay the cost of executing a filter/transform function at each access, when this access may be repeated over and over for the same elements.

  

One of the most common uses I have for immutable maps is to hold long-lived indexes that are initialized from some stream (whose size I can't predict). I'm happy for a Builder to over-allocate during initialization, but I don't want that over-allocation to last past the call to build().

I'm not disputing anybody's experiences or statistics; for sure many code bases wouldn't benefit from the optimizations I am suggesting. I agree that no regression to the performance of current usage should happen (see my previous reply), and my position is that we can support an important optimization of a new scenario - the use of Builders to create immutable collections off a dataset of known size - without any regression or significant tradeoff (that is, other than some coding). This may not be a common need for many apps, but it would be unfair to state that it's an incredibly contrived thing. The existence of six "of(...)" methods to optimally support collections with size 0-5, is already a concession to this exact scenario, except that it's not general enough, with six elements or more (or with each element added by a loop iteration) I'm out of luck.

A+

Osvaldo

 

[Louis Wasserman]

In that case, let's move this discussion to the appropriate place: http://code.google.com/p/guava-libraries/issues/detail?id=196.

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[Osvaldo Doederlein]

Thanks, didn't notice that issue, I guess the OP didn't either. So I posted some summary comments there, and also put some crappy code where my mouth is.

A+

Osvaldo