Schnelles C++

Für PHP-Arrays in seiner JIT-Compiler Optimierung für Facebook, wenn ich das jetzt richtig verstanden habe. Scheit wohl ein ziemlich schräges Konstrukt zu sein diese PHP-Arrays.

dachschaden

Ich bin so einer, der den Quatsch mitmacht. Also, dafür sorgen, dass es kaum Cache Misses gibt, weil ich mir aus zig Stellen im Speicher Sachen raussuche.

Vektorisierung, Prüfung zur Laufzeit, ob bestimmte Prozessorfeatures vorhanden sind, mit denen man bestimmte Sachen schneller machen kann (ich werfe mal AVX/SSE in den Raum - dafür habe ich übrigens auch ein API fertiggestellt, das mit ganz krudem Inline-Assembler arbeiten muss), und natürlich immer versuchen, malloc/free ganz weit weg zu lassen.

Manchmal geht das natürlich nicht. Manchmal, wenn man zum Beispiel Dateien read-onl einlesen will, kann man auch Funktionen des Betriebssystems verwenden, um diese in den Speicher zu mappen. Wenn der Kernel die Datei grad rumfliegen hat im Speicher, spart man sich das Kopieren der Datei in den Userspace. Stattdessen bekommt man die Pages dann direkt rein in den Speicher.

Manchmal braucht man auch nur so 4 KB Speicher, das mache ich dann lieber auf dem Stack - das spart wie gesagt malloc und free , und ich zwinge die CPU nicht zwangsweise, wieder eine Cache-Line vollzuhauen.

Manchmal, wenn ich Verzeichnisse rekursiv durchgehen will, mache ich es ganz besonders schlau. Dann berechne ich mir bereits im Voraus, wie viel Speicher ich insgesamt brauchen werde für das Durchlaufen bis zur n-ten-Ebene, die reserviere ich im Call der obersten Ebene und reiche Portionen des Speichers an Untercalls. Dann hat man zwar einen höheren Speicherverbrauch über die gesamte Zeit, in der die Verzeichnisse durchlaufen werden, aber das dann konstant.

Deswegen mag ich C übrigens mehr als C++. In C kannst du die dynamische Speicherverwaltung mit ein paar Tricks links liegen lassen. In C++ kannst du nicht einmal einen std::string anfassen, ohne wieder new und delete an der Backe zu haben.

Die Ergebnisse können sich dann zwar sehen lassen, aber du musst etliche Sachen beachten. Und den meisten ist das eh zu kompliziert. Ein Kollege meinte mal zu mir: "Speicher? Speicher will ich haben, nicht verwalten".

Macht Java das nicht ähnlich, also einen großen Block Speicher anfordern und dann selbst verteilen? Ich bin auch der Meinung mal irgendwo gelesen zu haben, dass man dies generell machen sollte, weil es, wie du schon sagst, die vielen langsamen Kernelroutinen-Aufrufe zum Speicher spart bzw stark reduziert. Also nicht generell bei allen Programmen, aber da wo die Anforderungen des Speichers zum Flaschenhals werden.

Womit sucht ihr eigentlich so nach Cachmisses und den ganz Kram? Ich habe da gar keine Ahnung, bzw. heute das erste Mal das Thema mir so richtig angeschaut.

volkard

dachschaden schrieb:

Ich bin so einer, der den Quatsch mitmacht. Also, dafür sorgen, dass es kaum Cache Misses gibt, weil ich mir aus zig Stellen im Speicher Sachen raussuche.

Wenns keine PHP-Arrays sind, kannste wie Scott gesagt hat, die Objekte nach Typ sortieren, damit dei aufgerufenen Funktionen hot bleiben. Oder kannst verschiedene Typen in verschiedene Speicher tun und auf den vptr ganz verzichten. Da fallen einem sofort unzählige Möglichkeiten ein.

dachschaden schrieb:

Manchmal, wenn ich Verzeichnisse rekursiv durchgehen will, mache ich es ganz besonders schlau. Dann berechne ich mir bereits im Voraus, wie viel Speicher ich insgesamt brauchen werde für das Durchlaufen bis zur n-ten-Ebene, die reserviere ich im Call der obersten Ebene und reiche Portionen des Speichers an Untercalls. Dann hat man zwar einen höheren Speicherverbrauch über die gesamte Zeit, in der die Verzeichnisse durchlaufen werden, aber das dann konstant.

Und das, wo ein FindNextFile Dir 1000 Takte wegkloppt? Irrsinn. Welchen Speicher zu allokieren sparst Du? Den Stackspeicher der lokalen Variablen? Naja, der ist nicht so irrsinnig teuer. Also eher kostenlos. Oder die ganzen strings für die root auf jeder Ebene? Kannst auch da einen unten anlegen und hochreichen. Bei Bedarf wächst er und schrumpft nicht.

dachschaden schrieb:

Deswegen mag ich C übrigens mehr als C++. In C kannst du die dynamische Speicherverwaltung mit ein paar Tricks links liegen lassen. In C++ kannst du nicht einmal einen std::string anfassen, ohne wieder new und delete an der Backe zu haben.

Kannst in C++ all diese Tricks auch machen und noch viel mehr. Eigentlich solltest Du C++ lieben.

volkard

Citizen42 schrieb:

Macht Java das nicht ähnlich, also einen großen Block Speicher anfordern und dann selbst verteilen? Ich bin auch der Meinung mal irgendwo gelesen zu haben, dass man dies generell machen sollte, weil es, wie du schon sagst, die vielen langsamen Kernelroutinen-Aufrufe zum Speicher spart bzw stark reduziert.

Das machen alle Sprachen (zum Beispiel verpackt in Funktionen wie malloc()).

Citizen42 schrieb:

Also nicht generell bei allen Programmen, aber da wo die Anforderungen des Speichers zum Flaschenhals werden.

Doch, gleich bei allen.

Citizen42 schrieb:

Womit sucht ihr eigentlich so nach Cachmisses und den ganz Kram? Ich habe da gar keine Ahnung, bzw. heute das erste Mal das Thema mir so richtig angeschaut.

Die meisten suchen gar nicht (wie auch?), sondern optimieren im Voraus (schlechte Angewohnheit, sagt Alexandrescu).

dachschaden

Citizen42 schrieb:

Macht Java das nicht ähnlich, also einen großen Block Speicher anfordern und dann selbst verteilen? Ich bin auch der Meinung mal irgendwo gelesen zu haben, dass man dies generell machen sollte, weil es, wie du schon sagst, die vielen langsamen Kernelroutinen-Aufrufe zum Speicher spart bzw stark reduziert. Also nicht generell bei allen Programmen, aber da wo die Anforderungen des Speichers zum Flaschenhals werden.

Das Problem haste auch so. Weil bereits malloc erst mal Listen durchgehen muss, wo verzeichnet ist, welcher Speicher jetzt belegt ist oder nicht. Wenn du dann Pech hast, gibt's Kontextwechsel. Aber auch so hast du ein paar Cycles verschwendet.

Citizen42 schrieb:

Womit sucht ihr eigentlich so nach Cachmisses und den ganz Kram? Ich habe da gar keine Ahnung, bzw. heute das erste Mal das Thema mir so richtig angeschaut.

Man sucht nach dem Symptom - das Programm läuft langsamer. Also, ich jedenfalls mach das so.

volkard schrieb:

Und das, wo ein FindNextFile Dir 1000 Takte wegkloppt? Irrsinn. Welchen Speicher zu allokieren sparst Du? Den Stackspeicher der lokalen Variablen? Naja, der ist nicht so irrsinnig teuer. Also eher kostenlos. Oder die ganzen strings für die root auf jeder Ebene? Kannst auch da einen unten anlegen und hochreichen. Bei Bedarf wächst er und schrumpft nicht.

Sowas tue ich nicht auf den Stack. Der Stack ist klein, der Heap ist groß. Wenn ich dann ein neues Verzeichnis öffne, lasse ich mir das auf dem Heap reservieren. Aber dann direkt zu Anfang und dann auch am Stück.
Soll ich etwa immer ein strlen machen, damit ich weiß, wie wie Speicher ich jetzt haben muss? Und dann ein malloc dafür? Nee. Neeeeeee.

volkard schrieb:

Kannst in C++ all diese Tricks auch machen und noch viel mehr. Eigentlich solltest Du C++ lieben.

Ach, Volkard ... da haste mich erwischt.
Hätte dazuschreiben sollen, dass das in C zum guten Ton gehört. In C++ kriegst du ja sofort eine gewatscht, wenn du anfängst, Indexe statt Iteratoren zu verwenden. Klar ist C++ in der Hinsicht mächtiger, keine Frage. Aber die Leute, die dann später deinen Code lesen, denken sich in C "Cool, dass der daran gedacht hat", und in C++ "WTF hat er sich dabei gedacht?".

volkard

dachschaden schrieb:

volkard schrieb:

Und das, wo ein FindNextFile Dir 1000 Takte wegkloppt? Irrsinn. Welchen Speicher zu allokieren sparst Du? Den Stackspeicher der lokalen Variablen? Naja, der ist nicht so irrsinnig teuer. Also eher kostenlos. Oder die ganzen strings für die root auf jeder Ebene? Kannst auch da einen unten anlegen und hochreichen. Bei Bedarf wächst er und schrumpft nicht.

Sowas tue ich nicht auf den Stack. Der Stack ist klein, der Heap ist groß. Wenn ich dann ein neues Verzeichnis öffne, lasse ich mir das auf dem Heap reservieren. Aber dann direkt zu Anfang und dann auch am Stück.
Soll ich etwas immer ein strlen machen, damit ich weiß, wie wie Speicher ich jetzt haben muss?

Vermutlich gehen wir von anderen Betriebsystem-Calls aus. Also ich denke schon dran nullterminirte Strings vom BS zu kriegen, und die beim Abstieg an meinen dranbauen zu müssen. strcat zum Beispiel oder string::+=. Beim Wiederaufstieg kann man in C++ auch wieder kürzen. Ich muss vorher nicht zählen (darf aber, oder darf sinnvoll schätzen), bei Bedarf wächst der string automatisch.
Ich gehe nicht von einer BS-Funktion aus, die mir ein ganzes Verzeichnis liefert, sondern daß ich FindFirst/FindNext zur Verfügung habe.

dachschaden schrieb:

Aber die Leute, die dann später deinen Code lesen, denken sich in C "Cool, dass der daran gedacht hat", und in C++ "WTF hat er sich dabei gedacht?",

Jo, ist lästig. Immer, wenns wieder anfängt, daß ich hier als C++-Nube beschimpft werde, weil mein Code zu einfach(lesbar+schnell) ist, poste ich irgendwo ein wenig Template-Gefrickel und hab wieder ein Jahr Ruhe. Ist viel weniger Arbeit, als C++ zu meiden, finde ich.

Was ist von dem Tool zu halten, was Herb Sutter an dieser Stelle zeigt: https://www.youtube.com/watch?feature=player_detailpage&v=L7zSU9HI-6I#t=5898 Es nennt sich RightMark Memory Analyzer und kann hier http://cpu.rightmark.org/download/rmma38bin.rar runtergeladen werden. Ich habe gerade kein Windows zum Testen unter den Fingern. Gibt es so etwas auch für OSX oder Linux?

dachschaden

volkard schrieb:

Vermutlich gehen wir von anderen Betriebsystem-Calls aus. Also ich denke schon dran nullterminirte Strings vom BS zu kriegen, und die beim Abstieg an meinen dranbauen zu müssen. strcat zum Beispiel oder string::+=. Beim Wiederaufstieg kann man in C++ auch wieder kürzen. Ich muss vorher nicht zählen (darf aber, oder darf sinnvoll schätzen), bei Bedarf wächst der string automatisch.

Hast dann aber wieder einen realloc . Mindestens.
Du nennst es "schätzen", ich würde es "wetten" nennen. Nee, ich gehe immer vom schlimmsten aus. Oder ich bin eher dazu bereit, Speicher zugunsten von Laufzeit zu opfern. Kommt dann aber auch wieder darauf an, für was für eine Plattform man da programmiert. Jenachdem ist dein Ansatz dann wesentlich intelligenter.

volkard schrieb:

Jo, ist lästig. Immer, wenns wieder anfängt, daß ich hier als C++-Nube beschimpft werde, weil mein Code zu einfach(lesbar+schnell) ist, poste ich irgendwo ein wenig Template-Gefrickel und hab wieder ein Jahr Ruhe. Ist viel weniger Arbeit, als C++ zu meiden, finde ich.

Ich rede hier nicht mal vom Forum. Da mache ich mir überhaupt nicht die Mühe, den Leuten was beweisen zu wollen.
Ich meine, wenn der Code reviewt wird. Vielleicht habe ich da auch eine Opfermentalität, weil ich selbst so reviews mache, und ständig Code zu sehen bekomme, der stark entweder nach Jürgen "Ich kann alles" Wolf oder von C++ abgeleitet aussieht. In einer Bude lag der Wolf dann auch tatsächlich rum. m(
Jedenfalls versuche ich, mich immer der Mentalität der Sprache anzupassen. Und wenn ich die gleichen Hacks in C++ wie in C anwende und sonst kaum einen der Vorteile von C++, dann kann ich gleich C verwenden. Das kompiliert auch schneller.

volkard

dachschaden schrieb:

Hast dann aber wieder einen realloc . Mindestens.
Du nennst es "schätzen", ich würde es "wetten" nennen. Nee, ich gehe immer vom schlimmsten aus. Oder ich bin eher dazu bereit, Speicher zugunsten von Laufzeit zu opfern. Kommt dann aber auch wieder darauf an, für was für eine Plattform man da programmiert. Jenachdem ist dein Ansatz dann wesentlich intelligenter.

Wenn ich zufällige Längen zwischn 0 und 999 hätte und 100 "schätzen" würde und 100000 Files hätte, käme ich auf durchschnittlich 7 reallocs. Wobei ich vom dümmlichen

if(r>m){
				m=r;
                                realoc(m);
			}

ausginge.
Bezahlbar, finde ich. Hab echt Angst, ich könnte statt der Mikrosekunde fürs reallocen vielleicht zwei Millionen Mikrosekunden ausgeben, um vorher durchzulaufen und die Maxgröße zu finden. Oder ich "wette" einfach, daß 2000 reichen werden und wenn nicht, kracht's eben. Wie stellst Du vorher die maximale Größe fest? Oder haste eine schlichte Garantie wie <=32786 und nimmst einfach die?
Mit m=r+r; bin auch auf 2.4 reallocs.

dachschaden

volkard schrieb:

Wie stellst Du vorher die maximale Größe fest? Oder haste eine schlichte Garantie wie <=32786 und nimmst einfach die?

Ich habe eine Funktion, die mir abhängig vom System die maximale Pfadgröße zurückgibt. Mit der arbeite ich. Wenn ich die nicht bekomme, schlägt der Call fehl. Also: Ja, ich suche mir so eine Garantie. Ja, dabei wird Speicher verwendet. Das ist mir klar.

volkard

dachschaden schrieb:

Ja, dabei wird Speicher verwendet. Das ist mir klar.

Speicher sparen, den kein anderer braucht, ist blöd. Embedded system nehme ich an und singlethreaded. Dann kannste die Garantie einfach benutzen und weiterreichen. Das Wachsen des Speichers, was ich auf PCs bevorzugen würde, könnte dümmstenfalls doppelt so viel Speicher fressen wie das feste Vorallokieren.
Seit ein paar Monaten darf man in C++ keine rohen Zeiger mehr nehmen. Würde ich aber da nehmen, ich Sau.

EOP

volkard schrieb:

Seit ein paar Monaten darf man in C++ keine rohen Zeiger mehr nehmen.

Sagt wer?

EOP schrieb:

volkard schrieb:

Seit ein paar Monaten darf man in C++ keine rohen Zeiger mehr nehmen.

Sagt wer?

Ein Global Moderator.

EOP

Ich hab kein C++11, also darf ich.

Warum hast du kein C++11?

EOP

Weil ich nur VisulStudio 2005 hab.

Warum lädst du dir keine neuere Version runter, oder nimmst MinGW oder Clang? Ich meine, C++11 ist der aktuelle Standard und der nächste steht schon vor der Tür. Ich kenne der alten Standard nicht so, da ich gleich mit C++11 angefangen habe, aber es hat sich ja schon wohl viel geändert.

Nathan

Citizen42 schrieb:

Ich meine, C++11 ist der aktuelle Standard und der nächste steht schon vor der Tür..

Ich finde das toll, dass das so an alle vorbeigeht: C++14 ist schon seit 4 Monaten draußen!

Ups echt? Ich dachte irgend ein Draft wäre fertig und muss noch durchgewunken werden.