Avoiding Default Parameter Checking in C# 4.0

[jehugaleahsa]

[...]
I try to avoid methods like Merge in my library. I have a version that
works with IEnumerables. For instance,

Because I can't resist...

   private static IEnumerable<T> Merge<T>(IEnumerable<T> collection1,
     IEnumerable<T> collection2, Comparison<T> comparison)
   {
     using (IEnumerator<T> enumerator1 = collection1.GetEnumerator(),
       enumerator2 = collection2.GetEnumerator())
     {
       bool hadMore1 = enumerator1.MoveNext(),
         hadMore2 = enumerator2.MoveNext();

       while (hadMore1 || hadMore2)
       {
         if (hadMore1 &&
           (!hadMore2 || comparison(enumerator1.Current,
enumerator2.Current) <= 0))
         {
           yield return enumerator1.Current;
           hadMore1 = enumerator1.MoveNext();
         }
         else
         {
           yield return enumerator2.Current;
           hadMore2 = enumerator2.MoveNext();
         }
       }
     }
   }

I prefer that form, simply because it has less code and I like less code
(less typing, less maintenance).  However, note that if you're into
micro-optimization , making the code smaller is one of the best things
you can do to improve performance.  Loop unrolling still has its place
in the right circumstance, but smaller code usually wins these days.

That's interesting. When I read Steve McConnell's book the first time
I threw up a lot. I don't like most of the advice he included in Code
Complete. He spends a good number of trees talking about ways to
optimize code. He talked about loop unrolling and what not. Both your
and my implementation would require the same number of item-to-item
comparisons. I am used to people referring to loop unrolling to do
something like this:

for (int i = 0; i < n; ++i) a = i;

- to -

int i;
for (i = 0; i < n - 1; i += 2)
{
a = i;
a[i + 1] = i + 1;
}
if (i < n)
{
a = i;
}

I wouldn't think it would have any impact on my example since it
requires the same number of iterations and value comparisons. I don't
know; I don't know what the compiler is doing behind the scenes. In my
eyes, my slightly longer code is easier to read because it has less
complex boolean expressions.

What would be the impact of adding loops to the inside of the outer
while loop. Meaning, what would happen if you replaced your example's
if/else-statement with two while loops?

 

[Peter Duniho]

That's interesting. When I read Steve McConnell's book the first time
I threw up a lot. I don't like most of the advice he included in Code
Complete. He spends a good number of trees talking about ways to
optimize code. He talked about loop unrolling and what not. Both your
and my implementation would require the same number of item-to-item
comparisons.

Yes (sort of), but your comparisons are spread throughout the method,
whereas mine are basically in just one place. (I say "sort of" because
when your code finds the elements in each sequence equal to each other,
it actually has fewer comparisons, because you automatically advance
both sequences, whereas my code will only advance one at a time...this
results in an extra time through the loop for each equal element; on the
other hand, it makes the performance and execution pattern of my code
much more predictable, which can improve performance on CPUs that do
things like branch prediction).

I am used to people referring to loop unrolling to do
something like this:

for (int i = 0; i < n; ++i) a = i;

- to -

int i;
for (i = 0; i < n - 1; i += 2)
{
a = i;
a[i + 1] = i + 1;
}
if (i < n)
{
a = i;
}

I wouldn't think it would have any impact on my example since it
requires the same number of iterations and value comparisons.

Well, as I mentioned above, you have a little "mini-unroll" in your
code, where you advance two sequences at once in a specific case. But
more generally, loop unrolling can accomplish a variety of things.
Sometimes it avoids or consolidates operations, other times it
simplifies a given loop so that it can operate faster (but then may
require additional loops later to cover the cases not dealt with in the
first).

But, sure...if you want to be restrictive about the definition of "loop
unrolling", perhaps your example doesn't really qualify, in which case
there's not even an optimization there, just a bunch of extra code.

I don't
know; I don't know what the compiler is doing behind the scenes. In my
eyes, my slightly longer code is easier to read because it has less
complex boolean expressions.

I agree with that. However, do consider that because the expressions it
does have are spread out, a person actually has to spend more time
reading the code to find them all, and has to keep more lines of code in
their head at once to understand the net effect.

What would be the impact of adding loops to the inside of the outer
while loop. Meaning, what would happen if you replaced your example's
if/else-statement with two while loops?

Meaning what, exactly? Something like this:

while (hadMore1 || hadMore2)
{
while (hadMore1 && comparison(enumerator1.Current,
enuemrator2.Current) <= 0)
{
yield return enumerator1.Current;
hadMore1 = enumerator1.MoveNext();
}
while (hadMore2 && comparison(enumerator1.Current,
enuemrator2.Current) > 0)
{
yield return enumerator2.Current;
hadMore2 = enumerator1.MoveNext();
}
}

?

If that's what you mean, then I can't tell you what the effect would be,
performance-wise (well, I could measure it on my computer, but I haven't
done that, and I suspect the different would be negligible).

The code is slightly larger, and that pattern actually would result in
extra, unnecessary calls to the comparison function. You could get rid
of the extra calls with some extra state variables, but then the code
gets even longer and more complicated.

I prefer the version I wrote, but the above example is not too bad
either. My main objection is the extra comparisons, but one could
easily argue that even that objection qualifies as premature
optimization.

If you meant some other variation, you'll have to post the code.

Pete

 

[jehugaleahsa]

That's interesting. When I read Steve McConnell's book the first time
I threw up a lot. I don't like most of the advice he included in Code
Complete. He spends a good number of trees talking about ways to
optimize code. He talked about loop unrolling and what not. Both your
and my implementation would require the same number of item-to-item
comparisons.

Yes (sort of), but your comparisons are spread throughout the method,
whereas mine are basically in just one place.  (I say "sort of" because
when your code finds the elements in each sequence equal to each other,
it actually has fewer comparisons, because you automatically advance
both sequences, whereas my code will only advance one at a time...this
results in an extra time through the loop for each equal element; on the
other hand, it makes the performance and execution pattern of my code
much more predictable, which can improve performance on CPUs that do
things like branch prediction).

I am used to people referring to loop unrolling to do
something like this:

            for (int i = 0; i < n; ++i) a = i;

- to -

            int i;
            for (i = 0; i < n - 1; i += 2)
            {
                a = i;
                a[i + 1] = i + 1;
            }
            if (i < n)
            {
                a = i;
            }

I wouldn't think it would have any impact on my example since it
requires the same number of iterations and value comparisons.

Well, as I mentioned above, you have a little "mini-unroll" in your
code, where you advance two sequences at once in a specific case.  But
more generally, loop unrolling can accomplish a variety of things.
Sometimes it avoids or consolidates operations, other times it
simplifies a given loop so that it can operate faster (but then may
require additional loops later to cover the cases not dealt with in the
first).

But, sure...if you want to be restrictive about the definition of "loop
unrolling", perhaps your example doesn't really qualify, in which case
there's not even an optimization there, just a bunch of extra code.  

I don't
know; I don't know what the compiler is doing behind the scenes. In my
eyes, my slightly longer code is easier to read because it has less
complex boolean expressions.

I agree with that.  However, do consider that because the expressions it
does have are spread out, a person actually has to spend more time
reading the code to find them all, and has to keep more lines of code in
their head at once to understand the net effect.

What would be the impact of adding loops to the inside of the outer
while loop. Meaning, what would happen if you replaced your example's
if/else-statement with two while loops?

Meaning what, exactly?  Something like this:

       while (hadMore1 || hadMore2)
       {
         while (hadMore1 && comparison(enumerator1.Current,
enuemrator2.Current) <= 0)
         {
           yield return enumerator1.Current;
           hadMore1 = enumerator1.MoveNext();
         }
         while (hadMore2 && comparison(enumerator1.Current,
enuemrator2.Current) > 0)
         {
           yield return enumerator2.Current;
           hadMore2 = enumerator1.MoveNext();
         }
       }

?

If that's what you mean, then I can't tell you what the effect would be,
performance-wise (well, I could measure it on my computer, but I haven't
done that, and I suspect the different would be negligible).

The code is slightly larger, and that pattern actually would result in
extra, unnecessary calls to the comparison function.  You could get rid
of the extra calls with some extra state variables, but then the code
gets even longer and more complicated.

I prefer the version I wrote, but the above example is not too bad
either.  My main objection is the extra comparisons, but one could
easily argue that even that objection qualifies as premature
optimization.  

If you meant some other variation, you'll have to post the code.

Pete- Hide quoted text -

- Show quoted text -

No. You nailed it. I see, so by reducing the total number of loops,
we provide more opportunity for optimization.

 

[Peter Duniho]

No. You nailed it. I see, so by reducing the total number of loops,
we provide more opportunity for optimization.

Well, sort of. IMHO, the most important "optimization" here is just
allowing the _hardware_ to do its optimizations.

The compiler, having less code to deal with, and with the repetitive
parts consolidated, might be able to do a better job. But IMHO more
importantly, you have fewer branches, and the code is less likely to
bump some other code out of the cache when it executes (with cache sizes
these days, either version will easily fit into the cache, but the
larger version still puts more pressure on the cache than the smaller).

At the level of a single method, this may not make much difference, but
when you apply the same reasoning to a large number of methods, it could
make a significant one.

Now, all that said:

-- I'm not arguing for the smaller code on the basis of
performance. I just like the way it looks and reads better. YMMV.

-- Your original version had more branches in the first loop, but
because you pulled the trailing cases out and handled them separately,
it could actually perform better in scenarios where one sequence is
_much_ longer than the other, because those loops may be slightly more
efficient (smaller, only checking one "hadMore" variable and only
checking it once per iteration...in fact, the compiler would probably
optimize away any uses of the "hadMore" variables for those last two
loops in your original code).

In any case, any claimed performance difference one way or the other is
entirely theoretical, until someone actually goes and measures the
difference in performance for the expected scenarios under which the
code will run. Worrying about a performance difference in this code,
and especially choosing one implementation over the other on the basis
of an _expected_ performance difference instead of a measured
performance difference is a waste of time.

Pete