Donnerstag, Mai 15, 2014

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...

Freitag, April 25, 2014

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.

Sonntag, August 25, 2013

Leserbrief zu "Haushälterträume" in der FAZ

In der FAZ vom Samstag las ich auf der Titelseite einen Kommentar von Heike Göbel zu Überschüssen im deutschen Regierungssektor. Wer den Kommentar sieht und mich kennt, der kann sich denken, dass ich mich beim Lesen sehr geärgert habe. (Wenn man es sich recht überlegt: Wer die deutschen Medien kennt kann meine Reaktion erahnen, ohne den Kommentar gelesen zu haben, so tief sind die Abgründe...)

Wer mich noch nicht so kennt, aber wirtschaftspolitisch interessiert ist, kann z.B. hier und hier mit dem Durchklicken und Lesen anfangen.

Wie dem auch sei: Ich habe einen kurzen Leserbrief an die FAZ geschickt, den ich der Vollständigkeit halber auch hier veröffentliche:
In der FAZ vom 23. August kommentiert Heike Göbel die Meldung über Haushaltsüberschüsse im deutschen Regierungssektor ("Haushälterträume", Seite 1). Spätestens seit den Arbeiten von Wolfgang Stützel zur Saldenmechanik ist bekannt, dass Überschüsse und Defizite eines Wirtschaftssektors nur im Kontext der Ergebnisse der anderen Sektoren sinnvoll bewertet werden können.

Da die Einnahmen des Einen stets die Ausgaben eines Anderen sein müssen, ist ein Haushaltsüberschuss nur dann möglich, wenn mindestens ein anderer Sektor ein Defizit erwirtschaftet. Dies ist eine einfache Angelegenheit von Addition und Subtraktion.

In unserer heutigen Situation wird der Haushaltsüberschuss des deutschen Regierungssektors rein arithmetisch durch Defizite in anderen Euroländern ermöglicht. Die Mathematik spricht eine klare Sprache: Wer die Haushaltsüberschüsse lobt, der darf die Defizite anderswo nicht unreflektiert kritisieren, denn ohne sie könnten die Überschüsse nicht existieren. Beides geht Hand in Hand.

Wir brauchen in unserem Land eine ehrliche Diskussion darüber. Wer - wie viele heutzutage mit einer Scheuklappen-artigen Fixierung auf Regierungshaushalte - an einer Stelle unbedingt Überschüsse sehen will, der muss auch erklären, wo er die dafür notwendigen Defizite haben will. Will er die Defizite bei sich selbst, vielleicht in Form einer Vermögenssteuer? Will er weitere Defizite in Südeuropa? Oder einigen wir uns angesichts der Arithmetik darauf, dass das mit den Regierungsüberschüssen doch eine dumme Idee war? Dies ist keine einfache Diskussion. Aber solange sie nicht stattfindet ist es wenig überraschend, dass der Euroraum global gesehen das klare Schlusslicht in der Bewältigung der Spätfolgen der Finanzkrise bleibt.

Donnerstag, Juli 25, 2013

"The Money is Stuck in the Banks"

In der wirtschafts- und finanzpolitischen Diskussion hört und liest man regelmäßig Phrasen wie "Die Banken parken ihr Geld bei der Zentralbank" oder "Das Geld bleibt in den Banken". Exemplarisch zum Beispiel hier:
Let's face it: inflation levels in Europe and Germany are astonishingly low, given the enormous amounts of newly printed money that was released by the ECB. To my mind this has several reasons:

1. The money is stuck in the banks. Which is good for Germany (little headline inflation) but bad for the periphery (credit crunch).
Diese Formulierungen sind allesamt Zeugen von unsauberem Denken. Denn von "Geld parken" spricht nur, wer eine andere Verwendung des Geldes für möglich hält. In der Diskussion der Geldbasis, also der Menge allen Zentralbankgeldes, gibt es aber keine andere Verwendung. Zentralbankgeld ist immer bei der Zentralbank geparkt solange es existiert.

Das hört sich erst einmal merkwürdig an. Man muss genauer untersuchen, was mit Zentralbankgeld eigentlich geschieht. Einen Einstieg bieten diese Artikel, und hier noch einer mit Bildern.

Jede Bank hat ein Konto bei der Zentralbank. Das Geld auf diesem Konto nennt man Zentralbankgeld, und es wird von den Banken für den Zahlungsausgleich verwendet. Es gibt genau drei Dinge, die eine Bank mit Zentralbankgeld tun kann:
  1. Sie kann das Zentralbankgeld auf das Zentralbankkonto einer anderen Bank überweisen.
  2. Sie kann mit dem Zentralbankgeld von der Zentralbank Bargeld kaufen.
  3. Sie kann mit dem Zentralbankgeld Kredite an die Zentralbank zurückzahlen oder Wertpapiere von der Zentralbank kaufen.
Bei den letzten beiden Punkten geht das Zentralbankgeld nirgendwo hin, sondern verschwindet einfach.[1] Die Schlussfolgerung ist: Zentralbankgeld ist immer auf einem Zentralbankkonto. Angesichts dessen ist es unsinnig davon zu sprechen, dass die Banken das Geld bei der Zentralbank parken - es kann nämlich nirgendwo anders sein!

Manchmal reden die Mitglieder des Kommentariats auch davon, dass "das Geld in den Banken bleibt", und meinen damit, dass die Banken wenig neue Kredite vergeben. Wenn sie das so meinen, dann sollten sie das auch so sagen: Die Banken vergeben wenig Kredite. Denn die andere Formulierung zeugt von unsauberem Denken. Sie basiert auf dem Irrglauben, die Banken würden das Geld ihrer Kunden verleihen.

Ein einfaches Gedankenexperiment zeigt, dass dem nicht so ist. Denn wenn es die Wahrheit wäre, dann wären wir mit der folgenden Szene vertraut:
Herr Kunde
Frau Bankière

Eine Bankfiliale. Frau Bankière sitzt an einem gut aufgeräumten, überdimensionierten Schreibtisch und telefoniert. Im Hintergrund sind weitere Pinguine zu sehen. Herr Kunde betritt die Bank und versucht, am Automaten im Vorraum Geld abzuheben. Dies scheint zu misslingen, worauf er den Hauptraum mit suchendem Blick betritt.

Frau Bankière: Grüß Gott, wie kann ich Ihnen helfen?
Herr Kunde: Ihr Geldautomat behauptet, mein Kontostand sei zu niedrig. Das kann eigentlich nicht sein!
Frau Bankière: Einen Moment. Dürfte ich Ihre ec-Karte sehen?

(Er überreicht die Karte, worauf sie etwas auf ihrem Computer eingibt.)

Frau Bankière: Doch, hier steht es. Auf Ihrem Konto sind gerade noch 17 Euro und 52 Cents.
Herr Kunde: Aber vorgestern waren da noch über 500 Euro drauf!
Frau Bankière: Das ist richtig, aber die haben wir inzwischen verliehen.
An der Absurdität dieser Szene erkennt man, dass Banken das Geld ihrer Kunden nicht verleihen.

Die Wahrheit ist: Wenn Banken Kredite vergeben, dann erzeugen sie neues Geld. Mit dem Geld, das bereits auf Konten von Kunden der Bank existiert, hat das nichts zu tun. Damit ist die Phrase vom Geld, das "in den Banken bleibt" genauso unsinnig wie die Phrase vom Geld, das "bei der Zentralbank geparkt ist".

Was lernen wir daraus? Die wenigsten Menschen scheinen wirklich zu verstehen, wie das Geldwesen funktioniert. Das gilt sogar für diejenigen, die es eigentlich wissen müssten -- zum Beispiel, weil sie Wirtschafts- und Finanzjournalisten sind. Es wird versucht, dieses Unwissen durch unpräzise und irreführende Sprache zu verstecken. Das wäre an sich auch gar nicht so tragisch, wenn nicht wichtige wirtschaftspolitische Entscheidungen auf diesem unsoliden Fundament aufgebaut würden.

Wie man daran etwas ändern kann? Solange mir nichts Besseres einfällt hoffe ich, dass steter Tropfen den Stein wirklich höhlt.

[1] Wenn man diese Aussage das erste Mal liest, sollte man darüber stolpern. Ich lege dem geneigten Leser nahe, sich diese Tatsache zu verinnerlichen: Wenn die Zentralbank Zentralbankgeld einnimmt, dann verschwindet es einfach. Das ist übrigens bei Banken konzeptionell genauso, wenn sie Kontoführungsgebühren einziehen: Wo vorher noch eine Verbindlichkeit der Bank in Form von Buchgeld war, ist jetzt auf einmal ein Gewinn der Bank. Der steht als solcher in der gedachten Bilanz auch erst einmal auf der Passiv-Seite, ist aber kein Geld.