[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hou
From: |
Alan Post |
Subject: |
Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours |
Date: |
Mon, 29 Nov 2010 10:58:05 -0700 |
On Sat, Nov 27, 2010 at 11:55:21PM +0100, Felix wrote:
> >
> > Reviewing the output from -debug 2, and rereading R5RS's
> > documentation on letrec, I've reworked the compiler and moved
> > the lambda that was being created for each use of a letrec variable
> > to the definition: '(record (lambda () ...)' rather than (record ...).
> > I changed the appearance of 'record' in other letrec definitions to
> > '(record)' rather than '(lambda () record)'.
> >
> > Essentially, I'm definining a lambda for each element in the letrec
> > (~880 elements) rather than for each usage (many, many more than
> > 880).
> >
> > The file now compiles in minutes rather than hours, and it is
> > roughly 7MB in size, rather than 61MB.
> >
> > I haven't checked this change in yet, as my left/right recursion tests
> > now fail and I broke any non-terminal where memoization is turned off:
> > This change was a proof of concept that I now need to clean up.
> >
> > However, things are looking good. I'll report back after I've
> > cleanup up and checked in all the code to confirm that everything is
> > working. So far, this does look like the culprit.
> >
>
> Excellent. Please keep us up to date about this.
>
I've just put together a prototype that I think will work for this
situation. It allows me to use generators that run only once to
initialize the non-terminal parser productions, and allows me to
recursively define connections between these routines without
generating a lambda expression for every reference to a letrec
record. The basic idea is that I'll wrap my letrec in a let,
which contains cons cells. I'll pass these cons cells around,
but only use the car/cdr of the cell, which is defined after the
grammar:
; a terminal rule matches input, it doesn't refer to other
; records
;
(define (terminal name char)
(pretty-print `(terminal ,name))
(lambda ()
(pretty-print `(terminaling ,name))
char))
; this is a mock-up of a production that calls another rule.
;
(define (generate name rule)
(pretty-print `(generating ,name))
(lambda ()
(pretty-print `(calling ,name))
(rule)))
; rather than generating a lambda for each reference, generate
; a fetch routine for each definition of a rule.
;
; This is the piece that should result in lower compile-time.
;
; I may need one fetch* routine per record, we'll see.
;
(define (fetch name rule)
(pretty-print `(fetch ,name))
(lambda ()
(pretty-print `(fetching ,name))
((cdr rule))))
(define grammar
; create a location for storing references to records. There
; is one -cache for each record.
;
(let ((foo-cache (list '()))
(bar-cache (list '()))
(baz-cache (list '())))
; generate recursive definitions. These could be mutually
; recursive if I wanted a more complex example.
;
; note that as I generate rules, I pass the cons cell of
; the -cache around. I really want the car/cdr, but I
; don't have that definition yet.
;
(letrec ((foo (generate "foo" (fetch "bar" bar-cache)))
(bar (generate "bar" (fetch "baz" baz-cache)))
(baz (generate "baz" (terminal "baz" "0"))))
; now that I've defined my grammar, update the -cache
; objects with the actual record definition.
;
(set-cdr! foo-cache foo)
(set-cdr! bar-cache bar)
(set-cdr! baz-cache baz)
; and return the grammar
;
foo)))
; as normal, run the parse
;
(pretty-print (grammar))
I haven't modified the compiler yet to test this, but it seems like
it should work to reduce the number of lambda expressions that are
generated.
I may not be able to make this change today, but I'll report back
the result after I do.
Did you have a chance to look at the '-debug bosp' stuff? I'm
curious to benefit from your expert eye, if you'd still like to do
that.
-Alan
--
.i ko djuno fi le do sevzi
- [Chicken-users] compiling jbogenturfa'i .scm => .c takes 2.5 hours, Alan Post, 2010/11/26
- [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Alan Post, 2010/11/26
- [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Alan Post, 2010/11/26
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Felix, 2010/11/27
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Alan Post, 2010/11/27
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Alan Post, 2010/11/27
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Alan Post, 2010/11/27
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Felix, 2010/11/27
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours,
Alan Post <=
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Felix, 2010/11/29
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Alan Post, 2010/11/29
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Felix, 2010/11/30
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Alan Post, 2010/11/30
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Felix, 2010/11/27
- Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours, Alan Post, 2010/11/27