AN ANALYSIS OF THE EFFECTS OF SPATIAL LOCALITY ON THE CACHE PERFORMANCE OF BINARY SEARCH TREES

Thomas B. Puzak, Chun-Hsi Huang

2006

Abstract

The topological structure of binary search trees does not translate well into the linear nature of a computer’s memory system, resulting in high cache miss rates on data accesses. This paper analyzes the cache performance of search operations on several varieties of binary trees. Using uniform and nonuniform key distributions, the number of cache misses encountered per search is measured for Vanilla, AVL, and two types of Cache Aware Trees. Additionally, concrete measurements of the degree of spatial locality observed in the trees is provided. This allows the trees to be evaluated for situational merit, and for definitive explanations of their performance to be given. Results show that the balancing operations of AVL trees effectively negates any spatial locality gained through naive allocation schemes. Furthermore, for uniform input, this paper shows that large cache lines are only beneficial to trees that consider the cache’s line size in their allocation strategy. Results in the paper demonstrate that adaptive cache aware allocation schemes that approximate the key distribution of a tree have universally better performance than static systems that favor a particular key distribution.

References

  1. Adelson-Velskii, G. and Landis, E. (1962). An algorithm for the organization of information. Doklady Akademii Nauk SSSR. English translation by Myron J. Ricci in Soviet Math.
  2. Bawawy, A., Aggarwal, A., Yeung, D., and Tseng, C. (2001). Evaluating the impact of memory system performance on software prefetching and locality optimizations. In 15th Annual Conference on Supercomputing, page 486.
  3. Bryant, R. and O'Hallaron, D. (2001). Computer Systems: A Programmer's Perspective. Prentice Hall Inc, New Jersey.
  4. Burger, D. and Austin, T. (2001). The SimpleScalar Tool Set, Version 2.0. SimpleScalar LLC.
  5. Chilimbi, T., Davidson, B., , and Larus, J. (1999a). Cacheconscious structure definition. In SIGPLAN 7899 Conference on Programming Languages Design and Implementation (PLDI 99).
  6. Chilimbi, T., Hill, M., and Larus, J. (1999b). Cacheconscious structure layout. In SIGPLAN 7899 Conference on Programming Languages Design and Implementation (PLDI 99).
  7. Chilimbi, T., Hill, M. D., and Larus., J. R. (2000). Making pointer-based data structures cache conscious. Computer Magazine, 33(12):67.
  8. Cormen, T., Leiserson, C., and Rivest, R. L. (1998). Intorduction to Algorithms. The MIT Press.
  9. Fix, J. (2003). The set-associative cache performance of search trees. In Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, page 565.
  10. Hallberg, J., Palm, T., and Brorsson, M. (2003). Cacheconscious allocation of pointer-based data structures revisited with hw/sw prefetching. In Second Annual Workshop on Duplicating, Deconstructing, and Debunking(WDDD).
  11. Havran, V. (1997). Cache sensitive representation for bsp trees. In Computergraphics 97, International Conference on Computer Graphics, page 369.
  12. Havran, V. (2000a). Analysis of cache sensitive representation for binary space partitioning trees. Informatica, 23(2):203.
  13. Havran, V. (2000b). Heuristic Ray Shooting Algorithms. PhD thesis, Czech Technical University.
  14. Iancu, C. and Acharya, A. (2001). An evaluation of search tree techniques in the presence of caches. In 2001 IEEE International Symposium on Performance Analysis of Systems and Software.
  15. Oksanen, K. (1995). Memory reference locality in binary search trees. Master's thesis, Helsinki University of Technology.
  16. Puzak, T. B. (2006). The effects of spatial locality on the cache performance of binary search trees. Master's thesis, The University of Connecticut.
  17. Sleator, D. and Tarjan, R. (1985). Self adjusting binary search trees. Journal ACM, 32:652.
  18. Weiss, M. (1999). Data Structures and Algorithm Analysis in JAVA. Addison-Wesley Longman Inc.
Download


Paper Citation


in Harvard Style

B. Puzak T. and Huang C. (2006). AN ANALYSIS OF THE EFFECTS OF SPATIAL LOCALITY ON THE CACHE PERFORMANCE OF BINARY SEARCH TREES . In Proceedings of the First International Conference on Software and Data Technologies - Volume 2: ICSOFT, ISBN 978-972-8865-69-6, pages 94-101. DOI: 10.5220/0001315900940101


in Bibtex Style

@conference{icsoft06,
author={Thomas B. Puzak and Chun-Hsi Huang},
title={AN ANALYSIS OF THE EFFECTS OF SPATIAL LOCALITY ON THE CACHE PERFORMANCE OF BINARY SEARCH TREES},
booktitle={Proceedings of the First International Conference on Software and Data Technologies - Volume 2: ICSOFT,},
year={2006},
pages={94-101},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001315900940101},
isbn={978-972-8865-69-6},
}


in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Software and Data Technologies - Volume 2: ICSOFT,
TI - AN ANALYSIS OF THE EFFECTS OF SPATIAL LOCALITY ON THE CACHE PERFORMANCE OF BINARY SEARCH TREES
SN - 978-972-8865-69-6
AU - B. Puzak T.
AU - Huang C.
PY - 2006
SP - 94
EP - 101
DO - 10.5220/0001315900940101