8 ms·

Make a Lisp in Nim

102 points by def- 12y ago

perturbation 12y ago
I had this idea as well (after seeing Make a Lisp on HN). Anything that you found challenging in porting the Python version to Nim?
- def- 12y ago
  It wasn't a direct port of the Python one. Instead I mostly followed the guide and looked at the Python code when something was unclear to me. Nim being statically typed meant I had to create many MalTypes instead of just using the built in Python ones. But nothing particularly challenging.
  - def- 12y ago
    Now that I think about it, I could have used implicit converters to make it look more like Python, but that would probably lead to confusion.
shared4you 12y ago
Are your graphs up to date ? Seems just an hour ago [1]: > Rust: build with --release. 10X performance boost! That might mean that Rust would top the charts instead of Nim. [1]: https://github.com/kanaka/mal/commit/434516e0d172904e06b05f6dee83ce2e7859b950 https://github.com/kanaka/mal/commit/434516e0d172904e06b05f6...
- def- 12y ago
  Yes, I updated it already.
  - e12e 12y ago
    Is the lua implementation very new and/or incomplete? It seems to be missing from the benchmarks, and if it's lua 5.1, maybe it'll work with luajit? [ed: Also interesting to note that the clojure version is much slower than scala/java. If nothing else, I guess it's an indication of performance gains that can be had by implementing parts of a clojure program in java (unless there's something off with the clojure implementation, of course.]
    - def- 12y ago
      I have no idea, I didn't run the benchmarks. I only have a few of these languages on my system.
    - kanaka 12y ago
      I'm rather hesitant to post any sort of benchmarks (since the existing ones suck so bad), but the using these, the lua 5.1.5 equivalents would be: 1, 1, 293 Lua does seem to be an odd one in that the short tests run quickly but this does not translate into iterations for the longer 10 second test. Perhaps the mal implementation is triggering bad GC behavior or something and that drags down the longer running tests. That's just speculation though. Again, please take the numbers with a mountain size grain of salt.
- pcwalton 12y ago
  Just one glance at the Rust version (e.g. [1]) shows a lot of needless allocation. For example: if *strn == "&".to_string() { ... } is a very slow (and verbose) way to write if &strn[..] == "&" { ... } and rr_string("'".to_string() + k.to_string() + "' not found".to_string()) is a very slow (and verbose) way to write rr_string(format!("'{}' not found", k))` Etc. etc. [1]: https://github.com/kanaka/mal/blob/master/rust/src/env.rs https://github.com/kanaka/mal/blob/master/rust/src/env.rs
  - steveklabnik 12y ago
    It's also using some manual clone instead of Cargo overrides, and manually running rather than `cargo run`... time for some PRs, I guess! EDIT: further, looks like it's on a really old Rust: https://github.com/kanaka/rust-pcre https://github.com/kanaka/rust-pcre wasn't updated since October... EDIT 2: I tried to update the code, but it's really, really out of date, and will be a ton of work. So I've just submitted https://github.com/kanaka/mal/pull/23 https://github.com/kanaka/mal/pull/23 instead. :(
    - kanaka 12y ago
      Well, I'm not going to remove it. But I will see if I can find some time to improve it in the next few days. I've been meaning to cycle back around. Of course, fixes from somebody who's actually a Rust expert would have been preferred :-) The reason it still uses the alternate pcre is because this still hasn't been fixed: https://github.com/rust-lang/regex/issues/28 https://github.com/rust-lang/regex/issues/28 I would love to get rid of that nastiness.
      - steveklabnik 12y ago
        That's a bummer, because until then, you'll be strongly mis-representing Rust :/
        kanaka 12y ago
        I'm quite happy to take PRs from an expert to address the issues and represent Rust better. :-) UPDATE: I will point out that the README is pretty clear that this is rust 0.13. Doesn't mean it's a good representation of rust 0.13 either of course, but it clearly isn't based on a recent version of Rust.
- Dewie 12y ago
  It's weird that people that make benchmarks don't investigate which flags to pass for getting the most optimized build. Many compilers don't do max optimization by default. In particular, people making benchmarks with rust code seem to tend to forget or be unaware of the `release` flag.
  - pcwalton 12y ago
    Yeah, this is happening again and again in Rust: people publish Rust benchmarks without optimization on. In fact, we just decided this week to change "Compiling" to "Compiling (Debug)" in Cargo if optimization isn't turned on to address this problem. It's sad :(
    - pjmlp 12y ago
      If it helps it doesn't happen only to Rust but to all languages. There is this misunderstanding between implementations and languages where people equate whatever they have installed on their computer with all implementations of the said language. Also not knowing about profilers and optimization flags. So yeah, it is sad.
  - omaranto 12y ago
    That's probably because there is no --release flag: $ rustc --release prog.rs error: Unrecognized option: 'release'. There is a -O for optimization, it is equivalent to -C opt-level=2. EDIT: Oh, cargo build does have a --release which seems to be equivalent to -C opt-level=3, which I guess is even better.
    - steveklabnik 12y ago
      `cargo build --release` does more than just `-C opt-level=3`, actually. For example a regular `cargo build` also adds `-g`, and that's removed for `--release`.
  - rdtsc 12y ago
    Maybe the release flag should be the default?
jeremycw 12y ago
Can someone explain the huge performance difference between nim and C? I though nim compiled to C, therefore I would think that good handwritten C would more or less be the upper performance bound for nim.
- chadzawistowski 12y ago
  One explanation could be "sufficiently advanced compilers". Reread your sentence in the context of C/asm: Can someone explain the huge performance difference between C and assembly? I though C compiled to assembly, therefore I would think that good handwritten assembly would more or less be the upper performance bound for C.
  - username223 12y ago
    I agree with what you wrote: "I would think that good handwritten assembly would more or less be the upper performance bound for C." I doubt a good C (or assembly) programmer has bothered to play this particular benchmark game, so the results look strange.
- tel 12y ago
  Here's a similar, comically pathological, example: "Haskell compiles to C therefore good, handwritten C ought to upper bound performance for Haskell" main :: IO () main = do x <- return ([1..100000001] !! 100000000) putStrLn "done" As Haskell is lazy and pure it "automatically" eliminates the `x` and returns nearly immediately avoiding all work. The correspondingly written C code would do much more work despite its waste. Of course, the human writing the C version might automatically perform this optimization, but similar things can arise in far less obvious locations in a more genuine compilation.
  - jlarocco 12y ago
    I'm not sure that distinction matters. Any C compiler worth using will optimize out 'x' in that case. The details of why (laziness vs code analysis saying it's unused) is pretty much irrelevant. Saying "the human writing the C compiler" is an odd way to put it. It's "the human writing the Haskell compiler" deciding it shouldn't be evaluated in Haskell, too. Totally meaningless distinction.
pkuki 12y ago
I thought it could be interesting to see ratio of program performance to its length. If I didn't make any mistake it looks like that: perf3 perf3 / macros chars chars * 100 ------------------------------------------------- scala 15963 24885 64,15 nim 11121 20263 54,88 java 17969 53223 33,76 ocaml 7063 24371 28,98 coffee 2326 15653 14,86 racket 2461 17229 14,28 cs 5414 45039 12,02 clojure 1174 10099 11,62 ruby 1255 13247 9,47 go 3048 36321 8,39 vb 4523 58099 7,78 rust 4084 56516 7,23 js 1726 26437 6,53 c 3649 73047 5,00 haskell 1163 30115 3,86 python 304 19632 1,55 forth 563 44715 1,26 php 331 27332 1,21
- pjmlp 12y ago
  What is perf3? Also, which specific interpreters/AOT compilers/JIT compilers are being used for each language being measured?
  - pkuki 12y ago
    Look at the original blog post. I just added third column to show ratio between given data.
    - pjmlp 12y ago
      I will do it at home. Currently behind a corporate firewall.
- codygman 12y ago
  For whatever reason I felt the random need to parse your table here in Haskell, so.... here's the code :P λ> import qualified Data.Text.IO as T λ> import qualified Data.Text as T λ> data Entry = Entry {name :: T.Text, macroPerf :: Int, charLength :: Int} deriving Show λ> -- parse into list of lists λ> let table = (fmap T.words) . T.lines <$> T.readFile "langstats.txt" λ> -- I need to parse these things... safely.. using the Safe package! λ> import Safe λ> -- parse table into list of `Maybe Entry` taking advantage of applicative instance λ> -- the list of lists are just name, perf3 macros, chars, and a field I'm ignoring for now λ> -- we can just use list destructuring (\(name : perf3macros : chars : _)) λ> entries <- fmap (\(n:p3:chars:_) -> liftA3 Entry (Just n) (toInt p3) (toInt chars)) <$> table λ> :t entries entries :: [Maybe Entry] λ> -- for easy sorting, we want just [Entry] λ> -- safely turn our [Maybe Entry] into [Entry] λ> import Data.Maybe (isJust, fromJust) λ> let entries' = map fromJust . filter isJust $ entries -- safe because we filter out the justs first! λ> -- speaking of sorting... we need a couple imports λ> import Data.List (sortBy) λ> import Data.Function (on) λ> let results = sortBy (compare `on` macroPerf) entries' [Entry {name = "python", macroPerf = 304, charLength = 19632},Entry {name = "php", macroPerf = 331, charLength = 27332},Entry {name = "forth", macroPerf = 563, charLength = 44715},Entry {name = "haskell", macroPerf = 1163, charLength = 30115},Entry {name = "clojure", macroPerf = 1174, charLength = 10099},Entry {name = "ruby", macroPerf = 1255, charLength = 13247},Entry {name = "js", macroPerf = 1726, charLength = 26437},Entry {name = "coffee", macroPerf = 2326, charLength = 15653},Entry {name = "racket", macroPerf = 2461, charLength = 17229},Entry {name = "go", macroPerf = 3048, charLength = 36321},Entry {name = "c", macroPerf = 3649, charLength = 73047},Entry {name = "rust", macroPerf = 4084, charLength = 56516},Entry {name = "vb", macroPerf = 4523, charLength = 58099},Entry {name = "cs", macroPerf = 5414, charLength = 45039},Entry {name = "ocaml", macroPerf = 7063, charLength = 24371},Entry {name = "nim", macroPerf = 11121, charLength = 20263},Entry {name = "scala", macroPerf = 15963, charLength = 24885},Entry {name = "java", macroPerf = 17969, charLength = 53223}] λ> -- how about some pretty printing? λ> mapM_ (\e -> putStrLn $ (T.unpack (name e)) ++ "\t" ++ show (macroPerf e) ++ "\t" ++ show (charLength e)) results

102 points by def- 12y ago

I had this idea as well (after seeing Make a Lisp on HN). Anything that you found challenging in porting the Python version to Nim?

def- 12y ago
It wasn't a direct port of the Python one. Instead I mostly followed the guide and looked at the Python code when something was unclear to me. Nim being statically typed meant I had to create many MalTypes instead of just using the built in Python ones. But nothing particularly challenging.
- def- 12y ago
  Now that I think about it, I could have used implicit converters to make it look more like Python, but that would probably lead to confusion.

shared4you 12y ago

Are your graphs up to date ? Seems just an hour ago [1]: > Rust: build with --release. 10X performance boost! That might mean that Rust would top the charts instead of Nim. [1]: https://github.com/kanaka/mal/commit/434516e0d172904e06b05f6dee83ce2e7859b950 https://github.com/kanaka/mal/commit/434516e0d172904e06b05f6...

def- 12y ago
Yes, I updated it already.
- e12e 12y ago
  Is the lua implementation very new and/or incomplete? It seems to be missing from the benchmarks, and if it's lua 5.1, maybe it'll work with luajit? [ed: Also interesting to note that the clojure version is much slower than scala/java. If nothing else, I guess it's an indication of performance gains that can be had by implementing parts of a clojure program in java (unless there's something off with the clojure implementation, of course.]
  - def- 12y ago
    I have no idea, I didn't run the benchmarks. I only have a few of these languages on my system.
  - kanaka 12y ago
    I'm rather hesitant to post any sort of benchmarks (since the existing ones suck so bad), but the using these, the lua 5.1.5 equivalents would be: 1, 1, 293 Lua does seem to be an odd one in that the short tests run quickly but this does not translate into iterations for the longer 10 second test. Perhaps the mal implementation is triggering bad GC behavior or something and that drags down the longer running tests. That's just speculation though. Again, please take the numbers with a mountain size grain of salt.
pcwalton 12y ago
Just one glance at the Rust version (e.g. [1]) shows a lot of needless allocation. For example: if *strn == "&".to_string() { ... } is a very slow (and verbose) way to write if &strn[..] == "&" { ... } and rr_string("'".to_string() + k.to_string() + "' not found".to_string()) is a very slow (and verbose) way to write rr_string(format!("'{}' not found", k))` Etc. etc. [1]: https://github.com/kanaka/mal/blob/master/rust/src/env.rs https://github.com/kanaka/mal/blob/master/rust/src/env.rs
- steveklabnik 12y ago
  It's also using some manual clone instead of Cargo overrides, and manually running rather than `cargo run`... time for some PRs, I guess! EDIT: further, looks like it's on a really old Rust: https://github.com/kanaka/rust-pcre https://github.com/kanaka/rust-pcre wasn't updated since October... EDIT 2: I tried to update the code, but it's really, really out of date, and will be a ton of work. So I've just submitted https://github.com/kanaka/mal/pull/23 https://github.com/kanaka/mal/pull/23 instead. :(
  - kanaka 12y ago
    Well, I'm not going to remove it. But I will see if I can find some time to improve it in the next few days. I've been meaning to cycle back around. Of course, fixes from somebody who's actually a Rust expert would have been preferred :-) The reason it still uses the alternate pcre is because this still hasn't been fixed: https://github.com/rust-lang/regex/issues/28 https://github.com/rust-lang/regex/issues/28 I would love to get rid of that nastiness.
    - steveklabnik 12y ago
      That's a bummer, because until then, you'll be strongly mis-representing Rust :/
      - kanaka 12y ago
        I'm quite happy to take PRs from an expert to address the issues and represent Rust better. :-) UPDATE: I will point out that the README is pretty clear that this is rust 0.13. Doesn't mean it's a good representation of rust 0.13 either of course, but it clearly isn't based on a recent version of Rust.
Dewie 12y ago
It's weird that people that make benchmarks don't investigate which flags to pass for getting the most optimized build. Many compilers don't do max optimization by default. In particular, people making benchmarks with rust code seem to tend to forget or be unaware of the `release` flag.
- pcwalton 12y ago
  Yeah, this is happening again and again in Rust: people publish Rust benchmarks without optimization on. In fact, we just decided this week to change "Compiling" to "Compiling (Debug)" in Cargo if optimization isn't turned on to address this problem. It's sad :(
  - pjmlp 12y ago
    If it helps it doesn't happen only to Rust but to all languages. There is this misunderstanding between implementations and languages where people equate whatever they have installed on their computer with all implementations of the said language. Also not knowing about profilers and optimization flags. So yeah, it is sad.
- omaranto 12y ago
  That's probably because there is no --release flag: $ rustc --release prog.rs error: Unrecognized option: 'release'. There is a -O for optimization, it is equivalent to -C opt-level=2. EDIT: Oh, cargo build does have a --release which seems to be equivalent to -C opt-level=3, which I guess is even better.
  - steveklabnik 12y ago
    `cargo build --release` does more than just `-C opt-level=3`, actually. For example a regular `cargo build` also adds `-g`, and that's removed for `--release`.
- rdtsc 12y ago
  Maybe the release flag should be the default?

jeremycw 12y ago

Can someone explain the huge performance difference between nim and C? I though nim compiled to C, therefore I would think that good handwritten C would more or less be the upper performance bound for nim.

chadzawistowski 12y ago
One explanation could be "sufficiently advanced compilers". Reread your sentence in the context of C/asm: Can someone explain the huge performance difference between C and assembly? I though C compiled to assembly, therefore I would think that good handwritten assembly would more or less be the upper performance bound for C.
- username223 12y ago
  I agree with what you wrote: "I would think that good handwritten assembly would more or less be the upper performance bound for C." I doubt a good C (or assembly) programmer has bothered to play this particular benchmark game, so the results look strange.
tel 12y ago
Here's a similar, comically pathological, example: "Haskell compiles to C therefore good, handwritten C ought to upper bound performance for Haskell" main :: IO () main = do x <- return ([1..100000001] !! 100000000) putStrLn "done" As Haskell is lazy and pure it "automatically" eliminates the `x` and returns nearly immediately avoiding all work. The correspondingly written C code would do much more work despite its waste. Of course, the human writing the C version might automatically perform this optimization, but similar things can arise in far less obvious locations in a more genuine compilation.
- jlarocco 12y ago
  I'm not sure that distinction matters. Any C compiler worth using will optimize out 'x' in that case. The details of why (laziness vs code analysis saying it's unused) is pretty much irrelevant. Saying "the human writing the C compiler" is an odd way to put it. It's "the human writing the Haskell compiler" deciding it shouldn't be evaluated in Haskell, too. Totally meaningless distinction.

pkuki 12y ago

I thought it could be interesting to see ratio of program performance to its length. If I didn't make any mistake it looks like that: perf3 perf3 / macros chars chars * 100 ------------------------------------------------- scala 15963 24885 64,15 nim 11121 20263 54,88 java 17969 53223 33,76 ocaml 7063 24371 28,98 coffee 2326 15653 14,86 racket 2461 17229 14,28 cs 5414 45039 12,02 clojure 1174 10099 11,62 ruby 1255 13247 9,47 go 3048 36321 8,39 vb 4523 58099 7,78 rust 4084 56516 7,23 js 1726 26437 6,53 c 3649 73047 5,00 haskell 1163 30115 3,86 python 304 19632 1,55 forth 563 44715 1,26 php 331 27332 1,21

pjmlp 12y ago
What is perf3? Also, which specific interpreters/AOT compilers/JIT compilers are being used for each language being measured?
- pkuki 12y ago
  Look at the original blog post. I just added third column to show ratio between given data.
  - pjmlp 12y ago
    I will do it at home. Currently behind a corporate firewall.
codygman 12y ago
For whatever reason I felt the random need to parse your table here in Haskell, so.... here's the code :P λ> import qualified Data.Text.IO as T λ> import qualified Data.Text as T λ> data Entry = Entry {name :: T.Text, macroPerf :: Int, charLength :: Int} deriving Show λ> -- parse into list of lists λ> let table = (fmap T.words) . T.lines <$> T.readFile "langstats.txt" λ> -- I need to parse these things... safely.. using the Safe package! λ> import Safe λ> -- parse table into list of `Maybe Entry` taking advantage of applicative instance λ> -- the list of lists are just name, perf3 macros, chars, and a field I'm ignoring for now λ> -- we can just use list destructuring (\(name : perf3macros : chars : _)) λ> entries <- fmap (\(n:p3:chars:_) -> liftA3 Entry (Just n) (toInt p3) (toInt chars)) <$> table λ> :t entries entries :: [Maybe Entry] λ> -- for easy sorting, we want just [Entry] λ> -- safely turn our [Maybe Entry] into [Entry] λ> import Data.Maybe (isJust, fromJust) λ> let entries' = map fromJust . filter isJust $ entries -- safe because we filter out the justs first! λ> -- speaking of sorting... we need a couple imports λ> import Data.List (sortBy) λ> import Data.Function (on) λ> let results = sortBy (compare `on` macroPerf) entries' [Entry {name = "python", macroPerf = 304, charLength = 19632},Entry {name = "php", macroPerf = 331, charLength = 27332},Entry {name = "forth", macroPerf = 563, charLength = 44715},Entry {name = "haskell", macroPerf = 1163, charLength = 30115},Entry {name = "clojure", macroPerf = 1174, charLength = 10099},Entry {name = "ruby", macroPerf = 1255, charLength = 13247},Entry {name = "js", macroPerf = 1726, charLength = 26437},Entry {name = "coffee", macroPerf = 2326, charLength = 15653},Entry {name = "racket", macroPerf = 2461, charLength = 17229},Entry {name = "go", macroPerf = 3048, charLength = 36321},Entry {name = "c", macroPerf = 3649, charLength = 73047},Entry {name = "rust", macroPerf = 4084, charLength = 56516},Entry {name = "vb", macroPerf = 4523, charLength = 58099},Entry {name = "cs", macroPerf = 5414, charLength = 45039},Entry {name = "ocaml", macroPerf = 7063, charLength = 24371},Entry {name = "nim", macroPerf = 11121, charLength = 20263},Entry {name = "scala", macroPerf = 15963, charLength = 24885},Entry {name = "java", macroPerf = 17969, charLength = 53223}] λ> -- how about some pretty printing? λ> mapM_ (\e -> putStrLn $ (T.unpack (name e)) ++ "\t" ++ show (macroPerf e) ++ "\t" ++ show (charLength e)) results