Sunday, June 29, 2008

How fast is Scheme? Well....

Thinking that it'd be a good idea to become familiar with Scheme as well as Common Lisp (but, er... probably after I've read Practical Common Lisp and amn't mentally overloaded, what with me being mental so busy and needing to focus my efforts in a more single-threaded manner), I checked out Gambit Scheme in the hopes that it'd produce faster code than the other free Scheme implementations.
I don't know much about Scheme (or Lisp at all really; I've only become interested in it during the last month or so) but it seems that the Scheme compilers produce quite sluggish code, at least looking through the grainy, distorted lens that is the Computer Language Benchmarks Game.

From some of the microbenchmarks published by the Gambit guy(s) on their homepage, it looks as if it fares really well against the Chicken and Mzscheme compilers, but I wanted to examine its performance on problems relative to SBCL, which is the Common Lisp compiler I've arbitrarily chosen.
Since it's not featured on the language shootout, I pulled the SBCL code for a few tests there as well as the Gambit code which was already prepared on their site (why hasn't Gambit appeared on the shootout site for the nosy hackers who want to find out if less mainstream (man I hate that word) languages are ridiculously slow? Many of them aren't! And they're more expressive and comfortable than C++/Java, use them!) and ran a few comparisons.
SBCL comes out very much on top; in general the Gambit programs take two or three times as long to do their job (although I haven't looked at memory usage). But as far as Scheme compilers go, Gambit seems to be improving things.

(Really dodgy) timings on my Macbook (input values = whatever's on the shootout site):

Gambit:
pidigits
real 0m3.611s
user 0m3.508s
sys 0m0.066s

binary-trees
real 0m7.519s
user 0m7.309s
sys 0m0.130s

fannkuch
real 0m12.571s
user 0m12.089s
sys 0m0.205s

fasta
real 0m46.334s
user 0m42.284s
sys 0m2.668s

Lisp SBCL:
pidigits
real 0m2.422s
user 0m2.018s
sys 0m0.308s

binary-trees
real 0m1.899s
user 0m1.723s
sys 0m0.127s

fannkuch
real 0m6.221s
user 0m5.982s
sys 0m0.098s

fasta
real 0m20.730s
user 0m15.267s
sys 0m4.375s

(ratio-pidigits: 1.5
ratio-binary-trees: 3.959
ratio-fannkuch: 2.021
ratio-fasta: 2.235)


One thing I've noticed from these coarse measurements is the "sys" component of the execution time is mostly higher for SBCL; maybe this means a lot of allocation and de-allocation of stuff is going on ...Or something.

Extra legs on a dog

This hi-larious entry on the wikiwikiweb offers a series of biological analogies for the origins of some popular/not-so-popular programming languages, on the premise "how other languages became ObjectOriented octopi".

I particularly like:

JavaLanguage
  • ..made by taking an 8-legged dog, housebreaking it, and tearing out its skeleton. Then giving it a machine shop.

    • a boneless 8-legged dog manages to be less useful than either an octopus or a dog - but it comes with a machine shop, so that's good.

That said, this is exactly the kind of thing that I would chuckle ceaselessly at, for which even fellow coders would shun me for being lame and non computer scientists would simply presume me to be insane. Fair play, really.

Tuesday, June 24, 2008

Lisp problem 10: RLE of a list

This one worked out much easier, but again, I went at it non-recursively. Bitching about my struggles with the previous problems made me realise that I had solved most of the previous problems recursively but non-tail-recursively.
I guess there's a danger there of writing really poorly-performing functions on the assumption that the compiler will optimise them. Actually, I don't even know if SBCL does tail-call optimisation... It somehow seems easier to express tail-recursive solutions in Haskell, so far anyway - as a complete newbie to both languages.

;; P10: Run-length encoding of a list.
(defun encode (list)
(let ((chunked (pack list)) result)
(dolist (chunk chunked)
(setf result (append result
(list (list (length chunk) (car chunk))))))
result))


Oh yeah, how do you get around doing that ugly (append result (list (list x y))) stuff? I assume that's super slow, unless Lisp lists have a pointer to the last element for quick access since (you'd think?) appending is common. But then, some of the stuff I read in Practical Common Lisp suggests a push/reverse pattern, which to me seems a bit awkward.

99 lisp problems. Some are hard!

This much publicised set of 99 Lisp problems (taken from an original set of Prolog problems) seems like a nice step for me to take in learning Lisp as a novice to the language.

I figured the first few would be really easy with a smooth learning curve as the questions get more difficult. Certainly, I didn't expect to spend at least two hours screwing up question 9; an ostensibly straightforward problem requiring you to convert a sequence into a list of sublists, grouped by consecutively equal elements (i.e. (1 4 4 8 1 9 1 1 1 2 2 3) -> ((1) (4 4) (8) (1) (9) (1 1 1) (2 2) (3))).

After trying to solve this one a few different ways, I rejected a recursive approach and simply looped through all the elements, doing dirty stuff:
(defun pack (list)
(let (a main-list)
(dolist (x list)
(if (and (not (null a)) (eq x (car (last a))))
(setf a (append a (list x)))
(if (null a)
(setf a (list x))
(progn (setf main-list (append main-list (list a)))
(setf a (list x))))))
(setf main-list (append main-list (list a)))
main-list))


I had a quick peek at the solution provided on the site and didn't bother going through it except to note that it was indeed recursive (and not tail-recursive). Partly because some of the identifier names are in Portuguese and partly because it looks similar to the mess I had when I tried to do it recursively; I'm just not comfortable with how lists work yet - I was getting stuff like ((1 (1 (2 3)))) and ((1 (1 (2))) . 3) and all sorts of other crap.
I'm sure I could have done this quicker (and much longer and uglier) in Java, but not figuring it out properly in Lisp is making me feel a bit stupid. Wah.