Python and STL efficiency

[Pebblestone]

Re: Python and STL efficiency

But note this a list (that is an array, a list is a different data

structure) of python becomes filled with pointers. I don't know what
your CL does exactly.

I heard that python's list is implemented as adjustable array.

Here's my lisp implementation:

+++++++++++++++ +++
(defun test-list ()
(let ((a nil)
(b nil))
(dotimes (i 1000000)
(progn
(push "What do you know" a)
(push "so long ..." a)
(push "chicken crosses road" a)
(push "fool" a)))
(setf b (remove-duplicates a))
(map 'list #'print b)))
+++++++++++++++ ++++++++++

And the benchmark result:

(time (test-list))

"fool"
"chicken crosses road"
"so long ..."
"What do you know"
Evaluation took:
2.88 seconds of real time
2.744172 seconds of user run time
0.136009 seconds of system run time
0 page faults and
74,540,392 bytes consed.

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

BTW, I couldn't install psyco on my system (ubuntu), gcc just prompt to
me thousands of lines of errors and warnings.




bearophileHUGS@ lycos.com wrote:

Pebblestone:

(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)))

>
>
That test4 function can be compared to this one, with explicit
preallocation (and xrange instead of range!):
>
def f2():
n = 1000000
a = [None] * n * 4
for i in xrange(0, n*4, 4):
a[i] = 'What do you know'
a[i+1] = 'so long...'
a[i+2] = 'chicken crosses road'
a[i+3] = 'fool'
for s in set(a):
print s
>
But note this a list (that is an array, a list is a different data
structure) of python becomes filled with pointers. I don't know what
your CL does exactly.
>
I can also suggest you to use Psyco too here
(http://psyco.sourceforge.net/):
>
import psyco
psyco.bind(f2)
>
It makes that f2 more than twice faster here.
>
Bye,
bearophile

[Pebblestone]

Re: Python and STL efficiency

Oh, I forgot.

Your python's example (use direct index array index) of my
corresponding lisp code works slower than the version which use
'append'.

This let me think how python's list is implemented.


Anyway, python's list is surprisingly efficient.


bearophileHUGS@ lycos.com wrote:

Pebblestone:

(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)))

>
>
That test4 function can be compared to this one, with explicit
preallocation (and xrange instead of range!):
>
def f2():
n = 1000000
a = [None] * n * 4
for i in xrange(0, n*4, 4):
a[i] = 'What do you know'
a[i+1] = 'so long...'
a[i+2] = 'chicken crosses road'
a[i+3] = 'fool'
for s in set(a):
print s
>
But note this a list (that is an array, a list is a different data
structure) of python becomes filled with pointers. I don't know what
your CL does exactly.
>
I can also suggest you to use Psyco too here
(http://psyco.sourceforge.net/):
>
import psyco
psyco.bind(f2)
>
It makes that f2 more than twice faster here.
>
Bye,
bearophile

[Pebblestone]

Re: Python and STL efficiency

Here's the result:

What do you know
fool
chicken crosses road
f elapsed: 1.260000 seconds
f2 elapsed 2.110000 seconds



bearophileHUGS@ lycos.com wrote:

Pebblestone:

(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)))

>
>
That test4 function can be compared to this one, with explicit
preallocation (and xrange instead of range!):
>
def f2():
n = 1000000
a = [None] * n * 4
for i in xrange(0, n*4, 4):
a[i] = 'What do you know'
a[i+1] = 'so long...'
a[i+2] = 'chicken crosses road'
a[i+3] = 'fool'
for s in set(a):
print s
>
But note this a list (that is an array, a list is a different data
structure) of python becomes filled with pointers. I don't know what
your CL does exactly.
>
I can also suggest you to use Psyco too here
(http://psyco.sourceforge.net/):
>
import psyco
psyco.bind(f2)
>
It makes that f2 more than twice faster here.
>
Bye,
bearophile

[bearophileHUGS@lycos.com]

Re: Python and STL efficiency

Pebblestone:

>I heard that python's list is implemented as adjustable array.

Correct, an array geometrically adjustable on the right.

>Here's my lisp implementation: <

What's the memory size of a before computing b? You can compare it with
Python, that may need less memory (because the array contains
pointers).

>BTW, I couldn't install psyco on my system (ubuntu), gcc just prompt to me thousands of lines of errors and warnings.<

Find a Win box ;-) It's already compiled for it (for Py 2.3, 2.4).

>Your python's example (use direct index array index) of my corresponding lisp code works slower than the version which use 'append'.<

For me (a slow PC) it's almost twice faster, computer life is usually
complex.
For me using the esplicit allocation + Psyco makes that program about 4
times faster (from 8 to 2 seconds).

>This let me think how python's list is implemented.<

You also have to think how the * allocation is implemented and many
other things :-)
The list implementation is rather readable, Python sources are online
too.

>Anyway, python's list is surprisingly efficient.<

But its access isn't that fast :-) Psyco helps.

Bye,
bearophile

[Pebblestone]

Re: Python and STL efficiency

What's the memory size of a before computing b? You can compare it with

Python, that may need less memory (because the array contains
pointers).

Here's the memory usage:

1) before the loop ( fully garbage collected)
29,052,560 bytes, 757,774 objects.

2) after the loop
103,631,952 bytes, 8,760,495 objects.

It seems A has consumed 74M bytes, 8bytes each cell. That make sense
because a cell in list consists of 2 pointers, (car cdr), and an mem
address is 32 bit.





bearophileHUGS@ lycos.com wrote:

Pebblestone:
>

I heard that python's list is implemented as adjustable array.

>
Correct, an array geometrically adjustable on the right.
>
>

Here's my lisp implementation: <

>
What's the memory size of a before computing b? You can compare it with
Python, that may need less memory (because the array contains
pointers).
>
>

BTW, I couldn't install psyco on my system (ubuntu), gcc just prompt to me thousands of lines of errors and warnings.<

>
Find a Win box ;-) It's already compiled for it (for Py 2.3, 2.4).
>
>

Your python's example (use direct index array index) of my corresponding lisp code works slower than the version which use 'append'.<

>
For me (a slow PC) it's almost twice faster, computer life is usually
complex.
For me using the esplicit allocation + Psyco makes that program about 4
times faster (from 8 to 2 seconds).
>
>

This let me think how python's list is implemented.<

>
You also have to think how the * allocation is implemented and many
other things :-)
The list implementation is rather readable, Python sources are online
too.
>
>

Anyway, python's list is surprisingly efficient.<

>
But its access isn't that fast :-) Psyco helps.
>
Bye,
bearophile

[Pebblestone]

Re: Python and STL efficiency

Sorry, I did some miscalculation. ... what a shame.....




bearophileHUGS@ lycos.com wrote:

Pebblestone:
>

I heard that python's list is implemented as adjustable array.

>
Correct, an array geometrically adjustable on the right.
>
>

Here's my lisp implementation: <

>
What's the memory size of a before computing b? You can compare it with
Python, that may need less memory (because the array contains
pointers).
>
>

BTW, I couldn't install psyco on my system (ubuntu), gcc just prompt to me thousands of lines of errors and warnings.<

>
Find a Win box ;-) It's already compiled for it (for Py 2.3, 2.4).
>
>

Your python's example (use direct index array index) of my corresponding lisp code works slower than the version which use 'append'.<

>
For me (a slow PC) it's almost twice faster, computer life is usually
complex.
For me using the esplicit allocation + Psyco makes that program about 4
times faster (from 8 to 2 seconds).
>
>

This let me think how python's list is implemented.<

>
You also have to think how the * allocation is implemented and many
other things :-)
The list implementation is rather readable, Python sources are online
too.
>
>

Anyway, python's list is surprisingly efficient.<

>
But its access isn't that fast :-) Psyco helps.
>
Bye,
bearophile

[bearophileHUGS@lycos.com]

Re: Python and STL efficiency

Pebblestone:

Sorry, I did some miscalculation. ... what a shame.....

Don't worry.
For me using Py 2.4.3 those memory values are 4536 before and 20184 kb
after, it means a difference of 15648 kb, that equals to about 16023552
bytes, that equals to about 1000000 * 4 * 4. That means 4 bytes for
each string reference into the array. If you don't use Psyco the
starting memory value is quite lower.

If you don't use Psyco but you use the append, the values are 1384 and
18880, this means about 4.47 bytes / value, because python lists grow
geometrically, so there is some wasted space.

I find the memory used with PsList called from the Python script:

http://www.sysinternals.com/Utilities/PsList.html

Bye,
bearophile

[Pebblestone]

Re: Python and STL efficiency

Ruby is also not far away :-)

Here's my code:

+++++++++++++++ +++++++++++++++ ++++++++++
require 'time'

def f
a = []
1000000.times do
a.push "What do you know"
a.push "so long ..."
a.push "chicken crosses road"
a.push "fool"
end
b = a.uniq
b.each do |x|
puts x
end
end

def f2
a = Array.new(40000 00)
1000000.times do |i|
a[i] = "What do you know"
a[i+1] = "so long ..."
a[i+2] = "chicken crosses road"
a[i+3] = "fool"
end
b = a.uniq
b.each do |x|
puts x
end
end


f_start = Time.now
f
f_end = Time.now

f2_start = Time.now
f2
f2_end = Time.now

puts "f: Elapsed time: #{f_end - f_start} sec."
puts "f2: Elapsed time: #{f2_end - f_start} sec."

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

And the benchmark result:

What do you know
so long ...
chicken crosses road
fool
What do you know
so long ...
chicken crosses road
fool
nil
f: Elapsed time: 3.600294 sec.
f2: Elapsed time: 11.182927 sec.

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

I like ruby because its purity. :p



Licheng Fang wrote:

Hi, I'm learning STL and I wrote some simple code to compare the
efficiency of python and STL.
>
//C++
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
>
int main(){
vector<stringa;
for (long int i=0; i<10000 ; ++i){
a.push_back("Wh at do you know?");
a.push_back("so long...");
a.push_back("ch icken crosses road");
a.push_back("fo ol");
}
set<stringb(a.b egin(), a.end());
unique_copy(b.b egin(), b.end(), ostream_iterato r<string>(cout , "\n"));
}
>
#python
def f():
a = []
for i in range(10000):
a.append('What do you know')
a.append('so long...')
a.append('chick en crosses road')
a.append('fool' )
b = set(a)
for s in b:
print s
>
I was using VC++.net and IDLE, respectively. I had expected C++ to be
way faster. However, while the python code gave the result almost
instantly, the C++ code took several seconds to run! Can somebody
explain this to me? Or is there something wrong with my code?

[andrei.zavidei@gmail.com]

Re: Python and STL efficiency

---------------------------- C++ --------------------------
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <windows.h>

using namespace std;

int main()
{
DWORD ticks = ::GetTickCount( );

const string s1("What do you know");
const string s2("So long...");
const string s3("chicken crosses road");
const string s4("fool");

typedef vector<const string*str_vect or_t;
typedef str_vector_t::i terator vec_iter;
typedef set<const string*str_set_ t;
typedef str_set_t::cons t_iterator set_iter;


const int size = 1000000;
str_vector_t vec;
vec.reserve(siz e*4);

for(int i = 0; i < size; ++i){
vec.push_back(& s1);
vec.push_back(& s2);
vec.push_back(& s3);
vec.push_back(& s4);
}

vec_iter new_end = unique(vec.begi n(), vec.end());
str_set_t set_(vec.begin( ), new_end);

for(set_iter it = set_.begin(); it != set_.end(); ++it){
cout<<*it<<endl ;
}
cout<<::GetTick Count()-ticks<<endl;

return 0;
}

In MS VC+ 2005 in release configuration it gets the work done in 187
ms.

---------------- Python + Psyco----------------
def f():
a = []
for i in range(1000000):
a.append('What do you know')
a.append('so long...')
a.append('chick en crosses road')
a.append('fool' )
b = set(a)
for s in b:
print s

import time
from time import clock

import psyco
psyco.full()
f_start = clock()
f()
f_end = clock()

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

In Python in manages to do the same in 1.8 secs (psyco boosts it to
0.7; see below)
so long...
What do you know
fool
chicken crosses road
Elapsed: 0.772899 seconds


Well, that's how it is in my book.

Regards,
Andrei