8 ms·

Going Faster with Lisp

124 points by foob 9y ago

flavio81 9y ago
TL;DR: Very interesting article about improving performance in Common Lisp. The author has a 6502 CPU emulator and finds out how to improve his assembly output. Additionally, it shows how the "static" typing facilities of Lisp help for increasing performance.
mamcx 9y ago
How easy is to embed this? If I wanna make a language and use a lisp as the "backend" this one is good for this?
- pmoriarty 9y ago
  Check out Guile Scheme[1]. It's designed to be embedded, and is a nice, modern Lisp. It's also the official GNU extension language. [1] - https://en.wikipedia.org/wiki/GNU_Guile https://en.wikipedia.org/wiki/GNU_Guile
  - lispm 9y ago
    'modern' in the sense of Scheme being modern in 1975? SCHEME: An Interpreter for Extended Lambda Calculus, Sussman/Steele, 1975 https://dspace.mit.edu/handle/1721.1/5794 https://dspace.mit.edu/handle/1721.1/5794
    - deleted 9y ago
      [deleted]
    - SwellJoe 9y ago
      According to that logic, you'd have to call Lisp modern by 1958 standards.
      - eadmund 9y ago
        Not really. The Common Lisp spec is quite a bit more modern than 1958 — and, unlike the several, not-universally-accepted Scheme specs, it's a well-crafted ANSI standard. It does suffer from backwards-compatibility, but it also enjoys the lessons of the past. Scheme is neat (in multiple meanings of the word), but honestly I don't think it's a good production tool. Being a Lisp-1 & lacking real macros means that it's more suited to being a pedagogical tool (n.b.: I believe that many Scheme implementations add real macros — but without a standard package system and a function namespace, this is not enough).
        shakna 9y ago
        > not-universally-accepted Scheme specs What do you mean by that? That implementers extend the language? > Being a Lisp-1 & lacking real macros Scheme has defmacro just like CL. You can modify the reader and change the AST. What does Scheme lack in macro-land? > but without a standard package system R7RS includes one. Currently implemented by Chez and Guile, to my knowledge
    - shakna 9y ago
      R7RS was finalised in 2013. [0] Scheme is actively developed by a large community. [0] http://trac.sacrideo.us/wg/wiki/R7RSHomePage http://trac.sacrideo.us/wg/wiki/R7RSHomePage
      - lispm 9y ago
        > R7RS was finalised in 2013 Only the small language. Looks to me like a plain old Scheme slightly updated.
        shakna 9y ago
        Isn't that what a standard should be? The first part of r7rs-large also got finalised as the Red Edition [0]. Scheme's roots do mean the standardisation process can move slowly at times, taking guidance from "living standards" like Chez. That's not necessarily a bad thing. The differences just tend to be including SRFIs, that everyone already use, in the standard. [0] http://trac.sacrideo.us/wg/wiki/RedEdition http://trac.sacrideo.us/wg/wiki/RedEdition
        lispm 9y ago
        Sure, but I still don't get it, what makes it a 'modern' Lisp, since much of the stuff has been part of Lisp decades ago... Especially if you look at Guile, the manual looks frightening - an implementation which has no clear language design, but accumulates stuff from SRFIs, R6RS, R7RS, own stuff, ... often similar things in multiple different ways - just look at error handling and its multiple variants - none looks really compelling.
        shakna 9y ago
        Define modern, otherwise you're going to go down a rabbithole where you can freely disagree with anybody. We refer to ES2017 as "modern", despite the fact that all it's shiny new features are ones that both CL and Scheme, and Smalltalk to a degree, had twenty years ago. "Modern" tends to mean "under active work today". C++17, PHP7, Python 3.7, all these are referred to as "modern". Scheme is actively developed today. That's modern enough. (And has had all the shiny features other language's consider "modern" for years). > Especially if you look at Guile, the manual looks frightening - an implementation which has no clear language design, but accumulates stuff from SRFIs, R6RS, R7RS, own stuff I have no idea where you're pulling that from. The language design seems clear enough [0] to me, in the manual. > but accumulates stuff from SRFIs, R6RS, R7RS, own stuff I don't see how that's a problem. Common libraries are included, as well as backwards compatibility, and some extensions. How is that different from GCC, MSVC, Luajit, etc? Even CPython has extensions on Python's language reference. In fact, what about SBCL? [1] The manual seems straight-forward, and easy to understand to me. No different from any other language manual. More detailed and just as straight-forward as SBCL's. [0] https://www.gnu.org/software/guile/manual/guile.html#About-Data https://www.gnu.org/software/guile/manual/guile.html#About-D... [1] http://www.sbcl.org/manual/#Idiosyncrasies http://www.sbcl.org/manual/#Idiosyncrasies
- terminalcommand 9y ago
  What do you want to achieve? Do you want to write an interpreter for your language in Lisp, or write a transpiler, which converts your language into Lisp and than maybe to native code? If you want to generate efficient machine code, I'd suggest looking at Clang's intermediate language IR. PS: I may have misunderstood your question, if that's the case apologies.
  - mamcx 9y ago
    Looking for a backend that allow to have a decent REPL and posibility to also compile (ie be both a interpreter + compiler). I'm on .net right now, and have found a way to have this. Just imagine that lisp could help there...
- lispm 9y ago
  For embedding either as source or as a shared library there are a bunch of Common Lisp implementations: ECL / Embeddable Common-Lisp -> Can build standalone executables and libraries -> https://common-lisp.net/project/ecl/main.html https://common-lisp.net/project/ecl/main.html ABCL / Armed Bear Common Lisp -> Embed Common Lisp into JVM applications -> http://abcl.org http://abcl.org Commercial CL implementations like Allegro CL and LispWorks support the delivery of shared libraries. That way you can compile your CL program to a shared library. There are even more options (like WCL, mocl, ...).
  - dmichulke 9y ago
    Can you elaborate a bit on the (dis-)advantages of ABCL compared to Clojure?
    - lispm 9y ago
      Well, it supports all of Common Lisp incl. the whole numeric tower, Condition System and CLOS. If you know Common Lisp, it's all there. That means it's compatible with much of the Lisp literature and thus automatically has a well-written specification for its core language. It provides an interpreter and a compiler. One can use it with GNU Emacs / SLIME. ABCL has also more the feel of what one would expect from Lisp, like an interpreter integrated with a compiler, useful backtraces, Lisp-like error messages and a Break-Loop REPL using the condition system. The compiler is written in Lisp. Thus it provides some more of debugging experience 'we' all love. It has much less users, less Java specific stuff, etc. It's also a bit slower than the typical native compiled Common Lisp.
    - flavio81 9y ago
      ABCL is a full implementation of Common Lisp (an ANSI-standarized language rich on features and with a proven record of success stories) that happens to run in the JVM and has good facilities for calling Java code. However it is a full Common Lisp implementation which means it has all the nice stuff you would expect from such a piece of software. Clojure, on the other hand, is a different programming language, which for some reasons, and by design, is deeply tied to the underlying Java platform. Clojure "looks like a Lisp", but in reality it is fundamentally different from languages "of the Lisp family" like Scheme, Emacs Lisp and Common Lisp. There are many, many differences between Clojure and Common Lisp. For a HN thread on this topic, see: https://news.ycombinator.com/item?id=10206827 https://news.ycombinator.com/item?id=10206827
- flavio81 9y ago
  >How easy is to embed this? A minimal Lisp is really easy to embed because writing a Lisp interpreter is simple. See for example the "MAL" (Make A Lisp) project. If you want a feature-laden Lisp, like Common Lisp, you may want to try Embeddable Common Lisp (ECL). The other main dialect of Lisp, Scheme, also has many options for embedding.
_ph_ 9y ago
SBCL is a very interesting compiler. I can only encourage anyone, who is interested in Lisp or dynamic languages in general to check it out. It always compiles to native code, and as the article has shown, you can see what it compiles to. That gives you direct feedback how good the resulting code is. By default, SBCL always generates "correct" code. That of course means for a dynamically typed language, that it has to assume any type. Also, for integer operations, it means, still producing a correct result, even if the integers exceed the values which can be represented by machine-sized integers. As a result, the generated code isn't overly impressive in the beginning. But SBCL has very high abilities to reason about the code, including type inferencing. So, when you add a few type declarations, the generated code gets substantially faster, often matching and sometimes even exceeding what GCC produces for C programs.
- flavio81 9y ago
  > it means, still producing a correct result, even if the integers exceed the values which can be represented by machine-sized integers To clarify for people alien to Common Lisp: In lisp, by default, integer numbers can be as big as they need to. From the Common Lisp Hyperspec, the entry on the integer data type says: An integer is a mathematical integer. There is no limit on the magnitude of an integer.
  - infogulch 9y ago
    This really is the correct default. If something unexpected happens the better failure case is to be a little slower than expected than giving completely absurd results. Then adding the optional power to constrain the inputs allowing the compiler to use more efficient implementation with those assumptions is awesome.
    - renox 9y ago
      Thee SPARC CPU has/had instructions to add tagged integers which show that this can be nearly as fast as "normal integers"
- geokon 9y ago
taeric 9y ago
Am I the only person that noticed the hover on the lisp code blocks? Surprised me at first. Can't tell if I like the idea or not. Rather, I know I like the idea. I can't decide if I like the execution. I'm leaning towards liking it.
- carapace 9y ago
  Oh that is cool. It works without JS!
- undershirt 9y ago
  I think it's an old thing from paste.lisp.org from: http://lemonodor.com/archives/001207.html http://lemonodor.com/archives/001207.html
- SwellJoe 9y ago
  I kinda want my editor to do that when working with Javascript. Deeply nested callbacks and Promises bend my brain, and it'd be nice to see where one thing ends and another begins. It's easy to bounce back and forth between opening and closing parens/brackets (e.g. % in vim) or have it highlighted, but I often find myself having to sort of scroll back and forth to sort it out in my head.
- kingcons 9y ago
  The code highlighting is powered by colorize (https://github.com/kingcons/colorize https://github.com/kingcons/colorize), a lisp library that doesn't have the _widest_ language support but does generate HTML with cool hover tricks. :)

124 points by foob 9y ago

TL;DR: Very interesting article about improving performance in Common Lisp. The author has a 6502 CPU emulator and finds out how to improve his assembly output. Additionally, it shows how the "static" typing facilities of Lisp help for increasing performance.

mamcx 9y ago

How easy is to embed this? If I wanna make a language and use a lisp as the "backend" this one is good for this?

pmoriarty 9y ago
Check out Guile Scheme[1]. It's designed to be embedded, and is a nice, modern Lisp. It's also the official GNU extension language. [1] - https://en.wikipedia.org/wiki/GNU_Guile https://en.wikipedia.org/wiki/GNU_Guile
- lispm 9y ago
  'modern' in the sense of Scheme being modern in 1975? SCHEME: An Interpreter for Extended Lambda Calculus, Sussman/Steele, 1975 https://dspace.mit.edu/handle/1721.1/5794 https://dspace.mit.edu/handle/1721.1/5794
  - deleted 9y ago
    [deleted]
  - SwellJoe 9y ago
    According to that logic, you'd have to call Lisp modern by 1958 standards.
    - eadmund 9y ago
      Not really. The Common Lisp spec is quite a bit more modern than 1958 — and, unlike the several, not-universally-accepted Scheme specs, it's a well-crafted ANSI standard. It does suffer from backwards-compatibility, but it also enjoys the lessons of the past. Scheme is neat (in multiple meanings of the word), but honestly I don't think it's a good production tool. Being a Lisp-1 & lacking real macros means that it's more suited to being a pedagogical tool (n.b.: I believe that many Scheme implementations add real macros — but without a standard package system and a function namespace, this is not enough).
      - shakna 9y ago
        > not-universally-accepted Scheme specs What do you mean by that? That implementers extend the language? > Being a Lisp-1 & lacking real macros Scheme has defmacro just like CL. You can modify the reader and change the AST. What does Scheme lack in macro-land? > but without a standard package system R7RS includes one. Currently implemented by Chez and Guile, to my knowledge
  - shakna 9y ago
    R7RS was finalised in 2013. [0] Scheme is actively developed by a large community. [0] http://trac.sacrideo.us/wg/wiki/R7RSHomePage http://trac.sacrideo.us/wg/wiki/R7RSHomePage
    - lispm 9y ago
      > R7RS was finalised in 2013 Only the small language. Looks to me like a plain old Scheme slightly updated.
      - shakna 9y ago
        Isn't that what a standard should be? The first part of r7rs-large also got finalised as the Red Edition [0]. Scheme's roots do mean the standardisation process can move slowly at times, taking guidance from "living standards" like Chez. That's not necessarily a bad thing. The differences just tend to be including SRFIs, that everyone already use, in the standard. [0] http://trac.sacrideo.us/wg/wiki/RedEdition http://trac.sacrideo.us/wg/wiki/RedEdition
        lispm 9y ago
        Sure, but I still don't get it, what makes it a 'modern' Lisp, since much of the stuff has been part of Lisp decades ago... Especially if you look at Guile, the manual looks frightening - an implementation which has no clear language design, but accumulates stuff from SRFIs, R6RS, R7RS, own stuff, ... often similar things in multiple different ways - just look at error handling and its multiple variants - none looks really compelling.
        shakna 9y ago
        Define modern, otherwise you're going to go down a rabbithole where you can freely disagree with anybody. We refer to ES2017 as "modern", despite the fact that all it's shiny new features are ones that both CL and Scheme, and Smalltalk to a degree, had twenty years ago. "Modern" tends to mean "under active work today". C++17, PHP7, Python 3.7, all these are referred to as "modern". Scheme is actively developed today. That's modern enough. (And has had all the shiny features other language's consider "modern" for years). > Especially if you look at Guile, the manual looks frightening - an implementation which has no clear language design, but accumulates stuff from SRFIs, R6RS, R7RS, own stuff I have no idea where you're pulling that from. The language design seems clear enough [0] to me, in the manual. > but accumulates stuff from SRFIs, R6RS, R7RS, own stuff I don't see how that's a problem. Common libraries are included, as well as backwards compatibility, and some extensions. How is that different from GCC, MSVC, Luajit, etc? Even CPython has extensions on Python's language reference. In fact, what about SBCL? [1] The manual seems straight-forward, and easy to understand to me. No different from any other language manual. More detailed and just as straight-forward as SBCL's. [0] https://www.gnu.org/software/guile/manual/guile.html#About-Data https://www.gnu.org/software/guile/manual/guile.html#About-D... [1] http://www.sbcl.org/manual/#Idiosyncrasies http://www.sbcl.org/manual/#Idiosyncrasies
terminalcommand 9y ago
What do you want to achieve? Do you want to write an interpreter for your language in Lisp, or write a transpiler, which converts your language into Lisp and than maybe to native code? If you want to generate efficient machine code, I'd suggest looking at Clang's intermediate language IR. PS: I may have misunderstood your question, if that's the case apologies.
- mamcx 9y ago
  Looking for a backend that allow to have a decent REPL and posibility to also compile (ie be both a interpreter + compiler). I'm on .net right now, and have found a way to have this. Just imagine that lisp could help there...
lispm 9y ago
For embedding either as source or as a shared library there are a bunch of Common Lisp implementations: ECL / Embeddable Common-Lisp -> Can build standalone executables and libraries -> https://common-lisp.net/project/ecl/main.html https://common-lisp.net/project/ecl/main.html ABCL / Armed Bear Common Lisp -> Embed Common Lisp into JVM applications -> http://abcl.org http://abcl.org Commercial CL implementations like Allegro CL and LispWorks support the delivery of shared libraries. That way you can compile your CL program to a shared library. There are even more options (like WCL, mocl, ...).
- dmichulke 9y ago
  Can you elaborate a bit on the (dis-)advantages of ABCL compared to Clojure?
  - lispm 9y ago
    Well, it supports all of Common Lisp incl. the whole numeric tower, Condition System and CLOS. If you know Common Lisp, it's all there. That means it's compatible with much of the Lisp literature and thus automatically has a well-written specification for its core language. It provides an interpreter and a compiler. One can use it with GNU Emacs / SLIME. ABCL has also more the feel of what one would expect from Lisp, like an interpreter integrated with a compiler, useful backtraces, Lisp-like error messages and a Break-Loop REPL using the condition system. The compiler is written in Lisp. Thus it provides some more of debugging experience 'we' all love. It has much less users, less Java specific stuff, etc. It's also a bit slower than the typical native compiled Common Lisp.
  - flavio81 9y ago
    ABCL is a full implementation of Common Lisp (an ANSI-standarized language rich on features and with a proven record of success stories) that happens to run in the JVM and has good facilities for calling Java code. However it is a full Common Lisp implementation which means it has all the nice stuff you would expect from such a piece of software. Clojure, on the other hand, is a different programming language, which for some reasons, and by design, is deeply tied to the underlying Java platform. Clojure "looks like a Lisp", but in reality it is fundamentally different from languages "of the Lisp family" like Scheme, Emacs Lisp and Common Lisp. There are many, many differences between Clojure and Common Lisp. For a HN thread on this topic, see: https://news.ycombinator.com/item?id=10206827 https://news.ycombinator.com/item?id=10206827
flavio81 9y ago
>How easy is to embed this? A minimal Lisp is really easy to embed because writing a Lisp interpreter is simple. See for example the "MAL" (Make A Lisp) project. If you want a feature-laden Lisp, like Common Lisp, you may want to try Embeddable Common Lisp (ECL). The other main dialect of Lisp, Scheme, also has many options for embedding.

_ph_ 9y ago

SBCL is a very interesting compiler. I can only encourage anyone, who is interested in Lisp or dynamic languages in general to check it out. It always compiles to native code, and as the article has shown, you can see what it compiles to. That gives you direct feedback how good the resulting code is. By default, SBCL always generates "correct" code. That of course means for a dynamically typed language, that it has to assume any type. Also, for integer operations, it means, still producing a correct result, even if the integers exceed the values which can be represented by machine-sized integers. As a result, the generated code isn't overly impressive in the beginning. But SBCL has very high abilities to reason about the code, including type inferencing. So, when you add a few type declarations, the generated code gets substantially faster, often matching and sometimes even exceeding what GCC produces for C programs.

flavio81 9y ago
> it means, still producing a correct result, even if the integers exceed the values which can be represented by machine-sized integers To clarify for people alien to Common Lisp: In lisp, by default, integer numbers can be as big as they need to. From the Common Lisp Hyperspec, the entry on the integer data type says: An integer is a mathematical integer. There is no limit on the magnitude of an integer.
- infogulch 9y ago
  This really is the correct default. If something unexpected happens the better failure case is to be a little slower than expected than giving completely absurd results. Then adding the optional power to constrain the inputs allowing the compiler to use more efficient implementation with those assumptions is awesome.
  - renox 9y ago
    Thee SPARC CPU has/had instructions to add tagged integers which show that this can be nearly as fast as "normal integers"
geokon 9y ago

taeric 9y ago

Am I the only person that noticed the hover on the lisp code blocks? Surprised me at first. Can't tell if I like the idea or not. Rather, I know I like the idea. I can't decide if I like the execution. I'm leaning towards liking it.

carapace 9y ago
Oh that is cool. It works without JS!
undershirt 9y ago
I think it's an old thing from paste.lisp.org from: http://lemonodor.com/archives/001207.html http://lemonodor.com/archives/001207.html
SwellJoe 9y ago
I kinda want my editor to do that when working with Javascript. Deeply nested callbacks and Promises bend my brain, and it'd be nice to see where one thing ends and another begins. It's easy to bounce back and forth between opening and closing parens/brackets (e.g. % in vim) or have it highlighted, but I often find myself having to sort of scroll back and forth to sort it out in my head.
kingcons 9y ago
The code highlighting is powered by colorize (https://github.com/kingcons/colorize https://github.com/kingcons/colorize), a lisp library that doesn't have the _widest_ language support but does generate HTML with cool hover tricks. :)