new implementation of modules + modules + top level

[Matthew Flatt]

For the past few months, I've been working on a from-scratch
implementation of Racket's macros, modules, and top-level. If you're
interested, see the "linklet" branch of

https://github.com/mflatt/racket

The word "linklet" refers to the simplified (relative to modules)
notion compilation, linking, and evaluation that's built into the
revised runtime system. A `linklet` is almost a `lambda`, but it
imports and exports variables instead of values. To put it another way,
a `linklet` is almost a `unit`, except that it doesn't support mutual
dependencies, and its compilation protocol supports cross-linklet
optimization (for cross-module optimization).

The macro expander, all module handling, and support for top-level
evaluation are implemented in Racket on top of linklets. That part is
in the "pkgs/expander" directory:

https://github.com/mflatt/racket/tree/linklet/pkgs/expander

The expander can build itself, and a tool in the "expander" directory
can extract the expander's implementation into a single linklet, which
is then embedded into the Racket runtime.

In the new implementation, 20k lines of well-organized Racket code
replace 35k lines of less organized C code. The expander's embedded
bytecode is roughly the same size as the compiled C code that it
replaces.

Although this new implementation works well enough to build the Racket
distribution, run DrRacket, and pass the core Racket tests, its
performance is not yet good enough to replace the current
implementation. Roughly, the new implementation uses x1.5 memory and
takes x1.5 to x3 as long to expand/compile/build programs. In absolute
terms, that seems pretty good for a 3-month-old, from-scratch
reimplementation of about 15% of `racket`, but it's not good enough to
impose on Racket users.

I'll continue trying to get this variant of Racket into shape.
Meanwhile, I enthusiastically welcome anyone who is interested in
helping to improve this expander and its performance. Bug reports are
welcome.

The new implementation of the expander is hopefully much easer to read
and modify than the old one, not just because it's written in Racket,
but because it's better organized. As an orientation, start with the
original repo,

https://github.com/mflatt/expander

which has "pico", "micro", "mini", and "demi" branches that build up to
the full expander. (Unfortunately, the jump from "demi" to the full
expander has become especially large.)

In case anyone gets as far as investigating performance, here are some
things to note relative to the old implementation:

* The old expander and compiler front-end are fused. When you use
`eval` or `compile`, then no fully expanded form is actually
generated; instead, bits of expanded code are converted to an
intermediate compiler representation as expansion proceeds, and that
fusion of expansion and compilation might be a significant shortcut.

* The new `compile` or `eval` not only fully expands a form before
compiling, it has an extra layer of compilation to convert from
modules (or top-level evaluation) to linklets.

* If you use `expand` on a module with the old expander, then it
always compiles the module body as well as expanding it. Compilation
is needed when the module contains a submodule that requires the
enclosing submodile, and so the old `expand` always compiles, just
in case. As a result, `expand` on a module can sometimes be faster
with the new implementation, because the new implementation is
lazier about compiling a module body.

These differences in structure account for some of the initial
performance differences. It's not clear how much the overall
performance difference depends on these factors, or how much it depends
(on or can be compensated by) other factors like different data
structures, algorithms, and the base performance of C versus Racket. I
can't help hoping that I've done something dumb in terms of performance
--- maybe the same dumb thing in the old and new expanders --- where
others will see and fix the problem just as soon as the code is
readable enough.

[Gustavo Massaccesi]

I skimmed https://github.com/mflatt/racket/blob/linklet/racket/src/racket/src/startup.inc
looking for things that look slow.

I noticed that the code uses many keyword procedures with optional
keywords. When all the keyword are used, the application is replaced
with an alternative without keywords. But when some of the keywords
are missing the generated code is slow and it has to check the
keywords at run time and it can't be inlined.

I think that extending the cases where a keyword procedure is expanded
during the macro expansion time will be useful, but I don't know if it
will be very useful. Anyway, if someone improves this it will be also
useful for other racket programs, so I make here an official feature
request for someone that is more familiar with the code.
https://github.com/racket/racket/blob/master/racket/collects/racket/private/kw.rkt

Gustavo

PS: Just a warning about startup.inc. That code is only expanded and
demodularized, so it has some silly parts like (if #f (something)
(void)) that are removed later during the optimization phase.

> --
> You received this message because you are subscribed to the Google Groups "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/57a4ce4c.8e87620a.6e604.c47fSMTPIN_ADDED_MISSING%40gmr-mx.google.com.
> For more options, visit https://groups.google.com/d/optout.

[Matthew Flatt]

Thanks for investigating!

I don't think it's a question of an optional keyword argument being
present. A call to a statically recognized (at expansion time)
keyword-accepting function is replaced with a call to a plain function
where every keyword argument is represented along with a boolean to
indicate whether the value is actually supplied.

As expanded, the expansion takes the form

(if (variable-reference-constant? (#%variable-reference
the-keyword-function))
(the-keyword-function-as-a-plain-function ....)
(apply-keyword-function the-keyword-function ....))

Usually, the optimizer discharges the `(variable-reference-constant?
...)` check statically, so that only the plain-function call is left.

It turns out that a function definition with only *required* keyword
arguments interferes with the `(variable-reference-constant? ...)`
optimization. That's because the definition expands to

(define the-keyword-function
(make-required 'the-keyword-function
(lambda (arg ...) ....)
....))

and the optimizer can't tell that `make-required` will always succeed
without referencing later definitions. So, there's definitely room for
improvement there, and I'll think about how to improve the handling of
functions with only required keyword arguments.

Still, if I have it all right, the penalty for now should be just an
extra `variable-reference-constant?` check at run time; after that
check, the call should still take the fast, direct path. I didn't
measure any speed-up from making required keyword arguments optional to
avoid the check.


FWIW, I've added a `decompile` target to the makefile in
"pkgs/expander", which should make it easier for anyone to see the
flattened and optimized form of the expander.

You may notice that the decompiled code includes some unused functions
for parsing keywords, such as `unpack11.1$1`. That's because the
dead-code pass in the resolver just discards functions like
`module-path-string?12.1` that have no references, but it doesn't
currently perform a GC that would discard `unpack11.1$1` after its only
reference in `module-path-string?12.1` is gone. There's not yet a
dead-definition GC because it wasn't so useful in the module world,
where even unexported definitions can become accessible via
`module->namespace`.

> https://groups.google.com/d/msgid/racket-dev/CAPaha9NvjU-9wuCqZZLMesou1on8H-7P%
> 3Da3ZBjiQmQpHsj2uaA%40mail.gmail.com.