Software Demonstration: New Memory Semantics for SACLIB

David G. Richardson and Werner Krandick

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.

The software demonstration will consist of the following three parts, and take approximately 20 minutes:

Efficacy of the new memory sub-system

  1. We compile a SACLIB application against SACLIB 2.1.
  2. We run the application using Valgrind.
  3. The output file generated by Valgrind shows that SACLIB has leaked 36 megabytes of memory when it was run.
  4. We compile the same SACLIB application against SACLIB 3.0 beta.
  5. We run the application using Valgrind.
  6. The output file generated by Valgrind shows the absence of memory leaks.

Efficiency of the new memory sub-system

  1. A suite of benchmarks will be run to measure the number of CPU cycles required to allocate, read, write, and de-allocate memory using the primitives of the SACLIB 2.1 and SACLIB 3.0 beta memory subsystems.
  2. The results of the benchmarks demonstrate compilers can avoid introducing any run-time overhead for the SACLIB 3.0 beta memory subsystem.

Backwards compatibility with SACLIB 2.1

  1. The differences between C and C++ linkage are demonstrated.
  2. We link a C program with SACLIB 3.0 beta.

References

1
Christopher W. Brown.
QEPCAD B: A program for computing with semi-algebraic sets using CADs.
SIGSAM Bull., 37(4):97-108, 2003.

2
Christopher W. Brown.
QEPCAD B: a system for computing with semi-algebraic sets via cylindrical algebraic decomposition.
SIGSAM Bull., 38(1):23-24, 2004.

3
G. E. Collins and R. G. K. Loos.
Specifications and index of SAC-2 algorithms.
Technical Report WSI-90-4, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, 1990.

4
George E. Collins 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.

5
George E. Collins and Hoon Hong.
Partial cylindrical algebraic decomposition for quantifier elimination.
Journal of Symbolic Computation, 12(3):299-328, 1991.
Reprinted in: B. F. Caviness, J. R. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Springer-Verlag, 1998, pages 174-200.

6
Electric Fence Developers.
Electric Fence.
http://www.pf-lug.de/projekte/haya/efence.php.

7
Hoon Hong, Andreas Neubacher, and Wolfgang Schreiner.
The design of the SACLIB/PACLIB kernels.
Journal of Symbolic Computation, 19(1-3):111-132, 1995.

8
IBM Corporation.
Rational Purify.
http://www-306.ibm.com/software/awdtools/purify/.

9
Werner Krandick and Kurt Mehlhorn.
New bounds for the Descartes method.
Journal of Symbolic Computation, to appear.

10
David G. Richardson and Werner Krandick.
Compiler-enforced memory semantics in the SACLIB computer algebra library.
In International Workshop on Computer Algebra in Scientific Computing, Lecture Notes in Computer Science. Springer-Verlag, 2005.
To appear.

11
Valgrind Developers.
Valgrind.
http://valgrind.kde.org.