Lean Programs, Branch Mispredictions, and Sorting

详细信息    查看全文

• 作者：Amr Elmasry (1) elmasry@diku.dk
  Jyrki Katajainen (1) jyrki@diku.dk
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7288
• 期：1
• 页码：119-130
• 全文大小：222.9 KB
• 参考文献：1. Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, & Tools, 2nd edn. Pearson Education, Inc., Boston (2007)
  2. Biggar, P., Nash, N., Williams, K., Gregg, D.: An experimental study of sorting and branch prediction. ACM J. Exp. Algorithmics 12, Article 1.8 (2008)
  3. Brodal, G., Moruz, G.: Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms. In: Dehne, F., L贸pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 385R11;395. Springer, Heidelberg (2005)
  4. Floyd, R.W.: Algorithm 245: Treesort 3. Commun. ACM 7(12), 701 (1964)
  5. Harel, D.: On folk theorems. Commun. ACM 23(7), 379R11;389 (1980)
  6. Katajainen, J., Tr盲ff, J.L.: A Meticulous Analysis of Mergesort Programs. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol. 1203, pp. 217R11;228. Springer, Heidelberg (1997)
  7. Kernighan, B.W., Ritchie, D.M.: The C Programming Language, 2nd edn. Prentice Hall, Englewood Cliffs (1988)
  8. Mortensen, S.: Refining the pure-C cost model. MasterR17;s Thesis, Department of Computer Science. University of Copenhagen, Copenhagen (2001)
  9. Patterson, D.A., Hennessy, J.L.: Computer Organization and Design, The Hardware/Software Interface, 4th edn. Morgan Kaufmann Publishers, Burlington (2009)
  10. Sanders, P., Winkel, S.: Super Scalar Sample Sort. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 784R11;796. Springer, Heidelberg (2004)
  11. Sedgewick, R.: Algorithms in C++, Parts 1R11;4: Fundamentals, Data Structures, Sorting, Searching, 3rd edn. Addison-Wesley Publishing Company, Inc., Reading (1998)
  12. Williams, J.W.J.: Algorithm 232: Heapsort. Commun. ACM 7(6), 347R11;348 (1964)
• 作者单位：1. Department of Computer Science, University of Copenhagen, Universitetsparken 1, 2100 Copenhagen East, Denmark
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

According to a folk theorem, every program can be transformed into a program that produces the same output and only has one loop. We generalize this to a form where the resulting program has one loop and no other branches than the one associated with the loop control. For this branch, branch prediction is easy even for a static branch predictor. If the original program is of length κ, measured in the number of assembly-language instructions, and runs in t(n) time for an input of size n, the transformed program is of length O(κ) and runs in O(κt(n)) time. Normally sorting programs are short, but still κ may be too large for practical purposes. Therefore, we provide more efficient hand-tailored heapsort and mergesort programs. Our programs retain most features of the original programsR12;e.g. they perform the same number of element comparisonsR12;and they induce O(1) branch mispredictions. On computers where branch mispredictions were expensive, some of our programs were, for integer data and small instances, faster than the counterparts in the GNU implementation of the C++ standard library.