Sorting big arrays

Discussion of Common Lisp

Sorting big arrays

Postby makia » Sat Jan 03, 2009 7:02 am

Hi, I was playing with some code where bottleneck was numeric sorting array with milions of fixnums and playing with both clozure cl and sbcl noticed that sorting is much faster in clozure .. 4-5x faster
Then just for fun i tested same thing in java (numeric sorting of 10mil integers with random values inserted) .. and on the end it's 10x faster then clozure CL and 40x times faster then sbcl.
Suprise for me that sbcl is much slower then ccl, also that java is so much faster then both clozure and sbcl ..
Also perl is 2x faster then clozure and 7-8x faster then sbcl .. and that is really unexpected.
Benchmarking just allocation and array access shows that sbcl is fastest (aprox 2-3x faster then java).
It's obvious that sorting is slow in both ccl and sbcl, meaby someone who understand implementation of lisp can tell me more.
I noticed that java implements quicksort and sbcl heapsort , but it cant be just that .. also java sort() is specialized numeric sort, and lisp sort accept predicate function ..

lisp testing code:

Code: Select all
(defun test ()
  (declare (optimize (speed 3) (debug 0) (safety 0) (compilation-speed 0)))
  (let ((a (make-array 10000000 :element-type 'fixnum)))
    (declare (type (simple-array fixnum (*)) a))
    (loop for i of-type fixnum from 0 below 10000000
       do (setf (aref a i) (random 100)))
    (setf a (sort a #'>))
    nil))
makia
 
Posts: 25
Joined: Tue Jul 22, 2008 2:37 am

Re: Sorting big arrays

Postby Ramarren » Sat Jan 03, 2009 10:35 am

I would guess that sorting in Perl is implemented in C, so high performance there is not that surprising. I might be wrong, but this seems typical for scripting languages. In any case I believe the problem is the cost of funcalling the predicate, which additionally loses context. That is, note that #'< is a function for comparing numbers of arbitrary type and might take more than one argument.

Just using a lambda with declared argument types dropped the time the test function took in my SBCL by a third. And then I noticed that (sort ...) in the SBCL source has maybe-inline declamation, which is an SBCL extension I didn't even know existed... anyway, changing the code to:
Code: Select all
(defun test2 ()
  (declare (optimize (speed 3) (debug 0) (safety 0) (compilation-speed 0))
           (inline sort))
  (let ((a (make-array 10000000 :element-type 'fixnum)))
    (declare (type (simple-array fixnum (*)) a))
    (loop for i of-type fixnum from 0 below 10000000
       do (setf (aref a i) (random 100)))
    (setf a (sort a #'>))
    nil))


drops the time to less than 15% of it's original time, which, by the counts you gave, is pretty close to what Perl does. This might be what clozure does by default. I don't know why Java would be so fast... are you sure you are sorting the same thing? They might be also playing advanced tricks with cache coherence or, it was some non-comparision sort rather than quicksort.
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Re: Sorting big arrays

Postby nuntius » Sat Jan 03, 2009 8:50 pm

FWIW, SBCL uses heapsort.

sbcl/src/compiler/srctran.lisp:4084
Code: Select all
;;; Like CMU CL, we use HEAPSORT. However, other than that, this code
;;; isn't really related to the CMU CL code, since instead of trying
;;; to generalize the CMU CL code to allow START and END values, this
;;; code has been written from scratch following Chapter 7 of
;;; _Introduction to Algorithms_ by Corman, Rivest, and Shamir.
(define-source-transform sb!impl::sort-vector (vector start end predicate key)
User avatar
nuntius
 
Posts: 498
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 3 guests