Add EfficientLength marker interface to some iterabels.

Add EfficientLength marker interface to some iterabels.

Use that in List.from and other methods to be more efficient when possible.

R=floitsch@google.com

Committed: https://code.google.com/p/dart/source/detail?r=28575

[Lasse Reichstein Nielsen, 2013-10-09 10:24:50]

What do you think?

[srdjan, 2013-10-09 16:13:52]

DBC:

I think this is a very bad design and misuse of subtyping. There must be a
better and less brittle OO design that gives you better performance than what
you are proposing here, which is:
- Add a dummy interface X as a marker, and implement it by classes that have
(currently) efficient length access.
- Test everywhere if an instance is or is not X and then do two different kind
of computation.

'Is' tests should be avoided as much as possible (it is slow, and often a crutch
to compensate for inadequate design).

[kevmoo-old, 2013-10-09 17:05:06]

DBC

(Since it's been a while since I've made a "well in .NET..." comment)

Iterable: int count(); -> might be O(N)

List (and Set, Map, etc): int get length; -> assumed to be O(1)

[sra1, 2013-10-09 21:01:19]

On 2013/10/09 16:13:52, srdjan wrote:
> DBC:
> 
> I think this is a very bad design and misuse of subtyping. There must be a
> better and less brittle OO design that gives you better performance than what
> you are proposing here, which is:
> - Add a dummy interface X as a marker, and implement it by classes that have
> (currently) efficient length access.
> - Test everywhere if an instance is or is not X and then do two different kind
> of computation.

I agree, but can you suggest a better design?

The issue here is that (often) the operation depends on two types.
When this is done with double-dispatch, you end up with O(N^2) xxxFromYyy
methods, and a class hierarchy that is closed to meaningful extension because
you have to add new xxxFromZzz methods to classes that you don't control.

> 
> 'Is' tests should be avoided as much as possible (it is slow, and often a
crutch
> to compensate for inadequate design).

Is the slowness of an is-test fundamental to the VM?
Is it any slower than, e.g, adding "bool isX() => false" to Object and "bool
isX() => true" to those types that implement X?  Calling isX() is a single
dynamic dispatch, the same cost as the second dispatch in double-dispatch, so in
principle, it need not be less efficient than double-dispatch.

[sra1, 2013-10-09 21:16:52]

https://codereview.chromium.org/26681002/diff/1/sdk/lib/_collection_dev/itera...
File sdk/lib/_collection_dev/iterable.dart (right):

https://codereview.chromium.org/26681002/diff/1/sdk/lib/_collection_dev/itera...
sdk/lib/_collection_dev/iterable.dart:585: if (_skipCount is! int || _skipCount
< 0) {
Skip and Take are asymmetrical w.r.t. where the skipcount is checked.

I would prefer checking before initialization so that a compiler can infer that
the field is non-negative.
(i.e. change Skip to match Take).

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart
File sdk/lib/collection/queue.dart (right):

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:12: abstract class Queue<E> implements
Iterable<E>, EfficientLength {
This is what is scary about tag interfaces.
They are irrevocable.
I can't "implement Queue" unless my implementation also guarantees
EfficientLength.
The implicit interface is polluted with implementation details.

A "get hasEfficientLength" method would allow subclasses to revoke the
attribute, but a method becomes an mandatory burden on each implementation.

To void this problem tag interfaces should be used only on private classes.

[Lasse Reichstein Nielsen, 2013-10-10 06:25:15]

On 2013/10/09 16:13:52, srdjan wrote:
> DBC:
> 
> I think this is a very bad design and misuse of subtyping. There must be a
> better and less brittle OO design that gives you better performance than what
> you are proposing here, which is:
> - Add a dummy interface X as a marker, and implement it by classes that have
> (currently) efficient length access.
> - Test everywhere if an instance is or is not X and then do two different kind
> of computation.

We want the two different kinds of computation, because the one where you know
the
length before you start is often significantly more efficient.

One alternative is to always call iterable.length, whether its efficient or not.
It's a linear overhead, and we are going to do an iteration of the iterable
anyway,
so complexity-wise it's a no-op.
However, our experience is that some users will make iterables that have
side-effects, 
and iterating them twice (once to get the length, another to get the elements)
will be
an error.

If that is out, we are back to checking, somehow, if we can use length safely
and 
efficiently.
I have considered three different approaches:
- Marker interface: implements EfficientLength
- Indicator method: bool get hasEfficentLength => true;
- Alternative length getter: int get efficientLength => length or null (or -1).

Neither of these are fantastic. The interface method is the least intrusive one,
since it doesn't change the interface of Iterable. It is inherited, so any List,
Set, or Queue must have efficient length, but that is perfectly fine.
It did make delegating classes more complicated because they can't just delegate
the lookup, but must have an extra class for the efficient length case
(skip/take/where-iterables).
 
> 'Is' tests should be avoided as much as possible (it is slow, and often a
crutch
> to compensate for inadequate design).

Agree. We haven't properly addressed this yet, which is why we had the "x is
List || x is Set || .." code. And why I got tired of not having anything done,
and did this.

Another alternative is adding a "toEfficientLengthIterable" operation that gives
another iterable with efficient length. If the original one didn't have it, it
would create a list, otherwise it would just use the original. Again, it puts
another method onto Iterable.

[floitsch, 2013-10-10 13:04:52]

LGTM with comments.
In particular I want the tagging-interface to be hidden and not public.

@Srdjan: this CL reduces the number of is-checks. Instead of having "if (o is
List || o is Set || o is Queue)" we now only check against one interface. This
is not perfect either, but it really is just a shortcut to make things faster.

https://codereview.chromium.org/26681002/diff/1/runtime/lib/array.dart
File runtime/lib/array.dart (right):

https://codereview.chromium.org/26681002/diff/1/runtime/lib/array.dart#newcode83
runtime/lib/array.dart:83: Iterator it = iterable.iterator;
Do this change in a separate CL.

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/hash_set.dart
File sdk/lib/collection/hash_set.dart (right):

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/hash_set.d...
sdk/lib/collection/hash_set.dart:60: List<E> result = growable ? (new
List<E>()..length = this.length)
do in a separate CL.

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/iterable.dart
File sdk/lib/collection/iterable.dart (right):

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/iterable.d...
sdk/lib/collection/iterable.dart:390: abstract class EfficientLength {
Move to _collection-dev.

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/list.dart
File sdk/lib/collection/list.dart (right):

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/list.dart#...
sdk/lib/collection/list.dart:410: int insertEnd = start + insertLength;  // aka.
end + delta.
No need for comment (imho).

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart
File sdk/lib/collection/queue.dart (right):

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:12: abstract class Queue<E> implements
Iterable<E>, EfficientLength {
On 2013/10/09 21:16:53, sra1 wrote:
> This is what is scary about tag interfaces.
> They are irrevocable.
> I can't "implement Queue" unless my implementation also guarantees
> EfficientLength.
> The implicit interface is polluted with implementation details.
> 
> A "get hasEfficientLength" method would allow subclasses to revoke the
> attribute, but a method becomes an mandatory burden on each implementation.
> 
> To void this problem tag interfaces should be used only on private classes.

I partially agree. However we already did "is Queue" checks and simply assumed
that it had an efficient length.
We should add documentation that 'length' of a Queue should be efficient.

And even then: if the length is not efficient the complexity of our operations
don't change. We just run through the elements twice (which is really only bad
when they have side-effects).
We could rename the TagInterface to something else.

@Lasse: add documentation for "length". ?

[floitsch, 2013-10-10 13:06:28]

On 2013/10/10 13:04:52, floitsch wrote:
> LGTM with comments.
> In particular I want the tagging-interface to be hidden and not public.
> 
> @Srdjan: this CL reduces the number of is-checks. Instead of having "if (o is
> List || o is Set || o is Queue)" we now only check against one interface. This
> is not perfect either, but it really is just a shortcut to make things faster.
> 
> https://codereview.chromium.org/26681002/diff/1/runtime/lib/array.dart
> File runtime/lib/array.dart (right):
> 
>
https://codereview.chromium.org/26681002/diff/1/runtime/lib/array.dart#newcode83
> runtime/lib/array.dart:83: Iterator it = iterable.iterator;
> Do this change in a separate CL.
> 
>
https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/hash_set.dart
> File sdk/lib/collection/hash_set.dart (right):
> 
>
https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/hash_set.d...
> sdk/lib/collection/hash_set.dart:60: List<E> result = growable ? (new
> List<E>()..length = this.length)
> do in a separate CL.
> 
>
https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/iterable.dart
> File sdk/lib/collection/iterable.dart (right):
> 
>
https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/iterable.d...
> sdk/lib/collection/iterable.dart:390: abstract class EfficientLength {
> Move to _collection-dev.
> 
> https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/list.dart
> File sdk/lib/collection/list.dart (right):
> 
>
https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/list.dart#...
> sdk/lib/collection/list.dart:410: int insertEnd = start + insertLength;  //
aka.
> end + delta.
> No need for comment (imho).
> 
> https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart
> File sdk/lib/collection/queue.dart (right):
> 
>
https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart...
> sdk/lib/collection/queue.dart:12: abstract class Queue<E> implements
> Iterable<E>, EfficientLength {
> On 2013/10/09 21:16:53, sra1 wrote:
> > This is what is scary about tag interfaces.
> > They are irrevocable.
> > I can't "implement Queue" unless my implementation also guarantees
> > EfficientLength.
> > The implicit interface is polluted with implementation details.
> > 
> > A "get hasEfficientLength" method would allow subclasses to revoke the
> > attribute, but a method becomes an mandatory burden on each implementation.
> > 
> > To void this problem tag interfaces should be used only on private classes.
> 
> I partially agree. However we already did "is Queue" checks and simply assumed
> that it had an efficient length.
> We should add documentation that 'length' of a Queue should be efficient.
> 
> And even then: if the length is not efficient the complexity of our operations
> don't change. We just run through the elements twice (which is really only bad
> when they have side-effects).
> We could rename the TagInterface to something else.
> 
> @Lasse: add documentation for "length". ?

@Kevin: we discussed two different length-getters several times, but always
decided against it.

[sra1, 2013-10-10 17:02:41]

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart
File sdk/lib/collection/queue.dart (right):

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:12: abstract class Queue<E> implements
Iterable<E>, EfficientLength {
On 2013/10/10 13:04:53, floitsch wrote:
> On 2013/10/09 21:16:53, sra1 wrote:
> > This is what is scary about tag interfaces.
> > They are irrevocable.
> > I can't "implement Queue" unless my implementation also guarantees
> > EfficientLength.
> > The implicit interface is polluted with implementation details.
> > 
> > A "get hasEfficientLength" method would allow subclasses to revoke the
> > attribute, but a method becomes an mandatory burden on each implementation.
> > 
> > To void this problem tag interfaces should be used only on private classes.
> 
> I partially agree. However we already did "is Queue" checks and simply assumed
> that it had an efficient length.
> We should add documentation that 'length' of a Queue should be efficient.

There are many interesting queue algorithms that do not have this property; to
require an efficient length would forego their use.

Can we at least move closer to the ideal of implementing EfficientLength only on
private classes?

What I propose:
'EfficientLength' is a statement about the behaviour of get:length, so it must
only be implemented by the classes that implement get:length.

Then at least you can visually check, and a programmable static analysis tool
might be able to enforce the style.

You can still screw up by overriding get:length, but that is a smaller problem
than polluting an abstract interface.

> 
> And even then: if the length is not efficient the complexity of our operations
> don't change. We just run through the elements twice (which is really only bad
> when they have side-effects).
> We could rename the TagInterface to something else.
> 
> @Lasse: add documentation for "length". ?

[floitsch, 2013-10-10 17:12:05]

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart
File sdk/lib/collection/queue.dart (right):

https://codereview.chromium.org/26681002/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:12: abstract class Queue<E> implements
Iterable<E>, EfficientLength {
On 2013/10/10 17:02:41, sra1 wrote:
> On 2013/10/10 13:04:53, floitsch wrote:
> > On 2013/10/09 21:16:53, sra1 wrote:
> > > This is what is scary about tag interfaces.
> > > They are irrevocable.
> > > I can't "implement Queue" unless my implementation also guarantees
> > > EfficientLength.
> > > The implicit interface is polluted with implementation details.
> > > 
> > > A "get hasEfficientLength" method would allow subclasses to revoke the
> > > attribute, but a method becomes an mandatory burden on each
implementation.
> > > 
> > > To void this problem tag interfaces should be used only on private
classes.
> > 
> > I partially agree. However we already did "is Queue" checks and simply
assumed
> > that it had an efficient length.
> > We should add documentation that 'length' of a Queue should be efficient.
> 
> There are many interesting queue algorithms that do not have this property; to
> require an efficient length would forego their use.
> 
> Can we at least move closer to the ideal of implementing EfficientLength only
on
> private classes?
> 
> What I propose:
> 'EfficientLength' is a statement about the behaviour of get:length, so it must
> only be implemented by the classes that implement get:length.
> 
> Then at least you can visually check, and a programmable static analysis tool
> might be able to enforce the style.
> 
> You can still screw up by overriding get:length, but that is a smaller problem
> than polluting an abstract interface.
> 
> > 
> > And even then: if the length is not efficient the complexity of our
operations
> > don't change. We just run through the elements twice (which is really only
bad
> > when they have side-effects).
> > We could rename the TagInterface to something else.
> > 
> > @Lasse: add documentation for "length". ?
> 

The List interface specifies that its length must be efficient. There is no
reason not to add it there.
I'm willing to discuss its usefulness on other interfaces.

[Lasse Reichstein Nielsen, 2013-10-11 05:44:32]

I'm surprised that the Set interface doesn't require an efficient length either,
and I would require it of Queue as well (and really, of anything
Container-like).
The interface of Queue easily allows keeping track of the number of elements in
the queue.
What ails me is that by keeping the EfficientLength interface private, a user
can't mark his custom Iterable to have efficient length if it's not a List, Set
or Queue.
It's likely to not be important in many cases (he can write his own toList
instead of using List.from, and avoid using it in List.insertAll).

My personal favorite is adding Iterable.efficientLength that may return null if
it can't return the value efficiently, but I fear it will be misunderstood
and/or misused. And it changes the interface of Iterable (but IterableBase can
easily default to returning null).

[sra1, 2013-10-11 07:20:11]

On 2013/10/11 05:44:32, Lasse Reichstein Nielsen wrote:
> I'm surprised that the Set interface doesn't require an efficient length
either,
> and I would require it of Queue as well (and really, of anything
> Container-like).
> The interface of Queue easily allows keeping track of the number of elements
in
> the queue.
> What ails me is that by keeping the EfficientLength interface private, a user
> can't mark his custom Iterable to have efficient length if it's not a List,
Set
> or Queue.

I'm *not* proposing that EfficientLength is private.

I am proposing that since it describes a property of get:length, it should be
implemented by exactly those classes that (1) implement get:length (2) do so
efficiently.
If you stick to this pattern, you can locally verify that the 'annotation' is in
fact correct.
This includes 'user' implementations.

That would remove it as an obligation, which is what I am objecting to.
Just because you can implement an O(1) Queue.length does not mean that you
should.
An application with 10^8 queues that are mostly empty should not need to burn
10^8 words to store a length that has an expected value near zero. 

> It's likely to not be important in many cases (he can write his own toList
> instead of using List.from, and avoid using it in List.insertAll).
> 
> My personal favorite is adding Iterable.efficientLength that may return null
if
> it can't return the value efficiently, but I fear it will be misunderstood
> and/or misused. And it changes the interface of Iterable (but IterableBase can
> easily default to returning null).

Is there another design based around not whether get:length is fast (that could
be a dynamic property), but the operations that are different when get:length is
fast or slow?

[Lasse Reichstein Nielsen, 2013-10-11 09:01:16]

On 2013/10/11 07:20:11, sra1 wrote:
> On 2013/10/11 05:44:32, Lasse Reichstein Nielsen wrote:
> > I'm surprised that the Set interface doesn't require an efficient length
> either,
> > and I would require it of Queue as well (and really, of anything
> > Container-like).
> > The interface of Queue easily allows keeping track of the number of elements
> in
> > the queue.
> > What ails me is that by keeping the EfficientLength interface private, a
user
> > can't mark his custom Iterable to have efficient length if it's not a List,
> Set
> > or Queue.
> 
> I'm *not* proposing that EfficientLength is private.
> 
> I am proposing that since it describes a property of get:length, it should be
> implemented by exactly those classes that (1) implement get:length (2) do so
> efficiently.
> If you stick to this pattern, you can locally verify that the 'annotation' is
in
> fact correct.
> This includes 'user' implementations.
> 
> That would remove it as an obligation, which is what I am objecting to.
> Just because you can implement an O(1) Queue.length does not mean that you
> should.
> An application with 10^8 queues that are mostly empty should not need to burn
> 10^8 words to store a length that has an expected value near zero. 

That is correct, but if you expect queues to be small, you may consider counting
elements to be efficient. And you are unlikely to do conversions on all these
queues.

In other words: You can always break the requirement that length is efficient if
you decide it suits your purpose. It will mean that other code using your
slow-length queue may be slower, but that's a tradeoff you make.

We were already assuming that all List, Set and Queue objects had efficient
length. This is just coupling those tests into a single interface instead, which
also allows us to use it on some select iterables (e.g., map of a List, which is
a common case for doing toList).

> 
> > It's likely to not be important in many cases (he can write his own toList
> > instead of using List.from, and avoid using it in List.insertAll).
> > 
> > My personal favorite is adding Iterable.efficientLength that may return null
> if
> > it can't return the value efficiently, but I fear it will be misunderstood
> > and/or misused. And it changes the interface of Iterable (but IterableBase
can
> > easily default to returning null).
> 
> Is there another design based around not whether get:length is fast (that
could
> be a dynamic property), but the operations that are different when get:length
is
> fast or slow?

The problem is mostly with new List.from, which is what is used by
IterableBase.toList, ListBase.toList and other most other toList
implementations, and List.insertAll. In these cases, knowing the number of
elements before doing the operation avoids a lot of allocation and copying.

The constructor could be worked around by having a helper function that knows
the length.
The insert function really has to work with any iterable. It could be done by
doing an addAll and three partial reverse operations, but it's still much faster
to use just one grow, one move and then inserting the elements.

[Lasse Reichstein Nielsen, 2013-10-14 10:40:17]

Committed patchset #5 manually as r28575 (presubmit successful).