Article View: comp.lang.functional
Article #915Re: Is efficient backtracking feasible in functional languages?
From: Julian Seward (DRL PhD)
Date: Fri, 13 Nov 1992 09:54
Date: Fri, 13 Nov 1992 09:54
27 lines
1872 bytes
1872 bytes
Kevin Hammond writes: | The Haskell B. (and LML) implementations have (or had) some | interesting space leaks (as Dave Wakeling's profiler pointed out). | One of these was due to not "black-holing" closures when they were | entered (so retaining space if arguments to the original closure | became dead before the closure was fully evaluated). It sounds as if | this may be the problem reported with the Haskell B implementation. | The most recent implementation has compiler flags to fix the problems | which Dave Wakeling reported, but I think they're disabled by default | (black-holing costs time, for instance, which you may not want to | spend). I thought the 0.998.* versions of lml/hbc have blackholing *on* by default. Anyway, you can turn it on manually by issuing the flag -fzap-redex to lml or hbc. I suspect blackholing doesn't cost more than about 5% in performance terms, but it would be interesting for someone to quantify this. As I understand it, the Glasgow compiler maintains a stack of pointers to closures under evaluation, so the garbage collector can do the redex zapping, rather than impose that cost on the mutator. lml/hbc unfortunately has to zap every closure as it goes along, which is more expensive. Jules
Technical Details
Message-ID:
<SEWARDJ.92Nov13095450@r6a.cs.man.ac.uk>Path:
arc1-ca.pugleaf.net!sparky!uunet!mcsun!uknet!mucs!m1!sewardjReferences:
<TMB.92Nov12122350@arolla.idiap.ch> <1992Nov12.162725.25836@cs.yale.edu> <BxM80r.1Hu@dcs.glasgow.ac.uk>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!mcsun!uknet!mucs!m1!sewardj From: sewardj@cs.man.ac.uk (Julian Seward (DRL PhD)) Newsgroups: comp.lang.functional Subject: Re: Is efficient backtracking feasible in functional languages? Message-ID: <SEWARDJ.92Nov13095450@r6a.cs.man.ac.uk> Date: 13 Nov 92 09:54:50 GMT References: <TMB.92Nov12122350@arolla.idiap.ch> <1992Nov12.162725.25836@cs.yale.edu> <BxM80r.1Hu@dcs.glasgow.ac.uk> Sender: newsman@cs.man.ac.uk Organization: Department of Computer Science, University of Manchester Lines: 27 In-reply-to: kh@dcs.glasgow.ac.uk's message of 12 Nov 92 18:14:49 GMT