hi,
i'm trying to optimize execution time of bubblesort. it already runs
~10sec faster than the vanilla approach. But it still is ~12times
slower than the c-version. Is there nothing more to get out of?
(defun bubblesort (x size)
(declare (type (simple-array fixnum *) x)
(type fixnum size)
(optimize (speed 3) (safety 0) (space 0) (debug 0)))
(let ((tmp 0))
(declare (type fixnum tmp))
(dotimes (i size)
(declare (type fixnum i))
(dotimes (j (- size i))
(declare (type fixnum j))
(when (> (aref x j)
(aref x (+ j 1)))
(progn
(setf tmp (aref x (+ j 1)))
(setf (aref x (+ j 1)) (aref x j))
(setf (aref x j) tmp)))))))
(defun main ()
(let* ((size 10000)
(x (make-array size :element-type 'fixnum :fill-pointer 0)))
(declare (type fixnum size))
(dotimes (i size)
(vector-push (random 100) x))
(time (bubblesort x size))))
; Evaluation took:
; 12.84 seconds of real time
; 12.514098 seconds of user run time
; 0.045993 seconds of system run time
; 30,819,166,116 CPU cycles
; 0 page faults and
; 0 bytes consed.
The c-version needs ~1sec.
kind regards,
alex
On Feb 27, 1:45 pm, "alex" <···············@gmail.com> wrote:
> hi,
> i'm trying to optimize execution time of bubblesort. it already runs
> ~10sec faster than the vanilla approach. But it still is ~12times
> slower than the c-version. Is there nothing more to get out of?
> [...]
> The c-version needs ~1sec.
What implementation of Common Lisp are you using?
This is SBCL 1.0.2, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defun bubblesort (x size)
[snip])
BUBBLESORT
* (defun main ()
[snip])
MAIN
* (main)
Evaluation took:
0.17 seconds of real time
0.160856 seconds of user run time
0.008781 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
*
On Feb 27, 12:45 pm, "alex" <···············@gmail.com> wrote:
> hi,
> i'm trying to optimize execution time of bubblesort. it already runs
> ~10sec faster than the vanilla approach. But it still is ~12times
> slower than the c-version. Is there nothing more to get out of?
Did you compile it (silly question, I know).
"alex" <···············@gmail.com> writes:
> hi,
> i'm trying to optimize execution time of bubblesort. it already runs
> ~10sec faster than the vanilla approach. But it still is ~12times
> slower than the c-version. Is there nothing more to get out of?
>
> (defun bubblesort (x size)
> (declare (type (simple-array fixnum *) x)
^^^^^^^^^^^^^^^^^^^^^^^
Unfortunately, it turns out that this is a lie to the compiler.
See below:
> (type fixnum size)
> (optimize (speed 3) (safety 0) (space 0) (debug 0)))
> (let ((tmp 0))
> (declare (type fixnum tmp))
> (dotimes (i size)
> (declare (type fixnum i))
> (dotimes (j (- size i))
> (declare (type fixnum j))
> (when (> (aref x j)
> (aref x (+ j 1)))
> (progn
> (setf tmp (aref x (+ j 1)))
> (setf (aref x (+ j 1)) (aref x j))
> (setf (aref x j) tmp)))))))
>
> (defun main ()
> (let* ((size 10000)
> (x (make-array size :element-type 'fixnum :fill-pointer 0)))
^^^^^^^^^^^^^^^^
Simple arrays are not allowed to have fill pointers.
Fill pointers make them not simple anymore.
> (declare (type fixnum size))
Also, you don't declare the type of X here.
> (dotimes (i size)
> (vector-push (random 100) x))
> (time (bubblesort x size))))
>
>
> ; Evaluation took:
> ; 12.84 seconds of real time
> ; 12.514098 seconds of user run time
> ; 0.045993 seconds of system run time
> ; 30,819,166,116 CPU cycles
> ; 0 page faults and
> ; 0 bytes consed.
>
> The c-version needs ~1sec.
I would suspect that the code is not compiled.
Subsequent messages in this thread confirm that.
--
Thomas A. Russ, USC/Information Sciences Institute
Interesting. On sbcl the code doesn't even get executed correctly:
* (main)
debugger invoked on a TYPE-ERROR:
The value #(26 13 75 70 24 76 63 11 66 0 94 91 ...)
is not of type
(SIMPLE-ARRAY FIXNUM).
Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.
restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.
(NIL #(26 13 75 70 24 76 63 11 66 0 94 91 ...) 10000)
And cmucl refuses cooperation when not adding ":fill-pointer 0" to the
make-array call:
* (main)
#(0 0 ... 0) is not an array with a fill-pointer.
[Condition of type SIMPLE-TYPE-ERROR]
Restarts:
0: [ABORT] Return to Top-Level.
Debug (type H for help)
(VECTOR-PUSH 95 #(0 0 0 0 0 ...))
Source: Error finding source:
Error in function DEBUG::GET-FILE-TOP-LEVEL-FORM: Source file no
longer exists: target:code/array.lisp.
I am a bit confused :)
On Feb 27, 1:45 pm, "alex" <···············@gmail.com> wrote:
> (dotimes (j (- size i))
On the first iteration this will give j = 10000 - 0 = 10000
> (declare (type fixnum j))
> (when (> (aref x j)
> (aref x (+ j 1)))
Would blow up over here ---^ if you hadn't optimized away all checks.
This seems like a case of premature optimization.
On Feb 27, 3:41 pm, "alex" <···············@gmail.com> wrote:
> Interesting. On sbcl the code doesn't even get executed correctly:
>
> * (main)
>
> debugger invoked on a TYPE-ERROR:
> The value #(26 13 75 70 24 76 63 11 66 0 94 91 ...)
> is not of type
> (SIMPLE-ARRAY FIXNUM).
You must be running different code or a different SBCL from me:
This is SBCL 1.0.2, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defun bubblesort (x size)
(declare (type (simple-array fixnum *) x)
(type fixnum size)
(optimize (speed 3) (safety 0) (space 0) (debug
0)))
(let ((tmp 0))
(declare (type fixnum tmp))
(dotimes (i size)
(declare (type fixnum i))
(dotimes (j (- size i))
(declare (type fixnum j))
(when (> (aref x j)
(aref x (+ j 1)))
(progn
(setf tmp (aref x (+ j 1)))
(setf (aref x (+ j 1)) (aref x j))
(setf (aref x j) tmp)))))))
BUBBLESORT
* (defun main ()
(let* ((size 10000)
(x (make-array size :element-type 'fixnum :fill-
pointer 0)))
(declare (type fixnum size))
(dotimes (i size)
(vector-push (random 100) x))
(time (bubblesort x size))))
MAIN
* (main)
Evaluation took:
0.179 seconds of real time
0.178825 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
*
It runs Wade's code, too.
> I am a bit confused :)
It would be easier to help you if you showed us exactly what you're
doing and told us what you're using to do it. SBCL compiles your
bubblesort very efficiently:
* (disassemble #'bubblesort)
; 497CD115: 31DB XOR EBX, EBX ; no-arg-
parsing entry point
; 17: 31C9 XOR ECX, ECX
; 19: EB5E JMP L4
; 1B: L0: 8B7DF0 MOV EDI, [EBP-16]
; 1E: 29CF SUB EDI, ECX
; 20: C745EC00000000 MOV DWORD PTR [EBP-20], 0
; 27: EB48 JMP L3
; 29: L1: 8B45EC MOV EAX, [EBP-20]
; 2C: 8B740201 MOV ESI, [EDX+EAX+1]
; 30: 8B5DEC MOV EBX, [EBP-20]
; 33: 83C304 ADD EBX, 4
; 36: 8B5C1A01 MOV EBX, [EDX+EBX+1]
; 3A: 39DE CMP ESI, EBX
; 3C: 7E2A JLE L2
; 3E: 8B5DEC MOV EBX, [EBP-20]
; 41: 83C304 ADD EBX, 4
; 44: 8B5C1A01 MOV EBX, [EDX+EBX+1]
; 48: 8B75EC MOV ESI, [EBP-20]
; 4B: 83C604 ADD ESI, 4
; 4E: 8B45EC MOV EAX, [EBP-20]
; 51: 8B440201 MOV EAX, [EDX+EAX+1]
; 55: 8945F4 MOV [EBP-12], EAX
; 58: 8B45F4 MOV EAX, [EBP-12]
; 5B: 89443201 MOV [EDX+ESI+1], EAX
; 5F: 8BF0 MOV ESI, EAX
; 61: 8B45EC MOV EAX, [EBP-20]
; 64: 895C0201 MOV [EDX+EAX+1], EBX
; 68: L2: 8B45EC MOV EAX, [EBP-20]
; 6B: 83C004 ADD EAX, 4
; 6E: 8945EC MOV [EBP-20], EAX
; 71: L3: 397DEC CMP [EBP-20], EDI
; 74: 7CB3 JL L1
; 76: 83C104 ADD ECX, 4
; 79: L4: 3B4DF0 CMP ECX, [EBP-16]
; 7C: 7C9D JL L0
; 7E: BA0B000030 MOV EDX, 805306379
; 83: 8D65F8 LEA ESP, [EBP-8]
; 86: F8 CLC
; 87: 8B6DFC MOV EBP, [EBP-4]
; 8A: C20400 RET 4
; 8D: 90 NOP
; 8E: 90 NOP
; 8F: 90 NOP
This should be fairly close to what your C version compiles to.
Regards,
Joel
"alex" writes:
> i'm trying to optimize execution time of bubblesort.
> ...
> (dotimes (i size)
> (declare (type fixnum i))
> (dotimes (j (- size i))
>
Isn't it ^^^^^^^^^^^^^(- size i 1) ?
Otherwise one may just test the speed of a silent crash in (aref x (+ j 1)).
> (defun main ()
> (let* ((size 10000)
> (x
>
If this is an option,
what about having x a dynamical variable ?
With my clisp, executing
(defvar size 1000)
(defvar x (make-array size :element-type 'fixnum :fill-pointer 0))
(dotimes (i size)
(setf (aref x i) (random 100)))
(time (bubblesort x size))
results in an hundred times improvement.
(I'd like to know why.
In C parlance, I thing x would go from the stack to the heap.
But what happens in CL/clisp,
and why is it such an improvement ?)
Hth.
--
Take it Easy Don't worry Be Happy
Thierry
�������o�o��������o�o��������o�o��������o�o��������o�o�������
On 27 Feb., 16:23, Thierry Pirot <····@thierrypirot.net> wrote:
> "alex" writes:
> > i'm trying to optimize execution time of bubblesort.
> > ...
> > (dotimes (i size)
> > (declare (type fixnum i))
> > (dotimes (j (- size i))
>
> Isn't it ^^^^^^^^^^^^^(- size i 1) ?
> Otherwise one may just test the speed of a silent crash in (aref x (+ j 1)).
Thanks for all your help. But there are still weird things happening.
I have a file called sort.lisp with the following contents:
(defun bubblesort (x size)
(declare (type (simple-array fixnum (*)) x)
(type fixnum size)
(optimize (speed 3) (safety 0) (space 0) (debug 0)))
(dotimes (i size)
(dotimes (j (- size i 1))
(when (> (aref x j)
(aref x (+ j 1))))
(rotatef (aref x j) (aref x (+ j 1))))))
(defun main ()
(let* ((size 10000)
(x (make-array size :element-type 'fixnum :fill-pointer 0)))
(declare (type fixnum size))
(dotimes (i size)
(vector-push (the fixnum (random size)) x))
(time (bubblesort x size))))
Now pls have a look at these two SBCL sessions:
This is SBCL 1.0.2, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (load (compile-file "sort.lisp"))
; compiling file "/storage/src/lisp/sort.lisp" (written 27 FEB 2007
05:04:42 PM):
; compiling (DEFUN BUBBLESORT ...)
; compiling (DEFUN MAIN ...)
; /storage/src/lisp/sort.fasl written
; compilation finished in 0:00:00
T
* (main)
debugger invoked on a TYPE-ERROR:
The value #(2549 5041 5005 8889 1212 9886 5339 8805 5300 6991 5590
8169 ...)
is not of type
(SIMPLE-ARRAY FIXNUM (*)).
Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.
restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.
(NIL #(2549 5041 5005 8889 1212 9886 5339 8805 5300 6991 5590
8169 ...) 10000)
0]
-----------------------
Now, if paste the code directly into the repl:
This is SBCL 1.0.2, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defun bubblesort (x size)
(declare (type (simple-array fixnum (*)) x)
(type fixnum size)
(optimize (speed 3) (safety 0) (space 0) (debug
0)))
(dotimes (i size)
(dotimes (j (- (- size i) 1))
(when (> (aref x j)
(aref x (+ j 1))))
(rotatef (aref x j) (aref x (+ j 1))))))
(defun main ()
(let* ((size 10000)
(x (make-array size :element-type 'fixnum :fill-
pointer 0)))
(declare (type fixnum size))
(dotimes (i size)
(vector-push (the fixnum (random size)) x))
(time (bubblesort x size))))
BUBBLESORT
* (main)
MAIN
*
Evaluation took:
0.417 seconds of real time
0.405938 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
*
-------------
What is going on here?
Why does the direct input thing work and the load/compile-file
approach fail?
First of all, get a decent editor. You've messed up your when form.
After emacs has indented your bubblesort it looks like this:
(defun bubblesort (x size)
(declare (type (simple-array fixnum (*)) x)
(type fixnum size)
(optimize (speed 3) (safety 0) (space 0) (debug 0)))
(dotimes (i size)
(dotimes (j (- size i 1))
(when (> (aref x j)
(aref x (+ j 1))))
(rotatef (aref x j) (aref x (+ j 1))))))
CL-USER> (defvar small-array (make-array 6 :element-type
'fixnum :initial-contents #(3 6 23 3 67 9)))
SMALL-ARRAY
CL-USER> (bubblesort small-array 6)
NIL
CL-USER> small-array
#(9 67 3 23 6 3)
It's simply broken, so my second advice would be: stop worrying about
the efficiency and make it -right- before you try to make it fast.
Third, as Wade Humeniuk has already pointed out, simple vectors don't
have fill pointers. Since you can't have a fill-pointer for x you also
can't use vector-push in main, and there's no need to:
(defun main ()
(let* ((size 10000)
(x (make-array size :element-type 'fixnum)))
(declare (type fixnum size))
(dotimes (i size)
(setf (aref x i) (random size)))
(time (bubblesort x size))))
Now that we've fixed the type errors, we can compile and load it just
fine with SBCL:
[stewie] 1:41 /tmp) cat sort.lisp
(defun bubblesort (x size)
(declare (type (simple-array fixnum (*)) x)
(type fixnum size)
(optimize (speed 3) (safety 0) (space 0) (debug 0)))
(dotimes (i size)
(dotimes (j (- size i 1))
(when (> (aref x j)
(aref x (+ j 1))))
(rotatef (aref x j) (aref x (+ j 1))))))
(defun main ()
(let* ((size 10000)
(x (make-array size :element-type 'fixnum)))
(declare (type fixnum size))
(dotimes (i size)
(aref x (random size)))
(time (bubblesort x size))))
[stewie] 1:41 /tmp) sbcl
This is SBCL 1.0.2, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (load (compile-file "sort.lisp"))
; compiling file "/tmp/sort.lisp" (written 25 FEB 2007 01:40:10 AM):
; compiling (DEFUN BUBBLESORT ...)
; compiling (DEFUN MAIN ...)
; /tmp/sort.fasl written
; compilation finished in 0:00:00
T
* (main)
Evaluation took:
0.153 seconds of real time
0.153177 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
*
It seems SBCL is more careful and includes more safety checks when
generating code by compile-file, and it's also producing even more
efficient code. This is probably based on the assumption that it's
important to compile quickly in an interactive session.
Perhaps Juho Snellman could clear that up?
The code is still wrong but it's very fast.
Regards,
Joel
On 27 Feb., 18:06, "Joel Wilsson" <············@gmail.com> wrote:
> First of all, get a decent editor. You've messed up your when form.
> After emacs has indented your bubblesort it looks like this:
> [...]
> It's simply broken, so my second advice would be: stop worrying about
> the efficiency and make it -right- before you try to make it fast.
>
> Third, as Wade Humeniuk has already pointed out, simple vectors don't
> have fill pointers. Since you can't have a fill-pointer for x you also
> can't use vector-push in main, and there's no need to [...]
Thanks, things are now going the way they should.
Joel Wilsson <············@gmail.com> wrote:
> It seems SBCL is more careful and includes more safety checks when
> generating code by compile-file, and it's also producing even more
> efficient code. This is probably based on the assumption that it's
> important to compile quickly in an interactive session.
> Perhaps Juho Snellman could clear that up?
It's a recently introduced bug, the type-check shouldn't be there when
compile-file is being used. Thanks for bringing it up.
--
Juho Snellman
alex <···············@gmail.com> wrote:
> (defun bubblesort (x size)
> (declare (type (simple-array fixnum (*)) x)
Here you're claiming that X is a SIMPLE-ARRAY.
> (type fixnum size)
> (optimize (speed 3) (safety 0) (space 0) (debug 0)))
Here you're declaring (SAFETY 0), and telling to SBCL to not check the
validity of the previous declaration.
> (dotimes (i size)
> (dotimes (j (- size i 1))
> (when (> (aref x j)
> (aref x (+ j 1))))
> (rotatef (aref x j) (aref x (+ j 1))))))
>
> (defun main ()
> (let* ((size 10000)
> (x (make-array size :element-type 'fixnum :fill-pointer 0)))
Here you're creating a non-simple-array (in SBCL, other
implementations might differ). It will later be passed to bubblesort,
which will then randomly corrupt memory, due to being passed an
invalid X.
> (declare (type fixnum size))
> (dotimes (i size)
> (vector-push (the fixnum (random size)) x))
So you need to remove the :fill-pointer 0, and replace this with
something like (setf (aref x i) (the fixnum (random size))).
--
Juho Snellman