[C++] Code optimieren

[Daifoku]

Hey,

ich würde gerne wissen, ob dieser Code der schnellstmögliche ist oder ob es da bessere Varianten gibt. Bisher habe ich immer alle Buffer, die eine variable größe haben, mit std::vector modelliert.

	std::vector<char> buffer;
	int fpos = 0; //aktuelle Position in der binären Dateien
	if (HttpQueryInfo(hFile, HTTP_QUERY_CONTENT_LENGTH | HTTP_QUERY_FLAG_NUMBER, &fileSize, &dwBufferLength, NULL) && fileSize > 0)
		dwNumberOfBytesToRead = fileSize;
	do {
		if (!fileSize) buffer.resize(dwNumberOfBytesToRead + fpos);
		InternetReadFile(hFile, &(buffer.at(fpos)), dwNumberOfBytesToRead, &dwNumberOfBytesRead);
		fpos += dwNumberOfBytesRead;
	} while (dwNumberOfBytesRead);
	if(!fileSize) buffer.resize(fpos); //shrink to full size

Ausgeben könnte ich den Code dann beispielsweise über

for (char & c : buffer) std::cout << c;

freue mich auf eure Meinungen und Erfahrungen

[warfley]

Nein es geht schneller, zunächst einmal die Größe der Datei ermitteln / aproximieren, dann den Vektor auf die Größe setzen und dann die Bytes einlesen, das ständige reisizen ist recht teuer.

[Daifoku]

Das wollte ich zunächst machen, allerdings weiß ich nicht, wie ich die Größe einer Online-Datei abfragen kann. Eine Idee ?

nvm, ich teste mal

dazu muss ich allerdings die oben gannte Funktion als Fallback nutzen, falls content-length nicht gesetzt ist

	if (HttpQueryInfo(hFile, HTTP_QUERY_CONTENT_LENGTH | HTTP_QUERY_FLAG_NUMBER, &fileSize, &dwBufferLength, NULL) && fileSize > 0)
		dwNumberOfBytesToRead = fileSize;
	do {
		if (!fileSize) buffer.resize(dwNumberOfBytesToRead + fpos);
		InternetReadFile(hFile, &(buffer.at(fpos)), dwNumberOfBytesToRead, &dwNumberOfBytesRead);
		fpos += dwNumberOfBytesRead;
	} while (dwNumberOfBytesRead);
	if(!fileSize) buffer.resize(fpos); //shrink to full size

So müsste es gehen, der buffer std::vector<char> wird nur ein einziges mal resized sofern HTTP_QUERY_CONTENT_LENGTH ein Ergebnis liefert, ansonsten wird die Fallback Methode verwendet, indem der Buffer, falls nötig, immer wieder vergrößert wird.

[warfley]

Wenn du die Datei aus einem Netzwerk stream ziehst ist die Geschwindigkeit des codes sowieso irrelevant, da die Read operation aus einem TCP socket faktoriell viel größer ist als die lokalen Operationen.

Was du auch machen kannst um deinen code laufzeittechnisch zu optimieren ist etwa so etwas

char* buff = malloc(1024);
char b[1024];
int capacity = 1024;
int len=0;
int ReadBytes;
...
while (buff != null && (ReadBytes = Read(Handle, &b[0], 1024)) >0) {
  if ((len + ReadBytes) > capacity) {
    buff = realloc(buff, capacity*2);
    capacity *= 2;
  }
  if (buff != null)
    bcopy(&b[0], b+len, ReadBytes);
  len += ReadBytes;
}

Das ist so ein Pseudo C code, da ich nicht wirklich mich mit C++ Klassen auskenne.
Somit wird am Anfang entsprechend Speicher allokiert, und nur wenn das gelesene mehr Speicher in Anspruch nimmt wird immer doppelt so viel allokiert, somit werden auch bei unbekannter Größe die resize Operationen minimiert

Büßt für Geschwindigkeit aber halt Speicherplatz ein, aber das ist meist der fall Laufzeit optimierung führt meist zu einer Verschlechterung der Platzkomplexität

[Daifoku]

Das wäre theoretisch das gleiche, was ich oben mit std::vector gemacht habe ^^ nur halt in C ;-) Dann bleib ich eher bei std::vector

std::vector realisiert den resize() Befehl ähnlich.
Falls resize() verwendet wird, um den Buffer zu verkleinern, wird einfach nur der Pointer anders gesetzt

[warfley]

Originally Posted by Daifoku

Das wäre theoretisch das gleiche, was ich oben mit std::vector gemacht habe ^^ nur halt in C ;-) Dann bleib ich eher bei std::vector

std::vector realisiert den resize() Befehl ähnlich.
Falls resize() verwendet wird, um den Buffer zu verkleinern, wird einfach nur der Pointer anders gesetzt

ja gut du approximierst die Größe linear ich gehe in 2er Potenzen hoch, somit ist bei einer date der größe 1 mb benötige ich 10 resizes, du (bei ein kb read) 1000 resizes

[Daifoku]

Gut für kleine Dateien, problematisch, wenn die Dateien zwischen 1kb und 15MB schwanken ;-) Manche Dateien die ich herunter lade, haben eine Größe von 15MB. Im schlechtesten Fall erhöht sich die RAM Nutzung um knapp 15Mb

[warfley]

Wie gesagt Zeitoptimierung geht oft auf kosten von Platz, nur Platz ist weniger wertvoll als Zeit, das System hat so genannte Paging Strategien um Speicher via Swapping auszulagern, so dass es nur sehr selten zu OOM (Out Of Memory) Exceptions kommt, du musst dir halt überlegen was dir wichtiger ist, du könntest auch immer die doppelte oder dreifache menge an Speicher aproximieren, somit würden deine Speicher allokationen sich entsprechend Faktoriell verringern.

Aber wie bereits gesagt bringt Optimierung bei diesem Speziellen problem recht wenig, ich führe das hier nur an, um mal Optionen auf zu zeigen.

Und solltest du wirklich mal so etwas gut optimieren müssen denk immer daran, Speicher dynamisch zu reallokieren ist verdammt Zeitaufwendig (Kontextwechsel zu Kernel mode, kernel sucht nach Speicher, muss diesen Speicher anlegen, Daten aus dem Alten Buffer in den neuen kopieren, alten buffer freigeben und noch ein Kontextwechsel in den Usermode). Wenn du einen Array einfach nur mit Berechnungen füllen musst hättest du in der zeit die ein realloc benötigt schon bereits etliche Felder ausgefüllt. Dagegen sind ein paar mb zu viel im HS nichts

[Ende!]

Originally Posted by warfley

ja gut du approximierst die Größe linear ich gehe in 2er Potenzen hoch, somit ist bei einer date der größe 1 mb benötige ich 10 resizes, du (bei ein kb read) 1000 resizes

Originally Posted by C++ Standard, 23.3.6.1

[...] Storage management is handled automatically, though hints can be given to improve efficiency.

Es ist der Implementierung der STL überlassen die Pre-Allocation mit einem für die Platform sinnvollen Verfahren zu implementieren. Das erlaubt dem vector bspw. auf PCs mit besagten 2er Potenzen zu arbeiten, während in der Embedded-Rubrik wohl eher weniger große Schritte genommen werden.

Die von der Standard-OSX-Buildchain verwendete STL z.B. implementiert offenbar einen Ansatz, bei dem immer prev-size * 2 verwendet wird:

% cat freepascalsucks.cc 
#include <vector>
#include <iostream>
#include <stdint.h>

int main()
{
    for (auto cur : {1, 10, 1000, 1000000}) 
    {
        std::vector<uint8_t> vec(cur, 'x');
        std::cout << "cur = " << cur 
                  << ", vec.size() -> " << vec.size() 
                  << ", vec.capacity() -> " << vec.capacity() << '\n';
        vec.resize(cur + 1);
        std::cout << "cur = " << cur 
                  << ", vec.size() -> " << vec.size() 
                  << ", vec.capacity() -> " << vec.capacity() << '\n';
    }
    std::cout << std::flush;
}

% clang++ --std=c++14 freepascalsucks.cc -o blah && ./blah
cur = 1, vec.size() -> 1, vec.capacity() -> 1
cur = 1, vec.size() -> 2, vec.capacity() -> 2
cur = 10, vec.size() -> 10, vec.capacity() -> 10
cur = 10, vec.size() -> 11, vec.capacity() -> 20
cur = 1000, vec.size() -> 1000, vec.capacity() -> 1000
cur = 1000, vec.size() -> 1001, vec.capacity() -> 2000
cur = 1000000, vec.size() -> 1000000, vec.capacity() -> 1000000
cur = 1000000, vec.size() -> 1000001, vec.capacity() -> 2000000

[ƬheGame]

Das ganze mit -O2 zu compilen wird mehr speed bringen, als jede Änderung die du daran vornehmen kannst. Warscheinlich wirst du sowieso so gut wie nichts feststellen könne egal wie sehr du das nun optimierst. Ob es nun 1/10ms oder 1/15ms dauert ist am Ende bei 99% der Applikaitonen egal.

Wenn du speed willst, lern Assembler. Damit könntest du den Code sicher doppelt so schnell machen.

[Daifoku]

Originally Posted by ƬheGame

Wenn du speed willst, lern Assembler. Damit könntest du den Code sicher doppelt so schnell machen.

Solche Aussagen finde ich ohne qualifiziertes Beispiel und Statistiken nicht sinnvoll und zudem habe ich C++ gefordert.
Ich kann auch in die Kirche gehen und zu Gott beten, manche schwören darauf, dass der alles erfüllt

Originally Posted by ƬheGame

..., als jede Änderung die du daran vornehmen kannst. Warscheinlich wirst du sowieso so gut wie nichts feststellen könne egal wie sehr du das nun optimierst.

Darum geht es hier nicht.
Ich bin mit der Performance zufrieden, möchte aber rein aus Interesse wissen, wie sowas "optimal" gelöst werden kann. Nur weil etwas gut läuft heißt es nicht, dass es auch gut ist. Der Mensch möchte sich weiterentwickeln ;-)
Ich habe von den Ende und Warfley bereits einiges gelernt und bin ihnen dankbar

[Padmak]

Hier gibts eine ziemlich detailreiche Erklärung, wie std::vector seine Größe ändert, vielleicht für den ein oder anderen ganz interessant (bzgl Debatte mit dem Growth-Faktor)

@TheGame:
In diesem Fall geht es nicht darum dass der geschriebene Code unperformant ist, sondern dass die Allokationen im Hintergrund viel Zeit wegfressen, weil sie unnötig oft durchgeführt werden. Bei permanentem realloc und entsprechenem Pech beim Paging hilft dir der schnellste Assembler-Code nichts

€: Aber grundsätzlich stimme ich schon zu, zu viel Optimierung macht's nur wieder schlechter. Die meisten Compiler wissen oft genug ziemlich genau, was sie tun

Padmak

[Daifoku]

interessant, habe mir den gesamten Artikel durchgelesen

Für Dateien unbekannter Größe hätten wir dann zusammenfassend

unsigned int HTTPDownload::readPartialFile(size_t partialSize)
{
	unsigned int filesize = 0;
	buffer.resize(partialSize + 1);
	do {
		buffer.resize(partialSize + filesize);
		InternetReadFile(hFile, &(buffer.at(filesize)), partialSize, &dwNumberOfBytesRead);
		filesize += dwNumberOfBytesRead;
	} while (dwNumberOfBytesRead);
        buffer.resize(filesize); /* set endPointer */
	buffer.shrink_to_fit(); /* free unused memory */
	return filesize;
}

size_t partialSize würde dann mit einem "optimalen" Parameter, je nach Anwendungsgebiet, gesetzt werden.

"it leaves the gaps in memory which would be reasonable to fill later"
lösen wir nach Ende der Aktion mit buffer.shrink_to_fit(); bzw swap()

[Dr. Coxxy]

Grundsätzlich:
durch optimierung durch gut geschriebenes assembler kannst du IMMER optimierungen herausholen (alleine schon weil du den vom compiler erzeugten asm code weiter optimieren kannst - und ja, man kann immer optimieren soooo super sind die compiler nicht.).
Nutzen kann hierbei zwischen 10 - 200% bis noch mehr bringen, je nachdem was du genau machst (idr. optimierst du auch den algorithmus/nutzt hardwarespezifische optimierungsmöglichkeiten wenn du in asm umwandelst - reine asm optimierung bringt vllt. 10-30% ggü. dem compiler).
Fraglich ist nur, ob und wieviel es bringt - im konkreten anwendungsfall ists vollkommener unsinn, weil dein bottleneck vermutlich deine internetverbindung ist, um das bottleneck herauszufinden eignen sich profiler wie z.b. der in vs integrierte oder eigene messungen, sowie bissle grundverständnis über optimierungsmöglichkeiten.

[warfley]

Und noch schneller ist man wenn man statt ner CPU ein FPGA nimmt und mit VHDL arbeitet.

Aber darum geht es ja nicht, er wollte wissen wie er mit C++ die beste Geschwindigkeit erreicht.

Außerdem muss man eher selten so eine Optimierungsstufe erreichen, selbst Echtzeitsysteme werden in Hochsprachen geschrieben (C oder im sicherheitskritischen Bereich eher Ada), und nur teile in ASM.