SACLIB

The SACLIB [4,7] library of computer algebra programs, originally derived from SAC-2 [3], contains reference implementations of numerous algorithms and also forms the basis of the quantifier elimination systems QEPCAD [5] and QEPCAD B [1,2]. SACLIB 2.1 contains about 70,000 lines of C-code. However, the library contains a number of memory management defects, all of which occur outside of SACLIB’s garbage collector. Memory leaks involving dynamically allocated arrays can slow down and preclude computations. Such problems have been caused by SACLIB 2.1 routines for computations with real algebraic numbers [9]; the same routines are also used in quantifier elimination. While runtime-tools such as Valgrind [11], Electric Fence [6], and Purify [8] can be used to detect some memory defects, the tools cannot guarantee their absence. This is unfortunate because dynamic arrays are used extensively in weakly typed computer algebra systems such as SACLIB. We will demonstrate SACLIB 3.0 beta [10], a C++ port of SACLIB 2.1. SACLIB 3.0 beta features an improved memory subsystem that removes the potential for any 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 the arrays themselves responsible for their memory management, and enables the compiler to prevent other parts of SACLIB from managing array memory. Our innovations reduce the amount of code responsible for array memory management from 10,000 lines of code to 2,000 lines of code. Concept design and template metaprogramming allow the compiler to act as a theorem prover that ensures that SACLIB 3.0 beta builds only if the uses of the new memory management subsystem do not contain any memory leaks or double deletes. SACLIB 3.0 beta requires a C++ compiler to build. SACLIB 3.0 beta is source- and link-compatible with SACLIB 2.1. For users that wish to use SACLIB 3.0 beta from C programs, all SACLIB functions are available with C linkage. Such users will still have the potential for memory leaks and double deletes in their own C code. However, the SACLIB 3.0 beta functions are free of memory leaks and double deletes.


References in zbMATH (referenced in 23 articles )

Showing results 1 to 20 of 23.
Sorted by year (citations)

1 2 next

  1. Richardson, David: Efficient programming techniques for the SACLIB computer algebra library. (Abstract of thesis) (2009)
  2. Meikle, Laura I.; Fleuriot, Jacques D.: Combining Isabelle and QEPCAD-B in the Prover’s Palette (2008)
  3. Ajwa, Iyad A.: A case study of grid computing and computer algebra: parallel Gröbner bases and characteristic sets (2007)
  4. Brown, Christopher W.; Davenport, James H.: The complexity of quantifier elimination and cylindrical algebraic decomposition (2007)
  5. Nagasaka, Kosaku: Towards more accurate separation bounds of empirical polynomials. II (2005)
  6. Richardson, David G.; Krandick, Werner: Compiler-enforced memory semantics in the SACLIB computer algebra library (2005)
  7. Brown, Christopher W.: QEPCAD B: A program for computing with semi-algebraic sets using CADs (2003)
  8. Schreiner, Wolfgang; Mittermaier, Christian; Bosa, Karoly: Distributed Maple: Parallel computer algebra in networked environments. (2003)
  9. Tiwari, Ashish; Khanna, Gaurav: Series of abstractions for hybrid automata (2002)
  10. González-Vega, Laureano; Recio, Tomas: Industrial applications of computer algebra: Climbing up a mountain, going down a hill (2001)
  11. Khanin, Raya; Cartmell, Matthew: Parallelization of perturbation analysis: Application to large-scale engineering problems (2001)
  12. Ajwa, Iyad A.; Wang, Paul S.; Lin, Dongdai: Another attempt for parallel computation of characteristic sets (2000)
  13. Schreiner, Wolfgang; Mittermaier, Christian; Winkler, Franz: Plotting algebraic space curves by cluster computing (2000)
  14. Díaz, Angel; Kaltofen, Erich: FOXBOX: A system for manipulating symbolic objects in black box representation (1998)
  15. Di Blasio, P.; Temperini, M.: On subtyping in languages for symbolic computation systems (1997)
  16. Jebelean, Tudor: Using the parallel Karatsuba algorithm for long integer multiplication and division (1997)
  17. Jebelean, Tudor: Practical integer division with Karatsuba complexity (1997)
  18. Limongelli, C.: Exact solution of computational problems via parallel truncated $p$-adic arithmetic (1997)
  19. Wang, Paul S.: Tools for parallel/distributed mathematical computation (1997)
  20. Hong, Hoon: An efficient method for analyzing the topology of plane real algebraic curves. (1996)

1 2 next