A “linear logic” Quicksort
1994; Association for Computing Machinery; Volume: 29; Issue: 2 Linguagem: Inglês
10.1145/181748.181750
ISSN1558-1160
Autores Tópico(s)Distributed systems and fault tolerance
ResumoThe linear style of programming inspired by linear logic has been proposed to reduce garbage collection and synchronization costs in serial and parallel systems. We programmed Quicksort for both lists and arrays in a "linear" fragment of Lisp to estimate the performance impact of linearity on a serial machine. Even though Quicksort is well-tuned for current non-linear architectures, we find that linearity extracts no real penalty. Our "linear" list Quicksort is as fast as any non-linear list Quicksort, and our "linear" vector Quicksort is only 3.5% slower than a non-linear vector Quicksort. The linear style is moderately pleasant, and the redundancy of linearity checking can aid in finding bugs.
Referência(s)