Qt Quick hates me

I haven’t blogged since a while, because I do not do much KDE hacking lately, but today I’ve got around to playing with QML again.

The goal was to build something like a breadcrumb navigation widget, where the current directory is indicated by its name being written in a larger font. Here’s what I arrived at after a few minutes:

import QtQuick 1.1

Rectangle {
    width: 800
    height: 100
    color: "black"

    Row {
        anchors.horizontalCenter: parent.horizontalCenter
        anchors.top: parent.top
        spacing: 10

        Repeater {
            id: repeater
            property int currentIndex: 4
            model: ["/home", "/username", "/some", "/pseudo", "/path"]

            Text {
                text: modelData
                font.pixelSize: index == repeater.currentIndex ? 40 : 20
                color: "white"
            }
        }
    }
}

Close enough. Just adjust that alignment:

...
Text {
    ...
    height: 60
    verticalAlignment: Text.AlignBottom
}
...

Gah! Can you see it? The baselines are misaligned. Usually, you lay out text such that all letters “sit” on an even line (the baseline).

The documentation does not mention any type baseline alignment in a Row element (or any type of vertical alignment in a Row element, for that matter).

I then tried to hack around this problem by dropping the Row element and laying out the Text elements manually, but the elements in the repeater won’t anchor to each other. That’s probably a problem with the elements not being fully initialized when the anchor property is evaluated, but at this point I give up.

This has been my second experience with Quick. When I tried it for the first time, my goal was a Quick version of the Planarity game. I got stuck when I noticed that Qt Quick 1 does not have any kind of line or ellipse primitive (only rectangles and images). Really?!?

So, while I understand very well and appreciate the idea behind Qt Quick, I have come to the conclusion that Qt Quick hates me. Or I have a talent of hitting a roadblock within ten minutes, regardless of the general direction.

P. S. Turns out the WordPress WYSIWYG editor hates me, too. (Well, either me or the combination of <pre> and images.)

Bug of the day: How ConfigParser ruined my calculations

For my thesis, I have implemented a series of numerical applications. The core application (written in C++) uses simple INI-like configuration files for reading system parameters. For example:


[system]
name=example2
r1=1.0
r2=1.5
V1=-0.05
V2=0.1
[...]


Nothing exciting there, reading this is a breeze with QSettings. Now I needed to do some symbolic calculations, for which I chose Python and the excellent SymPy module. To read the system configuration, I chose the standard ConfigParser module.


parser = ConfigParser.RawConfigParser()
parser.read("scatttd.conf")
sysType = parser.get("system", "name")
# read system parameters
sysParams = dict()
for key, value in parser.items("system"):
    if value != "name":
        sysParams[key] = float(value)


That reads the “system/name” key, and puts all other keys (which are assumed to be floats) into a dictionary, so the system-specific code does not need to deal with the ConfigParser object.


r1, r2 = params.get("r1", 1.0), params.get("r2", 1.0)
V1, V2 = params.get("V1", -0.1), params.get("V2", +0.1)


This code gets the parameters in the system-specific code. Nothing exciting here. Except, stuff doesn’t work. The results of the following calculations suddenly don’t match my expectations (or the predictions made by my other programs).

Since the code after the snippet above is about 30 lines of SymPy magic (accumulating expressions that print dozens of lines onto my terminal), I suspected that some error occurred there. After about two days of searching for the problem there, and calculating everything by hand, something occurred to me when I looked at the debug output:


DEBUG V1 = -0.1


Didn’t the configuration file say “V1=-0.05”? Let’s have a look at the parameter dict:


{'v1': -0.05, 'v2': 0.1, 'r1': 1.0, 'r2': 1.5}


See the problem? “v1” has a lower-case “v”, so params.get("V1", -0.1) fails and returns the default value (-0.1). One glimpse at the documentation says that


parser.optionxform = str


solves the problem. Gah!

Lost for words

commit 740673c11aee9762987e3a205443ce1dec11aee8
Author: Stefan Majewsky <majewsky@gmx.net>
Date:   Sat Nov 5 00:11:37 2011 +0100

    lolwut?

diff --git a/tagaro/interface/board.cpp b/tagaro/interface/board.cpp
index 199c007..17dbdfc 100644
--- a/tagaro/interface/board.cpp
+++ b/tagaro/interface/board.cpp
@@ -42,7 +42,6 @@ Tagaro::Board::~Board()
 
 Tagaro::Board::Private::~Private()
 {
-       QList<Tagaro::SpriteObjectItem*> m_items;
        for(QList<Tagaro::SpriteObjectItem*>::const_iterator a = m_items.constBegin(); a != m_items.constEnd(); ++a)
                (*a)->d->unsetBoard();
 }

Case study: Porting and modularizing an in-house Python application

Is it just a feeling, or has the number of technical posts decreased on the Planet? I definitely need to change that! (Update: The post got quite long, so I’ve shortened the syndicated version.)

These days, I’m usually working on my Diplomarbeit at the Institute of Theoretical Physics at the Technical University here in Dresden. (A Diplomarbeit is about comparable to a master’s thesis, though preparation time is one year since there was no bachelor’s thesis before it.) Our working group has an in-house application for inspecting iterated functions, which is quite intuitively called Iterator. Like many scientific applications, it has on one hand a very sharp functional objective, but contains tons of different tools and plugins.

As a part-time project besides my usual work, I’m working on a Qt port of the Iterator, which is currently based on wxWidgets. Of course, a port offers the opportunity to refactor badly engineered parts of the application. It clearly shows that all involved developers are first and foremost physicists which have not received any formal training in software design. Many antipatterns can be observed in the code. The most interesting is the existence of a god class called IteratorApp.

Implicit cast quirks

I thought I let you know why I just had to throw away three days worth of computation data.

double importantPrefactor(bool freeEvolution);

void multistep(bool freeEvolution, /* ... */)
{
    /* ... */
    const double pre = importantPrefactor(free);
    /* ... */
}

Yes, I used the wrong identifier inside the multistep function. Still it compiles and runs without error (except for the garbage data that comes out), because there’s a goddamn implicit cast from void(*)(void*) to bool. If you don’t believe this, try this:

qDebug() << "Is there a goddamn cast?" << ((bool) ::free);

Of course the conversion gives true because the function pointer is not null. Argh!

Optimization tricks: Fast sqrt(x^2 + y^2)

[Before I get to the boring (hah!) numerics stuff, some news: In order to test KDE Games on a touchscreen, and because I’ve wanted a tablet for a long time now, and because I want a 3G device, I’ve now ordered a WeTab 2. More news on this coming up soon when I have it in my hands.]

I’ve been optimizing my favorite jigsaw puzzle game Palapeli lately. Today, I looked at the bevelmap generation algorithm which renders the nice three-dimensional shadows atop the jigsaw pieces. There are a lot of norm computations in there, i.e. sqrt(x^2+y^2). All bells are ringing: There must be a way to optimize this.

Now nearly everyone who has to do with numerics and programming probably knows about the fast inverse square root which approximates 1/sqrt(x) very efficiently and sufficiently precise (about 1% maximum error). Using the inverse of this fast inverse square root does not really give an improvement, though. After all, the formula 1/InvSqrt(x*x+y*y) contains at least four floating-point operation plus everything that happens in InvSqrt.

This approach is especially inefficient because, in my special case, x and y are integers, and the result is also needed as an integer. Looking around the interwebs, I’ve found this lovely page on square root calculation, which also has a special algorithm for norms.

It all starts with two approximations to sqrt(x^2+y^2). The first one is max(abs(x), abs(y)), the second one is 1/sqrt(2)*(abs(x) + abs(y)). We need both because they are good for different values of x and y. To understand this, consider the unit circles of these approximations, that is: the set of x/y points where the approximation is 1. (You will probably make a sketch as you follow the discussion. I would have done one if it wasn’t so late already.) The unit circle for the first approximation is an upright square, while the second approximation’s unit circle is diamond-shaped (i.e. turned around by 45° compared to the first one).

An approximation is good when the unit circle comes nearby or touches the actual unit circle. For the first approximation, this happens when either x or y vanishes. The second approximation, on the other hand, is good when x and y are approximately equal. Now one can show that, at these conditions, the better approximation is always bigger than the other one. This means that we can define a third approximation by taking the maximum of both approximations. The unit circle for this approximation is a regular octagon, whose inscribed circle is the actual unit circle.

The approximation is thus always too big, except for the eight touching points of octagon and real unit circle, where approximation and exact result are identical. However, one can find a factor z such that the octagon, scaled by 1/z, is inside the circle. Scaling the approximation by (1+1/z)/2 thus distributes the approximational error to both the negative and positive side. Taking all these considerations into account, I’ve arrived at the following implementation:

template<typename T> struct fastnorm_helper { typedef T fp; };
template<> struct fastnorm_helper<int> { typedef qreal fp; };

//Approximates sqrt(x^2 + y^2) with a maximum error of 4%.
//Speedup on my machine is 30% for unoptimized and up to 50% for optimized builds.
template<typename T> inline T fastnorm(T x, T y)
{
    //need absolute values for distance measurement
    x = qAbs<T>(x); y = qAbs<T>(y);
    //There are two simple approximations to sqrt(x^2 + y^2):
    //  max(x, y) -> good for x >> y or x << y          (square-shaped unit circle)
    //  1/sqrt(2) * (x + y) -> good for x = y (approx.) (diamond-shaped unit circle)
    //The worse approximation is always bigger. By taking the maximum of both,
    //we get an octagon-shaped upper approximation of the unit circle. The
    //approximation can be refined by a prefactor (called a) below.
    typedef typename fastnorm_helper<T>::fp fp;
    static const fp a = (1 + sqrt(4 - 2 * qSqrt(2))) / 2;
    static const fp b = qSqrt(0.5);
    const T metricOne = qMax<T>(x, y);
    const T metricTwo = b * (x + y);
    return a * qMax(metricOne, metricTwo);
    //idea for this function from http://www.azillionmonkeys.com/qed/sqroot.html
    //(though the equations there have some errors at the time of this writing)
}

[License: I grant any entity the right to use the above code snippet for any purpose, without any conditions, unless such conditions are required by law. (This is the best approximation to placing the code in the public domain, which is not possible in my jurisdiction.)]

I have tested this function successfully on random input with T = double, float, int32_t. For integer types, this function needs only two floating-point multiplications, and thus runs much much faster than the trivial implementation and the InvSqrt-based solution. So please take this as my contribution towards Green IT, and reduce the time your computer spends calculating norms.

P.S. The extension of the above function for three-dimensional coordinates remains as an exercise to the reader. The only hurdle is to calculate the new prefactor z.

Update: As correctly pointed out by the commenters, if all you want is to compare the norm to some radius, e.g. sqrt(x*x + y*y) > r*r, the easiest solution is to avoid the square root and test for x*x + y*y > r*r instead.

“QDeclarativeComponent: Component is not ready”

I just spent over an hour shouting at my editor, and I want to save you from that, so I’m telling ya: If you call QDeclarativeComponent::create and get the error message above, this is (unlike stated elsewhere) not an indication for a specific type of error.

In fact, the words “Component is not ready” are wrong in this case and should be replaced by “I stopped loading your QML because some errors have occurred. If you were in qmlviewer right now, it would take care of printing these errors, but you aren’t, so you need to do qDebug() << component.errors() yourself, but I won't tell ya."

Programming in a finite world – The parable of limited resources

I am currently holding a tutorial as part of a Programming 101 course for physics students. The primary objective of the course is to gain the ability to analyze experimental data and perform numerical calculations, and we have only three lessons for the actual C stuff. I’m summarizing the lectures in the tutorials, and try to boil down everything as much as possible (e.g. the only datatypes I introduce are int and double), because it’s the first contact to programming for most freshmen.

They’re mostly doing well, but some are having trouble because of their mathematical background. They feel bad about stuff like

b = b+1;

because they consider this a truth statement instead of an assignment. How could one explain the difference in a didactically constructive manner? I’ll try this:

Mathematics is the same as the programming…

The common ground of mathematics and programming is that we’re attaching names to things and studying the behavior of these things. For example, if I write in C:

double f(double x) { return x * x; }

Then I can refer to the function that doubles its input by the name of “f”. The equal procedure in mathematics is to write down:

f: ℝ → ℝ, x ↦ x²

Read: f is a function mapping from real numbers to real numbers, which maps x to x².) Actually, the mathematical function f has already existed for an infinite time before I came along and attached a name to it. It existed inside the set of all ℝ → ℝ functions, and more generally in the set of all functions, and in the set of all objects. The function x ↦ x³ also exists, regardless of whether I give it a name or not.

…yet the previous heading was a lie

After the main similarity of mathematics and programming comes the main difference: the limited resources of a computer. No matter how large my memory is, it will never be sufficiently large to store π, while π can be defined in finite time using mathematical constructions. These constraints change how everything works: We cannot have everything available all the time, we need to create and give names to what we need when we need it. This applies to everything from variable declarations, functions to libraries.

The next difference is that the type of named objects changes. Mathematicians give names to mathematical objects which operate only inside their theory, while a programmer operates on actual hardware, and gives names to existing computer resources. While both languages, C and mathematics, allow the statement x = 5 to be made, the statement has a different meaning in both languages: The mathematical expression x = 5 attaches the name x to the mathematical object “real number 5”, which is the same as the mathematical object “integer number 5”. The C statement x = 5, on the other hand, is only valid when a variable x exists, because x is not the name of the mathematical object “number 5”, but the name of the physical resource “memory block no. 23421337 (or whatever)”, to which the system has granted you access.

While a mathematician may define a function f which works on all sets which define a multiplication operation, a programmer has to state explicitly the datatype of each function. (All Pythonistas out there please remember that this is about C programming.) In his world, f is not the name of a function that squares everything to which it is applied, but it is the name of a chunk of code that calculates the square of an integer number (for instance). If he also wants a function that handles double-precision numbers, he has to take care of implementing that function, too.

Mathematics is timeless

The limited-resource theme also explains immediately how the time axis comes into play, i. e. the order of execution. Mathematical objects exist as results of fully logical derivations, which are by their nature independent from their context and therefore from time. If there exists a root of the Riemann zeta function with non-half real part, its existence is not dependent on our knowledge of its exact value or even our knowledge of its existence.

Logical derivations are so versatile that they bring into existence infinitely many mathematical objects. So many that we cannot count them. The limited resources of computer technology do not allow us to replicate this structure in programming. And we do not need to: Those objects which are not relevant for our computations need not be created. This generates the time axis: Objects are brought to life when we need them.

For example, let the computer know about a double variable a and the function f as defined above. Now it is given the C expression x = f(5). At this point in time, the computer decides that the object f(5) (precisely: the physical representation of the mathematical object which is equal to f(5)) has to come to life inside the memory block represented by the name a. To achieve this, it has to call the function f. If you like, you can imagine that some chunk of memory is allocated, and the name x is attached to the first memory block, which is filled with 5. Also, the name “return value” is attached to the second memory block, and the function is instructed that it shall put the result of its computation in there.
return x * x;
The function starts by retrieving the value of 5 from the memory block called a:
return 5 * 5;
It calculates the result of the multiplication:
return 25;
and finishes by writing 25 into the memory block called “return value”.

By the way, this thought experiment also explains variable scopes: The variable x is only available inside the function f, of which it is a formal argument, because the variable is just the name of a memory block. The memory block might be reused for some different calculation after the function has been evaluated, so it is not safe to allow one to refer to the memory cell by the old name. If you like, think of the memory cell as an appartement: f pays the bills for x, so when f dies, x is forced to move out, and a new renter may move into the memory cell at any time.

Beyond single variables and simple expressions

After you know how to explain variables and functions, all other features of the C language can either be derived similarly, or are (from this perspective) mere convenience features. For example, control structures express nonlinear and conditional time flows (where the time is defined as the execution time, i.e. the time when the computer is occupied with evaluating statements). Arrays are a way to give a name to multiple similar memory blocks at once. And so on.

If you found this parable helpful to get started with C programming, feel free to leave a note below.

P.S. Be sure to take a look at the comments to this article, for some nice additions, and other parables that can be useful for beginners.

Tip of the day: Auto-generate forward includes

It’s common nowadays that libraries install forward includes (also known as “pretty headers”) which have the same name as the class declared in it. For example, to get the QPushButton, one includes <QPushButton> or <QtGui/QPushButton> instead of <qpushbutton.h>.

For a newer project of mine, I wrote a script that generates these forward includes automatically, and I thought that it might be worth sharing. The script is quite simple because the structure of the source tree is in my case identical to what gets installed below /usr/include. If you install your headers in a more complicated way, you will probably need to expand the script.


#!/bin/sh
# This script finds all headers (except for private headers) in the known
# library source trees, looks for exported classes inside there, and generates
# forward includes for all these classes.

# configuration
EXPORT_MACRO=TAGARO_EXPORT # the macro which denotes exported classes
HEADER_DIR=tagaro # the directory which contains the headers of your lib
INCLUDE_DIR=includes/Tagaro # the directory which shall be filled with the pretty headers
INCLUDE_INSTALL_DIR='${INCLUDE_INSTALL_DIR}/Tagaro' # the directory into which CMake shall install the pretty headers
MANUAL_HEADERS='Settings' # specify manually created headers in this list (separated by spaces)

if [ ! -f $(basename $0) ]; then
    echo "Call this script only from the directory which contains it." >&2
    exit 1
fi

(
    echo "#NOTE: Use the $0 script to update this file."
    echo 'install(FILES'
    (
        find $HEADER_DIR/ -name \*.h -a \! -name \*_p.h | while read HEADERFILE; do
            grep "class $EXPORT_MACRO" $HEADERFILE | sed "s/^.*$EXPORT_MACRO \\([^ ]*\\).*$/\\1/" | while read CLASSNAME; do
                echo '#include ' > $INCLUDE_DIR/$CLASSNAME
                echo -en "\t"; echo "$CLASSNAME"
            done
        done
        for MANUAL_HEADER in $MANUAL_HEADERS; do
            if [ -n $MANUAL_HEADER ]; then
                echo -en "\t"; echo $MANUAL_HEADER
            fi
        done
    ) | sort
    echo "DESTINATION $INCLUDE_INSTALL_DIR COMPONENT Devel)"
) > $INCLUDE_DIR/CMakeLists.txt


Tip of the day: CMake and Doxygen

With Doxygen, we have at hand a solid and widely-known open-source solution for the generation of API documentation. However, it is quite inconvenient when one has to use yet another tool as part of the daily hacking. So today, I looked into how I can integrate the generation of API documentation with my CMake workflow. Because I found no easy how-to on the web, I’m putting up one now.

The base situation is like this: In your source tree is somewhere a Doxyfile, which you previously used to generate documentation by running doxygen in this directory. Rename this file to “Doxyfile.in” and change the line that looks like

INPUT = ../src/

into

INPUT = @CMAKE_CURRENT_SOURCE_DIR@/../src/

(Of course, substitute “../src/” by what’s actually in there.) Now add the following to the CMakeLists.txt of this directory:

# add a target to generate API documentation with Doxygen
find_package(Doxygen)
if(DOXYGEN_FOUND)
configure_file(${CMAKE_CURRENT_SOURCE_DIR}/Doxyfile.in ${CMAKE_CURRENT_BINARY_DIR}/Doxyfile @ONLY)
add_custom_target(doc
${DOXYGEN_EXECUTABLE} ${CMAKE_CURRENT_BINARY_DIR}/Doxyfile
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
COMMENT "Generating API documentation with Doxygen" VERBATIM
)
endif(DOXYGEN_FOUND)

After another CMake run, you can type “make doc” to have CMake run Doxygen. To keep the source tree clean in out-of-source builds, the documentation is generated in the corresponding build directory. If that is too well hidden for you, exchange “CMAKE_CURRENT_SOURCE_DIR” for “CMAKE_CURRENT_BINARY_DIR” in the line starting with “WORKING_DIRECTORY”. The documentation will then be generated in the source directory again.

Installing the generated documentation is left as an exercise to the reader.

Update: I forgot to add one thing. With the above code, the target will not be included in the “all” target. That is, it will not be generated when you type “make”. You have to say “make doc” explicitly. If you want to include it in “make”, add the word “ALL” after “add_custom_target(doc”.