Make Lisp 15x faster than Python or 4x faster than Java

The finished program went down in runtime from 533.7s on my machine, to 24.42 seconds. If we adjust for machine speed (since the author's Python ran the python code in 474s), the comparative optimized result would be 21.7 seconds compared to author's hand-optimized lisp code at 30.2.

Note that this is probably an ideal case for Shedskin (which is a relatively new product: a 1-man job that's just a few years old compared to, I guess, hundreds if not thousands of man-years of research that have gone in LISP implementations).

Still, an interesting result.

SBCL:

  * (test)

  Evaluation took:
    45.268 seconds of real time

  Runtime was: 51086 Milliseconds

 

    local radius = 6371

    local function distance(latA, lngA, latB, lngB)
      local latAr = math.rad(latA)
      local lngAr = math.rad(lngA)
      local latBr = math.rad(latB)
      local lngBr = math.rad(lngB)

      local deltaLat = latBr - latAr
      local deltaLng = lngBr - lngAr

      return radius * 2 * math.asin(math.sqrt(
              math.sin(deltaLat/2)^2 + math.cos(latAr)
              * math.cos(latBr) * (math.sin(deltaLng/2)^2)))
    end

    local start = os.clock()

    for latA=-90,90,2.5 do
      for lngA=-90,90,2.5 do
        for latB=-90,90,2.5 do
          for lngB=-90,90,2.5 do
            distance(latA, lngA, latB, lngB)
          end
        end
      end
    end

    local stop = os.clock()
    print(stop-start)

I thought you would only really be finding deals at distances small enough to just assume the earth is flat. Or at least, aren't those the only ones people would actually be interested in? If it's beyond my physical reach, I don't care how far it is. I'll get it shipped.

Or am I missing something?

For example, take a look at the solutions to PRIME 1; the task is to generate a list of prime numbers: http://www.spoj.pl/ranks/PRIME1/

The top 20 C solutions all take less than 0.05 seconds. The top 20 Java solutions all take less than 0.5 second. Python has several solutions that took 0.55 seconds. But for Lisp, only one user was able to get it to less than 1 second, and then only barely.

There's not enough data to draw any real conclusions, but it does make me skeptical of claims that Lisp is near in speed to Java or C (any Lisp gurus who want to prove me wrong, feel free to code up a fast solution and submit it)

That said I think these kinds of benchmarks (and article titles) are misleading, because one who has deep knowledge in one language does not necessarily write good code in other languages. Even the article notes that "they are all just literal line-by-line translations of each other".

Now, I wonder whether I could use Lisp for what I do. One basic necessity would be to have a way to define a structure like this

  struct s {
    int32_t x;
    int32_t y;  
  };

Do you have any idea whether that could work with SBCL?

  for latA, lngA, latB, lngB in itertools.product(*[xrange(-90,91), xrange(-180,181)]*2):
      distance(latA, lngA, latB, lngB)

Also, the 2nd python example doesn't work; you need to drop all the 'math.' and use radians, sqrt, etc directly.

Python without Psyco : 522

Python with Psyco : 190

http://t-b-o-g.blogspot.com/2009/12/brians-brain-on-common-l...

It highlights the importance of profiling code first.

2. C translation takes 11 seconds (compare to 25.6 for SBCL)

http://gist.github.com/288936#file_silly distance loop

1.) A simple square macro will be faster than the expt function, because expt does special calculations for dealing with decimal exponents. All you really need to do is multiply it by itself. I think something like this:

(defmacro square (expression) (let ((symb (gensym))) `(let ((,symb ,expression)) (* ,symb ,symb))))

would work fine.

2.) you can turn degree to radian into a macro like so:

(defmacro degree-to-radian (deg) `(the single-float (* ,deg ,(/ (coerce pi 'single-float) 180))))

And avoid a couple of function calls and some multiplication. This way you also don't need to duplicate 'the single-float'...

On my machine, running clozure cl, this made it about 1/8th faster than the original optimized version.

3.) I was kind of wondering, could you do this sort of computation ahead of time for varying longitudes and latitudes, then store them in a table and do a simple look up and interpolation, instead of doing a lot of trigonometry (is this technically trigonometry?) at run time?

I'm not clear on the math exactly (whether it would work in this situation), but that sort of thing is done using pre-computed tables with fairly complex polynomial equations all of the time. In the case of a web app, it might be better to do this sort of thing (ram is cheap anyway).

I refer the honourable gentlman to Zed Shaw's "Programmers Need To Learn Statistics Or I Will Kill Them All"

http://www.zedshaw.com/essays/programmer_stats.html