Chain and the Gang
Posted by jgrant, 2009-05-30
So as usual I'm late to the party but better late than never right ?
Even if left-field indie rock is not your thing, Ian Svenonius' new band's debut is pretty groovy and anything but weak. Possibly some of his best work to date. Sarah Pedal's contribution is vocally indispensable too.
Seeing them do their thing live in downtown Seattle last night amongst a crowd of less than fifty (including a mix of socially-dead-ended hipster's) was quite ironic considering the content of the lyrics. Hardly a non-conforming stereo-type they played to but then again maybe this is the intended audience ?
"Youth is wasted on the young,
wealth is wasted on the rich and
beauty is wasted on the... beautiful."
All the songs from their debut album are great, the closing "Deathbead Confession" is really biting and stands up to(maybe even surpasses) anything Dylan-esque. After all this is the same mind that penned 'The Psychic Soviet'. Also parallels with Rodriguez' 'Cold fact' ?
Down with Liberty... Up with Chains !
Stop making college students sit through commencement speeches
Posted by jgrant, 2009-05-25
From Bill Maher's 'New Rules' (2009-05-15) :
You've just gone years into debt for a worthless diploma, and now here's a reward: 20 minutes of motivational bullshit from Coach Bobby Knight.
Now, maybe I'm just upset because I've never given a commencement speech. Even the girls' school I founded in South Africa for disadvantaged pole dancers hasn't asked me. And I think I know why. It's because I can't be trusted to bullshit. I firmly believe if college students wanted to hear more drivel they're never going to use again, they could go to class.
So, I would tell the class of 2009 exactly what they really have to look forward to: working at Starbucks. I'm joking of course. Starbucks isn't hiring.
But, here's the speech I would give. [he puts on mortar board] Graduates, faculty, alumni and guests, I am truly honored to speak at your university. Mostly because it's a great place to score cheap weed.
Now, I've been asked by your dean to keep it brief, and by your feminist studies club to keep it humorless. So, Class of 2009, as you go out in the world, here is my message for you: Give up.
Seriously, you're about to enter the worst job market since Adam and Eve hired the very first employee. A Mexican to tend their garden. On top of that, you went through the American educational system. You wrote "Hi, Mom" on your cap and misspelled "Hi."
And if all that wasn't enough, you are the first generation to inherit an environment that's probably already toast. But, hey, maybe you can make a few bucks smearing sunscreen on old people.
Just remember there's more to life than work. Maybe now's the time to appreciate the little things: a flower, a sunset, a shopping cart full of cans.
And, so I say to you as you embark on your adult life, take a moment to look back and honor your parents. Because they're the ones who paid for your education. They're the ones who stood by you the whole time. And they're the ones who you'll be moving back in with in the fall.
So, look at them. Look at your parents right now. Or, more likely, your dad and his new wife, who is your age. And your mom and her new boyfriend, who she met on MySpace.
And after the ceremony, I want you to take them aside and say something very important to them: "This is your fault!! Who do you think it was who tanked the economy and spent all the money and melted the planet and let the schools rot?!!"
Yes, it was us. But, at least, I hope we taught you that, in life, there really is no such thing as failure. Because, if there were, we wouldn't be seeing Dick Cheney on TV everyday.
In closing, remember that, above all, that no matter where life takes you, you will always have something deep inside you of great value: plasma! [he tosses mortar board in the air]
Beautiful sounds
Posted by jgrant, 2009-05-23
'God is an Astronaut' has made some of the most beautiful and telling music this millenium.
From 2003s 'The Beginning of the End' :
It's good to be wrong about Lisp performance
Posted by jgrant, 2009-05-06
The last article ended with a challenge hoping that someone would come up with an improved version of the boggle solver that beats my version. Well someone did, they also proved that with this particular algorithm the Lisp version can match C within about 20%. Very good !
Here are the new graphs (note that the first is no longer on a logarithmic scale).
The patches have been merged into the boggle git repo.
As for the problems encountered with the C version :
I've not done much testing on anything besides 64-bit linux. It's perfectly stable there for me and a few other folks. I don't have a 32-bit box to figure out what the issue is.
The response is much appreciated. The author also bullet points specific issues with the original code that everyone can benefit from.
It's good to be wrong about Lisp performance.
IWTB (in Lisp performance) - a followup
Posted by jgrant, 2009-05-04
The previous article had some serious traffic yesterday and today.
Due to abuse of the moderation system on some sites I've been forced to present my response here separately.
To the SBCL contributor : Relax, SBCL is still a great Lisp compiler. It always has been and I'm sure it always will be. Your work on the compiler is appreciated. It's unfortunate that you seem to fit the pontificating arm-chair theoretician stereo-type. You do have a few valid points to share in spite of your mostly incorrect presumptions regarding the Lisp code. The single worthwhile and correct contribution that you made to the discussion was your suggestion on type declarations in the critical path of the code. Thanks for that, you were one of only two people that has actually addressed the performance of the code so far. I posed a challenge to you because of your claims of being able to easily bring the code within under 3x the slowness of the C version. Your dismissive refusal to substantiate your claims with any real evidence speaks volumes to a wide ranging audience now.
The challenge to you stands indefinitely ...
anonymous coward : Thank you for the practical optimization suggestions on the code. You know what you're talking about.
You present facts objectively and we all gain from your experience in this area.
In spite of all the fury and rage (signifying nothing ?), I have recieved exactly ZERO submissions to beat the
performance of the original Lisp code. That's ZERO submissions up until now ! I'd rather not have the final word on this.
If someone does decide to submit a contender then feel free to use whatever data structures you like but if
you algorithmically optimize your Lisp code against the C version then that's just missing the point completely now isn't it ?
I'd love to be shown up with a pure Lisp version that matches the performance of C (or that at least beats my Lisp version) ...
I want to believe (in Lisp performance)
Posted by jgrant, 2009-05-03
* Update 2009-05-06 : The challenge has been met ! See the new graphs of performance. *
myths and legends
The myths and legends precede the language. Lisp. (The same holds true for its dialects and derivatives.)
Its 'bizarre' syntax, its alleged ability to stand up to low level language performance, the unique and powerful abstractions awarded the programmer who even dares to attempt its almost vertical cliff face of learning. Or so it seemed back then. With its more recent popularity there's been much hype surrounding its capabilities and especially so in contrast to other languages.
Lisp being an 'implementation' of Lambda Calculus for computers and a functional language means that many powerful abstractions are accessible to the programmer from fundamental symbolic expressions to its macros. Such abstractions simply don't exist in most other languages, specifically the imperitave kind. This has been covered a lot already on the web by some great writers and experienced Lisp hackers.
This essay will not focus on Lisp's powerful abstractions but on another practical concern of all programmers : performance, specifically compared with C.
measuring up
I'm not sure what the ratio of texts on Lisp's abstraction power vs. texts on Lisp's performance are but its cleary not 1:1.Some of the reasons have to do with the fact that the Lisp community has been more concerned with the former(and rightly so) over the last five decades than the latter. "CPU time is far cheaper than programmer time" or something like that.
A few decades ago hardware was custom designed for Lisp to run on. Nowadays most hardware is designed with C in mind.
So the author makes no claim that performance has been neglected by the Lisp community in compiler design/implementation but there's been more hype around the performance capabilities of Lisp than anything else related to the language.
There have been a few texts/papers that claim Lisp can match C in performance. My personal attempts to verify these claims seem to indicate that they are unsubstantiated (no code to demonstrate such claims) or that there was code provided but that it was so trivial(sometimes contrived) and focused on just a subset of Lisp datatypes. Sometimes benchmark code tends to suffer from this.
I think that slightly more complex code should be used to in/validate such claims. The code should be more than a couple hundred lines long but less than a thousand. Maybe it should vary a little more in its use of data types(strings, numbers etc.) and data structures(hashes, arrays, trees). It should solve some problem or play some game to excercise CPU, memory usage and IO. A reference implementation using a chosen algorithm should be implemented first in C. This will give us a performance goal for comparison with a follow-up Lisp implementation using the same algorithm, solving the same problem.
How about a boggle solver ?
I coded implementations in C and Lisp to get some answers. The details will not be explained here but the code is available at the end of the article. Both implementations use the same algorithm and corresponding data structures as far as possible.
One other rule : the implementations are intentionally not threaded to ensure that they only use one cpu core on the test hardware. The goal is not to measure multi-core performance or algorithmic/datastructure optimizations against each implementation but to instead compare the performance of the code(in time and space usage) that the respective compilers generate using as similar as possible algorithms and datastructures.
numbers & pictures
All the boggle solver implementations were compiled with 64-bit C(GCC 4.3.3) and Lisp (sbcl 1.0.18 & ccl64 1.3-r11954M) compilers. All tests were run on 64-bit Linux (Ubuntu 9.04 amd64).The test hardware is a 64-bit core2 duo(T7500 @ 2.20GHz) laptop(bus speed 800Mhz) with 2GB RAM (DDR2 @ 667 Mhz).
A few different board sizes were measured, from the standard boggle board size of 4x4 up to 1000x1000.
The fastest of 5 runs of each implementation was used.
Here are the results for running time of the solver implementations in table form :
# dimensions C SBCL CCL
4x4 0.0005 0.068 0.012
20x20 0.010 0.152 0.080
100x100 0.389 3.448 1.964
1000x1000 39.259 177.675 182.522
and as a line graph (please note the logarithmic scale) :
and memory usage of the solver implementations as a bar graph :
thoughts about the results
The memory usage between Lisp and C is fairly comparable (at least for CCL vs. C). Nothing really exciting here.For speed, as many would expect : on smaller data sets for the Lisp versions there is a higher price in start up time. This is not really an issue for real-world applications. The effects of garbage collection in the 1000x1000 scenario were only 7.720 seconds for SBCL and 4.899 seconds for CCL. As a fraction of the total respective runtimes this is fairly low. Something else is going on with the Lisp version to account for the significantly higher runtimes. The Lisp code has been carefully written to avoid boxing/unboxing of types and to let the compilers know ahead of time what types are being used at critical sections in the code. These standard typing practises do give large improvements in performance compared with performance of the same code if they were not made. In many cases this is about a 50 - 100 times improvement over Lisp code without type declarations.
Now for best case in performance of Lisp vs. C, the Clozure version performs better than SBCL over a range of input data sizes, roughly 5 times slower than C.
The SBCL version vs. C varies in performance from about 5 - 15 times slower than C depending on the input data size. SBCL seems to be slightly faster than CCL for the 1000x1000 board size but uses about 250MB more memory.
These results apparently line up with those from the "Computer Language Benchmarks Game".
lisp performance in the real world ?
Performance is only one amongst many other considerations when writing good software. In many real-world applications raw CPU performance is not the bottle-neck. its memory and IO. Web applications are a common example of this. However for the other applications where raw CPU performance is key, Lisp still is a viable competitor for many scenarios. its performance here is roughly close to other VM implementations for other languages such as Java or C#. In trivial cases (possibly purely numeric) Lisp may be able to match or even surpass C. Unfortunately trivial cases are hardly the norm.The hype that has been generated claiming Lisp to outperform C as if this was the general case is annoying and tarnishing to the Lisp community as a whole. It may be completely unfair but that's the way outsiders and new-comers will view things. What's worse is that when Haskell hackers make their claims about performance they are actually accurate most of the time. There are some advantages to being relatively later to the party so to speak. Pity about the syntax in some areas but Haskell is still an incredible and practical functional descendant of Lisp.
The gains in abstraction and expression in Lisp go far beyond a language like C and the loss in raw CPU performance is probably worth it for most applications. For the cases where this is not acceptable, re-writing the critical sections in C is fairly straight-forward and would bring the hybrid Lisp/C implementation very close to a pure C version in performance. This may be the topic of a future post here so look out.
To sum it all up : The small factor in difference between C and Lisp really does not matter. As the Lisp compilers improve in the code that they generate over the coming years the gap will close without much work on the Lisp hacker's part.
Also to note : the tested Lisp compilers were both open source. If anyone would like to test this code on commercial Lisp compilers, please do, I'd love to see the results. I have a feeling that the gap in performance between C and Lisp will be even smaller with commercial Lisp compilers.
Comments on this article :
http://news.ycombinator.com/item?id=591897">http://news.ycombinator.com/item?id=591897
http://www.reddit.com/r/programming/comments/8hlls/i_want_to_believe_in_lisp_vs_c_performance/
the code
browse : http://git.imagine27.com/cgit/boggledownload : http://git.imagine27.com/cgit/boggle/snapshot/boggle-master.tar.bz2
references
"expressivity of lisp/scheme but speed of assembly/C/C++" - Multiple authors - http://lambda-the-ultimate.org/node/670"As fast as CEE" - Multiple authors - http://c2.com/cgi/wiki?AsFastAsCee
"Lisp in Jak and Daxter" - Multiple authors - http://c2.com/cgi/wiki?LispInJakAndDaxter
"Lisp: Good News, Bad News, How to Win Big" - Richard P. Gabriel - http://www.dreamsongs.com/WIB.html
"How to make Lisp go faster than C" - Didier Verna - http://www.lrde.epita.fr/~didier/research/verna.06.imecs.pdf
"ANSI Common Lisp" - Paul Graham - CH. 13 "Speed".
"Computer Language Benchmarks Game" - Multiple Authors - "C vs. Lisp (SBCL)" - http://shootout.alioth.debian.org/u32q/benchmark.php?test=all&lang=gcc&lang2=sbcl&box=1
"Lisp as an Alternative to Java" - Ron Garret (nee Erann Gatt) - http://www.flownet.com/gat/papers/lisp-java.pdf
Boggle - Wikipedia - Multiple authors - http://en.wikipedia.org/wiki/Boggle
