Assume all List implementations have an EfficientLength

[matanlurey]

Today, a small number of SDK-only collections may implement EfficientLengthIterable:
dart-lang/sdk#29862

In #208, @leafpetersen states:

This is likely to be significantly more efficient, but is not a valid optimization that a compiler can do

I have another suggestion, just change this assumption:

• All List implementations are now assumed to have an efficient length.
• Deprecate and remove EfficientLengthIterable from the internal SDK.
• Eventually, remove implements List<T> from LinkedList if necessary.

As a benefit, this would:

• Nullify the discussion in Should spread of a List use the Iterable protocol or direct iteration? #208.
• Remove the need for google3 customers to roll for (var i =, l = loops over hot code everywhere.

... this doesn't solve classes that don't implement List (like BuiltList), but they aren't worse, either.

[munificent]

This is a good point to bring up, but doesn't totally nullify #208. Even if length is fast, that doesn't mean it's always available (you can spread non-List Iterables) nor that it's necessarily the best API for spread to use.

But overall, yes, I think language features that desugar to calling methods on Lists should be able to assume length is fast and safe to call.

[matanlurey]

Sure. I think at that point you let the compiler decide - if it can tell its backed by a *List (or not).

[lrhn]

All lists are assumed to have efficient length because the List interface extends EfficientLengthIterable. So does Set and Queue. All of them are documented as needing to have efficient length implementations.
(Again, EfficeintLengthIterable is an internal marker interface used by the platform libraries so it doesn't have to do x is List || x is Set || x is Queue, not as something you should care about otherwise).

The issue in #208 is not whether length is available or efficient. If it's a list, we know that to be the case. The issue is how the semantics of iteration over a user supplied iterable is defined, how it must or can be implemented.
If we always use iterator for iteration, then the user has predictable semantics and efficiency.
If the implementation must use length and [] if the iterable is a list, then we add overhead for the is List check if the static type is Iterable.
If we let it be determined by the static type, then we have inconsistent performance and behavior for the same List object depending on the static type of it. That's likely to be confusing.
If we leave it underspecified, and let implementations choose between the two (or more) ways of iterating, then we have completely unpredictable semantics and performance.

Those are the tradeoffs, between predictability of behavior, understandability by users, and performance.

We don't want a to just leave the door open to arbitrary use of the available API of the object (no for (int i = 0; i < x.length; i++) { var element = x.skip(i).first; ... } or similarly silly approaches), so we need to nail down some rules for what the iteration can do.

If you create your own simple wrapper around something, in order to make it spreadable, which functions must you implement. Say:

/// The sequence of individual one-codepoint strings of a string.
/// Only used for spreading: `var chars = [ ... _Chars("string"), "a"]`
class _Chars extends Iterable<String> /* or List<String> ?*/{
   final String _string;
   noSuchMethod(i) => throw Unimplemented(i.memberName);
   ... implement what here? ... 
   Iterator<String> get iterator => _string.runes.map((i) => String.fromCharCode(i)).iterator;
   int get length => _string.runes.length;
}

If we say that we always and only use iterator, then you only need to implement iterator here.
If we say that we might use length on any Iterable (even if we will only do that on efficient length iterables, but we can't say that because it's not a public type), then morally you should implement length here. Even if you "know" that it won't be needed, the spec says it might, so maybe it will at some point in the future.
The more precise we are, the more you know what you have to support (and make efficient).
The less precise we are, the more efficiency trade-offs the program can handle at run-time.

The original choice was "always use iterator". That's what for(... in ...) does already. If you want to use index iteration, you can write the for (var i = 0; i < x.length; i++) { ... x[i] ... } instead. You can do that for spreads too, if you want to, but it might be annoying that you have to. It is already annoying for for-in. We could change for-in to also allow .length/[] iteration if the iterable is a list - again with all the above trade-offs (based on static type or dynamic type? I'd probably say static type for for-in, which is curious because I also said dynamic type for spreads).

So, #208 is almost entirely independent of EffecientLengthIterable.

Also LinkedList (from dart:collection) does not implement List. It actually has efficient length, even if it's not visible (it doesn't implement EfficientLengthIterable). It has a bad name, because it is not a List like the name suggests.