How about this syntactic candy?

[Peter Duniho]

[...]
I've conducted more tests, but here's the gist of the results:
1) When the range ~= sample size, the two algorithms are roughly
equal, with the dictionary approach just about winning
2) As the sample size increases without changing the range, the array
approach is better than the dictionary approach, but by *about* a
factor of 2 (increasing slightly, but not dramatically) as the
proportion changes
3) As the range size increases without changing the sample size, the
dictionary approach is *much, much* better.

For what it's worth, while my own tests have resulted in similar
results (sorry, yes...I actually have done the tests, and while the
mature thing to do might have been to go ahead and post the results,
I'm bugged enough by the issues I've described that I just don't feel
like it at the moment), I've got some observations (including two
caveats, listed first):

1) The array implementation can be sped up quite a lot when the
input range is sparsely populated by creating a new list of the counted
values that include only those counts greater than 0. Without doing
that, the cost of sorting all those values that weren't even in the
input data create a huge liability as compared to the dictionary
solution.

The relative outcomes are still the same, but the dictionary solution
only winds up enjoying a smaller advantage (for a 1:100 range:samples
ratio, it's more like 10X instead of 100X).

Of course, you have to know in advance this is going to be an issue if
you're going to make a design decision based on this. In my own tests,
I just always did the copy before sorting; when the data isn't sparse,
it still doesn't add much to the total time cost, and when it is it
makes a very dramatic difference in performance.

2) I also found that when running multiple tests in the same
process, subsequent tests seem to enjoy some benefit from the execution
of the first test. That is, the first test is always slowed down
relative to the time it would take had it been performed later. This
accounted for as much as a 5-10% increase in time cost for a test.

In my own tests, I accounted for that by running a throw-away test to
start with, and of course the difference is small enough that it
wouldn't affect relative comparisons that were significant (I don't
consider a 10% time difference a significant enough performance
difference to qualify as sole justification for a change in design).
But it does mean that if the same effect happens on your computer, with
the array implementation always being run first it's always a bit
handicapped.

3) I was surprised to find that using an enumerator to iterate
through the sample data was actually faster than an explicit for() loop
(even one that uses a constant expression for the loop terminator )

4) In the dictionary solution, it is faster to call Contains() and
then retrieve and reassign the value, than to call TryGetValue(). As
with the iteration difference, I have not bothered to look closely at
the .NET implementation to better understand why the difference exists.
But it does (my suspicion is that TryGetValue() basically calls
Contains(), and so calling that method simply adds an extra call to the
loop).

Anyway, I appreciate that there's at least one person around here calm
and rational enough to just provide the numbers, regardless of whether
they will be heeded or not. And of course, if Hilton promises to
stop ducking the questions and respond favorably to the evidence he
claims to require, I will go ahead and post my own results.

Finally, if nothing else I find that the topic of the dictionary versus
array implementation _strongly_ reinforces the point about not engaging
in premature optimization.

In even such a simple scenario, I came up with 11 different
implementations of the two algorithms, each with varying performance.
Two implementations were awful (sorting a large range of zeros was very
costly, as is using exceptions to deal with missing keys in a
dictionary), two were not terrible but still enough slower that you'd
have to have a really good reason to choose them (those involved using
a class to contain data in the dictionary, but the performance cost of
the memory management for that outweighed the benefit of not having to
look up a key twice when iterating through the input data), and the
remaining seven varied in ways similar to those you've reported here.

A person would have to do a lot of research, and have a _very_ solid
knowledge of what input data their algorithm was going to be processing
before they could make any sort of informed decision regarding
algorithm choice based on performance goals. You would have to know
with absolute certainty that the data fell into the narrow scenario
that favors the array implementation in order to choose that
implementation.

Any statement regarding which algorithm is better based on performance
is clearly premature absent that research, and the data clearly
demonstrate that the array implementation is only faster in a very
specific scenario and even then not by all that much, while the
dictionary implementation is equal to or better in the majority of
cases and when it is noticeably better, it's better by a huge factor
(much greater difference than when it's slower).

Pete

 

[Jon Skeet [C# MVP]]

4) In the dictionary solution, it is faster to call Contains() and
then retrieve and reassign the value, than to call TryGetValue(). As
with the iteration difference, I have not bothered to look closely at
the .NET implementation to better understand why the difference exists.
But it does (my suspicion is that TryGetValue() basically calls
Contains(), and so calling that method simply adds an extra call to the
loop).

Really? Wow - that's a real surprise. I must investigate that further.
(Reflector shows that TryGetValue doesn't call Contains, but both call
FindEntry - so calling Contains and then the indexer to read will end
up finding the entry twice, but TryGetValue only finds the entry once.)

I'll look at it more tomorrow - it's time for bed now.

Anyway, I appreciate that there's at least one person around here calm
and rational enough to just provide the numbers, regardless of whether
they will be heeded or not.

You call me rational now... see if you still do after reading this:

http://msmvps.com/blogs/jon.skeet/archive/2007/11/28/don-t-call-us-we-
ll-call-you-push-enumerators.aspx

I blame Marc Gravell.

<snip>

 

[Peter Duniho]

Really? Wow - that's a real surprise. I must investigate that further.
(Reflector shows that TryGetValue doesn't call Contains, but both call
FindEntry - so calling Contains and then the indexer to read will end
up finding the entry twice, but TryGetValue only finds the entry once.)

I was surprised too. The reason I even compared the two is that I had
assumed that TryGetValue would do the check for containment and
retrieval as a single operation. If anything, I expected it to be
faster. But in my tests it's not.

I would not at all be surprised if looking at the code shows that
TryGetValue does indeed appear to have more efficient code (ie
retrieving at the same time as checking for the key's existence). But
_something_ is going on to slow it down. If nothing else, it's yet
another illustration of how optimizing code is best left for when
there's an actual problem to be solved, and when some real world data
can be obtained regarding actual performance.

I'll look at it more tomorrow - it's time for bed now.


You call me rational now... see if you still do after reading this:

http://msmvps.com/blogs/jon.skeet/a...-call-us-we-ll-call-you-push-enumerators.aspx
Well,

even the most rational among us need to escape once in awhile.

For what it's worth "push" enumeration isn't unheard of. I would
consider any sort of enumeration involving a callback to be an example
of that, of which there are examples in the Windows API and which I've
used in other contexts as well (I even used it in an image processing
class I wrote once).

Still, I don't know enough about LINQ to really "get" what you're
article is all about but if you think the design in your article is
crazy, who am I to argue?

I blame Marc Gravell.

Sounds good to me. Seems like we have precious little things to blame
on him, so why not? I'm sure he can handle the load.

Pete

 

[Jon Skeet [C# MVP]]

I was surprised too. The reason I even compared the two is that I had
assumed that TryGetValue would do the check for containment and
retrieval as a single operation. If anything, I expected it to be
faster. But in my tests it's not.

I'll need to test it myself - it'll be most odd if your tests show it
to be one way and mine show something else

For what it's worth "push" enumeration isn't unheard of. I would
consider any sort of enumeration involving a callback to be an example
of that, of which there are examples in the Windows API and which I've
used in other contexts as well (I even used it in an image processing
class I wrote once).

Well, it was the way of using it that was particularly odd. However,
we've got a better way of doing it

Still, I don't know enough about LINQ to really "get" what you're
article is all about but if you think the design in your article is
crazy, who am I to argue?

The basic thrust is to do efficient grouped aggregations.

For instance, consider a stream of newsgroup posts, and you want to
build a "most prolific posters" list. With LINQ in its current form,
that can't be done very efficiently (in terms of memory usage). The
push stuff helps with that a lot. The new design will also allow for
multiple aggregates to be computed at once, somewhat coincidentally.

Sounds good to me. Seems like we have precious little things to blame
on him, so why not? I'm sure he can handle the load.

His generic maths stuff is evil too. I hadn't looked at it properly
before this afternoon. Ouch, but cool ouch