Mindstab.net

Massive thanks to durka on #lisp on irc.freenode.net.
New versions of slime for emacs have had enabled by default a new feature, essentially a light highlighting of uncompiled changes to a file. At first I found it annoying but then I got used to it. It is kind of handy. However I wouldn't find out how to turn it on or off. Oh well.

Then I went to use emacs on the console and the subtle light grey background highlight was suddenly grey text on a white background and completely unreadable. Very annoying, suddenly this little feature rendered -nox emacs useless.

Hours of google searching turned up nothing so finally I resorted to the irc channel. In only 10 minutes we got the answer.

<durka> aha
 customize emacs - applications - slime - slime mode - slime mode faces
 change highlight edits face

Thank you.

Ok, so I know we announced it at around Christmas, but *now* the Mindstab AI Go Competition is starting to get under way. Both Rob and I now have entries that can compete, though mine is mostly just an over engineered random bot, until I get even more framework in place.
Still, everything has really started happening this week as now that school is over, I've had some time to devote to this, so my bot finally got off the ground. And then we got together to day and hacked on the server some more cleaning it up, and making an 0.2 release of out Go client/server software.
Finally, and most fun, we whipped together a Matchs page where you can see all the results of games so far. See, real proof that things are happening!
So with this out of the way I can really start to focus on the bot. To that end I've defiantly come up against some quicks in Lisp and SBCL. But then today we were also working in C, Python and PHP and we certainly came up against some quirks in the first two (oddly PHP really does manage to get out of your way and let you do your thing). Still, I think I have things mostly worked out and I can focus on the bot. Which is fun because I'm finding for the most part I'm really enjoying coding in Lisp and Slime+Emacs is pretty rocking. As for the bot, I'm excited. I've got some fun plans for it and I haven't done nearly enough fun coding since school's been on.

Well, since, I got Debian installed on my GP2X, the first thing I did was run some benchmarks. As per usual, I fell back on my "raw and simple math computation" benchmark suite Primes, a collection of prime number finders written in many languages. For the rest of the article we will thus be evaluating languages purely on math computational speed and nothing else.

I had already gathered data from some of my computers from when I bought Bast, my G3, so I just ran the benchmarks on the GP2X and added them in for comparison.

Machines

Results

Time in seconds to find all prime numbers between 1 and one million

	Inferno	Nika    Kvasir  Bast    GP2X
C	1.19	0.79	0.45	2.83	35.1
ObjC	1.19	0.8		2.83	43.4
C++	1.93	1.06	1.1	4.76	50.1
Java	3.59	1.63	2.14	40.3
C#	3.69	1.87		10.5	140
Awk	32.1	27.1	30	199	2065
Perl	38.2	21	23.3	145	1280
PHP	15.1	8.89	13.4	64.9	758
Python	54	38	43.8	211	1526
Lisp	10.4	5.19		36.3	2674

As you can see, of course, the 200MHz ARM GP2X was destroyed by everyone else. This really doesn't tell us anything at all actually.

Clearly scaling needed to be introduced so that we could see how the languages faired on the different architectures. All being equal I assumed that GCC would give the best optimization per platform and that the C results would be the least skewed, so I choose to represent all the results as multiples of the C time results, or divide all the times by the time that the C prime number finder took on that computer. It yielded the following results:

Time in multiples of C time to find all prime numbers between 1 and one million

	Inferno	Nika    Kvasir  Bast    GP2X
C	1.00	1.00	1.00	1.00	1.00
ObjC	1.00	1.01		1.00	1.24
C++	1.62	1.34	2.44	1.68	1.43
Java	3.02	2.06	4.76	14.24
C#	3.10	2.37		3.71	3.99
Awk	26.97	34.30	66.67	70.32	58.83
Perl	32.10	26.58	51.78	51.24	36.47
PHP	12.69	11.25	29.78	22.93	21.60
Python	45.38	48.10	97.33	74.56	43.48
Lisp	8.74	6.57		12.83	76.18

Analysis

x86 machines

You would think we could use these 3 machines to establish a baseline but we find a fairly large variance in results here. First of all, inexplicably, Inferno is the only machine to have a worse result for Perl than Awk. Also, we can see that when it comes to the interpreted languages, Kvasir is near the worst in all cases. I would attribute this to Hardened Gentoo adding very viable overhead to the interpreters. It seems to show there is a definite cost for added security in terms of efficiency.

PPC

The most notable result here is the Java result which is clearly markedly bad. Java for the PPC could use some optimization. C# care of mono on the other hand is competitive. The rest of the interpreted languages also lag behind on the PPC, although Lisp (SBCL) comes pretty close the the x86 scaled results.

ARM

And now what you've been waiting for, the ARM results for the GP2X. Well, Sadly, I just couldn't really get Java for the GP2X. Sun Java appeared to be unavailable. I could have used something like Kaffe or Jikes, but it probably wouldn't have been to fair, and also, on Debian, they insisted in pulling in some parts of Xorg as dependencies, and I didn't have a lot of space to play around with on the GP2X. Kind of lame, oh well. Again, as with the PPC, C# care of mono is very respectable. Other than that, the Lisp result was way off by a staggering amount, but that can be explained by SBCL not being available for ARM. I had to resort to the clearly slower CLisp compiler/'interpreter.'

Languages

As much hype as there is around Python these days, it appears to be fairly slow across the board compared to other interpreted languages. PHP on fact is the fastest of PERL, PHP, and Python on all tested architectures, so if you need speed and yet still the flexibility of an interpreted language, you might seriously want to use the CLI version of PHP. It seems the interpreter is very optimized across the board.

If you happened to be on an architectures supported by a good Lisp compiler like SBCL it is also a very attractive and viable option, but unfortunately for ARM, it looks like CLisp isn't, speed wise anyway.

As for Java, hopefully the GPLing of it will allow it to a) be further optimized for alternate architectures like PPC, and b) for it to be fully ported to 'new' architectures like ARM. If you're looking for speed but the middle ground flexibility of a VM language than in the mean time C# in the form of Mono is a fantastic looking choice.

Note: Ruby has again been omitted because until 2.0 is released, which includes a real VM, it is sadly not even remotely competitive in this area (math computation). It is about an order of magnitude slower than any of the other interpreted languages. Ruby 1.9 CVS last I checked (half a year ago) was competitive with Python :)

And that's it from me on the Primes front (at east until I acquire a Sparc box :P ...)

So aside from posting tid bits, and some complaints I haven't used this blog too much. So what am I up to?

School wise I'm taking a unix scripting class (prerequisite) and it's super easy and fun and an easy A. I'm also taking linear algebra and finding it hard but fun. It's neat stuff. Finally I'm taking calculus 3 which is not so much fun but also hard.

As you may have noticed from the direction of my blog posts, I've started reading the online version of Practical Common Lisp (ordered a hardcopy as well) in order to teach myself the language. It is a fantastic book and I can't recommend it enough. I love Paul Graham's essays but his ANSI Common Lisp left a lot to be desired. Practical Common Lisp takes a good approach to teaching a language by having lots of example code that the reader is expected to type in and test out. Through examples the reader is introduced to new parts of the language and complex programs are built up from the parts used to illustrate each point. This style is much preferred to other books that just give a more essayish intro to a language with minimal reader interaction. This book takes me back to a lot of the first computer books I read in high school when first learning Borland's Delphi. Those were also great books full of incremental examples. If you want to learn lisp, this is a great place to start.

Also, in order to use a nice lisp environment, I've had to start using and learning emacs. I've been a long time Vim user and fan and have shied away from emacs in the past. No more. And I'm finding on the whole I really like emacs... well, emacs + slime. It's a pretty amazing environment to code in. Being able to type functions into a file and compile each individual function independently and then go straight to a Lisp shell and interact with the function is pretty awesome and something that I've never really been able to easily do with any other language/IDE. So emacs + slime wins huge points there.

Compared to vim, you may have noticed my post/rant about how difficult getting auto-indent going (which failed) was. But to it's creadit, emacs does have smart tabbing so hitting tab anywhere will take you to where you should be. So it means one extra key per line (return + tab). I can live with that. Emacs seems to require more tinkering with files to get it setup just the way you want where as vim seems to be just about right by default.

As for vim or emacs in X (or win32 GUI), vim has a nice GTK interface where as emacs uses the very aged motif. Changing fonts isn't in the menu (M-x set-default-font Font name: 9x15), and neither is changing the color scheme (they both are in vim), but both are reasonably easily done via emacs commands, once figured out (read: googled). Also, you do have to manually install color schemes for emacs where as they ship with vim. This isn't too hard on Gentoo (emerge color-themes) but it's a bit more of a hassle for Windows on my USB stick. So some points off for usability. Emacs is more work to get up and running, but it's pretty awesome when it is. You'll also definitely want to work through the tutorial provided with emacs (C-h t) and the first chapter of Practical Common Lisp carefully. But I'm now getting the hang of it and it's pretty nice.

I doubt I'll ever switch to emacs for editing normal text files or even for programming in other languages, but it is the place to be for using Lisp. It's just too big and hulking and a bit of a hassle. Vim is so small, compact, simple, and everything I want for config file editing, text file editing, and even programing in other languages. Both have support for buffers but emacs pushes the support more and introduced it to you in the tutorial because you can't really use emacs with out understanding them. Vim (or at least vim's tutorial) doesn't focus much on them and I end up suing screen + several copies of vim for multi file editing. Again, Vim is easier to get into and learn, but emacs is probably more powerful in the long run.

As for Lisp, I'm slowly starting to get a better handle on it. It is pretty amazing it self. It has 'no syntax', you just code directly in the parse tree. It has a lot of really neat features that I've seen already that are trivial to do in Lisp and hard or impossible in other languages (anonymous functions defined and assembled in other functions, and returned as a result?). I really just can't wait to learn more. Its a lot of fun.

For some reason emacs from lispbox doesn't auto indent code by default (and as it turns out, all emcas doesn't auto-indent). Ok. But more confusingly, it isn't trivial to turn it on. It's actually hard to find information even about how to turn it on. It took me a little time with google to finally find what I was looking for some I'll repost it here.

Edit: So this failed to do anything for emcas installed on my home Gentoo box
Edit2: Also it turns out that these instructions break the Lisp Top Level and now I can't evaluate anything in emacs/lispbox so I had to disable it for lispbox too.

This is a bit silly. It should not be this hard to get auto-indent and that finally 'succeeding' it shouldn't hose everything else. Lame.

If anyone knows a sane way to get emcas to auto indent code please leave a comment letting me know how.

To get emacs to auto indent lisp code, add the following to your .emacs file.

.emacs

(defun my-set-newline-and-indent()
    (local-set-key [return] 'newline-and-indent))

(add-hook 'lisp-mode-hook 'my-set-newline-and-indent)
(add-hook 'Lisp-mode-hook 'my-set-newline-and-indent)

For other languages add do similarly like:

(add-hook 'c++-mode-hook 'my-set-newline-and-indent)

That should do it. Except for lispbox because by default it's .bat file tells it not to load config files. So change

%EMACS% --no-init-file --no-site-file --eval=%TO_EVAL

to

%EMACS% --eval=%TO_EVAL

And put your .emacs file wherever the HOME variable is set to.

I've started reading Practical Common Lisp and so I also wanted to get lispbox installed on my USB stick to play around with it. Lispbox is a fully self contained lisp environment + editor + extras that is supposed to be portable. I got it installed but it was giving me an error before loading. So that was sad.

After looking it at it more closely I noticed it was an access denied error. Upon further inspection it was trying to write to the C: drive and that's not possible on our school computers. After some googleing I came upon this post which had the solution. In lispbox.bat add 'set HOME=%CD%' just before the line launching emacs. Then it uses the USB stick as the 'home' directory and everything works.

So. Yes my Primes suite is a bad benchmark at times. Crude certainly. But also unfair for languages that I don't know well. Remember when I was surprised at how "slow" the lisp results were? Well my bad. I got Paul Graham's "ANSI Common Lisp" for my birthday on the 12th. Been doing some reading. I'm starting to get the idea behind lisp, and actually haskell too. Functional programing, programing with out side effects. Lots of recursion. Which normally I only use in certain circumstances but not in place of loops because it's innefficient. So my Lisp code used a loop. Well, it turns out that little did I know functional languages like these have something called "tail loops" (the recursive call is the last part of a function) and they can be optimized to goto loops or something. So I wrote a new primes in lisp.

primes2.cl

(defun check (max i sq)
  (if (> i sq)
    (format t "~d~%" max)
    (if (not (= (mod max i) 0))
      (check max (+ i 2) sq))))

(defun _primes (max i)
  (if (< i max)
    (progn
      (check i 3 (sqrt i))
      (_primes max (+ i 2)))))

(defun primes (max)
  (_primes max 3))

results.1000000.txt

(22/36) Common Lisp results:
Execute [sbcl]:         5.21 seconds

That's better looking. And I'm still just a total beginner. Cool though.

Food for after thought: I took a look at a haskel intro linked to on reddit and for the first time ever stuff about haskell actually made sense to me. Being a functional language like lisp, and having a list data type, like lisp, it's actually got surprisingly strong similarities. Huh.
Also, sadly, currently Ruby doesn't have tail recursion optimization, I've heard it said VARV (the ruby VM) in the next version of Ruby will support it.

So I found this (bcompile) on reddit. It's a tutorial on bootstrapping/writting a compiler starting only with a hex to binary compiler.

So I was thinking about languages again. And it's the summer (maybe that time of year again?). So today on this holiday weekend I bashed out a language that was as fast as I could make it (rather crappy as a side effect ;)).

ftp://ftp.mindstab.net/lang-2006.07.01.tar.gz

README

Unnamed language.
<haplo @mindstab.net>
www.mindstab.net

I wrote this 'language' in a day.  It's only goal was to be as fast as I
could make it.  To that end it has little to no error correction, and
statically sized buffers.  Still, it's pretty fast.

Compared to vm-proto, the 'language' I wrote last year:

vm-proto:
        assembly like syntax
        compiles to endian safe object code
        ~2.5x slower at calculating primes than unnamed lang
        has some registers
        written in c++
        usage:
                compile foo.vms
                vm foo.vmo

Unnamed lang:
        assembly like syntax
        compiles and executes code in memory
        (possibly endian safe but untested)
        about  1/3 code size of vm-proto
        has some registers
        has a working stack (small, but can be enlarged in the code by a define)
        written in dirty c (function and variable names aren't the sanest)
        usage:
                lang < foo.src

Considering this is about as fast as I can think to make a language, I honestly
don't know how languages that are so much more fully featured like PHP are
written considering PHP is only marginally slower (and faster than vm-proto),
and I assume VM's like mono and java compile their byte code to architecture
machine code at some point. (?)

I also have been running some bench marks with my old primes suite.

1000000

(1/36) C results:
Compile [gcc]:          0.10 seconds
Execute:                0.88 seconds

(4/36) x86 Assembly results:
Compile [gcc]:          0.04 seconds
Execute:                0.76 seconds

(13/36) C# (Mono) results:
Compile [mcs]:          1.03 seconds
Execute [mono]:         1.74 seconds

(16/36) AWK results:
Execute [awk]:          23.6 seconds

(17/36) PERL results:
Execute [perl]:         22.4 seconds

(18/36) PHP results:
Execute [php]:          9.65 seconds

(19/36) Python results:
Execute [python]:       41.3 seconds

(21/36) Ruby results:
Execute [ruby]:         227. seconds

(22/36) Common Lisp results:
Execute [sbcl]:         10.5 seconds

Compile [gcl]:          0.00 seconds
Execute [gcl]:          23.7 seconds

(26/36) Fourth results:
Execute [gforth-fast]:  2.15 seconds

haplo@nika ~/src/my/lang/vm-proto $ time ./vm primes.vmo > /dev/null
real    0m25.325s
user    0m25.226s
sys     0m0.052s

haplo@nika ~/src/my/lang/fast-lang $ time ./lang < primes.src >/dev/null
real    0m7.558s
user    0m7.412s
sys     0m0.024s

[Update: 2006.07.02]
optimized lang
haplo@nika ~/src/my/lang/fast-lang $ time ./lang < primes.src  > /dev/null
real    0m3.753s
user    0m3.736s
sys     0m0.008s

As you can see, PHP5 is really fast for it's class (interpreted language). I was surprised. Ruby is distressingly slow. Mono is rather closer to native compiled speed. And my newest language beats all the fancy interpreted languages! (I'm pretty sure forth has a pretty clear machine code compile path :)).

[Update: I was surprised to find out that GCL is slower by far than SBCL even though GCL compiles Lisp.]

[last published version of primes can still be found at ftp://ftp.mindstab.net/primes with both a .tar.gz available for download and all the source online for browsing.]