Hi Jan,
| Could anyone explain what is a relation between
| number of reductions and execution time of any
| given Haskell function? Is there any linear
| relationship between the two on any given machine
| and compiler/interpreter?
Absolutely, definitely not. To paraphrase George Orwell, "All
reductions are equal, but some are more equal than others."
| May I at least assume the implication:
| reduction_count1 > reduction_count2 ==> time1 > time2 ?
| when assessing efficiency of two similar algorithms
| running in Hugs?
No, that is not a valid assumption. This issue is actually discussed
in the Hugs manual; I'll attach an extract of that below. The reduction
count is still a useful statistic in some situations, but not for answering
the questions that you are interested in here.
All the best,
Mark
--- From the Hugs user manual:
Note that the statistics produced by +s are an extremely crude measure
of the behaviour of a program, and can easily be misinterpreted. For
example:
o The fact that one expression requires more reductions than another
does not necessarily mean that the first is slower; some reductions
require much more work than others, and it may be that the average
cost of reductions in the first expression is much lower than the
average for the second.
o The cell count does not give any information about residency, which
is the number of cells that are being used at any given time. For
example, it does not distinguish between computations that run in
constant space and computations with residency proportional to the
size of the input.
One reasonable use of the statistics produced by +s would be to observe
general trends in the behaviour of a single algorithm with variations in its
input.
