Archive for the “python” Category
The shorthand “WTF” is common among developers. It does not actually stand for “worse than failure” but I run a clean ship here people. [Hint: let's just say that WTF is a somewhat crude interrogative. Sample usage: "Dude, WTF?" or, if you prefer, comic form.]
I just spent two days looking for a bug in my code whose fix was simply replacing
A = A + np.dot(features, features - env.gamma * newfeatures) with
A = A + np.outer(features, features - env.gamma * newfeatures) In my defense, I didn’t spend two full days looking for this mistake, but the process was so demoralizing that I couldn’t find much willpower to do productive work when I wasn’t actively debugging.
Takeaway lesson, triple check your linear algebra. If you get something wrong, you’re likely to have a hard time figuring out why, or worse, you may mistake the junk for the correct answer. [Aside: note that I was really burned by the fact that '+' is overloaded in this case, and so is valid for both matrix, matrix addition and scalar, matrix addition. Despite the scorch marks, I do like this feature.]
No Comments »
A research problem I’m working on involves Isomap, a method of dimensionality reduction that requires computing all shortest paths over relatively large graphs. In interpreted languages like Matlab this is often done through the use of the Floyd-Warshall algorithm, a simple  dynamic programming approach to computing all shortest paths. In the reference Isomap code this algorithm takes only three lines:
for k=1:N
D = min(D,repmat(D(:,k),[1 N])+repmat(D(k,:),[N 1]));
endThe benefits of Floyd-Warshall are two-fold for languages like Matlab. The first is that the implementation is short and simple. The second is that the implementation can employ a number of linear algebra primitives that are highly optimized in languages like Matlab. In the code snippet above the repmat, addition, and min operations are all implemented as low-level highly optimized library calls. This means that Floyd-Warshall, despite the non-optimal runtime, is often the fastest Matlab approach to computing all shortest paths even on reasonably large problem sizes.
In my work, I’ve reimplemented Isomap in Python (which will soon appear in my algorithms gallery). My implementation of Floyd-Warshall uses NumPy for access to similarly optimized low-level linear algebra routines. Here’s my original Python code snippet:
for k in range(n):
adj = np.minimum( adj, np.add.outer(adj[:,k],adj[k,:]) )
return adjNote that I used outer products in my code, instead of the repmat approach in the original Isomap implementation. I decided to see if using tile, the NumPy equivalent or repmat, would result in an even faster Floyd-Warshall implementation:
for k in range(n):
adj = np.minimum(adj, np.tile(adj[:,k].reshape(-1,1),(1,n)) + np.tile(adj[k,:],(n,1)))
return adjTo test these two approaches, I generated a few random graphs on 1000 nodes and computed all shortest paths several times (to account for variations in CPU usage). To my delight, it turns out that my original implementation ran an average of 30 seconds faster (42.8 seconds) than the approach using tile (72.7 seconds). Though more experimentation might be required to make this comparison definitive, I am trying to uncover possible reasons for the performance difference, and in particular why the Matlab code uses repmat instead of outer products (I have yet to compare performance of different Matlab versions of this algorithm).
4 Comments »
So today I found myself trying to figure out how to pickle objects that are based on dynamically constructed classes. This is probably the simplest instance of metaclass magic in Python — the use of the ‘type’ builtin, a metaclass. A metaclass is a class whose objects are themselves class specifications. People use metaclasses to modify the default way classes are built, or in my case to build classes dynamically (say from a soup of mixins).
Anyway, the following code ran into problems.
import pickle
classes = {}
classes['ClassName'] = type('ClassName', (),{})
obj = classes['ClassName']()
pickle.dump(obj,open('test.pck','w'))Attempting to run this code gives:
Traceback (most recent call last):
File "/tmp/py17808UNS", line 8, in
pickle.dump(obj,open('test.pck','w'))
File "/usr/lib/python2.5/pickle.py", line 1362, in dump
Pickler(file, protocol).dump(obj)
File "/usr/lib/python2.5/pickle.py", line 224, in dump
self.save(obj)
File "/usr/lib/python2.5/pickle.py", line 331, in save
self.save_reduce(obj=obj, *rv)
File "/usr/lib/python2.5/pickle.py", line 401, in save_reduce
save(args)
File "/usr/lib/python2.5/pickle.py", line 286, in save
f(self, obj) # Call unbound method with explicit self
File "/usr/lib/python2.5/pickle.py", line 562, in save_tuple
save(element)
File "/usr/lib/python2.5/pickle.py", line 286, in save
f(self, obj) # Call unbound method with explicit self
File "/usr/lib/python2.5/pickle.py", line 748, in save_global
(obj, module, name))
PicklingError: Can't pickle : it's not found as __main__.ClassNameSo what was I trying to do? I’ve implemented a learning agent as an object and constructed a bunch of mixins that specify variations of the training algorithm, reward function, and various other modifiable agent properties. What I want to do is take the cross product of all the variations, testing each on the cluster here at UT. Of course I want to pickle each agent so that I can inspect the resulting performance later without having to rerun a thousand experiments.
I only have a small number of variations, so explicitly naming all the mixin combinations isn’t too onerous, but I am curious as to whether lack of serialization inhibits the use of mixins in Python programming generally.
Or maybe I’m just programming orthogonal to the norm.
No Comments »
Python is an interpreted language, and the interpreter is solid enough that you wouldn’t expect to encounter the following:
stober[~]{landmine}$ python test.py
Segmentation faultPretty scary stuff. So what was I running?
#!/lusr/bin/python
from opencv import highgui
from opencv import cv
writer = highgui.cvCreateVideoWriter("test.mpg", highgui.CV_FOURCC('m','p','g','1'), 30.0, cv.cvSize(100,100), True)99.9% of the time the Python interpreter is not at fault, so you can safetly bet the problem has something to do with a library, preferably some library that is
- not in part of the standard libraries
- not written in pure Python.
The Python bindings for OpenCV fit both of these criteria perfectly. So the question now is, what do I do about it?
A major advantage of open source is that, if you are so inclined, you may be able to figure out a solution directly. If you spend all day in Python, you may have forgotten about an old friend from your distant past — gdb.
With a debuggable OpenCV library at my disposal, here what my gdb session looks like:
This GDB was configured as "i686-pc-linux-gnu".
(gdb) file python
Reading symbols from /lusr/bin/python...done.
Using host libthread_db library "/lib/tls/i686/cmov/libthread_db.so.1".
(gdb) break cvCreateVideoWriter
Function "cvCreateVideoWriter" not defined.
Make breakpoint pending on future shared library load? (y or [n]) y
Breakpoint 1 (cvCreateVideoWriter) pending.
(gdb) run test.py
Starting program: /lusr/bin/python test.py
[Thread debugging using libthread_db enabled]
[New Thread 0xb7dee6c0 (LWP 32307)]
Breakpoint 2 at 0xb65b1a50: file cvcap.cpp, line 250.
Pending breakpoint "cvCreateVideoWriter" resolved
[Switching to Thread 0xb7dee6c0 (LWP 32307)]
Breakpoint 2, cvCreateVideoWriter (filename=0xb7d85634 "test.mpg", fourcc=23556205, fps=30, frameSize={width = 100, height = 100}, is_color=1) at cvcap.cpp:250
250 double fps, CvSize frameSize, int is_color )
Current language: auto; currently c++
(gdb) n
256 if(!fourcc || !fps)
(gdb)
271 result = cvCreateVideoWriter_FFMPEG(filename, fourcc, fps, frameSize, is_color);
(gdb) s
cvCreateVideoWriter_FFMPEG (filename=0xb7d85634 "test.mpg", fourcc=23556205, fps=30, frameSize={width = 100, height = 100}, isColor=1) at cvcap_ffmpeg.cpp:1274
1274 CvSize frameSize, int isColor )
(gdb) n
1276 CvVideoWriter_FFMPEG* writer = new CvVideoWriter_FFMPEG;
(gdb) n
692 CvVideoWriter_FFMPEG() { init(); }
(gdb)
1277 if( writer->open( filename, fourcc, fps, frameSize, isColor != 0 ))
(gdb) n
Program received signal SIGSEGV, Segmentation fault.
0xb76f3e9f in codec_get_id () from /u/robot/python/lib/libavformat.so.52
(gdb)I’ll omit the circuitous debugging path that resulted. Some strategic breakpoint settings later, I found out that the expression
highgui.FOUR_CC('m','p','g','1')led to the segfault. I never got to the root cause, but using the gdb session as intuition, and flipping through the code, I discovered that highgui has a
highgui.CV_FOURCC_DEFAULT field which lets the function cvCreateVideoWriter select the proper encoding based on the filename.
With the workaround, here’s what I get:
stober[~]{landmine}$ python test.py
Output #0, mpeg, to 'test.mpg':
Stream #0.0: Video: mpeg1video (hq), yuv420p, 100x100, q=2-31, 640 kb/s, 30.00 tb(c)
swig/python detected a memory leak of type 'CvVideoWriter *', no destructor found.Still some line noise, but no segfault! So what are the takeaways?
- Well, if you do a lot of work with open source libraries, be sure you are comfortable building debuggable versions of those libraries.
- Also, become familiar with using gdb to debug dynamically loaded libraries. If you use Python with a lot of imported shared libraries, you’ll need to know how to do so eventually.
- Finally, have patience. I omitted the better part of an afternoon’s worth of faulty assumptions, misleading code paths, and general confusion in the above description. Learn to manage your frustration as you learn to navigate unfamiliar code. Both skills are invaluable.
1 Comment »
You may have come across the following issue with OpenCV Python bindings:
image = cv.cvCreateImage(size, cv.IPL_DEPTH_8U, 3)
image.imageData = data # set some data Trying to set the “data” of an OpenCV image directly fails. The problem is in the underlying SWIG code that attempts to make the imageData field available for writing at the python level. You can see in CVS that the code gets fixed immediately after the 1.0 release.
But wait! Doesn’t OpenCV come with an adaptors.py that is supposed to provide methods for translating between various Python data types (NumPy < => PIL < => IplImage) ?
A quick look at the code:
def PIL2Ipl(input):
"""Converts a PIL image to the OpenCV/IPL CvMat data format.
Supported input image formats are:
RGB
L
F
"""
if not isinstance(input, PIL.Image.Image):
raise TypeError, 'must be called with PIL.Image.Image!'
size = cv.cvSize(input.size[0], input.size[1])
# mode dictionary:
# (pil_mode : (ipl_depth, ipl_channels, color model, channel Seq)
mode_list = {
"RGB" : (cv.IPL_DEPTH_8U, 3),
"L" : (cv.IPL_DEPTH_8U, 1),
"F" : (cv.IPL_DEPTH_32F, 1)
}
if not mode_list.has_key(input.mode):
raise ValueError, 'unknown or unsupported input mode'
modes = mode_list[input.mode]
result = cv.cvCreateImage(
size,
modes[0], # depth
modes[1] # channels
)
# set imageData
result.imageData=input.tostring() #FAIL!
return resultAs you can see, adaptors.py tries to set imageData as well, and so fails to convert from any format into IplImage. Your options are to work from the repository version of OpenCV or to back port the change from the repository to your local installation. Both require compiling from source and so as you may imagine, neither case is convenient when working with libcv as installed from your favorite package manager of choice.
A third option is to back port the changes from the repository to your own custom swig module whose only goal is to implement a function that sets the imageData field properly. That’s the approach I took, and though it took a considerable amount of time to implement (because I don’t really understand SWIG), the end result did not require many lines of code. Here’s my iplimage.i file:
%module iplimage
%{
#include "cv.h"
void set(CvMat *self, char *string);
%}
void set(CvMat *self, char *string);And here’s iplimage.c copied with minor changes directly out of the repository for OpenCV:
#include "cv.h"
void set(CvMat * self, char *string)
{
int depth = CV_MAT_DEPTH(self->type);
int cn = CV_MAT_CN(self->type);
int step = self->step ? self->step : CV_ELEM_SIZE(self->type) * self->cols;
long line;
long pixel;
if (depth == CV_8U && cn==3){
// RGB case
// The data is reordered beause OpenCV uses BGR instead of RGB
for (line = 0; line < self->rows; ++line)
for (pixel = 0; pixel < self->cols; ++pixel)
{
// In OpenCV the beginning of the lines are aligned
// to 4 Bytes. So use step instead of cols.
long position = line*step + pixel*3;
long sourcepos = line*self->cols*3 + pixel*3;
self->data.ptr[position ] = string[sourcepos+2];
self->data.ptr[position+1] = string[sourcepos+1];
self->data.ptr[position+2] = string[sourcepos ];
}
}
else if (depth == CV_8U && cn==1)
{
// Grayscale 8bit case
for (line = 0; line < self->rows; ++line)
{
// In OpenCV the beginning of the lines are aligned
// to 4 Bytes. So use step instead of cols.
memcpy
(
self->data.ptr + line*step,
string + line*self->cols,
step
);
}
}
else if ( depth == CV_32F )
{
// float (32bit) case
for (line = 0; line < self->rows; ++line)
{
// here we don not have to care about alignment as the Floats are
// as long as the alignment
memcpy
(
self->data.ptr + line*step,
string + line*self->cols*sizeof(float),
step
);
}
}
else if ( depth == CV_64F )
{
// double (64bit) case
for (line = 0; line < self->rows; ++line)
{
// here we don not have to care about alignment as the Floats are
// as long as the alignment
memcpy
(
self->data.ptr + line*step,
string + line*self->cols*sizeof(double),
step
);
}
}
else
{
}
}An example makefile that works on my system:
CFLAGS= `pkg-config --cflags opencv`
LDFLAGS= `pkg-config --libs opencv` -L.
CXX=g++
_iplimage.so: iplimage.c
swig -python iplimage.i
$(CXX) $(CFLAGS) -I/usr/include/python2.5 -c iplimage.c iplimage_wrap.c
$(CXX) $(LDFLAGS) -shared iplimage.o iplimage_wrap.o -o _iplimage.so If you manage to build the module, you can then invoke it from python using a call to iplimage.set(image,data) to set the imageData field for real. You can use the default OpenCV Python bindings that come with your package manager and simply install this small additional module. Hopefully, we’ll see a new release of OpenCV soon that negates the need for any of these acrobatics.
12 Comments »
I no longer choose to use Python. One day I decided to spend a couple of hours parallelizing some code for a new dual core machine. Than I discovered the GIL. From the Python list circa 2004:
I've said it before. One day enough people will think that the GIL is
a problem big enough to warrant a solution, e.g., when the majority of
systems where CPython runs have more than one CPU. Until then we have
to go back to early 90s programming and use IPC (interprocess
communication) to scale applications that want to run PURE python code
on more than one CPU.
That day has come to pass.
UPDATE: Though the lack of true threads is still a concern, I’ve found working with the latest iteration of numpy to be much easier than alternatives like Matlab or R. The truth: syntax matters.
No Comments »
I once tried to parallelize some Python code to take advantage of multiple processors, so I learned about the Global Interpreter Lock the hard way. Threads are supposed to allow for concurrency without protection. If you want concurrency and protection, use processes. The GIL is just a half-baked half measure between these two easy to state abstractions. That was the beginning of my path away from Python.
Anyway, for those still interested: Parallel Python
No Comments »
Is deferred a use of continuation passing style? In a sense.
continuation is a representation of some of the execution state of a program
Adding deferred callbacks defines a sequence of continuations. At each step, the deferred process calls the next function in the callback sequence using the data returned from the previous call. It’s not true CPS since the callbacks themselves don’t take continuations as parameters.
I like to think of it as CPS-light. Completely useless – until you need it.
No Comments »
Every so often I forget how to exit from the Python interpreter. I’ll type “quit” and be greeted by the following:
>>> quit
‘Use Ctrl-D (i.e. EOF) to exit.’
>>>
Then one day I was messing around with globals() and realized that quit is just a variable set to the string ‘Use Ctrl-D (i.e. EOF) to exit.’ by default.
No Comments »
|
Entries (RSS)
