Adds FixedSizeBuilder type

The existing ImmutableArray<T> builder pattern through the Builder type
uses a minimum of two array allocations to create a single
ImmutableArray<T> instance.  The ImmutableArray<T>.Builder type has an
array field which is manipulated in much the same way as the array
inside of List<T>.  The call to ToImmutable on the builder creates a
copy of this array at the current length and wraps the result in an
ImmutableArray<T>

This pattern is great for a number of sceanrios.  For example when the
length of the array is variable or the application has low memory
pressure.

There are many situations though where a no copy / single allocation
solution would be advantageous.  In particular where there are a known
fixed number of elements to be converted to an array.  There is no need
for a double copy solution here because the final size is known in
advance.  All that is needed is for the array to be created, populated
and then frozen in an ImmutableArray<T> instance.

A good example of this need is Roslyn within Visual Studio.  Roslyn is
very careful to avoid unnecessary allocations, especially on hot paths.
Many of the hot paths include building instances of ImmutableArray<T>.
To avoid the double allocation Roslyn pools ImmutableArray<T>.Builder
instances.  This successfully avoids the double allocation but increases
the overall Gen2 pressure in the system.

This PR proposes to fix this by adding a no copy builder pattern:
FixedSizeBuilder.  This is a very simple wrapper around T[] which allows
for the creation and population of the array without the ability to
store a long term reference to the underlying array.  Hence it can be
safely converted to an ImmutableArray<T> without the need to copy the
array.

The builder can be reused for subsequent ImmutableArray<T> builds via
the Reset method
That's the root of the disagreement. I don't believe the different types
offer any value except in very specific and limited circumstances.

In this particular case the exception type holds no real value for me at
least. Why handle IVO instead of just checking that the object was in the
right state in the first place? Or if you are not directly calling the
indexer how can you have confidence that everyone in the middle left
themselves in a good state when the IVO was thrown?

In that circumstance how is IVO any different than NRE? Sure someone
explicitly threw it but not everyone in the middle opted into the
behavior.  It's just as random and invasive as a NRE.

As for the NRE crashing a native app, wish we could get that behavior in
managed code. Best chance of getting an accurate stack trace of the bug. :)

Probably shouldn't rat hole on this too deep.  I'd prefer an NRE or OOB
exception here but I'm content to take it as is a and revisit if profiles
show it to be a problem.

On Tuesday, November 25, 2014, Andrew Arnott <notifications@github.com>
wrote:

> In
> src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray`1+FixedSizeBuilder.cs:
>
> > +            /// Gets or sets the element at the specified index.
> > +            /// </summary>
> > +            /// <param name="index">The index.</param>
> > +            /// <exception cref="System.IndexOutOfRangeException" />
> > +            /// <exception cref="System.InvalidOperationException" />
> > +            public T this[int index]
> > +            {
> > +                get
> > +                {
> > +                    CheckIsInitialized();
> > +                    return _elements[index];
> > +                }
> > +
> > +                set
> > +                {
> > +                    CheckIsInitialized();
>
> We have distinct exception types in the CLR because folks generally
> believe they have value. Throwing the wrong one erodes that value.
> NullReferenceException is almost always a sign of a bug in the frame that
> throws it. If it were native code, it would have crashed the process.
> InvalidOperationException is documented to mean an operation that might be
> allowed, but isn't given the state of the object -- in fact exactly what
> the case is here that we're discussing.
> … <#149ea1536c9bff25_>
> On Tue Nov 25 2014 at 6:57:54 PM Jared Parsons <notifications@github.com
> <javascript:_e(%7B%7D,'cvml','notifications@github.com');>> wrote: In
> src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray`1+FixedSizeBuilder.cs:
> > + /// Gets or sets the element at the specified index. > + /// </summary>
> > + /// <param name="index">The index.</param> > + /// <exception
> cref="System.IndexOutOfRangeException" /> > + /// <exception
> cref="System.InvalidOperationException" /> > + public T this[int index] > +
> { > + get > + { > + CheckIsInitialized(); > + return _elements[index]; > +
> } > + > + set > + { > + CheckIsInitialized(); I don't understand the
> reluctance to use one exception over the other. Either way the class is
> being used in an incorrect way and an exception happens as a result. It's a
> coding error and any recovery attempt is just masking the underlying
> problem in the calling code. … <#msg-f:1485801441797578073_> On Tuesday,
> November 25, 2014, Andrew Arnott <notifications@github.com
> <javascript:_e(%7B%7D,'cvml','notifications@github.com');>> wrote: In
> src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray`1+FixedSizeBuilder.cs:
> > + /// Gets or sets the element at the specified index. > + /// </summary>
> > + /// <param name="index">The index.</param> > + /// <exception
> cref="System.IndexOutOfRangeException" /> > + /// <exception
> cref="System.InvalidOperationException" /> > + public T this[int index] > +
> { > + get > + { > + CheckIsInitialized(); > + return _elements[index]; > +
> } > + > + set > + { > + CheckIsInitialized(); I and the BCL team were very
> reluctant to allow ImmutableArray to throw NRE as a result of removing the
> if check. But we relented because the Roslyn team had extreme perf
> requirements that couldn't be satisfied any other way (mostly because of
> the JIT and for loops wouldn't optimize with the if check). As long as we
> ensure that the code can be inlined, I think the perf for setting this
> should be reasonable. We don't have any callers of this API yet so I don't
> think we have extreme perf requirements and even if we did, I'd rather see
> evidence that the if check is actually making a perf requirement
> unreachable before I'd feel good about throwing the wrong exception here. —
> Reply to this email directly or view it on GitHub <
> https://github.com/dotnet/corefx/pull/154/files#r20913242>. -- Jared
> Parsons http://blog.paranoidcoding.com/ http://twitter.com/jaredpar —
> Reply to this email directly or view it on GitHub <
> https://github.com/dotnet/corefx/pull/154/files#r20913973>.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/dotnet/corefx/pull/154/files#r20914314>.
>


-- 
Jared Parsons
http://blog.paranoidcoding.com/
http://twitter.com/jaredpar