Re: Help B* and B+ Trees

[dewar@merv.cs.nyu.edu (Robert Dewar)]

Tarjei said

<<Not really. Any computer will suffice. If he had used Pascal like he did
with TeX and Metafont (I would of course prefer Ada 95) it would be
simple for any user to discover the differences. Pascal compilers are
widely available and it would be simple for interested parties to type
in the examples and analyze the results.

I believe he used mix simply because he likes bit twiddling. I don't
mind that, it just makes the books less readable and longer than they
could have been.
>>


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.

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.

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.

"it would be simple for interested parties to type in the examples and analyuze
the results"

FAR from simple, you have to look at, and fix up, the generated assembly
language.



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.

P.S. I once proposed the following minimal-number-of-comparisons
sorting routine to Knuth, and asked him why it did not qualify for
his chapter on sorting thtat considers only number of compares:


1. Get number of items to sort

2. Enumerate all possible decision trees corresponding to this number,
   and pick the one with the smallest number of levels.,

3. Sort using this decision tree

Only step 3 involves comparisons of the data elements

(of course there is rather a lot of uncounted book keeping in step 2 :-)

(he never replied :-) :-)