I figured out why `(+ 1 2)` is so slow in Nu. It was calling Arc's `or` which is pretty slow (compared to not calling it, anyways). So here's the new numbers, this time using the time library[1]:
As you can see, Nu is now faster than ar, but still slower than Arc 3.1. On the other hand, Nu's + is implemented in terms of case-lambda, so it should be better on memory in the case of only 2 arguments.
"I like what you're doing with the argument lists."
You mean the "destructuring is just lambdas" thing?
---
"Have you found your arc2js progress useful for this?"
No, except insofar as writing arc2js taught me some useful compiler things. For the most part, it's been pretty simple and easy, so I don't think arc2js helped much, if at all.
---
"Part of me wonders how Racket's local (define ...) forms compare against its other options in terms of performance."
(let a nil (%nocompile (racket-define a 5)) a)
(let a nil (= a 5) a)
Time: 1500-1600 ms
(let a nil (%nocompile (racket-let* ((a 5)) a)))
(let a nil (%nocompile (racket-let ((a 5)) a)))
(let a nil (let a 5 a))
(let a nil a)
Time: 1400-1500 ms
It would seem Racket optimizes lambdas very heavily.
---
"As far as the name "Nu" goes, it's actually been taken by another lisp (and I'm not even talking about NewLISP :-p )"
Darn. I still like the name "Nu" enough that I want to keep it, though.
It took me a while to reply because I was planning to do some of my own testing before posting, but I haven't found the time.
---
"You mean the "destructuring is just lambdas" thing?"
No, I don't know what to think about that yet. I like it if and only if this works:
(let (a . b) '(1 . 2)
...)
Even if that works, I almost expect Racket to copy a mutable argument list into an immutable one for use inside the lambda, so here's a second test case:
(withs (foo (list 1 2 3)
(a . b) foo)
(= b.0 4)
(is foo.1 4))
What I definitely do like is the use of Racket's optional arg syntax where possible. ^_^
---
"It would seem Racket optimizes lambdas very heavily."
IMO, those examples aren't normal uses of (define ...), since they're contexts where the variable is already defined. I'd like to test these cases:
; Racket code
(let ((a 5)) a)
((lambda (a) a) 5)
(begin (define a 5) a)
; NOTE: Make sure this (begin ...) isn't at the top level, or the
; definition will be global.
(let () (define a 5) a)
((lambda () (define a 5) a))
* Internal-definition expansion has changed to use `let*' semantics
for sequences that contain no back references. This change
removes a performance penalty for using internal definitions
instead of `let' in common cases, and it only changes the meaning
of programs that capture continuations in internal definitions.
Internal definitions are now considered preferable in style to
`let'.
Then again, if they're going to make more semantic changes like this one, it might be better to avoid compiling to an internal-definition style. :-p
Anyway, from the phrasing in the changelog, it sounds like internal definitions are implemented in ways the programmer can already control at a lower level with things like 'let*, so you'll probably continue to find that internal definitions are at least as slow as other options.
The reason is because racket-mlist->list expects a proper list. I can fix that easily.
Update: I fixed racket-mlist->list, but Racket's apply absolutely positively requires a proper list, so it looks like I can't use nested lambdas if I want to fix that: I'll have to use a Racket let*
---
"I almost expect Racket to copy a mutable argument list into an immutable one for use inside the lambda"
It's true, it does copy the list, so that returns nil. I wonder if I can work around that...
---
"One reason it's on my mind is the Racket 5.2 changelog"
I'm not using Racket 5.2. And even if I were, the reason for the speed tests was to see how it would perform within the (fn ...) expansion, where it does indeed overwrite an already-existing variable. (Though I could change it to use a gensym...)
Okay, some interesting info: Racket is apparently quite slow at applying a function at runtime. I ran this code in Arc 3.1, ar, and Nu:
(time (repeat 1000000 (let (a b) (list 1 2) a)))
Here are my results:
Nu time: 3165 msec.
Arc 3.1 time: 1830 msec.
ar time: 1391 msec.
Very surprising! Arc 3.1 expands into a Racket let* and Nu expands into a Racket lambda... but ar's code is implemented in Arc, so it expands into multiple nested Arc lambdas... yet somehow manages to be faster than Arc 3.1 and Nu.
I am not sure how plain lambdas are faster than Racket's built-in let* . In any case, I changed my code so it expands into let* and now Nu gets 1649 msec, which is comparable to ar. Thus the problem is clearly applying a function at runtime.
Just to remove some more variables, I changed the function so it didn't use rest or optional args, but it ended up being almost as slow, so I know it's not that.
Hm... perhaps it's not the fact that it's applying, per se. Perhaps it's because Racket has to create a function every single time. In other words, if Racket sees this:
((fn (x) ...) ...)
It can try and optimize it away so a function is never actually created. But when Racket sees this:
(apply (fn (x) ...) ...)
It can't do that optimization... thus it's forced to create a function. Creating and destroying a function every time the let is called could indeed cause a performance problem.
---
EDIT: to test my hypothesis, I used this code:
(let foo (fn ((o a) (o b) . rest) a)
(time (repeat 1000000 (let x (list 1 2) (apply foo x)))))
...unfortunately, it ended up getting 2966 msec, so it seems the problem is indeed Racket's apply, or perhaps my compiler's apply. I'll see if I can optimize it a bit.
Racket seems fairly good at "lambda lifting", if that is the correct term. To demonstrate with adding the numbers from 1 to n: version 0 should pretty obviously be compiled into a loop; versions 1 and 2 are less obvious. In 64-bit "racket", versions 1 and 2 seem to take twice as long as the loop in version 0, but that's still much better than allocating lambdas; in 32-bit, the "twice as long" difference is smothered by the cost of allocating/GCing bignums. The last version is actually written in Arc, and 25x slower in arc3.1; though in 32-bit, the cost of handling bignums makes arc3.1 only 2x slower. The results of the 64-bit version seem to demonstrate that Racket successfully avoided allocating closures at runtime in all cases.
(define (sum0 n)
(let loop ((n n) (tt 0))
(if (zero? n)
tt
(loop (- n 1) (+ n tt)))))
(define sum1
(λ (n)
((λ (f n tt)
(if (zero? n)
tt
(f f (- n 1) (+ n tt))))
(λ (f n tt)
(if (zero? n)
tt
(f f (- n 1) (+ n tt))))
n
0)))
(define sum2
(λ (n)
((λ (f) (f f n 0))
(λ (f n tt)
(if (zero? n)
tt
(f f (- n 1) (+ n tt)))))))
(= sum3
(fn (n)
((fn (f n tt)
(if (is n 0)
tt
(f f (- n 1) (+ n tt))))
(fn (f n tt)
(if (is n 0)
tt
(f f (- n 1) (+ n tt))))
n
0)))
;Paste this command in, but copy the above to clipboard before running:
arc> (let xs (readall:pbpaste) (map [eval (list '$ _)] butlast.xs) (eval last.xs)
(each x '(sum0 sum1 sum2 _sum3) (repeat 2 (time:eval `(($ ,x) 10000000)))))
;64-bit racket v5.2.0.3: no mallocing beyond initial compilation
time: 41 cpu: 41 gc: 0 mem: 25720
time: 40 cpu: 41 gc: 0 mem: 6096
time: 80 cpu: 80 gc: 0 mem: 7576
time: 80 cpu: 80 gc: 0 mem: 6136
time: 81 cpu: 80 gc: 0 mem: 7576
time: 80 cpu: 80 gc: 0 mem: 6096
time: 1026 cpu: 1027 gc: 0 mem: 7408
time: 1018 cpu: 1019 gc: 0 mem: 6112
;32-bit racket v5.1.3.10: runtime is dominated by consing bignums
time: 894 cpu: 892 gc: 24 mem: 1478560
time: 872 cpu: 872 gc: 16 mem: 1236500
time: 841 cpu: 841 gc: 15 mem: 1238156
time: 844 cpu: 843 gc: 17 mem: 1236476
time: 839 cpu: 839 gc: 15 mem: 1237300
time: 838 cpu: 837 gc: 15 mem: -15541124
time: 1857 cpu: 1857 gc: 18 mem: 1237784
time: 1864 cpu: 1864 gc: 17 mem: 1236436
I haven't fixed `apply` yet, but I did put in a workaround. Using Racket's `apply`, Nu is actually faster than Arc 3.1 and ar!
(timeit (let a 1 a))
ar time: 8.101 gc: 0.268 mem: 973.008
Nu time: 6.923 gc: 0.0 mem: 88.736
Arc 3.1 time: 4.77 gc: 0.28 mem: -3305.9
(timeit (let a (list 1 2) (car a)))
Arc 3.1 time: 17.3 gc: 0.86 mem: -7,759.58
ar time: 10.303 gc: 0.552 mem: 1258.64
Nu time: 8.158 gc: 0.196 mem: -515.648
(timeit (let (a b) (list 1 2) a))
Arc 3.1 time: 17.47 gc: 1.0 mem: -6997.07
ar time: 13.166 gc: 0.696 mem: -16510.112
Nu time: 12.102 gc: 0.512 mem: -10028.488
So, it seems my idea of applying nested functions to implement destructuring is good in essentially every way: faster, shorter, and easier to implement.
Interestingly, judging by the data above, it would seem Arc 3.1 is very slow at creating lists, probably because `list` is implemented in arc.arc, whereas ar and Nu provide faster implementations.
---
Now let's test optional args:
(timeit ((fn (a) a) 1))
ar time: 7.534 gc: 0.352 mem: 866.232
Nu time: 6.976 gc: 0.0 mem: 88.368
Arc 3.1 time: 4.78 gc: 0.28 mem: -3295.58
(timeit ((fn (a (o b)) a) 1))
ar time: 14.493 gc: 0.464 mem: 1639.648
Nu time: 7.903 gc: 0.248 mem: -1664.792
Arc 3.1 time: 5.84 gc: 0.36 mem: -2097.19
Overhead
ar - 6.959
Arc 3.1 - 1.06
Nu - 0.927
As you can see, in Nu and Arc 3.1, there's very little overhead from optional args, but in ar, optional args are quite costly.
Update: I didn't want to be unfair to Arc 3.1 because of its slow implementation of `list`, so I redid the tests using `quote` instead:
(timeit (let a '(1 2) (car a)))
Nu time: 10.628 gc: 0.196 mem: -1747.08
ar time: 8.529 gc: 0.252 mem: 967.432
Arc 3.1 time: 5.26 gc: 0.34 mem: 4952.98
(timeit (let (a b) '(1 2) a))
Nu time: 14.066 gc: 0.52 mem: 90.504
ar time: 13.305 gc: 0.376 mem: -9236.904
Arc 3.1 time: 6.79 gc: 0.35 mem: -2,093.93
Overhead
ar - 4.776
Nu - 3.438
Arc 3.1 - 1.53
As expected, Arc 3.1 is miles ahead of both ar and Nu. Interestingly, Nu is now listed as slower than ar... it would appear that either Nu has a faster implementation of `list`, a slower implementation of `quote`, or possibly both. In any case, this demonstrates that applying nested functions should be approximately the same as complex fns in terms of speed.
One thing I noticed is that Nu has drastically greater overhead than Arc 3.1, but less than ar.
It seems the problem was that quote was slow in Nu. I've fixed that, so here's the new times:
(timeit (let a '(1 2) (car a)))
ar time: 8.613 gc: 0.308 mem: 460.696
Nu time: 7.671 gc: 0.0 mem: 88.976
Arc 3.1 time: 5.33 gc: 0.35 mem: 5050.25
(timeit (let (a b) '(1 2) a))
ar time: 12.111 gc: 0.436 mem: -19278.128
Nu time: 11.438 gc: 0.324 mem: 1435.016 (apply fn)
Nu time: 8.96 gc: 0.0 mem: 125.352 (Racket let*)
Arc 3.1 time: 7.0 gc: 0.35 mem: -2124.82
Overhead
ar - 3.498
Arc 3.1 - 1.67
Nu - 1.289
Nu now has the lowest overhead out of the three...! Also note that Nu does not spend any time in garbage collection, unlike ar and Arc 3.1.
This seems to be a common trend: Nu either spending no time in garbage collection, or less time than ar and Arc 3.1. Not sure how important that is compared to raw speed, but it's nice.
Unfortunately, this also demonstrates that applying nested functions is slower than using a Racket let*. So the reason Nu won the speed contest earlier wasn't because of my destructuring idea: Nu was just plain faster than ar in general.
And since I'm in a timing mood, here's the times for optional args:
(time (repeat 1000000 ((fn (a (o b 3)) (list a b)) 1 2)))
Arc 3.1 time: 1828 msec.
ar time: 1814 msec.
Nu time: 1554 msec.
So, it does make a difference that Nu uses plain lambdas, rather than complex fns! Now I just need to get apply to be faster.
---
On a related note: racket-set! is slow. Using racket-let or Arc's let is faster, by a fairly significant amount. So I'll be changing my compiler so it doesn't use mutation.
Nu should be feature-complete, which means it implements everything that Arc 3.1 does.
However, seeing as how I've only spent the past 4-5 days working on it, obviously it may have bugs, might be slow, and is missing some new additions I want to add to it.
The "Details" section of the README should cover the stuff you want to know, but in case it doesn't, feel free to ask me.
---
Thank you to awwx for writing ar, which was both an inspiration and the physical basis for large parts of Nu.
I noticed at the end of the article that it mentioned that PLT Scheme had already implemented reset and shift in a library... Sure enough, in /usr/lib/plt/collects/mzlib/control.ss, I found the implementation.
I then shamelessly copied it and modified it so it would work in Arc. Not sure if that counts as copyright infringement, but either way I'm fine with releasing it under the LGPL. The result is composable.arc, which can be found on my lib branch:
The situation regarding Arc is somewhat... confusing. There is the official Arc 3.1 which is developed by Paul Graham and Robert Morris. It has not been updated in quite some time now.
There is the unofficial Anarki port[1], which has seen active development.
There are various ports of Arc to other languages, such an jarc[2] and Rainbow[3]. These are generally the same as Arc 3.1, but may have new features and may not be 100% backwards compatible.
There is also ar[4], created by awwx. It is essentially a rewrite of the Arc compiler from scratch, trying (more or less) to keep backwards compatibility while also adding new features. Its goal is to make the compiler accessible to Arc code, allowing for more hackability. This is what I personally use.
Then there are all the various other ports, forks, private repos, etc... not to mention spinoffs and libraries like wart[5], Lathe[6], or Arubic[7].
Basically, Arc is what you make it. Its goal is to be hackable, so that you can change the language itself. Thus the distinction between "official" and "unofficial" is somewhat less important than it is in other programming communities[8].
* [8]: The distinction may be less important, but it does still matter: if you want your code to be runnable by the widest possible audience, you need to be careful to write your code so that it works on at least Arc 3.1, and probably Anarki as well. This doesn't matter if you're targeting a single platform.
You can use the pipe-from function or the w/pipe-from macro:
(w/pipe-from x "ls -l"
(readlines x))
That will collect the output from the command "ls -l" and return it as a list of strings. Since it's a normal output port, you can use any of the standard stuff on it, like readc, readline, etc. I chose to use readlines because I use that the most often when dealing with scripts.
---
If you only want to call a script, and don't care about it's output, you can use system:
(system "ls -l")
And if you want to collect the output into one giant string, you can combine it with tostring:
(tostring:system "ls -l")
This returns a single giant string, rather than a list of strings, as in the pipe-from example. Using pipe-from is a bit more verbose, but gives you more power and control, so I prefer it rather than system.
It would appear readlines is also specific to my copy of Arc, so here it is as well:
(def readlines (x)
(drain:readline x))
I have included lots of useful stuff like that in my fork of Arc... And here is an obvious shortened version, for the common case of getting the output as a list of strings:
(def pipe-lines (y)
(w/pipe-from x y readlines.x))
