Re: Help B* and B+ Trees

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

Tarjei said

<<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.>>

Slight historical mismatch here. KV3 was written around 1970, when
memories were as fast as processors, and cache hit and miss times
were irrelevant since machines were typically uncached. I agree it
is FAR harder to get accurate timings these days. You did not even
mention TLB misses.

The point is that you still come much closer to the real world at this
level than at the O(N**2) comparisons counted level!

<<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).>>

Fine: you are actually strongly agreeing with me, so if you don't see this,
you did not quite understand my suggestion. 

Obviously you can't explain all timing differences at the high level
language level, because of the factors you mention, still you can
indeed come pretty close PROVIDING, and this is a very important PROVIDING,
you have a computational model of the language you are using. That is what
I meant by "adopting a very high level machine with known complexities ..
based on a subset of Ada or Pascal or C or whatever). The point is that
if you want to reference source code in understanding complexity, then
you must restrict the source code to operations for which you have some
reasonable understanding of their computational complexity (e.g. we 
do NOT want to include propagation of exceptions in the mix).

<<Then one can relate the time to the number of statements executed>>

Only if you have some idea of what it means to execute a statement in
terms of computational complexity!