The devil is in the details: assertions

I've been debugging my btree removal code for the last 2 days. Assertions (#include <assert.h>), together with suitable printf() debugging, have proven as an invaluable tool during the process.

The code is after the purely textual description of the BTree data structure in Knuth's volume 3. There he says that "removal is only slightly more complicated than insertion". That might (actually, is) so on a conceptual level. But, when translated into code: aroud 4x more code, around that much more time and a number of corner-cases.

I've run the code through valgrind and I have no errors. Wow! :)

Tags: TAOCP algorithms Knuth

Linux performance counters

Performance counter drivers under linux are an interesting affair. There's oprofile, perfctr and perfmon2. Neither does exactly what I need in combination with Xeon, but put together they'd be an excellent tool.

Now: I want to measure L1 cache misses on Xeon. oprofile can't do it out of the box (one has to program some extra registers that oprofile doesn't seem to know about), perfctr has very weak user-mode tools (basically, it's just a library), and perfmon2 doesn't seem to support Xeon. perfmon2 seems the best designed project, compiles cleanly and reports it's initialized, but trying to start any user-mode program just says that the processor isn't supported. The author of perfctr has himself said on a mailing list that he's giving up on perfctr development in favor of perfmon2.

Has anyone managed to get perfmon2 working on Xeon/P4 (not Pentium M)? And how?

Tags: linux performance xeon oprofile perfctr perfmon2

A neat trick

Recently I was reading Knuth's The Art of Computer Programming (vol. 3). The "uniform binary search" algorithm uses ceil(x/2) operation where x is an integer. A very short, branch-free way occured to me how to code this operation. The following code assumes x in %eax and finishes with the desired result in %eax

shrl $1, %eax
adc  $0, %eax

TAOCP assembler knuth

Airplane traveling

For my vacation I went to Croatia, taking Norwegian airlines from Oslo to Rijeka (and back). The flight from Oslo was more than half an hour late, and then the pilot had to wait extra 10 minutes because he missed the time-slot. And fritt setevalg is a bad idea: it takes people to board the plane much longer than when the seat is assigned upon check-in. Miraculously, the flight from Rijeka was in time and the plane arrived even a bit earlier :)

Disembarking from the plane is another story. People are simply too slow. Somewhere I've heard that the plane layout must be such so that it's possible to evacuate it in 1 minute (60 seconds). This seems impossible to me :)

During the 2:30 flight the following question came to my mind: does the long-distance flight route take Earth's rotation into account?

Tags: norwegian airplanes travel

Vacation

Finally, 2 weeks of vacation! I won't be posting much I guess.

GCC obscenity

Today, while debugging some of my code, I accidentaly noticed that in certain cases gcc "optimizes" printf() calls into calls to puts(). This is plainly unacceptable for at least two reasons:

1. printf() might have side-effects that puts() doesn't (f.ex. see this bug report).


2. It makes LD_PRELOAD interception of certain functions ineffective.

This "optimization" takes place even when I compile my program with the -ansi switch. I haven't been able to find a switch to turn off this "optimization". In addition, the generated code in this case is plain wrong. No optimization should change the semantics of the program (which it does in this case).

C has always been the language in the lines of do what I say. How many other such surprises are hidden in gcc?

What they have done with this "optimization" is on the level with (if not worse than) MS's adaptation of C++ for CIL. Strangely, so many people bark at MS for their "wrong-doings", but the bug report cited above never even got a response. Well, at least I'm going to say this: shame on you gcc developers!

Tags: gcc