Sunday, October 11, 2009

Follow up for meeting regarding Iterators/Ranges

We were looking at the examples Jon gives in his chapter on iterators, especially his take on ranges.
We had a hard time understanding the code of the GetEnumerator code:

image
Why these two constructs? And why using CompareTo directly?
Lets look at the second question first! Basically what the GetEnumerator method should do is yielding a new value and “incrementing” the value as long as the value is contained in the range. But the original code in the example behaves slightly differently. When you look at it a little bit closer you’ll notice the loop will only terminate when the value is equal or greater then the end value of the range. This assumes that the values will be increasing all of the time. But if the values are decreasing the values will always be less than the end of the range: We have an infinite loop. And what’s more we get values that will not return true when provided as an argument to the Contains method of the object that produced the value in the first place.
A simple test reveals this fact:
image
which gets us this test result:
image
If we simply change the code to use the Contains method the Range<T> class already provides the class will behave as expected.
Here is the modified version:
image
This is not only working correctly even for step values that will result in decreasing results of GetNextValue but it is much easier to understand.
There is one thing that is to say for the original code: It runs faster. To check that I changed to code of the GetEnumerator to use either the original or the modified code.
image
I will just use a static variable in the Switcher class to either use the original (Jon’s) code or the modified version. The following performance test
image
creates a range of 50 million integers and iterates over them using the GetEnumerator method and outputs the switch settings, the elapsed time, the ticks per iteration and finally a comparison of the performance between the original and the modified code. Here is the result:
image

1 comment:

  1. Thanks for this analysis. Will examine it closer when I'm going through that chapter. There is *some* method in my madness though: using Contains fails when the values wrap around. For example, consider a byte range 0-255 inclusive. A simple GetNextValue which wraps from 255 to 0 will keep going forever.

    See http://csharpindepth.com/ViewNote.aspx?NoteID=48 for a bit more information.

    Given the trickiness of all of this, I may well overhaul the example completely...

    ReplyDelete