Python and STL efficiency

[Pebblestone]

I tested in Common Lisp and compared the result with python.

My PC is: 3.6GH Pentium4
My OS is: Ubuntu 6.06 i386
My lisp implementation is SBCL 0.9.8 for i386
My python's version is: V2.4.3
Both implementations were installed via apt-get install.

Here's my Lisp program:

++++++++++++++++++++++++++++++++++++++++++++++++++
;;; from slow to fast implementation

(proclaim '(optimize (speed 3) (debug 0) (safety 0) (space 0)))

(defun test1 ()
  (let ((a (make-array 0 :adjustable t :fill-pointer 0))
		(b nil))
	(dotimes (i 1000000)
	  (progn
		(vector-push-extend "What do you know" a)
		(vector-push-extend "so long ..." a)
		(vector-push-extend "chicken crosses road" a)
		(vector-push-extend "fool" a)))
	(setf b (remove-duplicates a :test #'string-equal))
 	(map 'vector #'print b)))

(defun test2 ()
  (let ((a (make-array 0 :adjustable t :fill-pointer 0))
		(b nil))
	(dotimes (i 1000000)
	  (progn
		(vector-push-extend "What do you know" a)
		(vector-push-extend "so long ..." a)
		(vector-push-extend "chicken crosses road" a)
		(vector-push-extend "fool" a)))
	(setf b (remove-duplicates a :test #'eq))
 	(map 'vector #'print b)))

(defun test3 ()
  (let ((a (make-array 4000000 :element-type 'string
					   :adjustable nil
					   :fill-pointer 0))
		(b nil))
	(dotimes (i 1000000)
	  (progn
		(vector-push "What do you know" a)
		(vector-push "so long ..." a)
		(vector-push "chicken crosses road" a)
		(vector-push "fool" a)))
	(setf b (remove-duplicates a))
	(map 'vector #'print b)))

(defun test4 ()
  (let ((a (make-array 4000000 :element-type 'string
					   :adjustable nil))
		(b nil))
	(dotimes (i 1000000)
	  (progn
		(let ((j (1- (* 4 i))))
		  (setf (aref a (incf j)) "What do you know")
		  (setf (aref a (incf j)) "so long ...")
		  (setf (aref a (incf j)) "chicken crosses road")
		  (setf (aref a (incf j)) "fool"))))
	(setf b (remove-duplicates a))
	(map 'vector #'print b)))

+++++++++++++++++++++++++++++++++++++++++++++++++++++++

1. When using string equal comparator (test #1), the speed slows down
dramatically. 1.93 -> 9.35
2. It seems that append(vector-push) in lisp costs much more than
direct access via index.

Here's my benchmark result:

+++++++++++++++++++++++++++++++++++++++++++++++++++++++
#1
(time (test1))

"What do you know"
"so long ..."
"chicken crosses road"
"fool"
Evaluation took:
  9.346 seconds of real time
  9.020564 seconds of user run time
  0.328021 seconds of system run time
  0 page faults and
  457,565,688 bytes consed.


#2
(time (test2))

"What do you know"
"so long ..."
"chicken crosses road"
"fool"
Evaluation took:
  1.931 seconds of real time
  1.884118 seconds of user run time
  0.048003 seconds of system run time
  0 page faults and
  49,561,312 bytes consed.


#3
(time (test3))

"What do you know"
"so long ..."
"chicken crosses road"
"fool"
Evaluation took:
  1.721 seconds of real time
  1.704107 seconds of user run time
  0.016001 seconds of system run time
  0 page faults and
  32,012,040 bytes consed.


#4
(time (test4))

"What do you know"
"so long ..."
"chicken crosses road"
"fool"
Evaluation took:
  0.843 seconds of real time
  0.824051 seconds of user run time
  0.020001 seconds of system run time
  0 page faults and
  32,012,040 bytes consed.

+++++++++++++++++++++++++++++++++++++++++++++++++++

Here's my python's code:

ef f():
        a = []
        for i in range(1000000):
                a.append('What do you know')
                a.append('so long...')
                a.append('chicken crosses road')
                a.append('fool')
        b = set(a)
        for s in b:
                print s

import time
from time import clock

f_start = clock()
f()
f_end   = clock()

print "Elapsed: %f seconds" % (f_end - f_start)



And benchmark result:

python -O test.py
so long...
What do you know
fool
chicken crosses road
Elapsed: 1.260000 seconds


Oops, Python beat native-compiled lisp code.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Any way,

MY CONCLUSION is: C++ is not the right model for symbolic computation.