Re: Help B* and B+ Trees

["Tarjei T. Jensen" <tarjei@online.no>]

I suppose we more or less agree.

Robert Dewar wrote:
> 
> I strongly disagree. I don't think exact evaluation of concrete complexity
> at the machine cycle level is relevant to Knuth's work, so I agree it would
> have better been left out. BUT, given that he wanted to address this, then
> using a concrete machine is the only way of doing things. Yes, he could
> certainly have used a real machine instead of MIX, though I don't think
> there was any very good choice at the time.

And how do you propose to get cache hit and misses into this? It is a
time since I read about the implementation of Mix. I doubt that the
implementation takes into account internal pipelining and the effect of
cache hits and misses which we would normally have in a real system.

The only way I can see we can get this into the equation is to use real
computers. E.g. time the same code on a 386, 486 (with and without
cache) and various pentiums (with cache and without cache).

> I strongly disagree with the notion that the same results can be obtained
> using high level languages. You are FAR too dependent on vagaries of
> compilers and are likely to be measuring glitches in code generation,
> rather than fundamental differences in computation complexity if you do this.

It would be silly to teach algorithms that way. When dealing with
algorithms one should constrain oneself to timing the execution of the
algoritm. If neccessary repeat the execution enough times to obtain a
meaningful result.

Then one can relate the time to the number of statements executed. The
object of the exercise would be to make the student able to estimate
relative execution time of an algoritm.

Analyzing the generated code is something that should be done in a
microprosessor architecture or compiler architecture course.

> In my graduate course on microprocessor architecture at NYU this last
> semester, I gave as a project picking one particular issue and investigating
> efficienty issues at the machine level, e.g. multiple if's compared to
> a case jump table, or inlining on/off, or the value of hardware integer
> multiplication. It is amazing how much compilers got in the way of these
> projects by generating strange stuff. Nearly everyone had to significantly
> modify the compiler ASM output to get meaningfule unbiased results.

That is as it should be for a microprocessor architechture or compiler
architecture course. It becomes interesting to ask why the compiler
generates this or that code and what the effects of doing things
differently would be. In an algorithm course this only confuses.

> Probably the best approach is to adopt a very high level machine with
> known complexities for its high level operations (this could be based on
> a subset of Ada or Pascal or C or whatever). This at least would allow
> one to avoid the gross distortion that comes from, e.g. only counting
> comparisons in a sort.

I don't see how this reflects the real world where a compiler writer may
want to keep jumps within the instruction pipeline or obtain a cache
hit.

I still want to time the algorithm and then explain the time differences
with references to the source code. I see no point in complicating
matters by decoding compiler output (unless the result is confusing).

Greetings,

-- 
// Tarjei T. Jensen 
//    tarjei@online.no || voice +47 51 62 85 58
//   Support you local rescue centre: GET LOST!