Walking a Binary Tree

• Speed of walking a binary tree is limited by raw access time to main memory.

  • No pipelining, no unrolling, no pre-fetch.
  • Caches don’t help much.

• Binary tree’s memory-wait penalty accounts for 65% of runtime on R8000. Worse on Origin2000.

• Can’t live without space partitioning, alternative is massive O(n) search, X slower.

Previous slide

Next slide

Back to first slide

View graphic version