On Sun, 30 Sep 2001, Lex Spoon wrote:

>
> On disk, the exact number of dereferences makes a big difference.  With

Its the number and the predictability of the dereference. If you can
preload it, it doesn't matter. In this case, the cost of loading 16 bytes
versus 16k is so little, that its faster to load the 16k, do 10 binary
tree comparisons, than do 10 disk seeks.

> a binary tree, you divide your search space by 2 with each dereference;
> with a btree, you divide it by a larger number.  I'd guess it's similar
> for skip lists, though I've only heard about them, not studied them.
>

> Hmm, with "main" memory being so much slower than cache, btrees might
> even start making sense for in-memory structures.  But not necessarily

Nope. Most cachelines are 16 bytes.. You pay a lot more with the extra
comparisons. Nor do you save anything with teh ability to prefetch; you
cannot predict which branches you'll need. You might get semi-close with
splay trees though, because they can use locality of access, so the
effective number of accesses is much better.

I'll probably eventually implement them.

> for Squeak, where an "array of foo's" won't necessarily have all of the
> foo's next to each other, anyway, and thus where accessing items within
> a node still causes fetches to distant parts of memory.

Distant parts don't hurt; cache lines are 16 bytes. The closest they could
get to hurting is if they hit the TLB too heavily. (TLB for x86 has 64
entries for 4kb pages. Or, 256k. access outside that costs about 3 memory
lookups to read in the new page table entry for that 4kb. PTE lookups can
be cached.)

>
> Anyway, I'd rather work on something higher-level.  This
> hyper-optimization stuff is only useful on small portions of most of the
> programs I ever work on.

Exactly.. The O(log n) will beat your O(n) every time you start getting a
lot of data. If it does in profiling, then implement the O(log n)
algorithm, and contribute it.


Don't discount profiling.. Profiling has found out places in my network
stream library where invoking #origionalContents instead of #contents sped
it up by 3x,


And this little beauty: fidding with one line of code has lead to speedups
of 30% in the queueing code.

I found out that:
   ``readPosition  > (writeLimit/2)'' is about 30 times slower than
   ``readPosition * 2 > writeLImit''
(if writeLimit is randomly distributed. If writeLimit is always odd, its
60x.)

Which was the absolute last thing I expected to be consuming 20% of my
CPU time. Profiling is useful, use it. :)

Scott


--
No DVD movie will ever enter the public domain, nor will any CD. The last CD
and the last DVD will have moldered away decades before they leave copyright.
This is not encouraging the creation of knowledge in the public domain.