Today on the Coverity Development Testing Blog’s continuing series Ask The Bug Guys I’ll discuss the question “why does my enumerator not advance when I call MoveNext()in a lambda?” Check it out!
As always, if you have questions about a bug you’ve found in a C, C++, C# or Java program that you think would make a good episode of ATBG, please send your question along with a small reproducer of the problem to TheBugGuys@Coverity.com. We cannot promise to answer every question or solve every problem, but we’ll take a selection of the best questions that we can answer and address them on the dev testing blog every couple of weeks.
Fabulous adventures in coding 
Pingback: Dew Drop – May 22, 2014 (#1782) | Morning Dew
Thinking about the design of the foreach loop (and I’m probably not the first) and I wondered what-if the foreach loop lowered to this pattern…
var x = a.Start();
while (x = x.Next(); x.IsFinished == false)
{
/* Use x.Value. */
}
This would allow the iterator to be an immutable struct. There’s probably a very good reason why MS didn’t adopt this pattern way back.
As Eric explicitly points out in his article:
“Why then did the designers of the base class library choose to make the iterator of a list be a mutable value type? For an answer to that question, see my 2011 article on that subject.”
can be found there: https://ericlippert.com/2011/06/30/following-the-pattern/
Historical accident one could say, because I’d be exceedingly surprised if the JIT wouldn’t avoid the boxing/unboxing cost in any case (HotSpot in Java certainly does).
Good example of the fact that whenever you accept a design flaw for performance reasons you will be stuck with it, even when the original performance regression doesn’t exist anymore.
That article covers the behavior of a collection class, taking the established meaning of foreach as a given. My comment was about how foreach itself works underneath.
(Unless I missed it again, which is always possible.)
Indeed, there are certainly ways to design enumerators that are immutable, and that would be very useful. In particular it would mean that you could “bookmark” a place in a collection and come back to it later. I don’t know why the decision was made to require enumerators to be mutable.
As far as I can recall, every enumerator or iterator or whatever in any language I’ve used that has the idea has always been mutable.
Immutable enumerators sounds like a great idea to me, but not one I’ve heard of or thought about before.
Maybe it wasn’t a specific decision as much as following the status quo.
You have seen immutable value type iterators:
for(int i = 0; i < 100; ++i) { item = items[i]; ...The indexiis logically used just like an enumerator andintis an immutable value type. (The variable is of course mutable, but the type itself is not.)The decision made was to capture both the mutability of the variable and the notion of a position in a sequence in the
IEnumeratorinterface. That wasn't strictly speaking necessary; the enumerator could have captured only the position, been logically immutable, and kept the mutability in a variable.Ha ha, good point.
There are some cases where an immutable-enumerator design could be helpful from a client-side perspective (especially in scenarios that may involve backtracking) but implementing many kinds of enumerator (including compiler-generated iterators) would be just about impossible. Having a mutable “cursor” is IMHO the “right” approach, and one which might have been helpful for some aspects of `IList[T]` as well. For example, finding element N of a tree-backed collection may take time O(lgN), but if one has just found element N, finding element N+1 may take time O(1). A collection which cached the location of the last element received could not be very well shared between threads, but if it allowed each thread to request an `IReadableByIndex[out T]`, then each thread could request its own independent reader object, each of which could cache whatever would be useful for that thread.
Doesn’t solve the problem… Actually, the specific situation wouldn’t be possible, and boxing to IEnumerator wouldn’t solve it either, and performance would suffer when boxing is needed (ex: Linq), but if performance is the reason some IEnumerators are mutable structs the design isn’t all that good either, the “Current” property may throw exceptions and as such may not be inlined, this function call is for every element is far worse than one boxing or object creation at the beggining.
Does `List[T].Enumerator.Current` ever throw exceptions? I don’t think it does. The documentation for `IEnumerable[T].Current` says that the value is undefined in certain invalid-usage cases, but does not mandate that an exception be thrown. I would think many enumerators would simply define `Current` to unconditionally return the value of a field.
It does… If I remember correctly from a test I did when posting this, the yield implementation also does, anyway, the foreach implementation copies the value to another field, maybe the worse case from performance perspective.
After last Eric’s last post I had to go back to my test project and check it again, List enumerator indeed does not throw exception on “Current”, but arrays do, as the “yield” implementation.
Pingback: Following the pattern | Fabulous adventures in coding
In a framework which supports `ref` variables, does the IEnumerator[T] design have any concrete advantages over one with a single method `T TryReadNext(out bool success);` which would either return the next `T` if any or else `default(T)` [the `success` flag would indicate which]? The latter design would seem more like the way many languages’ file operations work.
I thought the same, initially, a single method wich does not throw exceptions and writes directly to the variable declared by the programmer, would work fine in .Net 2.0, but not so fine in 4.0, if it were designed as it is today, IEnumerator is covariant, an ref or out (wich are implemented equal) can not be covariant.
The normal MS try/do pattern is hostile to covariance because of a generically-typed `out` parameter, but using a generically-typed return variable and non-generic `success` should avoid that problem. After writing the above, I realized one slight advantage to the present pattern, which is that some types might be able to optimize repeated calls to `MoveNext()` which have no intervening calls to `Current`; on the other hand, an even better way of handling that would be to have a method to skip ahead an arbitrary number of elements without reading them. There are many data structures which could read a range of items (e.g. 1,000,000-1,000,999) much more quickly than they could either skip over all the individual items before the range or read out all the individual items within the range, and no type which implements IEnumerable should have any difficulty with a “skip ahead N items” command [any type could simply call MoveNext/ReadNext the appropriate number of times, but many types could use alternative means to skip ahead in O(1) or O(lgN) time]
Comments are unreadable, at least on an iPhone. Formatting is a mess…
If you wish for to take much from this piece of writing then you have
to apply such techniques to your won website.