Allow EfficientLengthIterable equivalent for non-SDK libraries

[davidmorgan]

See #23328 for context; the SDK uses EfficientLengthIterable to decide whether an Iterable is backed by something that can quickly return "length". Because non-SDK libraries cannot access EfficientLengthIterable they are always treated as not having efficient "length", leading to extra work.

It's not clear what could be done to fix this, but if there's any way to do it with 2.0, that would be great.

[lrhn]

There really is not a good way to introduce this feature.

What we do not want is anyone, ever, writing myFunction(EfficientLengthIterable elements) .... That would be introducing a new concept that users need to worry about - it locks out all the perfectly good normal iterables and complicates things for everybody.
There is no way to make a marker interface that can't also be used as a type.

So, the answer for #23328 stands for now - use List, Set or Queue for your efficient-length needs.
It really was originally introduced to make is List || is Set || is Queue shorter for ourselves to write :)
The standard Iterable.map function preserves efficient-length-ness of the source too.

Hmm, perhaps we could expose an EfficientLengthIterableWrapper that wraps any iterable and claims to have an efficient length. It would not work as a type because List doesn't have that type, but both would have the internal EfficientLengthIterable as superclass.
It's still not pretty, and I'd prefer not doing it.

We'll think about it, but it's not high on the list of 2.0 features.

[davidmorgan]

Hmm. Actually I think I have a workaround.

I don't want to implement List/Set/Queue because they carry methods that I won't implement. (The Java/Guava route for immutable collections). But I can do this:

class BuiltList<T> implements Iterable<T> {
  factory BuiltList() => new BuiltListImpl<T>();
}

class BuiltListImpl<T> implements BuiltList<T>, List<T> {
}

That means I get the static checks I want. At runtime, instances will be EfficientLengthIterable via List.

This does mean that if anyone is doing processing based on the runtime type and checking for List they may be surprised ... but I can't see that being particularly important.

WDYT? Do you see any downsides to doing this? Thanks!

[davidmorgan]

My workaround is slightly less nice than hoped :/ ... because BuiltList methods clash with List, and BuiltSet with Set.

But I can use/abuse Queue, since none of its methods clash with mine and they're just going to throw UnimplementedError anyway.

Benchmarking List#addAll(new BuiltList(...lots of data)) shows a 2x speedup, as you would expect -- it can straight away grow the list by the right amount.

@lrhn it's not pretty but I think I can live with this. What do you think, please?

[lrhn]

@floitschG

I think it's an extremely ugly hack, but I can also see that we are not giving you a better alternative.

I'll consider whether to expose a subclass of EfficientlengthIterable in some way, so you can implement that, but it can't be used to detect/require iterables with efficient length (since List doesn't implement that particular subtype). It's still ugly, and it's sort-of sad that users can't check if an iterable has efficient length and use it themselves.

Maybe (and definitely no promises):

class EfficientLengthIterable implements _internal.EfficientLengthIterable {
   factory EfficientLengthIterable._cannotBeExtendedOrInstantiated() => null;
   static bool isEfficient(Iterable iterable) => iterable is _internal.EfficientLengthIterable;
}

That would allow class MyIterable implements EfficientLengthIterable { ... }, but not meBeingClever(EfficientLengthIterable iter) => ... (which we want to prevent, and evidence shows that it will happen if we don't prevent it). The latter won't work because it rejects List, and nobody wants that :)
We will still get code like:

meBeingTooCleverByHalf(Iterable iter) {
  assert(EfficientLengthIterable.isEfficient(iter));
  ...
}

but we can't prevent all self inflicted wounds like that, just recommend that they say List instead.

[davidmorgan]

What about splitting EfficientLength from Iterable altogether -- then making it public?

abstract class EfficientLength {
  int get length;
}

List would then implement both EfficientLength and Iterable.

There's then no point in writing

void myFunction(EfficientLength e)

because you can't do anything useful with it.

[floitschG]

That's what we had before. (Not publicly exposed, but still).

We merged them, because least-upper-bound computations found EfficientLength on things like [ new List(1), new Set()].

Already at that time, we debated, if we should expose EfficientLength or not... It just feels wrong to have such a class in the core libraries.

We are now wondering, if we can reduce the need for it. Most of the time, when we use it, is because the API accepts an Iterable. In many cases, we should just request a List instead.

[davidmorgan]

There probably aren't too many important uses, but List#addAll seems to be one.

[lrhn]

When we had EfficientLength by itself, it wasn't clear what it meant. There was at least one case of it being used on a Map implementation, which it was never intended for (all maps should have efficent lengths, and nobody ever checks it on anything but iterables anyway). That, and the odd least-upper-bound behavior, was why it became EfficientLengthIterable.

[pschiffmann]

What do you think about using an annotation as a marker?

import 'dart:collection' show efficientLength;

@efficientLength
class BuiltList<E> implements Iterable<E> { ... }

[davidmorgan]

@pschiffmann I don't think an annotation helps -- there's no way to check for it given an instance of that type.

[pschiffmann]

@pschiffmann I don't think an annotation helps -- there's no way to check for it given an instance of that type.

After reading lrhn's last comment I thought thats' what he wanted. And trying to look at it from that perspective, it made sense to me: Instantiating user-written data structures (trees, linked lists) from the Iterable is done one node at a time; sequential map/filter/reduce don't care about length; and parallel stuff requires a proper List anyways. You only need to know the length of an Iterable before you consume it, if you want to allocate a contiguous memory region for all its elements.
Dart exposes that through new List.from and List.addAll, so wouldn't it be sufficient if these two methods could check whether their parameter is an EfficientLength? And since List is provided by the implementation, it can check for the annotation through cheap reflection (Dart VM) or AOT code transformation (DDC).

Please don't get me wrong, I'm not trying to sell you my idea here. I just got more and more interested in language design recently and just saw a change to contribute my first idea ;-) So if you'd take the time to point out my thought flaws and teach me something in the process, I'd be very thankful!

[davidmorgan]

Ah, I see what you mean -- yes, I guess the SDK could do something special to allow just blessed code to check for it at runtime. Interesting. I don't work on the SDK though, so my opinion doesn't count for much :) ... @lrhn what do you think please?

For the record, there are currently 5 places in the SDK using "is EfficientLength": array_patch.dart, growable_array.dart, string_patch.dart, queue.dart and iterable.dart.

[lrhn]

The EfficientLength was originally introduced internally as a shorthand for x is List || x is Set || x is Queue, as an optimization in List.from and similar functions. It was found useful for a few Iterables derived from those classes too, and some of the insert operations on List, but it wasn't intended as something a user should care about. It's not documented anywhere which functions actually do the check, so it was very much black magic to add implements EfficientLength for anything not closely related to the platform libraries. It's most certainly not intended as a "just add performance" marker.

We tried making it public so a class could mark itself as having efficient length, but the uses of it weren't encouraging (using it as a type, having functions expecting an EfficientLength, not what was intended for an implementation detail), so we rolled that back again.
That's basically the status now. It's an internal and undocumented optimization for some functions in the platform library. It's not documented which classes actually implement EfficientLengthIterable (as it's now called), nor is it documented which function check for it. It's not a feature that's really designed for general use (which quickly became clear when we tried making it available), and in the perfect world, nobody would even know that it exists, and we could remove it tomorrow with no impact except a little performance.

So, no, there is no current plan to make the feature generally available.
If we did, we might also want an EfficentContains marker, and it quickly gets complicated, which is the opposite of the chosen design for Dart collections. We only have one List type, not a ReadOnlyList, WritableList, GrowableList, etc. Efficient-length is one more behavioral bit that we don't expose, and the current plan is to keep it that way.

We definitely do not want annotations to mean anything to the platform libraries at runtime. If it's important at runtime, it should be reflected in the runtime objects.

[dnfield]

Perhaps as a slightly different version of this request, I'd like to have a EfficientRandomAccessIterable, which is like EfficientLengthIterable but also indicates the following:

• first, last, and length reliably return the same things and do not mutate any state (or, if state is mutated, it is efficiently memoized by the iterable). They can safely be invoked any number of times.
• The iterable implements some accessor that can efficiently access random elements, such as an operator[] or elementAt or something like that.

There's a fairly common source of confusion when you get used to working with Iterables that are really List/Set/Queue - that calling length is cheap and that it is safe to call multiple times. It can be quite shocking for a user when they suddenly encounter this code -

void myFunction<T>(Iterable<T> iterable) {
  print(iterable.length); // 5
  print(iterable.length); // 0!
  print(iterable.first); // exception? null? certainly not the first element at the start of this method.
}

It would be helpful to have a SDK type that could be passed in instead like void myFunction<T>(EfficientRandomAccessIterable<T> list).

[dnfield]

Also as a type implementer, I'd like to impelement things sometimes that are basically lists but do not derive from list.

[lrhn]

We are not planning on introducing any public marker interface for classes having efficient length, contains, last, etc.