Daniel wrote:

>A. How do you find out the real relative costs of parts of an
>algorithm, in Squeak?

MessageTally>>spyOn: will perform statistical sampling on a block and 
provide a report of where the time is spent.  For example:

| a b c |
a := 1 / 3.
b := 1 / 5.
MessageTally spyOn: [
1 to: 5000 do:
	[:i | a := a + b]].

Results in:
----
 - 185 tallies.

**Tree**
100.0 Fraction +
  69.2 Fraction reduced
    |69.2 Fraction class numerator:denominator:
    |  67.6 primitives
  24.9 primitives
  5.9 Fraction class numerator:denominator:
    3.2 Fraction setNumerator:denominator:
    2.7 primitives

**Leaves**
70.3 Fraction class numerator:denominator:
24.9 Fraction +
4.9 Fraction setNumerator:denominator:
----

>It seems to me now that the big deal in Fraction arithmetic is the
>allocation, but I certainly wouldnt bet on it.

In the case above, you can see that your supposition is true: 70% of the 
time is spent allocating a new Fraction.


>B. Having decided you want to improve the performance of a specific
>feature, how do you go about devising good benchmarks, to find out
>whether you've succceded?
>Especially, to find out what parts of the system use that algorithm,
>and how?

Ah, now there's the really interesting problem.  For example, if we 
change our benchmark above just slightly:

| a b c |
a := 1 / 3.
b := 1 / 5.
c := 8 / 9.
MessageTally tallySends: [
1 to: 100 do:
	[:i | a := a + b. b := b * c]].


We get an entirely different result:

 - 3356 tallies.

**Tree**
55.8 Fraction +
  |49.3 Fraction reduced
  |  |44.3 Integer gcd:
  |  |  |25.6 LargePositiveInteger bitShift:
  |  |  |  |25.6 Integer bitShift:
  |  |  |  |  22.4 Integer digitRshift:bytes:lookfirst:
  |  |  |  |    20.4 primitives
  |  |  |11.2 LargePositiveInteger -
  |  |  |  |11.2 Integer -
  |  |  |  |  10.3 Integer digitSubtract:
  |  |  |  |    7.4 primitives
  |  |  |  |    2.4 SmallInteger bitAnd:
  |  |  |  |      2.4 LargePositiveInteger +
  |  |  |  |        2.4 Integer +
  |  |  |3.1 LargePositiveInteger \\
  |  |  |  |3.1 Number \\
  |  |  |2.2 Integer even
  |  |5.0 LargePositiveInteger //
  |  |  5.0 Integer //
  |  |    4.8 LargePositiveInteger quo:
  |  |      4.8 Integer quo:
  |  |        4.8 Integer digitDiv:neg:
  |  |          2.5 SmallInteger bitAnd:
  |  |            2.5 LargePositiveInteger +
  |  |              2.5 Integer +
  |  |                2.1 Integer digitSubtract:
  |3.3 Integer lcm:
  |  |2.4 Integer gcd:
  |  |  2.3 LargePositiveInteger \\
  |  |    2.3 Number \\
  |2.6 LargePositiveInteger /
  |  2.6 Integer /
  |    2.4 Integer digitDiv:neg:
44.2 Fraction *
  43.7 Fraction reduced
    39.8 Integer gcd:
      |25.1 LargePositiveInteger bitShift:
      |  |25.1 Integer bitShift:
      |  |  22.0 Integer digitRshift:bytes:lookfirst:
      |  |    20.1 primitives
      |8.1 LargePositiveInteger -
      |  |8.1 Integer -
      |  |  7.5 Integer digitSubtract:
      |  |    6.8 primitives
      |3.0 Integer even
    3.8 LargePositiveInteger //
      3.8 Integer //
        3.7 LargePositiveInteger quo:
          3.7 Integer quo:
            3.7 Integer digitDiv:neg:

**Leaves**
41.0 Integer digitRshift:bytes:lookfirst:
21.3 Integer digitSubtract:
6.4 Integer digitDiv:neg:
5.2 Integer even
4.8 LargePositiveInteger normalize
3.6 Integer bitShift:
3.5 Integer class new:neg:
2.4 Integer =
2.0 LargePositiveInteger digitAt:
----

So creating a good benchmark test requires that you know not only the 
approximate number and distribution of methods used, but also the 
distribution of data types.

You might be able to get some of this info by modifying the existing 
Fraction class methods to tally the message counts and data types while 
running whatever code you are interested in.



     -- tim