Deutsch-Schorr-Waite algorithm

sepp@cs.tu-berlin.de (Maximilian Spring)
Thu, 30 Mar 1995 09:38:04 GMT

          From comp.compilers
Related articles
Deutsch-Schorr-Waite algorithm sepp@cs.tu-berlin.de (1995-03-30)
| List of all articles for this month |
Newsgroups: comp.compilers
From: sepp@cs.tu-berlin.de (Maximilian Spring)
Keywords: GC, storage, question
Organization: Technical University of Berlin, Germany
Date: Thu, 30 Mar 1995 09:38:04 GMT

In the mark phase of a mark-sweep garbage collector I use the
Deutsch-Schorr-Waite algorithm for a non-recursive traversal of the
live heap objects. Now I want to speed up the mark-phase by
implementing a last-call optimization. But I find only solutions
where I need additional stack space :-(.


I have read in "Speicherbereinigung fuer Prologsysteme"
(engl. "Garbage collection for Prolog Systems"), U. Neumerkel, Vienna
(URL http://www.complang.tuwien.ac.at./ulrich/dipl/D-3.html.gz),
that M. Broy & P. Pepper in "Combining algebraic and algorithmic
reasoning: an approach to the Schorr-Waite algorithm", ACM TOPLAS,
4 (3), 362-381, July 1982, remark explicitly that the Last-call optimization
could be used within the Deutsch-Schorr-Waite algorithm.


Does anyone have experiences with that?


Bye,
Max.




P.S. Ok, I'll get the later paper...
--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.