A few days ago I wrote a post about how to convert a csv list to a table. I spent some time writing my program in C (for fun and for performance).
About the C implementation
The C implementation uses only standard C library (stdlib.h, stdio.h, string.h). The good thing is that the program is very portable and easy to compile. The bad thing is that I do not have access to powerful datatypes (hash tables, balanced trees, sets). This basically means wasting time reinventing the wheel, and not getting a perfect wheel anyway. My estimation is that the C implementation is O(n) for suitable input (fairly sorted data) and O(n)Sqrt(n) for unsuitable data (reversely sorted). This is for fairly “square” matrices. The C implementation is not really optimized (perhaps a later excercise).
About the python implementation
The python implementation was written after the C implementation, and very nicely utilizes the python built in set and dict datatypes. Should be O(n) or O(n)log(n) depending on Python dict implementation.
The benchmarks are performed using the time command on an AMD Athlon II X2 250 machine with 4GB of RAM. The machine runs x64 Xubuntu 11.10.
|Environment||gcc 4.6.1, -O2||Python 2.7.2+|
|Lines of code
(excl help text)
|355 lines||53 lines|
|Input size||Execution time|
|Sorted data: 0.014s
Reversed data: 0.027s
|0.039s – 0.052s||0.18s|
|0.16s – 0.25s||0.64s|
|0.57s – 1.2s||2.6s|
|2.4s – 7.8s||10s|
|9.7s – 51s||41s|
|40s – 337s||Not enough RAM|
|RAM usage for
I draw the following conclusions:
- Python is a very efficient language compared to C, when it comes to producing code fast, in this case about 10x faster
- Python is impressively fast, even startup overhead is reasonable
- Python can beat C on performance, when C programmer has not found optimal data type/algorithm. The Python datatypes makes it easy to write code that is fast even for large data
- A well written C program uses 10% the RAM of Python, and is at least 5x faster. Especially the small RAM requirement is very powerful and valuable for many applications
It is tempting to optimize the C program to see if I can get 2x, 3x or 5x speedup.
It is also tempting to write a C program that uses Glib, and have access to well implemented data types. How would it compare?