|Problems? Is your data what you think it is?|
The Ovidian Transformby Ovid (Cardinal)
|on Dec 31, 2001 at 13:21 UTC||Need Help??|
How to gain a 50% performance increase over the Schwartzian Transform
Note: Where else could I get away with a title as cheeky as this one? :) If anyone can make suggestions to improve the C code, that would be welcome. I'd also like to point out that the title is a joke. There is nothing revolutionary about using C to resolve Perl performance bottlenecks. Also, this mode was more an exploration of Inline::C and not an attempt to speed up the Schwartzian Transform.
I hate forgetting things that I once knew. I returned to college when I was in my mid-twenties because I hated the fact that I had forgotten how to speak French¹. You can understand, therefore, why it bugs me that I no longer know how to program in C. I started programming in the early 80s, writing games in BASIC. BASIC, as most of you know, runs as fast and elegantly as a dead gazelle. In order to speed up the critical portions of my programs, I taught myself assembler. It was tedious, but I had to do it. You can imagine how delighted I was when I learned C in college.
That was 15 years ago. I haven't programmed in C since. I've been trying to improve my resume and started Java classes. I'm going to keep taking them because knowing Java will tremendously expand my marketability, but I really don't care for Java². So, I was browsing through Powell's technical bookstore here in Portland, Oregon, and picked up a copy of O'Reilly's "Practical C". It was a godsend.
Relearning C is fine and dandy, but putting it to some practical use is finer and, um, dandier. So, I went to the CPAN and downloaded Inline. The Inline module allows you to embed other programming languages, such as C, Java, or Python, in Perl. If you have extensive libraries written in another language, it's great to be able to simply reuse them rather than rewrite them in Perl. In the case of Inline::C (which is bundled with Inline), you can also gain significant performance benefits.
If you've ever tried to embed C in Perl without Inline, I feel sorry for you. I never considered it due to the daunting nature of XS and SWIG. With Inline, it's almost trivial. I installed Inline using Cygwin on a Windows 98 machine. The install was flawless, though it took longer to install than any previous module. One of the sections of make test took 504 wallclock seconds! However, having such a large module install without problems on a Cygwin box told me that someone had done an excellent job of things.
After the install, I ran pod2html on Inline.pod, C.pod, and C-Cookbook.pod. Reading through them was fairly straightforward. Inline.pod tells you to go ahead and skip to the Cookbook if you want to get started right away, but I wouldn't. The documentation can be a bit dry at times, but it's very useful and the first time some of your embedded C fails to compile, you'll be grateful for reading the documentation because that is chock full 'o tips and tricks of which you should be aware.
After working through many of the examples in the Cookbook, I decided it was time to try writing something myself. My first inclination, to be fair, was to try writing CGI::Inline. Many people balk at the performance of the CGI module, but since I need to walk before I can run (and I don't have as much free time as I would like), I figured I would would start with something small. The Schwartzian Transform (ST) seemed like a perfect candidate for this. The ST is one of the fastest sorting methods available, so trying to speed it up a bit with C seemed like a nice challenge. The basic structure of the ST is this:
Basically, you take an array of data and turn every element into a 2 item array reference with first item in the reference being the original data and the second item in the array being the data you want to sort on (in a sortable form, of course). Then, you sort the array by the second item and map the original data back to an array.
Hmm... what should I optmize? Well, if &expensive_function isn't crying out for some help, I shouldn't be programming - of course, some would argue that I shouldn't be programming anyway, but I try not to listen to the voices coming from the toaster.
I decided to tackle the traditional problem of sorting strings with an embedded date. I created an arbitrary data format like the following:
I need to grab that date as efficiently as possible. I used the following Perl snippet:
Using substr, index, and unpack is about as efficient as you can get. Now, I need to figure out how to do that with Inline. Passing a scalar to an Inline function and getting back a scalar is fairly simple. I merely define the the correct return type of the function (SV*), pass it a string and return a new scalar value. I do this with this:
I merely call the function with a char* foo argument and padding it with a NUL is handled for me. Getting the date from this is trivial. Here's the full function as I would embed it in Perl.
If you prefer, you can also add the C code after the __DATA__ token or in another module or file. Now, the first time this is run, it will take quite some time as Inline has to go through all of the steps necessary to compile the C and make it accessible to Perl. On subsequent runs, Inline generates a checksum for the C code and, if the checksum is the same, Inline will not recompile, as it assumes that the C has not changed. You can override this behavior if you wish.
Once this has been done, you call the C function like you would call any other function:
Now that I have my Perl code and C code to test against, I run some benchmarks. There's no point in repeating them here as the two ran neck and neck. Repeatedly. I had taken too simple of a task and Perl was too efficient. I decided to complicate things a bit. Many Americans use a MMDDYYYY date format. Now, I not only have to grab the date, I need to rearrange the digits into a sortable YYYYMMDD format. Here's the Perl:
Here's the C code I whipped up:
Now we have something just a tad more interesting. It turns out that we also have something that's over 20% faster in C:
Now, that's nice and all, but I was hoping for something a bit more dramatic. Taking a closer look at the ST, we see that the last two steps are a sort, which returns a list, and a map, which returns a list. Wouldn't it be nice if the sort just returned what we wanted? Imagine doing this:
Of course, that won't work, but I started thinking a bit more about this. My initial idea was to write a bit of C code that would read the array off the stack, create a struct with the original data and the date, sort on the date, and just return the original data. Then, I had a weird inspiration. Now, my original idea is probably better, as the following is filled with dangers and will not always be appropriate for your task, but it should work in many cases.
I remembered that bikeNomad had asked How to make bi-modal variables like $! ?. After some discussion, and taking an idea from tye, he came up with this code snippet. It occurred to me that I could strip the date, make the original value bi-modal, sort on the numeric value and return the string value all in one go! I call this (pardon the hubris) "The Ovidian Transform" :) It just has one map and one sort. Here are the benchmarks:
I ran them several times and got consistent results. A performance improvement of about 50% over the Schwartzian Transform. Full code is below. Enjoy!
1.Perversely, I have forgotten French again. I was in Paris buying a pack of cigarettes and asked the cashier if she had any matches (les allumettes). I said "Pardon, avez-vous des alouttes?" (Pardon me, do you you have any larks?). It was most confusing.
2.It's bloated, slow, has irritating limitations like not being able to subclass String to add methods, etc. Very annoying. On the other hand, it has taught me quite a bit about OO programming and has a tighter type-checking system than Perl. And when was the last time you wrote an applet in Perl?
Update: I'm trying to remember which monks helped me with some C questions. wog was one. /msg Ovid ... if you also helped. I'd like to give credit where credit is due!
Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.