Ausländische Investitionen

Syriza hat die Wahlen in Griechenland mit deutlichem Abstand gewonnen. Typisch für der Herren eigener Geist, in dem sich unsere heutige Zeit spiegelt, sorgen sich die Verfechter der marktkonformen Demokratie um die verschiedenen wirtschaftlichen Konsequenzen des Wahlergebnisses. Zum Beispiel: Sieht es für ausländische Investitionen in Griechenland jetzt düster aus? Ich möchte dies als Anlass für ein paar grundsätzliche Überlegungen nehmen.

Lauscht man den Sonntagsreden der Politiker, dann gehört die Steigerung der Attraktivität des eigenen Landes für ausländische Investoren zu den wichtigsten Tugenden einer Regierung. Zeit für die Frage nach des Kaisers neuen Kleidern: Warum eigentlich?

Die oberflächlichen Argumente sind einfach: Da kommt jemand, stellt eine Fabrik o.ä. hin, und das schafft Arbeitsplätze. So weit richtig, sofern man mal von den vielen Beispielen der Enttäuschung absieht, in denen ein ausländisches Unternehmen mit zeitlich beschränkten Steuergeschenken angelockt wird. Wenn diese Geschenke dann auslaufen sind alle furchtbar überrascht, wenn sich das Unternehmen wieder verabschiedet.

Aber selbst wenn die Investoren bleiben, so bleiben sie nur, wenn und weil sie einen dauerhaften Profit darin sehen. Aus der Perspektive des Auslands sieht das super aus: Man schickt eine einmalige Geldsumme, und erhält anschließend einen potentiell ewig anhaltenden Geldstrom, ohne, dass man dafür eine Gegenleistung bieten muss. Dies ist schließlich das Wesen allen Profits und aller Kapitalerträge.

Dementsprechend schlecht sieht der Deal für das Land aus, in dem die Investition getätigt wird: Klar, am Anfang kommt da eine Geldsumme herein, und klar, da werden Arbeitsplätze geschaffen. Aber gleichzeitig verpflichtet sich das Land dazu, potentiell auf ewig einen Geldstrom ins Ausland zu schicken, ohne dafür eine Gegenleistung zu erhalten.

Auf einmal sehen ausländische Investitionen überhaupt nicht mehr so toll aus.

Es wird noch schlimmer: Braucht man die ausländischen Investitionen überhaupt, um die Arbeitsplätze zu schaffen? In vielen Fällen nein. Das nötige Geld für den Aufbau der Fabrik o.ä. kann auch im Inland zum Beispiel durch den Finanzsektor bereitgestellt werden. Die gleiche Produktion kann oft gewährleistet werden, ohne dass danach langfristig Geld ins Ausland fließt. Schlimmstenfalls fließen die gleichen Ströme an reiche Inländer, bestenfalls in Pensionsfonds oder in einen Staatsfonds à la Norwegen oder Alaska.

Ein schönes Beispiel für all diese Überlegungen ist die Ausbeutung Rohstoff-reicher armer Länder. Dort kommen ausländische Investoren und bauen Minen. Sie entziehen dem Land die Bodenschätze, aber die Gewinne kassieren Ausländer. Dabei könnten diese Länder prinzipiell die gleichen Minen selbst bauen. Sicherlich müssten sie anfänglich notwendige Maschinen aus dem Ausland kaufen - aber die langfristigen Gewinne würden sie selbst einkassieren. Es wäre genau das umgekehrte Bild: eine einmalige Geldsumme wurde anfänglich ans Ausland gehen, damit ein langfristiger Geldstrom an Gewinnen aus dem Ausland aufgebaut wird. Das sieht kurzfristig teuer aus, ist aber langfristig der intelligentere Weg. Manche Regierungen verstehen das auch.

Das Beispiel der Maschinen, zu deren Bau das technische Know-How zumindest anfänglich nicht im Inland verfügbar ist, zeigt auch, dass ausländische Investitionen unter bestimmten Umständen ein akzeptabler Kompromiss sein können. Zum Beispiel eben dann, wenn das organisatorische Know-How im Inland nicht verfügbar ist, und dafür gesorgt wird, dass diese Know-How im Zuge der Investition langsam aufgebaut wird. Letzteres zu garantieren ist aber ein extrem schwieriges Spiel mit dem Feuer.

Die Idee, sich für ausländische Investitionen attraktiv machen zu wollen, ist fehlgeleitet. Das heißt nicht, dass man sich abschotten muss. Es heißt erst recht nicht, dass man auf internationalen Handel verzichten sollte - das ist eine andere Geschichte. Aber es heißt eben, dass es besser für ein Land ist, wenn es Investitionen aus sich selbst heraus generiert. Daran sollte sich Politik orientieren.

Use .kateconfig for setting per-project indentation and tab settings in Kate

Everybody who has ever worked with source code knows: proper indentation is vital to keeping your sanity.

However, people cannot seem to agree on whether to use tabs or spaces (and if the latter, how many spaces) to use for indentation. This is unfortunate, because the obviously correct way of doing it is with tabs. The only reason why many people believe spaces are superior is because

1. they want their indentation to look shorter than 8 fixed-width characters, the tab-width was not configurable back in the computing stone age, and people in general are incredibly conservative; and
2. they fundamentally misunderstand the difference between indentation and alignment, and generally overuse alignment.

Having contributed my part to the eternal flame war, even more important than using tabs for indentation is having a consistent style within each project.

So what is a user of the Kate editor (like myself, who uses it as part of KDevelop) to do when faced with working in different projects with different styles? I recently discovered a feature of Kate that is not documented widely enough: It will search the full hierarchy of parent directories for a file named .kateconfig. So just put a .kateconfig file in the root directory of each project you're working on, containing a single line like the following:

kate: space-indent off; indent-width 4; replace-tabs off; tab-width 4; indent-mode cstyle;

And voilà, you're good to go!

A subtle issue with C++11 unique_ptrs and move semantics

I'm moving the code of an internal tool to C++11 these days, and I stumbled upon a somewhat worrying subtle issue.

C++11 introduces rvalue references and move semantics, which allow the new smart pointer type std::unique_ptr that can be used inside std::vector. One might have some code like this:

std::vector<std::unique_ptr<Foo>> foos;

...

foos.push_back(std::unique_ptr<Foo>(new Foo(...)));

This works just fine, but it's a bit convoluted. Since C++11 introduced both rvalue references and variadic templates, std::vector has a method emplace_back, which looks more convenient. Let's use it:

std::vector<std::unique_ptr<Foo>> foos;

...

foos.emplace_back(new Foo(...));

This works and looks good. However, there is a subtle problem: What happens if the new object of type Foo is constructed, but then the emplace_back needs to allocate more memory, and that allocation fails?

The documentation that I can find states that nothing will happen in this case. Does "nothing" mean that we get a memory leak of one Foo object? Apparently it does - and at least a cursory look into the g++ 4.8 STL seems to confirm this suspicion. It appears that this is a potential memory leak that cannot really be avoided in good-looking code.

What to do about this? It would be nice if emplace_back guaranteed that the desired constructor is called no matter what happens. Unfortunately, such a guarantee would mean constructing the element explicitly in the cleanup path of a bad_alloc exception, which is prone to triggering yet another exception. Seems like this is quite the conundrum...

Finding duplicate elements in an array

This is a story about the power of randomness and universal hashing.

Suppose you are given an array of elements of some fixed type. How would you go about figuring out whether two elements of the array are equal?

At the time that I am writing this post, searching for its title leads almost universally to discussions about an interview-type puzzle question where you are given an array of size N that contains integers in the range from 0 to N-1. Indeed, clever solutions to this problem are proposed. Most of them amount to the same kind of trickery that radix sort employs to get a linear-time sorting algorithm. I hope the reader agrees that this is cute, but of limited use.

The most straightforward efficient solution to this problem that applies to general types is to sort the array using an arbitrary sorting function. Then a simple linear scan suffices to answer the question. The overall running time of this approach is O(N log N), and Misra and Gries showed in the 1980s that no comparison-based algorithm can be asymptotically faster.

Let me present their argument, which should feel familiar to anybody who has seen the proof that comparison-based sorting requires time Omega(n log n) (the result in the paper is more general).

Every deterministic algorithm for finding duplicates in an array using comparisons can be thought of as a family of infinitely many ternary decision trees, one tree for every array size. For any given array size, the algorithm starts at the root node of the tree for that size, comparing the elements at the indices given by that node. Depending on how they compare, the algorithm moves down in the tree. This process continues until a leaf node is reached which is labelled either YES (duplicate elements have been found) or NO (all elements are unique). Here is a decision tree for an array of size 3:



We will argue that every decision tree for arrays of size N must have more than N! leaves. Via Stirling's approximation, this implies that any such tree has depth at least Omega(N log N), which in turn implies the same bound for the worst-case running time. In fact, the average depth of leaves is Omega(N log N). This means that even a randomized algorithm, which we can think of as choosing one of many decision trees at random, has an expected worst-case running time of at least Omega(N log N).

Let us fix a decision tree T for arrays of size N. There are N! different permutations of size N. We can think of such a permutation as an array of size N filled with the integers from 1 to N without duplicates. Let P1 and P2 be two different such permutations/arrays, and define the array Q as

Q[i] := min(P1[i], P2[i])

The array Q contains duplicate entries. In fact, let m be the smallest number that appears at different positions in P1 and P2. Then m appears twice in Q.

As a consequence, the computation for Q must end in a YES-leaf of T, while P1 and P2 must lead to NO-leaves. What if P1 and P2 lead to the same NO-leaf N? Let V be a node on the path to N, and let us say that i and j are the array indices that are compared at the node V. Then the comparison P1[i] vs. P1[j] has the same result as the comparison P2[i] vs. P2[j]. But then, by the definition of Q, the comparison Q[i] vs. Q[j] also has the same result. This means that the computation for Q must also follow the same path and end in a NO-leaf! That is clearly a contradiction, and so we can conclude that the computations for P1 and P2 must end in different NO-leaves. Hence, the decision tree T must have at least N! NO-leaves, and this completes the proof.

So, to summarize up to this point: As long as we can only compare array elements, no algorithm can beat the running time of O(N log N) that a simple sort followed by a linear scan offers. However, this isn't the end of the story.

Suppose you have a universal family of hash functions for the type of elements in the array (and indeed, such families are not too difficult to construct). That is, suppose you can randomly choose a hash function h:U -> [m], with m within a constant factor of N, such that for different array elements A[i] and A[j] you know that the probability of a hash collision is low:

Pr[h(A[i]) = h(A[j])] <= 1/N

Note that if the guarantee is slightly weaker, e.g. a bound of 2/N on the probability of a collision, the following argument will still work with only minor modifications to the constants in the computations.

We will now follow a simple strategy: Build a hash table of the elements of A according to h. Since equal elements will be hashed into the same bucket, it is then sufficient to check for duplicate elements within each bucket by sorting and a linear scan, or by an even simpler quadratic check.

What is the running time of this approach? If b(i) is the number of array elements mapped into the i-th bucket, then even the running time of the simple quadratic check can be bounded by

sum(b(i)2, i=1..m),

which is exactly the number of hash collision pairs:

sum(b(i)2, i=1..m) = #{ (i,j) : h(A[i]) = h(A[j]) } = N + #{ (i,j) : i != j, h(A[i]) = h(A[j]) }

The expected cardinality of the last part is bounded by the number of pairs (i,j) with i != j times our bound on the probability that a pair results in a hash collision. This product is N-1. That is, the expected running time of the algorithm we have outlined is linear.

Observe that we must choose the hash function randomly for this approach to work. If we were to use a fixed, deterministic hash function, then an adversary could construct an array in which all elements hash to the same bucket (using the pigeonhole principle and assuming that the universe U of possible array elements is large enough). We would be back in the case where only comparisons are allowed, and hence a linear running time is impossible.

So we see that the combination of hashing and randomness, in the form of universal hashing, allows us to solve the original problem in a running time that is asymptotically better than what is achievable using deterministic algorithms.