jimx0r: (Default)
So, work has decided to help a user re-implement his code written originally in Basic in a language that might be A) a bit faster and B) easier to compile/run under Linux. A co-worker mentioned this to me and I said "hmm, bet we could do it in Lisp!"....

So, I got myself a copy of the code. And, frankly, it is ugly as sin! I did a quick-and-dirty re-implementation in CL, a quick bit of profiling and optimization (mostly just declaring the types of my arrays to be floats) and my code takes about 1.5 seconds to run the same problem as his code can do in only 1.5 *hours* (yes, that's a 3 orders of magnitude improvement!).

One of the things that I did in my code, rather than a naive "translation" of the original code, was to replace statements that looked like the following with what I considered to be more reasonable alternatives:


Where "dist$" is previously set to a string like this:

I replaced these in my code with a macro that expands to
(- (aref position j) (aref position i)) where i, j, and position all come from the lexical environment.

So, I told my co-worker that initially turned me onto the problem about my speed-up. To say the least, he was a bit skeptical! We got to wondering if writing the code as inefficiently in CL would produce similarly slow code... In fact, I was *asked* if I could implement the equivalent of the above code in CL.

My first take was something like this:
(defmacro dist (array i j)
   `(eval '(- (aref ,array ,j) (aref ,array ,i))))

Unfortunately, that eval is done in the NULL Lexical environment, so I, J, and position are not bound! :P So, I stopped into #lisp and got a few suggestions. What I finally came up with is this:
(defmacro dist (array i j)
       (append '(lambda (array))
                           (format nil
                                       "(abs (- (aref array ~A) (aref array ~A)))"
                                       ,i ,j)))))

In short, I read from a string that I generate with I and J substituted for their values which gives me the "formula" and pack that into a function. I decided to "hard-code" i and j into the strings so that they would be unique each time (so that Lisp won't be able to optimize away a the entire eval statement! I then funcall this function with the value of the array from the environment.

Now that I've made my *awesome* modification to the code, it runs in about 2 hours! YES! I beat the horribly written code written in a horrible language at being *really slow* with my own carefully-crafted to be insanely slow CL code! Lisp wins again!

I did a little more with optimization of the non-slow code, I've now got it running in about 0.6 seconds!  This has resulted in the code becoming nearly unreadable as it's littered with declarations and THE statements (to specify the type of the result of an expression). 

I think that this excursion into complete perversity will help us to make the original BASIC code at least 10 if not 100 times faster .  OR, if I can convince the author of the BASIC code to switch to the dark side.... he can easily have a 1000 times speedup!


jimx0r: (Default)

July 2012

2930 31    


RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 05:24 am
Powered by Dreamwidth Studios