Advertisement

Compiler-Enforced Memory Semantics in the SACLIB Computer Algebra Library

  • David G. Richardson
  • Werner Krandick
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3718)

Abstract

We present a memory management subsystem for the computer algebra library SACLIB that removes the potential for memory leaks or double deletes in applications using the system. The system encapsulates the management of arrays that are allocated on the heap or on the system stack. The system makes arrays responsible for their own memory management, and enables the compiler to prevent other parts of SACLIB from managing array memory. To prove that our memory module and all applications using it are leak free and double delete free we introduce a new iterator concept and implement a model of that concept using generic programming techniques such as template meta-programming. Our innovations reduce the amount of code responsible for array memory management from 10,000 lines of code to 2,000 lines of code. Using hardware performance counters we show optimizing compilers are capable of avoiding any runtime overhead.

Keywords

Memory Management Return Type Double Delete Runtime Overhead Void Function 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Collins, G.E., et al.: SACLIB User’s Guide. Technical Report 93-19, Research Institute for Symbolic Computation, RISC-Linz, Johannes Kepler University, A-4040 Linz, Austria (1993)Google Scholar
  2. 2.
    Hong, H., Neubacher, A., Schreiner, W.: The design of the SACLIB/PACLIB kernels. Journal of Symbolic Computation 19, 111–132 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Collins, G.E., Hong, H.: Partial CAD contruction in quantifier elimination. Technical Report OSU-CISRC-10/89 TR45, Computer Science Department, Ohio State University (1989)Google Scholar
  4. 4.
    Hong, H.: An improvement of the projection operator in cylindrical algebraic decomposition. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 261–264. ACM Press, New York (1990)CrossRefGoogle Scholar
  5. 5.
    Hong, H., Liska, R., Steinberg, S.: Testing stability by quantifier elimination. Journal of Symbolic Computation 24, 161–187 (1997)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Brown, C.W.: QEPCAD B: A program for computing with semi-algebraic sets using CADs. SIGSAM Bulletin 37, 97–108 (2003)zbMATHCrossRefGoogle Scholar
  7. 7.
    Brown, C.W.: QEPCAD B: A system for computing with semi-algebraic sets via cylindrical algebraic decomposition. SIGSAM Bulletin 38, 23–24 (2004)CrossRefGoogle Scholar
  8. 8.
    Krandick, W., Mehlhorn, K.: New bounds for the Descartes method. Journal of Symbolic Computation (to appear)Google Scholar
  9. 9.
    Valgrind Developers: Valgrind, http://valgrind.kde.org
  10. 10.
    Electric Fence Developers: Electric Fence, http://www.pf-lug.de/projekte/haya/efence.php
  11. 11.
    IBM Corporation: Rational Purify, http://www-306.ibm.com/software/awdtools/purify/
  12. 12.
    Alexandrescu, A.: Modern C++ Design. Addison Wesley Longman, Inc., Amsterdam (2001)Google Scholar
  13. 13.
    Abrahams, D., Gurtovoy, A.: C++ Template Metaprogramming. Addison Wesley Longman, Inc., Amsterdam (2005)Google Scholar
  14. 14.
    Vandevoorde, D., Josuttis, N.M.: C++ Templates. Addison Wesley Longman, Inc. (2003)Google Scholar
  15. 15.
    Musser, D., Schupp, S., Loos, R.: Requirement oriented programming concepts, implications, and algorithms. In: [14], pp. 12–24Google Scholar
  16. 16.
    Musser, D.R., Shao, Z.: Concept use or concept refinement: An important distinction in building generic specifications. In: George, C.W., Miao, H. (eds.) ICFEM 2002. LNCS, vol. 2495, pp. 132–143. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  17. 17.
    Schupp, S., Loos, R.: SuchThat—Generic programming works. In: [42], pp. 133–145Google Scholar
  18. 18.
    Gregor, D., Schupp, S., Musser, D.: Design patterns for library optimizations. Scientific Programming 11, 309–320 (2003)Google Scholar
  19. 19.
    Schupp, S., Gregor, D., Musser, D., Liu, S.: Semantic and behavioral library transformations. Information and Software Technology 44, 797–810 (2002)CrossRefGoogle Scholar
  20. 20.
    Schreiner, W., Danielczyk-Landerl, W., Marin, M., Stöcher, W.: A generic programming environment for high-performance mathematical libraries. In: [42], pp. 256–267Google Scholar
  21. 21.
    International Standards Organization: ISO/IEC 14882:2003: Programming languages—C++ (2003), http://www.iso.org
  22. 22.
    Stroustrup, B.: The C++ Standard: Incorporating Technical Corrigendum No. 1. John Wiley and Sons, Chichester (2003)Google Scholar
  23. 23.
    Josuttis, N.M.: The C++ Standard Library. Addison Wesley Longman, Inc., Amsterdam (1999)Google Scholar
  24. 24.
    Kernighan, B.W., Ritchie, D.M.: The C Programming Language, 1st edn. Prentice-Hall, Englewood Cliffs (1978)Google Scholar
  25. 25.
    Innovative Computing Laboratory: PAPI, http://icl.cs.utk.edu/PAPI
  26. 26.
    Sutter, H.: Exceptional C++. Addison Wesley Longman, Inc., Amsterdam (1999)Google Scholar
  27. 27.
    Parnas, D.: On the criteria to be used in decomposing systems into modules. Communications of the ACM 5, 1053–1058 (1972)CrossRefGoogle Scholar
  28. 28.
    Sutter, H.: More Exceptional C++. Addison Wesley Longman, Inc., Amsterdam (2001)Google Scholar
  29. 29.
    Meyers, S.: Effective STL. Addison Wesley Longman, Inc., Amsterdam (2001)Google Scholar
  30. 30.
    Meyers, S.: Effective C++, 2nd edn. Addison Wesley Longman, Inc., Amsterdam (1997)Google Scholar
  31. 31.
    Stroustrup, B.: The C++ Programming Language (Special Edition). Addison-Wesley, Reading (2000)Google Scholar
  32. 32.
    Stroustrup, B.: The Design and Evolution of C++. Addison-Wesley, Reading (1994)Google Scholar
  33. 33.
    Austern, M.H.: Generic Programming and the STL. Addison Wesley Longman, Inc., Amsterdam (1998)Google Scholar
  34. 34.
    Boost: Boost libraries and documentation, http://www.boost.org
  35. 35.
    Veldhuizen, T.L.: Arrays in blitz++. In: Caromel, D., Oldehoeft, R.R., Tholburn, M. (eds.) ISCOPE 1998. LNCS, vol. 1505, pp. 223–230. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  36. 36.
    Czarnecki, K., Eisenecker, U., Glück, R., Vandevoorde, D., Veldhuizen, T.: Generative programming and active libraries. In: [42], pp. 25–39Google Scholar
  37. 37.
    Czarnecki, K., Eisenecker, U.: Generative Programming: Methods, Tools, and Applications. Addison-Wesley Professional, Reading (2000)Google Scholar
  38. 38.
    GNU: The GNU Compiler Collection, http://gcc.gnu.org/
  39. 39.
    Intel Corporation: The Intel C++ Compiler, http://www.intel.com/software/products/compilers/clin/
  40. 40.
    International Standards Organization: ISO/IEC 9899:1999: Programming languages—C (1999), http://www.iso.org
  41. 41.
    British, S.I.: The C Standard: Incorporating Technical Corrigendum 1. John Wiley and Sons, Chichester (2002)Google Scholar
  42. 42.
    Jazayeri, M., Musser, D.R., Loos, R.G.K. (eds.): Generic Programming: International Seminar on Generic Programming. LNCS, vol. 1766. Springer, Heidelberg (2000)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • David G. Richardson
    • 1
  • Werner Krandick
    • 1
  1. 1.Drexel UniversityPhiladelphiaU.S.A.

Personalised recommendations