Performance tips for Clojure

[This has been edited since I was wrong about some things]

Clojure is very fast.
It is also extremely easy to write slow Clojure code.

So here are 5 tips that will help you optimize Clojure code if you are suffering from performance problems.
I'm not going to add this as a point, since it has been written all over the Internet, but it is nonetheless the most important thing to keep in mind.
Make it work, then make it right, then make it fast.
Premature optimization is the root of all evil.
Any other famous frase?

Improving the algorithm is almost always better. No matter how well you micro-optimize an algorithm that runs in exponential time, performance is still going to suck. Some of the tips presented here however, deal with algorithmic properties of some Clojure functions and structures.

To measure speed bottlenecks, you need a profiler. A very good profiler is the Yourkit Java Profiler. Unfortunately it is closed-source and not cheap. They release free early-access versions of the software that you can download. As of the time of this writing, a new version just came out and there is no early-access program.

The profiler that I have been using is JVisualVM. It comes with recent JVM's. I don't like it quite as much as Yourkit, but it's very nice and more than enough.

Follow the following steps only if you have exhausted all possible algorithmic improvements.

1. Profile. Edit one thing. Profile again.

Profile your code with your chosen profiler. Identify the bottleneck. Formulate a theory of what is to blame, fix it, and test it. Don't try two things at once. Try one improvement at a time. This is a general optimization strategy that will serve you well if you don't know it already.

2. Beware of reflection

Use (set! *warn-on-reflection* true) so that Clojure warns you about reflection.

Look at the following function:

(defn str-split [s regex]
      (vec (. s split regex)))

Clojure doesn't know if 's' is a string, so it will do an actual search to find a matching method which name is "split" on whatever class 's' belongs to. This will be horribly slow.
It is easily fixed this way:

(defn str-split [#^String s regex]
      (vec (. s split regex)))

This new version tells Clojure that str-split expects 's' to be a string.

3. Understand the Clojure data structures' performance characteristics.
[Turns out I didn't understand them. I'll add something later]

4. Iterating is tricky.

When you are writing functions with side-effects, you will often resort to the good-old 'for' loop. The closest equivalent in Clojure is:

(dotimes [i 100])

This is macro-expanded to something like this

(let* [limit (clojure.core/int 100)]
      (loop [i (int 0)]           
           (when (< i limit)
        (recur (Unchecked-inc i)))))    

..which will be as fast as Java.

If you need a more powerful 'for' loop, it is a very simple macro to write =).

5. Use java primitives.

If you need to do fast arithmetic operations, using encapsulated Integers, Doubles, etc.. is not good enough. You need Java primitives like int,double, etc..

Integer operators do overflow checking to convert Integers and Longs to BigIntegers. You can get around this check by using unchecked operators: unchecked-add, unchecked-dec... etcetera

The usual operators +,*,inc,/, etc.. do not do checking for floats and doubles, and as long as you use primitives they will be fast.

6. When all else fails...
... use Java classes. A Java array will be faster than a Clojure vector. A Java map will be faster than a Clojure map. Use this as a last resort. Clojure's data structures are very fast and should almost always be enough.

This are my tips so far. I may edit this post in the future to add more points if I come up with something or if people that read this suggest something else. I am pretty ignorant with regard to the performance of STM. Maybe someone can add a point about it.

Lisp after Python after Lisp.

(Or, Python vs Clojure rant)

This post assumes some familiarity with Lisp and Python from the reader.

Like loads of programmers, I have read most of Paul Graham's essays, and I always finish them with that feeling that if I'm not using Lisp then I must be an idiot. Like most programmers, I certainly don't want to be an idiot, so I went ahead and learned Lisp, Common Lisp.

At first, I was horrified by all those damned parentheses. Still, I kept at it until I was able to write code half-decently. I didn't get very far, and truly diving into Lisp was buried deep into my to-do list.

I didn't really got Lisp until I learned about Clojure.
Clojure is a new functional Lisp that runs on the JVM. It is a great language with brilliant design and it has the potential to bring some great research ideas into the mainstream.

Learning Clojure has gotten me to really appreciate Lisp for what it is.
Some months ago I wrote about how I loved LINQ. With Lisp, I can't complain if I don't have LINQ, I can just write a macro to implement it.
I understand that when I'm writing Lisp code, what I am writing is an abstract syntax tree (AST) in human-readable form. You can see code as the very data structure that represents your program, and you can modify it as such. That is why Lisp must be just the perfect language for Genetic Programming, where code needs to modify itself.

I love the fact that in Lisp everything is an s-expression. S-expressions have an advantage that I hadn't anticipated. They make editing easier in an editor like Emacs where you have commands that explicitly handle sexps.
Editing Lisp inside Emacs, after a while, is a very enjoyable experience. You can transpose,kill,navigate through and mark sexps as if they were letters or words. And since everything in Lisp is an s-expresion, it becomes very malleable.

So, after having my Lisp epiphany, I started seeing Python through a new light. I saw that Python was just like Lisp in so many ways, yet it was different in many others.

Python is dynamic and has a REPL. Both are huge advantages that Lisp has had for decades.
In Python, there is a difference between statements and expressions. This was my first big no-no on my comeback to Python.
I would like to write something like this:

a = if (x == 2):
           "Hello"
    else:
           "Goodbye"

Lisp code is elegant, and Lisp as a language is mathematically beautiful. It is also true that once you get used to all the parentheses you start not to notice them. However, Lisp is just not as pretty as Python. There's only so much you can do when your language requires the programmer to write the AST directly.

Python has the most beautiful syntax I have yet to see. Letting whitespace have syntactic meaning is a great design decision. The resulting code is indented the way people should indent their C-style programs anyway.
I have found downsides to this approach. In programs with lots of consecutive, horrible OpenGL API calls, things would look prettier if the language would let you indent at will. 99% of the time, however, it is a feature rather than a bug.

Every programmer has some personal pseudocode. This pseudolanguage is the language we think in. Python is as close to most programmers' pseudocode as you can get. I get this warm, fuzzy feeling when I code in Python. Its philosophy dictates that programming is so hard that the language should really just get out of the way of the programmer.

Programming in Clojure has definitely changed the way I program. More thanks to the fact that it is functional than to the fact that it is a Lisp. After you pass the brain-freeze that is inevitable when dealing with lack of state, you reach a point of enlightenment. That is that you realize that programming functionally frees you from worrying about post-conditions and pre-conditions. It is such a nice feeling when you know that a function isn't really changing the world, that it will change the way you code in other languages. Being stateless lets you stop worrying about a huge set of problems. It makes you smarter, since you are keeping less things in your head, and it reduces the bugs you can create. I am not saying you'll absolutely loathe state after spending time with a functional language. I love a for loop as much as the next dude, I am saying that you will avoid state when you can. I agree with Tim Sweeney in that the functional paradigm should be the default. And that modifying state should be made explicit. I think this concept is present in Clojure's STM approach, although it hasn't really been proven effective in huge, complex applications.

I still prefer to code in Python than to code in Clojure, just like I still prefer to speak in Spanish, my native language, than to speak in French.

When I code in Lisp, I write pseudo-code that is pretty similar to Python and then I translate to Lisp as I write. Yet now, when I'm writing in Python, I often say "This would could be easier to express with Clojure". I would like to know if my pseudolanguage is a product of having been exposed to imperative programming all these years. I don't know if there are programmers out there whose pseudo-language is functional. Maybe it's just human nature to think imperatively.
If my pseudolanguage ever starts to look like Clojure, I guess I'll have my answer

3n+1 Programming challenge in clojure. (Clojure is fast!)

My cousin was solving a programming challenge involving the collatz conjecture. He was implementing his solution using dynamic programming in C++

I thought it would be fun to try and write it in Clojure.

Our solutions are pretty similar, and mine ended up being about 2 times slower than his.

(set! *warn-on-reflection* true)

(defn check-len*
  ([l cache] (check-len* l cache 1))
  ([k cache len]
  (loop [k (long k)
         len (long len)]
    (let [val (get cache k)
          is-even (even? k)]
      (if val
        (unchecked-dec (unchecked-add len (long val)))
        (if (== k (long 1)) len
              (recur (long (if is-even
                             (bit-shift-right (long k) (long 1))
                             (unchecked-add (long k) 
                                     (unchecked-add (long 1)
                                     (long (bit-shift-right k 1))))))
                     (long (if is-even
                             (unchecked-inc len)
                             (unchecked-add len (long 2)))))))))))

(defn check-max [a b]
    (loop [i (long a)
           max (long 0)
           cache {}]
      (if (>= i b) max
        (let [val (check-len* i cache)]
          (recur (inc i)
                 (long (if (> val max) val max))
                 (assoc cache i val))))))

(defn go [beg end]
  (time (check-max beg end)))

As of memory, for the range 1-10,000,000 I am using 1.7gb of heap memory, while the C++ implementation is using 1.2gb.
My implementation is 42% beefier. and 2x slower. But it's smaller!

Since almost half the time is spent putting and getting values from the clojure map, using a Java HashMap is an improvement, and actually makes the solution faster than the C++ version. (Memory-wise, it settles on less than 1.2gb after the solution, but just before it finishes it reaches 1.4gb)

(set! *warn-on-reflection* true)
(import '(java.util HashMap))

(defn check-len*
  ([l #^HashMap cache] (check-len* l cache 1))
  ([k #^HashMap cache len]
  (loop [k (long k)
         len (long len)]
    (let [val (. cache get k)
          is-even (even? k)]
      (if val
        (unchecked-dec (unchecked-add len (long val)))
        (if (== k (long 1)) len
              (recur (long (if is-even
                             (bit-shift-right (long k) (long 1))
                             (unchecked-add (long k) 
                                    unchecked-add (long 1)
                                   (long (bit-shift-right k 1))))))
                     (long (if is-even
                             (unchecked-inc len)
                             (unchecked-add len (long 2)))))))))))

(defn check-max [a b]
    (loop [i (long a)
           max (long 0)
           cache (new HashMap)]
      (if (>= i b) max
        (let [val (check-len* i cache)]
          (. cache put i val)
          (recur (inc i)
                 (long (if (> val max) val max))
                 cache)))))

(defn go [beg end]
  (time (check-max beg end)))

An all-around better solution is to use the optimization tips on the wikipedia article for the Collatz Conjecture, which would reduce it to some arithmetic trickery.

Lack of CS interest in Google trends.

So the other day I was checking out Google trends, and I figured I'd check how my favorite editor, Emacs, was doing.



Turns out that there has been a steady decline in the number of google searches done for "emacs" from 2004 to Jan 2009.
I wanted to see how "eclipse" was doing, but I figured that most of the people that would search for eclipse must mean an actual eclipse, not the IDE. So I then proceeded to see how Java was doing:


As you can see, there is a very similar decline, though with less of a slope.

Intrigued, I checked the trend for the much more general term "Algorithm":


Almost the same decline as "emacs"!! Except for spikes that seem to correlate to school terms.

Now take a look at the trend for "computer science":


If you ask me, I would tell you that this is a sign of a steady decline of interest in computer science/programming, since the very general term "math" doesn't show the same slope:
(Note that there are very marked valleys correlating with school vacations).

What's the angle between two continuous functions?

I want to write about something very cool I learned about in my Linear Algebra class the other day.
Since since the sum of two continuous functions is continuous, and a continuous function multiplied by a scalar is continuous, the set of all continuous functions defined on the domain [a,b] is a vector space.
You can define an inner product [F|G] as the integral of the product F*G from point a to b (This operation has everything it takes to be an inner product). The inner product naturally gives us a norm. ||F|| = sqrt([F|F]), and an angle between functions: [F|G] = cos(theta) * ||F||||G||. The norm gives us a distance ||F-G||.
So now we have distance between functions and angles between functions. That means we can project a function onto another the same way that we can project a vector onto another in R^n. That's awesome! And potentially useful. =P

(Edit: Yes, it's useful. You can deduce the Fourier Series by noting that the cosine and sine as basis for this vector space)

Word Challenge cheating program

I have been playing Word Challenge on facebook, it is a very fun game. It made me start playing with anagrams, and I decided to write an anagram-solving program. However, I read about Donald Knuth's insight that if you sort a word and its anagram alphabetically, it will give the same word.
Example:
sergio -> egiors
orgies -> egiors
That means 'orgies' is an anagram of my name =P.
So, using a hash table it is pretty easy to find anagrams in constant time. You just have to associate a word made up of ordered letters to a list of all the possible anagrams. You can do it in O(n) by iterating through a dictionary file. There's no problem to solve when there is already an optimal solution.
I then decided to write a program that finds every possible word that can be formed by a group of letters (Which would be perfect to use if I ever wanted to cheat on Word Challenge. Which of course I never would! =P) .

I wrote an algorithm on top of Knuth's idea that is stupidly slow.
It takes n letters, and sorts them. It then finds all the anagrams associated to that sorted word and adds them to a set. Then it recurses to each possible word created by removing one letter, until it reaches the minimum number of letters. Which is, by default, 3.

I haven't proven it, but if my math is right, my algorithm is O( (n^2)(n-1)! ).
It works instantly on my machine when n<9.

http://sites.google.com/site/bigmonachus/Home/wc-py
It reads any dictionary file that is composed of single lines containing words on some language.
It is written in English, but there is some Spanish output. (You can probably figure out what it says.)

I was thinking of not uploading it, but there are probably already a lot of web applets that do the exact same thing, and I guess your average cheater wouldn't go through the trouble of running a Python script if he/she can't go through the trouble of practicing to get better at the game.


There are some obvious optimizations that could be made, like taking into account repeated letters.
There is also the option to change the data structure: First, load the dictionary to a list. Then order that list by the size of the words (from short to long).
For each word, create a key and append that word to the hash map with that key.
Create n sub-keys, where n is the number of letters in that key. Each sub-key has a letter removed. Since the key is sorted, each sub-key is also sorted. That means it is a valid key. Since it is shorter, it has already been added to the hash map (unless it doesn't have any anagrams or it is below our limit. In those cases, we ignore it). We add the values associated to these sub-keys to the value of the hash-map for the current key.
We are using dynamic programming, since we are eliminating the need for recursion by saving state. I don't know if I explained myself right..
There is no implementation for this idea since I came up with it as I was writing it =D. The new data structure would allow us to get all possible words for n letters in constant time!. And that structure can probably be filled pretty fast.

I'll edit this post when I have a working implementation =D

Update: New implementation.

I implemented the idea I wrote about, and it worked! (Sort of..)
First off, it takes a lot more memory. I have a Spanish dictionary with around 80,000 words, and my program is consuming about 177 MB of memory. This can be hugely improved by using indexes instead of storing strings.
The good news is that if you input any word to the program, and that word or any of its anagrams are in my dictionary, the program outputs all the possible words that can be formed by those letters in constant time.
The bad news is that if you input any word whose key is not in the hash table, the program can't tell you anything.
The solution to this was to check for this problem, and in those cases, iterate recursively through the possible sub-keys until we find the ones that are in the hash map.
This solution will cause the program to be extremely slow when you input large strings whose keys are not in the hash table.
Link to the new version.
Again, there are a lot of things that can still be improved. But this version works better than the last one.

Some sound processing ideas..

Today I was spending some time trying to find a really cool thing to do with my Arduino and accelerometers, without having to spend more money on electronics. I came up with what I think is a really neat idea: Acceleration-controlled digital audio processing!, which is fancy-talk for "I want to plug-in my guitar to my computer and do some crazy effects that change as I move some part of my body".
One idea is to use the accelerometer to interface with OpenAL's 3D audio functionality. So if I want to listen through the back speakers of a 5.1 system, I just have to tilt my device backwards!. This would come in handy for testing how well are my Bose Companion 5 speakers working. I think this will be pretty easy to implement on top of my rotating cube idea.
The second idea is a lot more sophisticated. I would like to write some real-time sound effects and run them through some input. Specifically, my guitar =). The idea is to eventually have a device strapped to some body part with a weight associated to each acceleration axis, each associated with an effect, or an effect-parameter. I'll start writing a prototype for the first idea today, as soon as I finish my homework..