Sort 1TB file

hustbaer

@volkard
Ja, 100% Linear-Lesen Geschwindigkeit wird man nicht bekommen. (Ich hab' mich auch wiedermal verschätzt mit 1 MB Puffern ist man sogar noch deutlich davon entfernt - siehe unten.)

Aber wenn man den Grossteil der 2 GB RAM die man hat zum Puffern der 500~1000 Input-Streams verwendet, dann wird's schon gehen. 1 MB pro Input-Stream sollten damit locker drin sein. Wenn man die Grenzen gut auslotet (also wie viel RAM man wirklich verwenden kann, bevor das OS anfängt zu pagen) vermutlich sogar etwas mehr.

Laut h2benchw liegen Desktop HDDs so im Bereich 12~20ms für das Lesen eines Sektors an einer zufälligen Position - nehmen wir mal 16ms an (Mittelfeld).
Danach geht's mit Linear-Lesen Geschwindigkeit weiter - im Moment so ca. 130~150 MS/s -- nehmen wir 140 MB/s an.
D.h. pro Megabyte ca. 7ms.
In Summe für 1 MB Lesen an einer zufälligen Position dann 16+7=23ms.
D.h. wir bekommen auf der HDD immer noch ~43 MB/s hin.
Also ca. 1/3 von der Linear-Lesen Geschwindigkeit.

Die Zwischenpuffer für das Mergen von je zwei Streams zu einem kann man viel kleiner machen, da ein "Seek" im RAM ja kaum weh tut. 64 KB sollten da locker reichen, d.h. dafür geht kaum RAM drauf (insgesamt weniger als 100 MB).

Den Output-Puffer können wir grösser machen, von dem brauchen wir ja nur einen. 100 MB sollte man sich dafür leisten können. Ich nehme dafür jetzt einfach mal 100 MB/s für's Schreiben an (wird real eher mehr sein), also 10ms pro Megabyte.

D.h. wir brauchen für den Merge pro Megabyte insgesamt 23ms zum Lesen und 10ms zum Schreiben, also in Summe 33ms.

Wenn wir mehrere Durchgänge machen, so dass wir immer volle Speed bekommen, brauchen wir pro Megabyte pro Durchgang idealerweise 7 Lesen + 7 Schreiben=14ms.

=> Wenn wir mit zwei Durchgängen auskommen, dann sind wir mit 28 statt 33 ms knapp schneller.
Wenn wir mehr als zwei Durchgänge brauchen gewinnt aber schon die "alles in einem" Variante (deutlich). Und mit ner SSD sowieso.

Verkürzend zusammengefasst: Ich habe mit einer 32GB großen Daten gemessen. Auf dein Bauchgefühl re iops mag ich mich nicht verlassen. Auf mein Bauchgefühl sollte ich mich auch nicht verlassen. Die 250 MB/s kamen aus dem Link im Text. Deine SSD kann ich nicht nachmessen; wenn du selbst nachmessen willst, wieviel Random-I/O sie hinkriegt, gegen harte Fakten werde ich nicht argumentieren. Andernfalls muss ich das selbst machen, was aber dauert, bis ich eine Maschine mit SSD in die Finger kriege. Bulk-Merge wäre keine gute Idee, weil das quadratisch skaliert -- führt zu weniger I/O, dafür zu mehr Extrarechenaufwand, als das I/O gekostet hätte. Darum ist Mergesort auch nirgends mit Bulk-Merge spezifiziert. Ich mag mich manchmal verschätzen, aber wenn du ernsthaft glaubst, dass ich absichtlich schlechte Implementationen einer Methode aussuche, um damit ergebnisverfälschende Vergleiche anzustellen, dann brauchen wir nicht mehr miteinander zu diskutieren. Im konkreten Fall solltest du es einfach mal ausprobieren; nach meinen Hochrechnungen würde das Mergen im RAM auf die Art nicht eine halbe Stunde, sondern auf der gleichen Maschine grob anderthalb Tage dauern.

Was Hashmaps angeht, ich finde per Suchmaschine nichts, was deinen Standpunkt erhärtet. Hast du eine Quelle für mich? Meine eigene Messung:

#include <ctime>
#include <iostream>
#include <map>
#include <unordered_map>
#include <random>

void measure_tree() {
  int tsum = 0;
  std::map<int, int> treemap;
  std::mt19937 rng;

  std::clock_t beg = std::clock();

  for(int i = 0; i < N; ++i) {
    ++treemap[rng()];
  }

  for(auto &e : treemap) {
    tsum += e.second;
  }

  std::clock_t end = std::clock();

  std::cout << tsum << ", " << static_cast<double>(end - beg) / CLOCKS_PER_SEC << '\n';
}

void measure_hash() {
  int hsum = 0;
  std::unordered_map<int, int> hashmap;
  std::mt19937 rng;

  hashmap.max_load_factor(0.8);
  hashmap.reserve(N / 0.8 + 1);

  std::clock_t beg = std::clock();

  for(int i = 0; i < N; ++i) {
    ++hashmap[rng()];
  }

  for(auto &e : hashmap) {
    hsum += e.second;
  }

  std::clock_t end = std::clock();

  std::cout << hsum << ", " << static_cast<double>(end - beg) / CLOCKS_PER_SEC << '\n';
}

int main() {
  measure_hash();
  measure_tree();
}

ergibt

$ for i in 1000000 10000000 100000000; do g++ -std=c++11 -O3 -DN=$i foo.cc && ./a.out; done
1000000, 0.187788
1000000, 0.636026
10000000, 2.05519
10000000, 10.8927
100000000, 26.4502
100000000, 181.287

Und das wird mit mehr Elementen nicht besser.

Nachtrag: Die besten Ergebnisse für den Bulk-Merge kriege ich mit folgendem Code:

#include <ctime>
#include <algorithm>
#include <random>
#include <vector>
#include <iostream>

struct merge_data {
  std::size_t vector_index;
  std::vector<int>::const_iterator iter;
};

int main() {
  std::vector<std::vector<int>> vecs(1 << 10, std::vector<int>(1 << 12));

  std::mt19937 rng;

  for(auto &v : vecs) {
    std::generate(v.begin(), v.end(), rng);
    std::sort(v.begin(), v.end());
  }

  std::vector<merge_data> iters(vecs.size());
  for(std::size_t i = 0; i < vecs.size(); ++i) {
    iters[i].vector_index = i;
    iters[i].iter = vecs[i].begin();
  }

  std::clock_t beg = std::clock();

  while(!iters.empty()) {
    auto next = std::min_element(iters.begin(),
                                 iters.end(),
                                 [](merge_data const &lhs, merge_data const &rhs) {
                                   return *lhs.iter < *rhs.iter;
                                 });
    ++next->iter;
    if(next->iter == vecs[next->vector_index].end()) {
      iters.erase(next);
    }
  }

  std::clock_t end = std::clock();

  std::cout << static_cast<double>(end - beg) / CLOCKS_PER_SEC << '\n';
}

Dauert hier gut 4.4 Sekunden. Für 16 MB. Mit größeren Blöcken wird die Sache schlimmer, weil der CPU-Cache dann nicht mehr reicht; dann kommt etwa Faktor 8 (ymmv) nochmal drauf (66 Sekunden für 32 MB). Aufs Terabyte hochgerechnet sind das 3 Tage und 8 Stunden, wenn alls immer heiß im Cache ist. Das ist die theoretische Untergrenze; ob das File-I/O, das in unregelmäßigen Abständen stattfinden müsste (für jeweils 16KB am Stück), möglich ist, ohne den CPU-Cache-Effekt zu beschädigen (so wegen Kontext-Switches und derlei), ist für mich nicht offensichtlich. Ohne diesen Effekt reden wir pessimistisch von etwa vier Wochen.

Das alles nur fürs Iterator-Schubsen. Aus Dateien gelesen oder in sie geschrieben ist damit noch nichts, wobei das bei dieser Vorgehensweise nicht den Löwenanteil ausmachen dürfte.

@seldon

Dein Code sortiert und merged alles auf einmal. Das ist aber nicht der diskutierte Ansatz. Schneller (ich kann es hier im Moment nicht ausprobieren) ist mit sehr hoher wahrscheinlichkeit eine paralleles Sortieren der einzelnen Vektoren und danach ein Merge derart, dass immer nur das erste Element der bereits sortierten Vektoren betrachtet und das davon kleinste in das Ziel kopiert wird. So sind bei n Vergleichen n-1 ELemente im Cache. Zumindest bis zu einer gewissen Anzahl von Vektoren.

prioq schrieb:

Kein Problem, dafür gibt's die std::priority_queue .

volkard

seldon schrieb:

Bulk-Merge wäre keine gute Idee, weil das quadratisch skaliert

Nimm nen Heap, in den Du (ersterWert;ZeigerAufStream) der 500 Streams stopfst. Dann skaliert Bulk-Merge auch logarithmisch und alles wird gut.

hustbaer

@seldon
Man merged natürlich immer nur zwei Streams direkt.
Aber halt insgesamt trotzdem alles auf einmal.

Das was du hintereinander machen würdest, mit zurückschreiben auf die Disk dazwischen, baust du als Baum auf. Ein Durchgang bei dir wird zu einer Ebene im Baum.
Die Leaf-Ebene (1. Durchgang) besteht aus Disk-Readern.
Danach kommen jeweils Merger.
Jeder Knoten hat einen Puffer und eine "FillBuffer" Operation, mit dem der Knoten darüber den Puffer neu auffüllen kann wenn er leergelaufen ist.

Das "FillBuffer" vom Disk-Reader liest dabei einfach nur, und das "FillBuffer" vom Merger merged eben.

Die Merge-Schleife arbeitet dabei also auf 2 Arrays und schreibt ihren Output in ein weiteres Array. Sehr Cache-freundlich. Und ab und an muss sie die "FillBuffer" der Kindknoten aufrufen.

Ah.

...

Okay, das sind Argumente. Auf beides bin ich gestern irgendwie überhaupt nicht gekommen, was mir im Nachhinein ziemlich peinlich ist.

nurf

Zurück zum Ursprungsthema, wer fragt sowas und warum.
Das ist ein typischer Einstellungstest für Facebook oder Google.
Dabei geht es auch darum "Out-Of-The-Box" zu denken.
Bei der Anzahl von Kollisionen braucht doch keiner wirklich eine sortierte Zielmenge, das ist doch schon ne Fangfrage.

Ansonsten: Quicksort ist vielleicht nicht das Schnellste hier, aber alle Anfänger stürzen sich auf Quicksort.

Nicht einmal hab ich in diesem Thread bisher das Stichwort "Kompression" gelesen (vielleicht hab ichs auch überlesen).

Folgende Lösungsansätze biete ich mal an:
Naives durchzählen: 1TB => 40bit Addressierung
10 Mal sequentiell die Ausgangsmenge durchgehen.
Dauer = 10TB/Festplattenspeed
Wegschreiben von 10*2 GB ist vernachlässigbar.

4Bit Durchzählen:
So bringt man die Werteraum in 2GB unter.
Wenn der 4bit Wert überläuft -> wegschreiben und mit dem Wert auf Festplatte addieren.
Das können aber Extra-Threads machen.
Vorteil: nur 1TB sequentiell lesen
Nachteil: randomisierte Lese/Schreibzugriffe auf Zielmenge.

volkard

nurf schrieb:

Nicht einmal hab ich in diesem Thread bisher das Stichwort "Kompression" gelesen (vielleicht hab ichs auch überlesen).

Ich hatte einen Vorschlag, der zusammenfaltet.

nurf schrieb:

Folgende Lösungsansätze biete ich mal an:
Naives durchzählen: 1TB => 40bit Addressierung
10 Mal sequentiell die Ausgangsmenge durchgehen.
Dauer = 10TB/Festplattenspeed
Wegschreiben von 10*2 GB ist vernachlässigbar.

Versteh Deine Rechnung nicht.
Eine Zahl kann maximal 2^36 mal vorkommen, also lauter 36-Bit-Zähler, also 9 Byte, also passen 238Mio Zähler ins ram, also 291 Durchläufe.

nurf schrieb:

4Bit Durchzählen:
So bringt man die Werteraum in 2GB unter.
Wenn der 4bit Wert überläuft -> wegschreiben und mit dem Wert auf Festplatte addieren.
Das können aber Extra-Threads machen.
Vorteil: nur 1TB sequentiell lesen
Nachteil: randomisierte Lese/Schreibzugriffe auf Zielmenge.

Ähm, der 4-Bit-Wert läuft dauernd über! Es muss immer oder zu mehr als 99.9% weggeschrieben werden. Das wird lahm, weil das Wegschreiben ja nix zur Sortierung beiträgt.

hustbaer

@seldon
Siehst du, genau deswegen dachte ich auch du willst mich vielleich veräppeln

@nurf
Ich denke wir haben hier schon eine ziemlich gute Lösung.
Und ob das ne Fangfrage ist oder nicht ist dabei doch völlig egal.
Ob es ne Frage für nen Einstellungs-Test ist, ist natürlich nicht egal, genau so wie ob es ne Klausurfrage oder Hausaufgabe ist.
Aber hey, ich hab' zumindest nicht als erster geantwortet

SeppJ

hustbaer schrieb:

Aber hey, ich hab' zumindest nicht als erster geantwortet

Der Fragesteller hat sich ja sogar schon im Eingangsbeitrag selber geantwortet mit einer Lösung, die im Ansatz der diskutierten gleicht. Nur die Details habt ihr inzwischen feiner ausgearbeitet. Also eigentlich ideal, wie ein Thread wie dieser verlaufen soll.

hustbaer

Stimmt, das entspricht im Prinzip "unserer" Lösung.
Hatte ich ganz vergessen, da ich auch erst auf dem "zählen" Dampfer war, und mir gedacht habe das geht viel besser

Einzig wie das mit dem Mergen gemeint ist ist nicht klar, also ob ihm klar ~~ist~~ war dass man das mit nem Graphen aus 2-Way-Merge "Streams" machen sollte.