Alternative ArrayList implementation

[gavinking]

Currently, ArrayList<E> stores its elements in an Array<E?> to reflect that the array is "oversized" i.e. bigger than the length of the list. This has the side-effect of preventing the Array from optimizing its storage to use primitive arrays of unboxed values or java.util.String[] for strings.

An alternative strategy would be to use an Array<E> of the exact length of the list, thus taking advantage of the use of primitive arrays with unboxed values.

There are interesting tradeoffs:

• Arrays of boxed values waste a lot of space.
• But arrays of boxed values are more efficient to iterate with, say, filter().
• For lists with a lot of mutation, reallocating the array every time the list is mutated is very expensive. (But many, many lists are read-mostly.)

Now, according to my plans for ceylon/ceylon.language#312, ArraySequence will be able to take advantage of the optimization, so perhaps that's all we need. That is to say, to get your unboxed list, you just call ArrayList.sequence.

Or perhaps it might be worth having an alternate implementation of List in ceylon.language?

Note sure.

[gavinking]

Since we have reified generics, one thing we could do in the future, with ArraySequence, or with an "alternative" ArrayList is specialize some of the functions like map(), etc, for primitives, to allow the functions to completely avoid boxing. For now we can't do that, because you need to box when you invoke a Callable. But if we had specialized Callables optimized for primitives, we could do it.

[tombentley]

If Callable was implemented in terms of MethodHandle it is possible we could do this without having to specialize Callable itself. On 11 Jan 2014 18:25, "Gavin King" notifications@github.com wrote:

Since we have reified generics, one thing we could do in the future, with ArraySequence, or with an "alternative" ArrayList is specialize some of the functions likemap(), etc, for primitives, to allow the functions to completely avoid boxing. For now we can't do that, because you need to box when you invoke aCallable. But if we had specializedCallable`s optimized for primitives, we could do it.

— Reply to this email directly or view it on GitHubhttps://github.com/ceylon/ceylon-sdk/issues/181#issuecomment-32103144 .