(silly?) speed comparisons

mk mrkafk at gmail.com
Tue Jul 8 18:06:21 EDT 2008


Out of curiosity I decided to make some speed comparisons of the same 
algorithm in Python and C++. Moving slices of lists of strings around 
seemed like a good test case.

Python code:

def move_slice(list_arg, start, stop, dest):
	frag = list_arg[start:stop]
	if dest > stop:
		idx = dest - (stop - start)
	else:
		idx = dest
	del list_arg[start:stop]
	list_arg[idx:idx] = frag
	return list_arg

b = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']

 >>> import timeit
 >>> t = timeit.Timer("move_slice.move_slice(move_slice.b, 4, 6, 7)", 
"import move_slice")
 >>> t.timeit()
3.879252810063849

(Python 2.5, Windows)

Implementing the same algorithm in C++:

#include <vector>
#include <iostream>
#include <string>

using namespace std;

vector<string> move_slice(vector<string> vec, int start, int stop, int dest)
{
	int idx = stop - start;
	vector<string> frag;
	
	// copy a fragment of vector
	for (idx = start; idx < stop; idx++)
		frag.push_back(vec.at(idx));
	if( dest > stop)
		idx = dest - (stop - start);
	else
		idx = dest;
	// delete the corresponding fragment of orig vector
	vec.erase( vec.begin() + start, vec.begin() + stop);
		
	// insert the frag in proper position
	vec.insert( vec.begin() + idx, frag.begin(), frag.end());

	return vec;
}
	
	
int main(int argc, char* argv)
{
	vector<string> slice;
	string u = "abcdefghij";
	int pos;
	for (pos = 0; pos < u.length(); pos++)
		slice.push_back(u.substr(pos,1));

	int i;
	for (i = 0; i<1000000; i++)
		move_slice(slice, 4, 6, 7);

}

Now this is my first take at vectors in C++, so it's entirely possible 
that  an experienced coder would implement it in more efficient way. 
Still, vectors of strings seemed like a fair choice - after all, Python 
version is operating on similarly versatile objects.

But I was still rather surprised to see that C++ version took 15% longer 
to execute!

(vector, 4, 6, 7)
$ time slice


real    0m4.478s
user    0m0.015s
sys     0m0.031s

Compiler: MinGW32/gcc 3.4.5, with -O2 optimization (not cygwin's gcc, 
which for some reason seems to produce sluggish code).


When I changed moving the slice closer to the end of the list / vector, 
Python version executed even faster:

 >>> t = timeit.Timer("move_slice.move_slice(move_slice.b, 6, 7, 7)", 
"import move_slice")
 >>> t.timeit()
1.609766883779912

C++:

(vector, 6, 7, 7)
$ time slice.exe


real    0m3.786s
user    0m0.015s
sys     0m0.015s

Now C++ version took over twice the time to execute in comparison to 
Python time!


Am I comparing apples to oranges? Should the implementations be 
different? Or does the MinGW compiler simply suck?

Note: it appears that speed of Python lists falls down quickly the 
closer to the list beginning one deletes or inserts elements. C++ 
vectors do not seem to be as heavily position-dependent.





More information about the Python-list mailing list