I've taken a look at garbage collection and I have used kernelopts(gctotaltime) to measure the amount of time used in garbage collection while the repeated test is being run using CodeTools:-Usage. I have then subtracted this (suitably scaled) from the cpu time returned by CodeTools:-Usage to give a `computational' time. Is this a reasonable approach?

I still get certain series of tests where the cpu time taken (with the gc time subtracted out) is still not monotone and varies quite dramatically between runs:

  n     UsgCPU   #GC   GCAvgT CompTim   %GC
  10   0.01568      0.1   0.00085   0.01485    5.42
  20   0.05524      0.2   0.00424   0.05100    7.67
  30   0.15864      0.4   0.01221   0.14644    7.70
  40   0.39508      1.0   0.03514   0.35995    8.89
  50   0.87532      1.0   0.07079   0.80454    8.09
  60   2.10220      2.4   0.14219   1.96002    6.76
  70   1.96860      1.9   0.12311   1.84550    6.25
  80  20.17000   17.3   1.26725  18.90275    6.28
  90  22.21856   17.8   1.43343  20.78513    6.45
 100   9.71568     2.9   0.50991   9.20578    5.25

  n     UsgCPU  #GC GCAvgT   CompTim  %GC
  10   0.01580    0.1   0.00095   0.01487    6.03
  20   0.04528    0.1   0.00241   0.04287    5.32
  30   0.10964    0.2   0.00747   0.10216    6.82
  40   0.26832    0.4   0.01630   0.25201    6.08
  50   0.37088    0.4   0.02591   0.34498    6.98
  60   2.37912    2.7   0.16044   2.21868    6.74
  70   4.92120    4.6   0.32445   4.59675    6.59
  80  19.39848   16.5   1.28816  18.11033    6.64
  90   3.54524    1.4   0.21389   3.33135    6.03
 100   6.90320    2.2   0.32098   6.58223    4.65

  n     UsgCPU #GC  GCAvgT   CompTim  %GC
  10   0.01588    0.1   0.00092   0.01498    5.77
  20   0.04548    0.1   0.00279   0.04270    6.13
  30   0.11236    0.2   0.00897   0.10339    7.98
  40   0.42176    0.5   0.02905   0.39271    6.89
  50   0.36504    0.4   0.02583   0.33921    7.08
  60   1.15616    0.6   0.08300   1.07314    7.18
  70   4.00492    1.9   0.26600   3.73891    6.64
  80   5.01212    2.2   0.29837   4.71375    5.95
  90   4.86440    1.9   0.26801   4.59641    5.51
 100   8.27412    2.8   0.41663   7.85748    5.04

These were the results of three runs of the same test on the same machine with just a couple of terminal windows open. (#GC is the average number of calls to the garbage collector during the CodeTools:-Usage call with iterations set to 25 -- i.e. the total number of calls is 25 times the #GC number; GCAvgTime is the total time spent in gc returned by kernelopts(gctotaltime) divided by 25; CompTim is the difference between the cputime returned by Usage and the GCAvgT)

As you can see the timings are different at best and wildly different at worse. The algorithm is O(n^2) in the number of basic operations used although this is not as helpful as with fp operations as each operation is not performed in constant time.

I have no idea as to why the number of gc calls balloons in some runs and not others nor why this increase in calls makes the execution time go higher (rather than the time in the gc calls).

Any help gladly received.

p.s. Is there any `standard' way of measuring the complexity of intermediate expressions? Both the implementations I am comparing perform very poorly on certain input data; I assume that this is causes by some intermediate computations becoming very large and causing simplify to have to work very hard to get a more compact form. It would be interesting to know if/where this is happening in the two implementations.

@acer 

Many thanks for your detailed response. As you have probably gathered, I'm very new to Maple programming so much of what you say has gone over my head. However, I do now know where to start looking and will do some experimenting.

**** One other query, I use time() in the test rig to get execution times for comparison purposes and I print the max, min and average execution times over multiple runs. There is always quite a difference between the max and min times even when no other user programs are running. Is there a reason for this and/or a more accurate timing mechanism? 

@tomleslie 

Thanks for the response. I'm afraid the problem in 2. you found is due to 45+ years of Fortran! 

I made both sets of changes and I do now get comparably compact values in the inverse. The downside is that the execution time is now 100+ longer which wasn't what I was hoping for! I will try some experimenting with the ideas `acer' gives below.

Best wishes,

Tim