Peter Norvig's Sudoku solver: Clojure & Python side by side(jkkramer.wordpress.com)
jkkramer.wordpress.com
Peter Norvig's Sudoku solver: Clojure & Python side by side
http://jkkramer.wordpress.com/2011/03/29/clojure-python-side-by-side/
12 comments
You are probably only in the minority because K, J, APL and what have you look like perl turned up to 11 for those of us who are unfamiliar with the syntax.
Though if you consider that these are all vector programming languages, they are really made for this kind of thing.
Though if you consider that these are all vector programming languages, they are really made for this kind of thing.
Arthur's languages are awesome, no doubt about it. But the fact remains that they are proprietary and prohibitively so. As much as you romanticize k/q, I bet you can't even afford to run it on your home computer, let alone do any real work on it.
J, which is close enough, was always free-to-use and recently open sourced https://github.com/openj/core
K4/Q 32-bit is free for noncommercial use http://kx.com/trialsoftware.php and has been from the day it became generally available. (And before that, k2/k3/ksql were similarly available)
A free / open source K3 interpreter is being developed in https://github.com/kevinlawler/kona , and while incomplete it is already quite capable.
Oh, and Kx are (or at least were) quite reasonable with commercial use licenses for businesses that can't yet afford them.
> Arthur's languages are awesome, no doubt about it.
That is the only true thing you wrote.
K4/Q 32-bit is free for noncommercial use http://kx.com/trialsoftware.php and has been from the day it became generally available. (And before that, k2/k3/ksql were similarly available)
A free / open source K3 interpreter is being developed in https://github.com/kevinlawler/kona , and while incomplete it is already quite capable.
Oh, and Kx are (or at least were) quite reasonable with commercial use licenses for businesses that can't yet afford them.
> Arthur's languages are awesome, no doubt about it.
That is the only true thing you wrote.
Not what I heard last time I asked ;-). How about > 250K for a small multi-core installation?
Last time I asked (3 or 4 years ago), the smallest installation was ~$100k, and it was a multi-core installation.
IIRC in 2006 they mentioned that they were willing to entertain other financing models (such as equity) if it makes sense, although I have no idea how common that was, or if they are still considering it.
Regardless, the claim that "you can't afford to run it on your home computer" is preposterous - k itself is free for noncommercial use, and kona and J are free, both libre and gratis.
IIRC in 2006 they mentioned that they were willing to entertain other financing models (such as equity) if it makes sense, although I have no idea how common that was, or if they are still considering it.
Regardless, the claim that "you can't afford to run it on your home computer" is preposterous - k itself is free for noncommercial use, and kona and J are free, both libre and gratis.
Interesting that the clojure stuff is slower than python. From what I gather most clojure stuff never actually gain any of the possible multi-core performance boost that is one of promises of the language.
Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language. But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times.
Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language. But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times.
It's a simple port that avoids mutation entirely. The fact that it's only slightly slower than the Python version says a lot about Clojure performance.
In anycase, the OP was clear, the goal was to write a comparison of the original design, not to write the fastest Clojure program (and there are many ways to make the Clojure version faster, yet it's not clear to me how to best Norvig's design in pure Python).
In anycase, the OP was clear, the goal was to write a comparison of the original design, not to write the fastest Clojure program (and there are many ways to make the Clojure version faster, yet it's not clear to me how to best Norvig's design in pure Python).
> Interesting that the clojure stuff is slower than python. From what I gather most clojure stuff never actually gain any of the possible multi-core performance boost that is one of promises of the language.
Clojure always sad its designed for CONCURENCY and he said that Clojure has great primitives for parallism. Most people just dont know the diffrence.
> Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language.
That wasn't a designgoal of clojure to provid parallism just out of box. It maybe is a designgoal now because everybody wants it to be.
> But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times.
pmap does work great for some things but just thinking you can throw in some 'p'-s want wrok. Rich or anybody else never claimed that this will be possible he infact always said that it wan't but people in the internet just dont listen that well.
Clojure always sad its designed for CONCURENCY and he said that Clojure has great primitives for parallism. Most people just dont know the diffrence.
> Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language.
That wasn't a designgoal of clojure to provid parallism just out of box. It maybe is a designgoal now because everybody wants it to be.
> But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times.
pmap does work great for some things but just thinking you can throw in some 'p'-s want wrok. Rich or anybody else never claimed that this will be possible he infact always said that it wan't but people in the internet just dont listen that well.
Clojure always said its designed for concurrency and he said that Clojure has great primitives for parallelism. Most people just dont know the difference.
Well, here's the difference (according to Wikipedia):
Parallelism - a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). There are several different forms of parallel computing: bit-level, instruction level, data, and task parallelism. Parallelism has been employed for many years, mainly in high-performance computing, but interest in it has grown lately due to the physical constraints preventing frequency scaling.
Concurrency - a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. The computations may be executing on multiple cores in the same chip, preemptively time-shared threads on the same processor, or executed on physically separated processors. A number of mathematical models have been developed for general concurrent computation including Petri nets, process calculi, the Parallel Random Access Machine model and the Actor model.
Well, here's the difference (according to Wikipedia):
Parallelism - a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). There are several different forms of parallel computing: bit-level, instruction level, data, and task parallelism. Parallelism has been employed for many years, mainly in high-performance computing, but interest in it has grown lately due to the physical constraints preventing frequency scaling.
Concurrency - a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. The computations may be executing on multiple cores in the same chip, preemptively time-shared threads on the same processor, or executed on physically separated processors. A number of mathematical models have been developed for general concurrent computation including Petri nets, process calculi, the Parallel Random Access Machine model and the Actor model.
I would remove the word "simultaneously" from the concurrency definition. Two threads can be executing concurrently on the same processor - strangely, the next sentence seems to acknowledge this. My personal definitions, based on my experience in systems and high performance computing research:
Parallelism: simultaneous calculations executing in the service of a single problem, usually with the goal of improved performance.
Concurrency: executions in the same time granularity, but not necessarily simultaneous. Also not necessarily in the service of the same problem, but some form of synchronization is required.
Parallelism: simultaneous calculations executing in the service of a single problem, usually with the goal of improved performance.
Concurrency: executions in the same time granularity, but not necessarily simultaneous. Also not necessarily in the service of the same problem, but some form of synchronization is required.
Having hacked a decent amount of Clojure, I've learned that Clojure can be very fast or very slow depending on which features of the language one chooses to take advantage of. A perusal of the Clojure Google group will illustrate many examples where a few small changes to a program give an order of magnitude performance boost (or penalty for that matter). This makes it somewhat difficult to write performant code in Clojure (for me at least) as a lot of experimentation is required. Additionally, a given program has to run for at least a little while before hotspot JVM optimizations kick in which make a huge difference.
but part of the hype
One of Clojure's primary goals is to allow sane mutation and out of that falls a facilitation of concurrency and parallelism. However, it does not solve the problem of effectively utilizing multicore processors automatically. How would it ever do that without programmer intervention?
exactly.
Same thing for Erlang implementation:
https://github.com/apauley/sudoku-in-erlang
Initially Python was faster, however after some discussion and some performance optimisations Erlang got faster: http://erlang.org/pipermail/erlang-questions/2011-March/0571...
Of course, it is worth keeping in mind that they didn't also go and try to optimize the Python version. So perhaps after doing that Python would win again.
Initially Python was faster, however after some discussion and some performance optimisations Erlang got faster: http://erlang.org/pipermail/erlang-questions/2011-March/0571...
Of course, it is worth keeping in mind that they didn't also go and try to optimize the Python version. So perhaps after doing that Python would win again.
The design of the Clojure code can be clearly seen from the Python code. But I'm not sure if that's idiomatic Clojure. I'd like to see what the Clojure version would look like if a Clojure programmer solved the problem without looking at the Python code first. That would give me more insight into the differences between the languages.
Follow Norvig's lead from Paradigms of Artificial Inteligence - write fast embedded paradigms. So write a performant Constraint Solver DSL couple it with a performant Prolog DSL. Solve all kinds of problems declaratively instead of just Sudoku. I've been working on that https://github.com/swannodette/logos ;)
Yeah, I started a port of this code into Clojure about a year ago with no attempt to keep the design and it diverged a bit. I never finished it though as my plane landed. :)
Why is Clojure so slow (more exactly, why is it as slow as Python)? Naively I would have expected it to be much faster than Python - it's not.
My guess is because the Python example was written by Peter Norvig.
Hard to argue with. I don't have a Clojure environment running, but I'd like to see a comparison of Norvig's spell-checker, and Rich Hickey's Clojure translation: http://norvig.com/spell-correct.html
There is a port of the spell checker to clojure. What it does is grind the swap file for about two minutes, then abort with an out of memory exception. Sorry, don't have the link handy.
Clojure is not a very fast language.
http://shootout.alioth.debian.org/u32/which-language-is-best...
Not true according to these microbenchmarks and certainly not in my own experience.
Not true according to these microbenchmarks and certainly not in my own experience.
YMMV. I find that stuff I write in Ruby is faster than that I write in clojure. I suppose it depends on the problem space, if your problems are greatly speeded up by mutability and C bindings then clojure is not a perfect fit.
I find that stuff I write in Ruby is
faster than that I write in clojure.
Sure. I'm not saying I'm a good programmer. From the comments here a lot of people seem surprised that any clojure version isn't automatically faster than a python one, just by the intrinsic fastness of clojure. I just don't think clojure is the go-to language for simple raw speed, but apparently I hit a nerve saying it's not super-fast because I'm getting downvoted.
As a clojure novice I would assume that just by using pmap over map, computation would be faster, but it doesn't seem like it, I've experimented a little but never gotten very good at optimizing speed in clojure, here's a little test where I thought I could get at some multi-core goodness by using pmap, but probably the lazy structures are fooling me.
https://github.com/sunkencity/Adaptor-Reductor/blob/master/s...
As a clojure novice I would assume that just by using pmap over map, computation would be faster, but it doesn't seem like it, I've experimented a little but never gotten very good at optimizing speed in clojure, here's a little test where I thought I could get at some multi-core goodness by using pmap, but probably the lazy structures are fooling me.
https://github.com/sunkencity/Adaptor-Reductor/blob/master/s...
Sure. I'm not saying I'm a good programmer.
The rote replacement of map with pmap will never work as a general solution because there is overhead involved with using pmap. The impact of the overhead requires thoughtfulness in usage on a case-by-case basis.
Hm, I suppose I can agree to that.
I find that a few real-life experiments with clojure has been disturbingly slow, and that it's not trivial to optimize speed with lazy structures and magic background threads. Although some web stuff I've done has been pretty spiffy.
I find that a few real-life experiments with clojure has been disturbingly slow, and that it's not trivial to optimize speed with lazy structures and magic background threads. Although some web stuff I've done has been pretty spiffy.
Whether pmap is faster than map depends a lot on the duration of the task: see http://incanter.org/downloads/fjclj.pdf page 45
Anecdotally, at what point this is true also seems to depend on the host OS. Windows 7's pmap was beneficial at a lower n than Mac OS X's for a simple O(n) function. I have always wondered why this is.
A beautiful deck, may I add!
A beautiful deck, may I add!
[deleted]
While sometimes it's great that you have the option to use C bindings in Ruby, my take is that if possible you should write stuff in Ruby when doing Ruby. If that's not the case you are not doing ruby, you are doing C.
I would write clojure and drop back to java for speed. Only in a extrem case I would then use C, but its possible. I haven't done it but read that its not all that bad. (there is a clojure wrapper.
I'm using ruby to glue together fast stuff in C.
I think your statmend is missleading.
1. I guess you compair small programms and clojure suffers from the JVM startup slowness not because of the clojure implementation.
2. You can use java objects, collection or arrays from clojure its just not often used.
3. Clojure has very good Java bindings and I think the C bindings arn't that bad. (there is a wrapper ofer the normal java stuff)
I guess ruby only performs better for scripting.
1. I guess you compair small programms and clojure suffers from the JVM startup slowness not because of the clojure implementation.
2. You can use java objects, collection or arrays from clojure its just not often used.
3. Clojure has very good Java bindings and I think the C bindings arn't that bad. (there is a wrapper ofer the normal java stuff)
I guess ruby only performs better for scripting.
Do you see why people might have thought your comment was misleading, with the "fast stuff in C" not in Ruby? :-)
http://shootout.alioth.debian.org/u32/benchmark.php?test=all...
http://shootout.alioth.debian.org/u32/benchmark.php?test=all...
Remember the mantra: servers are cheap, programmers are expensive. If you have a language that's significantly faster to develop with but at a small performance price, i'd still go with it.
If the app becomes a Google-sized success, then I'll worry about performance. Chances are I'll never have to.
If the app becomes a Google-sized success, then I'll worry about performance. Chances are I'll never have to.
That's so wrong it's not even funny.
You know, part of the reason Google is Google is that they were worried about performance from day 1 - every possible kind of performance.
AltaVista was king at the time. It gave low quality answers, true -- but it was also slow. All the early adopters that I know of that switched to Google were impressed more by its speed than by its quality - if you knew what you were searching for, you DID get high quality content from AltaVista at the time (much like you could with Google even before the recent "farmer" update, despite the complaints from all over). What you couldn't get from AltaVista, no matter how much you tried, was a speedy answer. AltaVista would take 5 seconds; Google would have a response in 0.05 seconds.
Unless your app is defining a new niche, you have to compete with the current players. Facebook needed to compete with MySpace. Google needed to compete with AltaVista.
Google did it by storing an index of the whole internet in Ram. That's performance you worry about from day one, not something you can add in retrospect.
You know, part of the reason Google is Google is that they were worried about performance from day 1 - every possible kind of performance.
AltaVista was king at the time. It gave low quality answers, true -- but it was also slow. All the early adopters that I know of that switched to Google were impressed more by its speed than by its quality - if you knew what you were searching for, you DID get high quality content from AltaVista at the time (much like you could with Google even before the recent "farmer" update, despite the complaints from all over). What you couldn't get from AltaVista, no matter how much you tried, was a speedy answer. AltaVista would take 5 seconds; Google would have a response in 0.05 seconds.
Unless your app is defining a new niche, you have to compete with the current players. Facebook needed to compete with MySpace. Google needed to compete with AltaVista.
Google did it by storing an index of the whole internet in Ram. That's performance you worry about from day one, not something you can add in retrospect.
> Google did it by storing an index of the whole internet in Ram. That's performance you worry about from day one, not something you can add in retrospect.
It really depends on implementation. I have changed many applications from RDBMS-based to file-based to memory-based when the need arose. Of course, if you intend speed to be your competitive advantage, then you need to optimize early.
It really depends on implementation. I have changed many applications from RDBMS-based to file-based to memory-based when the need arose. Of course, if you intend speed to be your competitive advantage, then you need to optimize early.
it's true that his code is very nice.
Its thread-safe, for starters. All the algorithms that depend heavily on mutation will run (kinda) slowly on Clojure.
This is very, very cool. I wanted to look at that for a long time. This gives me a good reason.
To those questioning Clojure's performance I will just leave this: http://meshy.org/2009/12/13/widefinder-2-with-clojure.html here.
Don't want to start a religious war, but to me the Python code just looks more clean.
I am amazed that Python ran anywhere close to Closure in terms of speed, let alone faster!
I am amazed that Python ran anywhere close to Closure in terms of speed, let alone faster!
Don't want to start a religious war,
but to me the Python code just looks more
clean.
Its a straight code port. I think it would if norvig would of used CL or Clojure you could say the same thing to a python port.
I do agree that the python code looks a little cleaner but both look fine.
I do agree that the python code looks a little cleaner but both look fine.
I really like Python, but CPython is an ugly monster.
Edit: did the down-voters ever cared to read the code or even write a Python module in C?
Edit: did the down-voters ever cared to read the code or even write a Python module in C?
Isn't pypy pretty fast and feature comple? Im not up to date.
Yes, our current release implements Python 2.5 completely, and our trunk implements 2.7. As for speed, I'll let: http://speed.pypy.org/ speak for itself.
Is there a memory use comparison?
I feel like his reduce-true could be implemented with take-while and reductions, but my Clojure isn't strong enough to produce it. (last (take-while identity (reductions f ns)))) is close, but we need to take one more element than take-while does.
The spikes you are mentioning might be due to the OS lowering your process priority. If you are on a FreeBSD machine, try running rtprio(1) to avoid the OS changing the process priority upon extensive CPU usage.
The spikes are from hard problem instances - he's not running on the same data set each time.
From Norvig's post:
From Norvig's post:
But the main message is that the mean and median stay
about the same even as we sample more, but the maximum
keeps going up--dramatically. The standard deviation
edges up too, but mostly because of the very few very
long times that are way out beyond the 99th percentile.
This is a heavy-tailed distribution, not a normal one.They are more likely due to properties of the puzzles themselves than operating system behaviour, especially on a modern operating system on a multi-core machine. Plus, in the original Norvig article (http://norvig.com/sudoku.html) he talks about several puzzles which take 10s and 100s of seconds to complete, which is extremely unlikely to be due to scheduler behaviour.
With languages like Python and Clojure several background processes (like GC pauses) could also contribute to some drops in throughput.
Of course, it would be easy to tell these cases apart by counting operations (backtracks, etc) rather than time.
With languages like Python and Clojure several background processes (like GC pauses) could also contribute to some drops in throughput.
Of course, it would be easy to tell these cases apart by counting operations (backtracks, etc) rather than time.
to see the code side-by-side
http://tin.nu/sudoku.html
http://tin.nu/sudoku.html
As much as I like lisp the beauty, strength and philosophy of Lisp, it seems like I can't make the switch in my real production project. Why? Because of the readability: (Taken from the article)
let width .. inc apply max of map comp coun, wtf. Let's start from the end. map all squares with comp count values, take the max of those, increment it, put that in width. ok
then, line join repeat 3 join.. wtf. let's try it from the end; minus three times the width repeat.. ok, repeat 3width '-', then, join this, repeat it 3 times, then join again with +, and put that in line.
I always struggle like that when reading lisp, people always give example like:
(map square '(1 2 3 4)) where you can read it all in one pass.. but real code is usually more complicated. So, if I had to rewrite that more clearly, I'd probably just separate it in more functions so I don't have to have more than, say 4 nested ().
And, yeah, the problem is not that much the "read from the end", but more about the actual work of each line of lisp being a puzzle to guess where to start reading it. Some are better to read up front, others are better to start from the last. Sometime you skip the first part, and read the last part, then come back at the beginning. That is what trouble me. I want to be able to read code as fast as possible - skim over it while understanding it.
Now, you might argue that you can write nested stuff in every languages. True enough BUT it seems like the philosophy in python is more about making things clearer and using more function if it makes everything simpler/easier to maintain and understand.. while in practically all lisps code I read, it feels like it is a write-only code without thought about you will read it after.
Is it because all the "Here's why lisp is better" are written by new-lisper who are too much excited as they can now use closures and nest everything rather than using simple, yet useful, normal functions?
When I read lisps forum, it's always about how that or that doesn't support tail recursive function or why macro rocks everything, but never talking about readability and good practices about not nesting everything up. Yeah, they say to use real editor, to never look at the (), to align thing smartly.. I don't know for you, but I feel like my brain works in a kind of stack. I can put some stuff in my short memory, but I can't put more than say 5-6 stuff at once. And when I see this:
When I read python code, I think about pattern, modularity, what's the goal of the actual file. When I'm reading lisp, I can't go quickly into it because of those 10 levels nested function.
/end of rant.
(let [width (inc (apply max (map (comp count values) squares)))
line (join \+ (repeat 3 (join (repeat (* 3 width) \-))))]
let width .. inc apply max of map comp coun, wtf. Let's start from the end. map all squares with comp count values, take the max of those, increment it, put that in width. ok
then, line join repeat 3 join.. wtf. let's try it from the end; minus three times the width repeat.. ok, repeat 3width '-', then, join this, repeat it 3 times, then join again with +, and put that in line.
I always struggle like that when reading lisp, people always give example like:
(map square '(1 2 3 4)) where you can read it all in one pass.. but real code is usually more complicated. So, if I had to rewrite that more clearly, I'd probably just separate it in more functions so I don't have to have more than, say 4 nested ().
And, yeah, the problem is not that much the "read from the end", but more about the actual work of each line of lisp being a puzzle to guess where to start reading it. Some are better to read up front, others are better to start from the last. Sometime you skip the first part, and read the last part, then come back at the beginning. That is what trouble me. I want to be able to read code as fast as possible - skim over it while understanding it.
Now, you might argue that you can write nested stuff in every languages. True enough BUT it seems like the philosophy in python is more about making things clearer and using more function if it makes everything simpler/easier to maintain and understand.. while in practically all lisps code I read, it feels like it is a write-only code without thought about you will read it after.
Is it because all the "Here's why lisp is better" are written by new-lisper who are too much excited as they can now use closures and nest everything rather than using simple, yet useful, normal functions?
When I read lisps forum, it's always about how that or that doesn't support tail recursive function or why macro rocks everything, but never talking about readability and good practices about not nesting everything up. Yeah, they say to use real editor, to never look at the (), to align thing smartly.. I don't know for you, but I feel like my brain works in a kind of stack. I can put some stuff in my short memory, but I can't put more than say 5-6 stuff at once. And when I see this:
(let [width (inc (apply max (map (comp count values) squares)))
When I read python code, I think about pattern, modularity, what's the goal of the actual file. When I'm reading lisp, I can't go quickly into it because of those 10 levels nested function.
/end of rant.
len(values[s]) for s in squares)
(map (comp count values) squares)
(inc (apply max
1+max
line = '+'.join(['-'*(width*3)]*3)
line (join \+ (repeat 3 (join (repeat (* 3 width) \-))))
So only real diffrences are on the first line clojure uses apply and on the second repeat instead of join.
I think is just a matter of training. Much harder then the language reading is to know what the standard functions really do.
I love Lisps, and I have the same problem. You really have to learn to approach reading code in a different way. Lisp (and Haskell, say) are so information-dense that you just have to look closely at every word to understand what is going on, as opposed to C or Python where you can glance at a "paragraph" of code and get a decent sense of what it is doing , because it is basically executing a set of statements in order. Probably the closest you get to this dense unpacking issue in Python is when reading a gnarly list comprehension.
The upside is that the code actually is smaller, so you have to read less of it. But I agree that it is fatiguing to read dense code that you can't really skim.
The upside is that the code actually is smaller, so you have to read less of it. But I agree that it is fatiguing to read dense code that you can't really skim.
(inc (->> squares (map (comp count values))
(reduce max)))
[deleted](1)
( can be found with a test case in http://nsl.com/k/sudoku/aw3.k )
The Norvig code is smarter - it always tries to fill the square with the least options. The Whitney code is dumb - it just recursively tries everything that's not blocked by peers in order. Both backtrack on failure.
The codes are equally general - both work off a data driven peer list (peers, p). The K code runs much faster for most boards, but there are boards in which the Norvig heuristic makes a x100 difference.
Personally, I prefer the K version, although I'm aware I am in the minority.