^ 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:
Code: Select all
(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.