Weird profiling behaviour

[Colin Runciman]

Ketil Z. Malde wrote:

>I have what I think is a really strange problem.  I have a fair sized
>problem, which involves sorting a data set, first on labels (which are
>Strings) and then on scores (which are Ints).
>
>The strange thing is that string sorting is *vastly* faster than int
>scoring!  Now, I've tried modifying the sorting routinges, moving them
>into the same module, and so on, to no avail.  Is there any likely
>explanation?  The pipeline is basically
>
>         sortBy int_cmp . compound_equal . sortBy string_cmp
>
>I hesitate to post the code, since it's part of a rather large
>program, and in the hope that somebody will pop up and say that oh,
>yes, it's a well know feature of 'sortBy'.  Or that it's an artifact
>of profiling.  Or something like that.
>
>Any, and I mean any, suggestions really, really welcome.
>
>-kzm
>
Could it be that the string-comparison sort simply has less sorting to do
than the int-comparison sort?  The default definition of sortBy uses
insertion sort, so if the string-sort input happens to be already sorted
it takes linear time and if the int-sort input happens to be in
reverse order  it takes quadratic time.

Colin R