Bash Job Management Essentials

Did you ever wish your program had a pause button? I did so regularly. I regularly have to do lengthy calculations, for example for evaluating some heuristics for an optimization problem such as Maximum Independent Set or Matchings. A typical program could look like this:

for all benchmark graphs G:
  for all algorithm variants A:
    for k in [2, 4, 8, ..., 128]:
      Execute A on G with the current value for k

Now if this computation takes 20 hours and I'm running this on my laptop, one of the CPU cores is hogged and the fan goes berserk. So what happens if I want to take my computer somewhere else or view a movie? As it turns out, I can simply suspend the machine and after waking up the program will continue to run. This already solves the first problem and shows that the operating system can suspend my program out of the box. The bash shell (and I'm sure other shells, too) helps me with the second problem: It is able to do basic job management. Consider the following command sequence. This lists my temporary directory and pastes it through less. less will wait for my input.

$ ls /tmp | less

Now, I press Ctrl+Z to suspend less:

[1]+  Stopped                 ls /tmp | less

Neat! How do we get back the listing. With fg %<job number>:

$ fg %1

We can also have multiple jobs:

$ ls /tmp | less
Ctrl+Z
[1]+  Stopped                 ls /tmp | less
$ ls /usr | less
Ctrl+Z
[2]+  Stopped                 ls /usr | less

The command job gives us a listing of the current jobs:

$ jobs
[1]-  Stopped                 ls /tmp | less
[2]+  Stopped                 ls /usr | less

There is one gotcha: If you use the bash command time, it will display the passed time when you suspend your job and not print the remaining spent time after you restart it again:

$ time ls /tmp | less
Ctrl+Z
[1]+  Stopped                 ls /tmp | less

real 0m1.139s
user 0m0.001s
sys 0m0.003s
manuel@coxorange ~
$ fg %1
ls /tmp | less
Ctrl+Z
[1]+  Stopped                 ls /tmp | less

In this case, use time on fg %1:

$ time ls /tmp | less
Ctrl+Z
[1]+  Stopped                 ls /tmp | less

real 0m0.723s
user 0m0.001s
sys 0m0.003s
manuel@coxorange ~
$ time fg
ls /tmp | less
Ctrl+Z
[1]+  Stopped                 ls /tmp | less

real 0m0.913s
user 0m0.000s
sys 0m0.000s

The Joys Of Floating Point Numbers

Sometimes, floating point numbers are the thing that futile hours of programming are made of. Whether they come as 32, 64 or any other precision you want, they can truly give you unnecessary and unexpected work if you do not use them correctly. The problem I stumbled over yesterday was the problem of rounding errors. Consider the following C snippet

double pi = 3.1415926535897932384626433832795;
double val = sqrt(pi) * sqrt(pi);

printf("pi  = %f\n", pi);
printf("val = %f\n", val);

which yields

pi  = 3.141593
val = 3.141593

Which is what we expected! val is the same as pi (the square is the inverse of the square root as we all know). However, the following C snippet shows the problem we run into:

if (val == pi) {
 printf ("pi == val\n");
} else {
 printf ("pi != val\n");
}

which yields

pi != val

So two apparently equal values are not equal any more! Where is the problem? It is in the precision of printf(), of course. We modify the first snippet so the printf() calls print the floating point values to more significant places

printf("pi  = %.16f\n", pi);
printf("val = %.16f\n", val);

and now we get

pi  = 3.1415926535897931
val = 3.1415926535897927

So how do we resolve this? Instead of comparing floating point values directly, we calculate their difference and make sure it is below a small value, for example 1e-9:

if (abs(val - pi) < 1e-9) {
 printf ("pi == val\n");
} else {
 printf ("pi != val\n");
}

which now gives us

pi == val

I guess most programmers are aware about the problems with floating point numbers and I have also known about the problem for a long time. What made me stumble, however, was that I trusted the printed value - which was inaccurate. As far as I know, there is no generic solution to the problem with floating point inaccuracies. You will get away with comparing whether the difference between two floating point values is smaller than a given value for comparing. In Ruby, you could hack the built in Float class with the following:

class Float
  def ==(value)
    self - value < 0.01
  end
end

This allows us to compare floating point values “fuzzily”:

>> Math.sqrt(2) ** 2 == 2.0
=> false
>> require 'floathack'
=> true
>> Math.sqrt(2) ** 2 == 2.0
=> true

However, I do not think that this is a good idea! Overwriting the == operator of the Float as above breaks its transitivity, i.e. we get the following (in-)equalities 1.99 == 2.00 == 2.01 but 1.99 != 2.01 Another idea would be only to compare the first n numbers after the point, e.g. consider 3.1415926535897931 to be 3.141 for n = 2. However, this does not help us if a floating point error gives us two values just next to a “boundary”, i.e. a result of 1.999 would not be considered correct if 2.001 was expected and we only cared about the result being “sufficiently close” to the expected value. So be careful when using floating point values are checking two of them for equality. Trouble will strike and most probably find some way to trick you into wasting time. An extensive, academic - and arguably dry - discussion of the implications of floating point arithmetics can be found in What Every Computer Scientist Should Know About Floating-Point Arithmetic, by David Goldberg.

SQLite gotcha

SQLite is great. No, really, I do mean it. If you ever need to work on structured data and editing it from the outside is a must, then SQLite is worth checking out and might be a superior choice to XML and will be a superior choice to your own proprietary format.

I cannot speak about performance - there are some outdated claims that SQLite is faster than postgres and mysql for the most common operations; but those benchmarks don't feature a single join, and that's where database implementation gets interesting and hard. I just cannot believe that SQLite stands up to any full scale DBMS.

I spent a few hours chasing down a bug in my own code after realising that I've been utterly stupid and put my parameters in the wrong order into my parameter list.

To boil it down, this is what happens in SQLite if I compare an integer field with a string in a WHERE part of a statement:

sqlite> CREATE TABLE my_favourite_numbers (number integer);
sqlite> SELECT * FROM my_favourite_numbers WHERE number = "foo";
sqlite>

You get no result. No error is thrown, like in Postgres:

# CREATE TABLE my_favourite_numbers (number integer);
# SELECT * FROM my_favourite_numbers WHERE number = 'bla';
ERROR: invalid input syntax for integer: "bla"

I know now what to look out for in the future.