Category: Programming

On overflowing stacks

I recently set out to implement a few basic data structures in C for the hell of it (and to reassure myself that I can still code C), and ran into an interesting compiler wart…

I was trying to instantiate a static array of 10 million integers (who doesn’t?), in order to test insertions and deletions in my tree. However, as you can astutely deduce from the title of this post, this was too much for the stack of my poor program and ended up in a segfault – a textbook stack overflow.

I did not think of that at first though, and tried to isolate the offending piece of code by inserting a return 0; in the main() after a piece of code I knew to be working, and working my way down to pinpoint the issue.

Much to my dismay, this didn’t really work out. Why? Check the following code:

Do you think it works with that last line uncommented? You’d be wrong!

[15:20:35]florent@Air:~/Experiments/minefield$ gcc boom.c
[15:20:40]florent@Air:~/Experiments/minefield$ ./a.out
Segmentation fault

GCC (4.2.1) wants to instantiate the array even though it’s declared after the function returns!

Interestingly enough, when you tell GCC to optimise the code, it realises the array will never get reached and prunes it away.

[15:26:06]florent@Air:~/Experiments/minefield$ gcc -O2 boom.c
[15:26:16]florent@Air:~/Experiments/minefield$ ./a.out
Hello world!

Clang (1.7) exhibits exactly the same behaviour.

Lessons learnt? return is no way of debugging a program.

Javascript closures as a way to retain state

Long time no blog! Let’s get back into it with a nifty and clean way of retaining state in Javascript – closures.

I was recently looking for an easy way to call a specific function after two separate/unrelated AJAX calls to two remote endpoints have been completed. The naive method would be to make the first AJAX call -> callback to the second AJAX  call -> callback to doSomething, but we can use the fact that these two AJAX calls are not related and run them concurrently. An easy way to achieve that is to:

1. set flags, say initialising two global variables at the beginning of the file:

var callback_one_done = false;
var callback_two_done = false;

2. have each callbacks set its own flag to ‘true’ upon completion and call doSomething
3. check both flags in doSomething:

var doSomething = function() {
    if (callback_one_done && callback_two_done){
        // actually do something
    }
}

But this is a bit ugly, as it litters the global namespace with two flags that are only used there. Instead, thanks to Javascript’s lexical scope we can declare doSomething as a closure and have the flags live inside the function itself:

var doSomething = (function(){
        var callback_one_done = false;
        var callback_two_done = false;
        return function(source) {
            if (source === 'callback_one') { callback_one_done = true; }
            if (source === 'callback_two') { callback_two_done = true; }
            if (callback_one_done && callback_two_done) {
                // actually do something
            }
        };
    }());

What we’ve done here is declare an anonymous function that returns a function. This newly created function, that gets attributed to doSomething, is a closure that contains both the code needed to run and the flag variables. The state is set and kept inside the function itself, without leaking on the outside environment.

Now we just need to call doSomething(‘callback_one’) from the first AJAX call and doSomething(‘callback_two’) from the second AJAX call and doSomething will wait until both calls are complete to run the “actually do something” part.

Bits of javascript goodness

(This blog post is better followed with the associated github repo. Run the Sinatra server with ‘ruby slowserver’, pop up a browser, and follow the revisions to see how the code gradually gets better. :) )

Recently at work, we wanted to modify some js ad code to include weather data for better ad targeting. For certain caching reasons, weather data has to be fetched by an AJAX call, then fed to the ad code.

The existing ad code was (schematically) as follows.

My first idea was to replace those calls by a call to a single js method, which would stall the ad calls using, say, a setTimeout, until the weather data is retrieved. The js looked like this.

Before you go get the pitchforks, I knew that this code was crap, and asked one of my amazing colleagues for help. He advised me to get rid of the timeOuts and instead use a function that would either, depending if the data was retrieved or not, shelf the task in an array, or execute it.

Using an array of tasks (actually callbacks, or anonymous functions, or closures) allows us to have actual event-driven javascript. This means executing the ad loading code only once, not using resources for timeouts when the resource is not available yet, and maybe most importantly not looking stupid when code review time codes.

Additionally, my code littered the general namespace with his variables. We could instead create a module, and have only that module’s name public – we clean up the global namespace and also get private variables for free!
The module pattern is an amazingly useful javascript pattern, implemented as a self-executing anonymous function. If that sounds clear as mud, Ben Cherry has a better, in-depth explanation on his blog.

The js code now looked like this.

But the HTML still contained <script> tags, and separation of concerns taught us it’s better to keep HTML and JS as separate as possible. Cool beans, let’s just add a couple of line to our js file.

Result: a pure event-driven wait for a callback, a single variable in the global js namespace, and a cleaned-up HTML.

And of course… We ended up not using it. The ad code actually expects a document.write, making this delayed approach impossible (document.write appends data inline while the page is still loading, but completely rewrites the page if called after pageload). Good learning experience still!

Format perlcritic output as TAP to integrate with Jenkins

Perl::Critic is a nifty syntax analyzer able to parse your Perl code, warn you against common mistakes and hint you towards best practices. It’s available either as a Perl module or a standalone shell script (perlcritic). Unfortunately, there is no standard way to integrate it with Jenkins.

Jenkins, the continuous-integration-tool-formerly-known-as-Hudson, is the cornerstone of our continuous building process at work. It checks out the latest build from Git, runs a bunch of tests (mainly Selenium, as we develop a website) and keeps track of what goes wrong and what goes right. We wanted to integrate Perl::Critic to Jenkins’ diagnostics to keep an eye on some errors that could creep in our codebase.

So Jenkins doesn’t do Perl::Critic. However, Jenkins supports TAP. TAP, the Test Anything Protocol, is an awesomely simple format to express test results that goes as follow:

1..4
ok 1 my first test
ok 2 another successful test
not ok 3 oh, this one failed
ok 4 the last one's ok

The first line (the plan) announces how many tests there are, and each following line is a test result beginning by either “ok” or “not ok” depending on what gave.

Based on such a simple format, we can use a bit of shell scripting to mangle perlcritic’s output to be TAP-compatible:

# Perl::Critic                             \
# with line numbers (nl)...                \
# prepend 'ok' for passed files...         \
# and 'not ok' for each error...           \
# and put everything in a temp file

perlcritic $WORKSPACE                      \
  | nl -nln                                \
  | sed 's/\(.*source OK\)$/ok \1/'        \
  | sed '/source OK$/!s/^.*$/not ok &/'    \
  > $WORKSPACE/perlcritic_tap.results.tmp

# Formatting: add the TAP plan, and output the tap results file.
# TAP plan is a line "1..N", N being the number of tests
echo 1..`wc -l < $WORKSPACE/perlcritic_tap.results.tmp` \
 |cat - $WORKSPACE/perlcritic_tap.results.tmp > $WORKSPACE/perlcritic_tap.results

# Cleanup
rm -f $WORKSPACE/perlcritic_tap.results.tmp

(§WORKSPACE is a Jenkins-set variable referring to where the current build is being worked on.)

And voilà! Jenkins reads the TAP result file and everything runs smoothly.

The only downside of this approach is that the number of tests will vary. For example, a single .pm file containing 5 Perl::Critic violations will show up as 5 failed tests, but fixing these will turn into a single successful test.

Optimising a video editor plugin

During the past few weeks, I have been writing a C++ plugin to grade C41 digital intermediates in Cinelerra, an open-source Linux video editor. C41 is the most common chemical process for negatives, resulting in films that look like this — you probably know it if you’ve ever shot film cameras.

Of course, after scanning those negatives, you have to process (“grade”) them to turn them back to positive. And it’s not as simple as merely inverting the values of each channel for each pixel; C41 has a very pronounced orange shift that you have to take into account.

The algorithm

The core algorithm for this plugin was lifted from a script written by JaZ99wro for still photographs, based on ImageMagick, which does two things:
– Compute “magic” values for the image
– Apply a transformation to each channel (R, G, B) based on those magic values

The problem with film is that due to tiny changes between the images, the magic values were all over the place from one frame to the other. Merely applying JaZ’s script on a series of frames gave a sort of “flickering” effect, with colours varying from one frame to the other, which is unacceptable effect for video editing.

The plugin computes those magic values for each frame of the scene, but lets you pick and fix specific values for the duration of the scene. The values are therefore not “optimal” for each frame, but the end result is visually very good.

However, doing things this way is slow: less than 1 image/second for 1624*1234 frames.

Optimising: do less

The first idea was to make optional the computing of the magic values: after all, when you’re batch processing a scene with fixed magic values, you don’t need to compute them again for each frame.

It was a bit faster, but not by much. A tad more than an image/second maybe.

Optimising: measure

The next step —which should have been the first!— was to actually benchmark the plugin, and see where the time was spent. Using clock_gettime() for maximum precision, the results were:

~0.3 seconds to compute magic values (0.2s to apply a box blur to smooth out noise, and 0.1s to actually compute the values)

~0.9 seconds to apply the transformation

Optional computing of the magic values was indeed a step in the right direction, but the core of the algorithm was definitely the more computationally expensive. Here’s what’s to be computed for each pixel:

row[0] = (magic1 / row[0]) - magic4;
row[1] = pow((magic2 / row[1]),1/magic5) - magic4;
row[2] = pow((magic3 / row[2]),1/magic6) - magic4;

With row[0] being the red channel, row[1] the green channel, and row[2] the blue channel.

The most expensive call here is pow(), part of math.h. We don’t need to be extremely precise for each pixel value, so maybe we can trade some accuracy for raw speed?

Optimising: do better

Our faithful friend Google, tasked with searching for a fast float pow() implementation, gives back Ian Stephenson’s implementation, a short and clear (and more importantly, working) version of pow().

But we can’t just throw that in without analysing how it affects the resulting frame. The next thing to do was to add a button that would switch between the “exact” version and the approximation: the results were visually identical.

Just to be sure, I measured the difference between the two methods, and it shows an average 0.2% difference, going as high as 5% for the worst case, which are acceptable values.

And the good news is that the plugin now only takes 0.15 to 0.20 second to treat each image, i.e. between 5 and 6 images/second — an 8-fold gain since the first version. Mission accomplished!