Lisp newbie trying to optimize recursive algorithm, help?

Hi

I've written an algorithm to count the number of inversions in a list of integers (pairs of integers that are out of order), but it runs very slowly. It takes ~400 seconds to run on a list of 100,000 integers. In contrast, the same algorithm written in Java runs in less than a second.

The algorithm itself is basically merge-sort, a binary recursive call, but counting the number of merges that would need to be done without actually doing them.

This is my basic Lisp form:

(defun count-inversions (lst &optional (predicate #'<))
  (if (or (null lst) (null (cdr lst))) ;recursive base case
      0
      (let* ((half (ceiling (/ (length lst) 2)))
	     (left-list (subseq lst 0 half))
	     (right-list (subseq lst half)))
	(+ (loop for a in left-list ; loop over the left and right halves of the list
	      summing (loop for b in right-list
			 counting (not (funcall predicate a b)))) ; count inversions between left and right lists
	   (count-inversions left-list predicate)
	   (count-inversions right-list predicate))))) ;recur on left and right lists

And this is that same form with various type declarations and optimization, it shaves about sixty seconds of the running time, but it still takes almost six minutes:

(defun count-inversions (lst &optional (predicate #'<))
  (declare (optimize (speed 3)
		     (compilation-speed 0)
		     (debug 0)
		     (safety 0)))
  (declare (type list lst))
  (declare (type (function (fixnum fixnum)) predicate))
  (if (or (null lst) (null (cdr lst)))
      0
      (let* ((half (the fixnum (ceiling (/ (the fixnum (length lst)) 2))))
	     (left-list (subseq lst 0 half))
	     (right-list (subseq lst half)))
	(declare (type fixnum half))
	(declare (type list left-list))
	(declare (type list right-list))
	(+ (the bignum (loop for a in left-list
			  summing (loop for b in right-list
				     counting (not (funcall
						    (the function predicate)
						    (the fixnum a)
						    (the fixnum b))))))
	   (the bignum (count-inversions left-list predicate))
	   (the bignum (count-inversions right-list predicate))))))

I'm using SBCL (+emacs +slime) on Ubuntu.

Why does this take so long? Is there anyway to get the running time comparable to Java? I have read that properly optimized CL can be competitive with C, so I would hope that this algorithm can be made better than a hundred times slower than Java.

Any help is appreciated,
tensorproduct

(defun count-inversions-1 (x &optional (predicate #'<) (len (length x)))
  (if (or (null x) (null (cdr x)))
      0
      (let* ((half-a (1- (ash len -1)))
             (half-b (- len half-a))
             (right-list (split-in-two! x)))
        (+ (loop for a in x
                summing (loop for b in right-list
                             counting (not (funcall predicate a b))))
           (count-inversions-1 x predicate half-a)
           (count-inversions-1 right-list predicate half-b)))))

(defun split-in-two! (x &optional (len (length x)))
  (setq len (1- (ash len -1)))
  (do ((c x (cdr c))
       (r)
       (i 0 (1+ i)))
      (nil)
    (when (= i len)
      (setq r (cdr c))
      (rplacd c nil)
       (return r))))

Could you try it with something like this? I'm not 100% certain I understood what exactly the function has to do, it looks like reduce'ing instead of looping might do a better job (although insignificantly, I guess). The major problem with your algorithm is that it:
- intensively recalculates the length of the lists many-many times, and it's a O(n), while in Java you probably used ArrayList (which, contrary to its name is a dynamic array, nothing to do with lists), or just an array of int (even faster), and "calculating its length is O(1).
- creates a lot of needless conses. subseq creates new conses - but this is what you don't want to do! You've no use for the old conses after new are created, and, although the runtime may try to be smart and reduce the conses creation by reusing some old ones you threw away, it will be still taxing the memory. However, splitting arrays in two is a much simpler task then splitting lists (again O(1) vs O(n), you could say it's O(n/2) but there's no such thing). And you had to call subseq twice!

Alright, I'm hoping that the above will improve your code somewhat, but, ultimately, if you want to get near Java's speed on this task you need to use arrays, not lists, because arrays are better for this algorithm.

Thanks wvxvw. I think that you're right. I hadn't appreciated the difference between a lisp list and an array. I'll modify my code to work on an integer array (for starters) and see what sort of improvement that yields. I'm guessing that it will be significant.

Is there any simple method to convert a list to an array? Some thing like (vector *input-list*), I'm guessing.

Cheers.

tensorproduct wrote:Thanks wvxvw. I think that you're right. I hadn't appreciated the difference between a lisp list and an array. I'll modify my code to work on an integer array (for starters) and see what sort of improvement that yields. I'm guessing that it will be significant.

Is there any simple method to convert a list to an array? Some thing like (vector *input-list*), I'm guessing.

Cheers.

(COERCE #(1 2 3) 'LIST)

pjstrling, almost, but you did it backwards you are coercing an array to list. You wanted

(coerce '(1 2 3) 'vector)

or

(make-array 3 :element-type 'fixnum :initial-contents '(1 2 3))

I would prefer the second way because it allows for more precise type specification.

The funcall to predicate is a huge timesink.

I tested your program with Clozure CL v1.6 under Windows and without the funcall to predicate it took 0.205 seconds for a list of 10.000 elements.
I also rewrote your program in C with Visual C++ 6 using a static array and it took 0.175 seconds. I doubt Java would make 100.000 elements in less than a second.

Thanks for the replies guys.

Moving from a list to an array didn't quite have the impact I was expecting, maybe 10% off the running.

Taking out the funcall to a predicate on the other hand made all the difference. It brings the running time down to 25 seconds, a huge speed up.

So, does this mean that writing fast Lisp code is mutually exclusive to passing first class functions? Or are there other ways of doing this than "funcall"-ing things?

Konfusius wrote: I doubt Java would make 100.000 elements in less than a second.

I admit that I quoted that figure without doing any proper timing. 3 to 4 seconds is a more accurate quotation.

Actually, a lot of the problem here is not with FUNCALL itself but with the fact that FUNCALL screens optimizations. If you pass as a predicate not #'<, which is generic multi-argument function, but (lambda (a b) (declare (fixnum a b)) (< a b)) it will reduce the time by more that half alone.

Of course for a very small operation like numeric comparison the cost of indirection will always be significant. A first class function shouldn't be an innermost operation in a long loop. There are ways around this (for example, use a compiler macro to catch a compile-time predicate or recompile at runtime when the predicate is available), but it should be done only when you know that it would be actually useful, and if it is impractical to pass a larger behaviour.

tensorproduct wrote:So, does this mean that writing fast Lisp code is mutually exclusive to passing first class functions? Or are there other ways of doing this than "funcall"-ing things?

It's all about the implementation. The Lisp implementations I know (SBCL and Clozure CL for Windows) generate abyssmal code for funcalls of functions that they cannot determine at compile time. I don't know if the commercial implementations (Allegro/Lisp Works) are better at this.

tensorproduct wrote:Moving from a list to an array didn't quite have the impact I was expecting, maybe 10% off the running.

This isn't a surprise to me. The purpose of arrays is to speed up code but ironically untyped arrays are horribly slow in Common Lisp. Typed arrays should be fast but SBCL and Clozure CL don't seem to be able to make proper use of that type information. Arrays seem to be pretty much useless in the free implementations. Lists are amazingly fast, though.

tensorproduct wrote:I admit that I quoted that figure without doing any proper timing. 3 to 4 seconds is a more accurate quotation.

I doubt that, too. My C implementation took 17.625 seconds. (VC++6 doesn't generate the best code, though) Here is the C source:

#include <windows.h>
#include <stdio.h>

#define NUM 100000

int a[NUM];

int
count_inversions (int start, int end)
{
  int cnt=0,i,j,half=start+(end-start)/2;

  if(end-start<2) return 0;

  for(i=start; i<half; i++)
	for(j=half; j<end; j++)
	  if(a[i]>a[j])
		++cnt;

  return cnt+count_inversions(start,half)+count_inversions(half,end);
}

int
main (int argc, char **argv)
{
  int i,cnt;
  DWORD t;

  for(i=0; i<NUM; i++) a[i]=NUM-i;

  t=GetTickCount();
  cnt=count_inversions(0,NUM);
  printf("time=%f seconds\n",(double)(GetTickCount()-t)/1000E0);
}

PS: Maybe this post sounds a bit more negative about Lisp than I intended. In fact, your original code (without a funcalled predicate) runs only ~15% slower (in Clozure CL v1.6) than the C version on my PC. I think thats pretty impressive for a dynamic language, especially since your code uses lists and does a lot of consing due to subseq, while the C version uses a static array.

That's why I like Lisp. It's powerful and still pretty fast. Even without arrays.

I decided to do some full-scale testing and experimenting with your example, and, as others have said that... The most time consuming operation appears to be the funcall.

http://pastebin.com/J26Nt1TV

here are the results. It may be possible to optimize it further a bit by manipulating pointers to the segments of the array being compared instead of dividing the array, but it appears that memory allocations are rather super fast, so that's not important, unless memory itself is important.

And... by thee wee, the results for my last example (without funcall) are:

Evaluation took:
  17.825 seconds of real time
  17.777111 seconds of total run time (17.777111 user, 0.000000 system)
  99.73% CPU
  49,873,143,567 processor cycles
  18,720,528 bytes consed

That's pretty close to C! (but it can be even better)

Processor	8x Intel(R) Core(TM) i7 CPU 930 @ 2.80GHz
Memory	6127MB (4327MB used)
Operating System	Debian GNU/Linux 6.0.4

* just in case...

I tested your heavily optimized array version count-inversions-6 on my PC and it still takes more than twice the time than the OPs version without a funcalled predicate (0.562 seconds vs 0.205 seconds). Maybe its just my hardware (Intel Pentium Dual-Core E5300 @ 2.60GHz) but all the arrays and declarations don't seem to help very much.

Konfusius wrote:I tested your heavily optimized array version count-inversions-6 on my PC and it still takes more than twice the time than the OPs version without a funcalled predicate (0.562 seconds vs 0.205 seconds). Maybe its just my hardware (Intel Pentium Dual-Core E5300 @ 2.60GHz) but all the arrays and declarations don't seem to help very much.

I've tested my original code (without the funcall) against wvxvw's and I found the opposite to what you have: 0.169 seconds vs 0.275 (on a 10000 element array or list).

^ I think Konfusius compared the optimized array version which uses funcall against your version which he modified to not use funcall. In which case it sounds likely to be true, as the impression I've got from my tests was that the funcall ate most of the resources.
One more thing to test is, as Ramarren suggested: instead of using a funcall to a generic function, do something like:

(defun comparator (a b)
  (declare (type (fixnum a b))
    (ftype (function (fixnum fixnum) boolean) comparator))
  (< a b))

(defun count-inversions (source &optional (predicate #'comarator))
  (declare (inline comparator)) ...)

But this would be identical (I believe...) to just using the concrete #'< function inside count-inversions, but this sounds more like gambling. Sorry for the untested code above, it's intended for illustration.

Oh, wait, I see it's count-inversions-6, in which case that sounds rather unlikely to be true, or, possibly the Lisp implementation did something wrong compiling that function... wait, there's ideone site, could be good for testing. I'll try it there.

EDIT: http://ideone.com/ufhJ6
(Note that I've reduced it by one order of magnitude so that it would fit into 5 seconds time limit.)
The Lisp used at ideone.com is CLISP, and, well, in this particular case we are seeing the work of the compiler in effect. Probably SBCL knows how to optimize array-based code, while CLISP might be at all using lists to represent arrays, or that would be my guess.

I tested count-conversions-6 again but this time with both SBCL and Clozure. In Clozure it took 0.594s and in SBCL it took only 0.1875s. So it was the Lisp implementation.

The OPs version took about 0.21s in both implementations. But this is still only a difference of about 11% compared to the heavily optimized array version.

EDIT
I slightly optimized the OPs code to use fixnums and now its slightly faster than the array version again in SBCL and still more than twice as fast in Clozure CL.

(defun count-inversions (lst &optional (predicate #'<))
  (if (or (null lst) (null (cdr lst)))
	0
	(let* ((half	   (ceiling (/ (length lst) 2)))
		   (left-list  (subseq lst 0 half))
		   (right-list (subseq lst half)))
	  (+ (loop for a fixnum in left-list
			   summing (loop for b fixnum in right-list
							 counting (not (< a b)))) ;(funcall predicate a b))))
		 (count-inversions left-list predicate)
		 (count-inversions right-list predicate)))))

Well, that shouldn't happen, because it doesn't make sense, or there must be very bad array implementation in both Clozure and CLISP. I mean, you can't beat O(1) with O(n), unless you do something very silly. In fact, I suspect that as some other dynamic languages (for example JavaScript or Lua) arrays may be implemented as hash tables with integer keys, in which case splitting such an array would be even worse then splitting a list (it would be some kind of O(n log n) I suppose). Though, ultimately, that should not happen with "normal" arrays.

And, by the way, inspired by my guess, I tried this, and the result is quite surprising! Could you please try with CLISP to see if you get the result similar to array?

(defun make-big-hash-table (x)
  (do* ((y (make-hash-table :size x))
	(i 0 (1+ i)))
       (nil)
    (when (= x i) (return y))
    (setf (gethash i y) (random 1000))))

(defun count-inversions-7 (table &optional (predicate #'<))
  (let ((ht-size (hash-table-count table)))
    (if (< ht-size 2)
	0
	(let* ((half (floor (/ ht-size 2)))
	       (right-table (split-hash-table table half)))
	  (+ (loop for a fixnum being the hash-values of table
		summing
		  (loop for b fixnum being the hash-values of right-table
		     counting (not (< a b)))) ;(funcall predicate a b))))
	     (count-inversions-7 table predicate)
	     (count-inversions-7 right-table predicate))))))

(defun split-hash-table (table half)
  (let ((result (make-hash-table)))
    (maphash
     #'(lambda (key value)
	 (when (>= key half)
	   (setf (gethash (- key half) result) value)
	   (remhash key table))) table) result))

(time (count-inversions-7 (make-big-hash-table 10000)))

;; Evaluation took:
;;   0.499 seconds of real time
;;   0.492031 seconds of total run time (0.492031 user, 0.000000 system)
;;   98.60% CPU
;;   1,397,445,267 processor cycles
;;   16,766,080 bytes consed

I didn't use CLISP but SBCL. But I tried your version 7 with CLISP too and it took 4.266s after manually compiling (CLISP doesn't compile automatically). As expected CLISP is very slow because it compiles to interpreted bytecode instead of machine code.

With SBCL your version 7 took 0.672s and 3.031s with Clozure. Thats still much slower than my optimized OPs version.

wvxvw wrote:Well, that shouldn't happen, because it doesn't make sense, or there must be very bad array implementation in both Clozure and CLISP. I mean, you can't beat O(1) with O(n), unless you do something very silly.

The list version isn't O(n). Its mostly O(1) because the lists are traversed sequentially. And the subseq-ing of the lists doesn't fall into account for big n's because its effectively copying the original list only log(n) times.

OTOH, array access in Common Lisp is slow by design because it has to check for index boundaries, simple/non-simpe arrays, and for the various specialized array types.

array access in Common Lisp is slow by design [...]

Well, that's something I thought I would avoid by setting the optimization setting as they were - I still don't know Lisp assembler at the level I can understand what is going on in the code it generates, but I hoped to get something similar to C plain arrays of integers (i.e. by setting safety to 0 I would ensure that it would rely on me I will not read/write out of bounds). I thought it was possible because if I did read past the array bounds I would get a memory fault, something I assumed to be similar in nature to the one I'd get in C.

I didn't mean version 7 to be more optimized, I was suggesting it might work the same as the one with the array - because I thought that the implementation that performed bad with arrays might be using a hash-table behind the stage to represent an array.

Re' O(n) - besides doing subseq the algorithm measures the length, and it does it every time, which is really redundant - you need this only once. And the speed of doing subseq is linear, no log(n), sorry It contributes to the complexity of the entire algorithm in a non-linear way (just as you say) - I agree, but if you compare (subseq list) vs (subseq array) it is O(n) vs O(1) proper.

I still don't understand why the result is as you describe, but I'm not knowledgeable enough to research it more. I hope, one day I'll know