Oct 14, 2021

Performance Benchmarks on Nlisp

So far, I've studied the tutorial on creating a toy interpreter using libgccjit, and the examples for gnu lightning and libjit. Libjit abstracts away the little details of assembly coding.

The Boyer and Btree (aka GCbench) benchmarks reveals nlisp spents up to 80% of its time in the garbage collector, GC, under heavy loads.

In the btree.l, "binarytrees:", test, (nlisp -L btree.l 16), the profiler shows nlisp spent about 25% of its time in the GC. For a larger tree traversals, (nlisp btree.l 17), the profiles shows nlisp spent greater than 80% of its time in the GC. This degradation of performance is due to the GC repeatedly trying to allocate more memory, and continually traversing long trees to mark each accessible cell. As each cell segment gets larger, it will take an exponentially longer time to complete a sweep of the unmarked cells. The compaction of vector segments did not impact performance too much as it took only 2% of the running time.

In the future, I may try to implement a 3-color scheme on top of the mark-and-sweep which might be the perfect fit for nlisp. (ref: Mike Pall's New-Garbage-Collector).


Sept 29, 2021

A Little Review on Implementing JIT for Mlisp

Now, I seem to be sliding backwards when trying to move forwards developing a design for Mlisp. What's becoming clear to me now is that I could not develop a JIT without a virtual machine. That's the reason I gave up on the old nlisp which had no byte code compiler. It would be hard to come up with a simple way to write advanced procedures without embedding sub-procedures or subroutines within higher level procedures. For example, recursion fits within an execution model using the virtual machine. The lambda function defines a way to build procedures up from the integration of smaller sub-procedures. It's almost as if a fuller lambda expansion necessarily required the dispatching function of a virtual machine.

And that's the machine. That's what all the little parenthesis, ie./eg., (*(!*(%(&^(&^%$(**)*&^).....)))) are about. Might seem obvious in retrospect, but is necessary maybe to think about now.

David Betz's stack oriented Xlisp and hence Mlisp have a lot in common with Maclisp. Maclisp had it's origin in Scott Fahlmann's Spice lisp which led to CMUCL and SBCL. I spent some time reading the old code in CMUCL this weekend. It's amazing software considering it was written in the early 1980's when the C-language was still not in wide spread use. CMUCL was designed for special computers with its own microcode. The more modern CMUCL's virtual machine was written in C with a design which is rather a standard way VM's for lisp are written today. What's incredible to me is that it uses an "implicit continuation representation" (in ref: Design of CMU Common Lisp) design in its compiler. There's a well written story on this in Gabriel and Steels's "Evolution of Lisp", section 2.8, Scheme: 1975-1980. Scheme's continuation model can actually simplify the construction of lisp compilers. My interpretation of this is that "context", especially temporal, time ordered context (or "aka" continuations) is a necessary requirement for a descriptive language. Continuations is analogous to an operating system's context switches.

CMUCL and SBCL uses the ideas for continuation in its compiler, but never implemented continuations in the language itself. This makes sense because in practical applications today, the use of continuations is still not as efficient relative to using coroutines or threads. The Ruby language implemented continuations, but now makes it available only as an installation option. Practical languages like Ocaml versus SML/NJ do not have continuations. This perfectly fits the usage of the language. But for writing languages with greater descriptive powers, parallel processing algorithms maybe required due to the associative capabilities required in a short temporal intervals characteristic of spoken languages.

In the next couple of days I'll probably continue reading "From Folklore to Fact: Comparing Implementations of Stack Continuations" and "Implementation Strategies for First-Class Continuations". This is "where the rubber meets the road" as they say. Moving forward on Mlisp's JIT would parallel work like using GNU-Lightning in speeding up Smalltalk. Trying to create a specific design plan for this has me really absorbed.


Sept 15, 2021

Selecting the JIT Tool

I've been thinking about a JIT tool for developing mlisp for about a month, and during the last couple of days it's become obvious to me that I should try GNU Lightning first. This is because Lightning was originally designed to speed up Smalltalk's context switching between objects. Smalltalk objects are the counterpart to Lisp procedures with respect to the language's internal virtual machine. Both objects and procedures require the same kind of contextual management of its arguments and values. And in many instances these kinds of language implementations uses stacks to track of objects or procedures.

Lightning explicitly refers to continuations in the section on setting up procedures (ie., trampolines, continuations and tail call optimization). This is at the core of what JIT for mlisp is about.

The challenge for me is to implement JIT efficiently so that mlisp will run the ctalk benchmark, for example, as fast as possible. Most scheme implementations don't consider fast execution of continuations critical. In my opinion, if you want to create a machine which understands language, with all the complexity of words in its context, then fast context switching with continuations is essential.

So I'm focusing my attention now on Lightning, and will focus to a lesser extend on libgccjit or luajit's dynasm for now. I don't seem to have the time to looking into the Smalltalk's implemention of Lightning, nor maybe Ruby's JIT. The horizon for languages using objects like Smalltalk and Ruby shines bright, but they're intrinsically inefficent because of their exaggerated requirement to explicitly depend on object linkages (in the form of inheritance). But as time passes, the evolution of programming languages will follow Smalltalk's original design concept, and that's the same for mlisp, in my opinion.


Sept 11, 2021

The Nbody Benchmark

                        (time in seconds)
 # of particles      chez      sbcl      luajit
 
  5000              0.15s      0.14s      0.01s
  500000            1.54s      0.22s	  0.16s
  5000000           14.6s      0.98s      1.44s
  50000000           188s      8.14s      14.5s

This is an extremely interesting computationally intensive benchmark.
SBCL and Luajit were notably robust at 50 million particles.

The Luajit language implementation is extremely efficient. Most notable is its small size, and simplicity. It's a model implementation of a programming language for mlisp to try to follow.


Sept 9, 2021

States or Values, Ordered Sequences, and Procedures

The intuitive model that I follow for thinking about context switching using continuations comes from temporal sequences describing physical processes. For me, a simple description of a computational processes requires keeping track of a procedure's calculation within an "environment" for the procedure which includes its arguments, and also all of the data or states which can be associated its arguments. The procedure can become enfolded in the global data environment which is the context in which all computation occurs.

It's worth reading formal descriptions of using continuations to get a perspective on how wide the applications of continuation is. For example, John Reynolds' article "Definitional Interpreters for Higher-order Programming Languages" (1998), is a concrete explanation on continuations. The article provides one a really good background on continuations. This article explains relationships between "embedding continuations in values", and how procedures can occur as values.

How procedures occur as values in a programming language is a key idea.


Sept 3, 2021

Continuations

Conceptually, I like using first class or full continuations for asynchronous event handling. Using continuations is not hard if you can keep things simple. Modelling the real world events requires asynchronicity. Thus in a rather insane fashion I'm leveling anything that gets in the way of continuations. This includes exception handling with throw/catch and unwind-protect for now. This does mean I won't go back to using these special operators in some form in the future if there's a simple way to do so. (Ref: Kent Pitman's comments on unwind-protect versus continuations.)


August 25, 2021

Mlisp JIT - Now The Tedious Coding

Moving to add native compilation to Mlisp requires spending more time on the bytecode interpreter. So I'm archiving Nlisp-0.3 for now. The complexity of Mlisp-0.7's coupled continuation/gc code requires me to still strip away alot of the continuation dispatch structures. So I'm not going to develop jit for Mlisp-0.7. Instead I'm using the latest Mlisp-0.6 lisp which I'll call Nlisp-0.4 to develop jit on. This jumping between lisp versions might seem messy, but there's still too much bugs (and complexity) in the continuation/gc part of the current Mlisp-0.7 for me to develop jit on.

Currently, the opcode tracing in Nlisp-0.4 still has lots of problems. It may take a couple of weeks for me to get this working correctly. In the mean-time I've been trying to understand how libgccjit works in gccemacs. Since the jit is complex and does lots of optimizations this might be a good tool to look into. The performance gains using libgccjit on emacs is almost 4 times (not the 10x boost I was hoping for :-)).

  A good reference is the gccemacs wiki page.
     ___________                        _____________
    |_byte code_| --->  libgccjit ---> |_native code_|


August 16, 2021

The Plan for Mlisp JIT

Mlisp is currently a bytecode compiler. What we need to do is get Mlisp to translate the byte-code to machine-code, or "mcode" (versus "bcode"), on the fly. The Mlisp module make_code_string produces what is call a "byte code string" (it's also commonly referred to as a "code vector") for execution. It was called a code "string" because the Mlisp variable bcode was typed as a unsigned string, ("ucstr bcode;"), in Mlisp.

So in essence we want to change make_code_string to be a make_mcode_string. The final code object for execution would be a machine code string. This means we have to used the X86 assembler for our machine whcih runs the linux operating system. The assembler I'll use is gas. I don't know if all this will work yet because I've never done this before. But I'm laying out a plan to produce machine code vectors. I don't know how far I'll get.


August 13, 2021

JIT for Mlisp

The lisp implementations which are fast are SBCL, Clozure and Chez. I've never looked at the source code for these implementations yet because I don't have a background in JIT or just-in-time compilation. The Chicken Scheme implementation is also fast but does a static compilation from Scheme to C code. The source code for Scheme2c looked pretty messy to me, and JIT toolkits like libJIT seems as if it'll be too much work for me to try to use.

However, I feel that Mlisp might be able to run the CTAK benchmark in the speed range of Chez if it used a JIT to compile its functions or procedures. Mike Pall's luaJIT project was amazing since it boosted Lua's speed by an order of magnitude. I'm starting to feel that I should study or use the methodology of luaJIT to increase Mlisp's execution speed.

Mlisp is a compact bytecode implementation originally written by David Betz. The theoretical design philosoply is essentially very simple, but its implementation is complicated because its components parts like context execution (continuations), code evaluation and garbage collection are really tightly coupled together. But I feel there's essential beauty and capabilities in Mlisp which makes it deserve a JIT compiler for its procedures. So in the future months or years, I might be working towards this goal. I've not spent too much time on this project lately, but getting this done requires this. But I am interested in doing this.


August 5, 2021

I've hit a wall trying to work with the continuation dispatch table. So for now, I'm putting it aside. I'll probably not go back to using it; since for me, it's too complex in design. I'm continuing in the direction of using the "Context" data structure, and plain "Jmpbuf" to do the context switching.


July 22, 2021

mlisp-0.6q is depreciated and archived. nLisp (David Betz's xlisp-0.17 which did not have a bytecode compiler) uses the same basic structures as mLisp, however, is does not have continuations. The old mxLisp which grew out of xlisp-3 does a really remarkable job of implementing continuations. So the path ahead looks like I'll be trying to merge the execution context flavored of code from xlisp-2 with the continuations in xlisp-3. Currently, as has been in the past, I am sort of inspired by elegance of David Betz's implementation of continuations.

Maybe for the rest of this year, I'll be working on mlisp-0.7 which is a continuation of developing the old mxlisp.


  
  April 21, 2021

  mxlisp is being depreciated. I'm stopping work on mxLisp
  because I'm starting to understand its code better now. I can
  see the evolution of mLisp into mxLisp (David Betz's xscheme-0.28
  which evolved into xlisp-3.0) alot clearer now than I did a few
  years ago.

  Moreover, since I'm also seeing how nLisp (David Betz's xlisp-0.17
  which did not have a bytecode compiler) uses the same basic
  structures as mLisp, I've been able to understand better now
  how the bytecode compiler was constructed.  I'm planning to merge
  mLisp into nLisp, but change the style of the byte code interpreter
  to one which has fewer opcodes.  mLisp will be depreciated soon in
  favor of nLisp.

  I don't want to maintain 3 sets of lisps so I will focusing on
  nLisp which has a simpler code base, but still does not have
  continuations.  I think this is the best part and most challenging
  part of designing nLisp.  I hope this can happen soon, within the
  next year. "Stay tuned."