Wednesday, June 2, 2010

One more List<>.collect Implementation

I realized that I left out a listCollect method from the previous set of tests. That is, the really, really naïve method which uses indices rather than enumeration. This reduces the cost somewhat, since there is no need to set-up enumeration. This cost is very small for a single call, but it can add up if listCollect is called millions of times.

Here is the code; I called it listCollect7. (As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

let listCollect7<'a,'b> (f:'a->List<'b>)
                        (la:List<'a>) : List<'b> =
  let lb = new List<'b>()
  for ila=0 to (la.Count-1) do
    let fla = f la.[ila]
    for ifla=0 to (fla.Count-1) do
      lb.Add fla.[ifla]

The numbers from the previous tests showed some variation due to variations in CPU load, GC, the random nature of the test data I was using, etc. So I decided to do a larger test. This test involved 25 million calls of listCollect in each of the seven versions. Below is the tale of the tape. As can be seen, the indexed method was the fastest, beating the enumerated version by about 20%.

At this point, however, I want to sound a cautionary note. I want it to be understood that I am NOT saying that one should ALWAYS pick the fastest method. Rather, one should always pick the BEST method. For performance-critical applications, the fastest method may indeed be the best method. However, in most situations, maintenance will trump speed.

By maintenance, I mean “development usability” in all aspects: the ability to find and avoid bugs, the ability to modify code, composability, etc. And often, the best approach to maintainability is the path of the language-appropriate idiom.

Always think of the user. If the user has to wait a tenth of a second for a screen refresh in a game, she’ll thank you for writing faster code. If she has to wait ten days for a simple change request or bug fix, she’ll thank you for writing more maintainable code.

No comments: