Gibt es einen Algorithmus in der STL, der.....

... mir Elemente performant in meinen Vector kopieren kann?

meine Methode sieht momentan so aus:

ssize_t capacity = _Buffer.capacity();
 ssize_t size = _Buffer.size();
 if( (capacity - size) < 4096)
 {
      _Buffer.reserve(capacity + 65536);
 }

 // Put the data in the vector
 // (One Element per byte)	
 for(int i = 0; i < numberOfBytes; i++)
 {
      _Buffer.push_back(Data[i]);
 }

unsigned char Data[4096];
std::vector<unsigned char> _Buffer;

kann man da noch was verbessern?

An einer weiteren Stelle muss ich meinen Vector an einen anderen "heranhängen", was ich auch in einer Schleife mache:

std::vector<unsigned char>::iterator iterator;

 for( iterator = _Buffer.begin(); iterator != _Buffer.end(); ++iterator)
 {                
      // Copy the value to the out parameter
      rxdata->push_back(*iterator);
 }

std::vector<unsigned char> rxdata;

gruß Paddy

Jester

Auch beim Kopieren solltest Du mittels reserve für ausreichenden Platz sorgen. Ansonsten läßt sich da vermutlich nicht so viel machen. Das Kopieren kannste auch von std::copy erledigen lassen. Schneller ist das aber auch nicht.

Bei der zweiten Variante, nutze ich bereits reserve. Kommt aus ner Methode, in der man angeben kann, ob man den gesamten Vektorinhalt oder n Bytes haben möchte.... Dementsprechend wird halt für rxdata Speicher reserviert.

Aber ansonsten geht da nichts mehr, oder?
Wie sieht es mit bound checking aus?
Führt push_back ein bound checking durch? sonst könnte ich eventuell noch über den index operator [] selber die Elemente reinkopieren.
Ich kümmere mich ja mittels reserve selber drum, dass genügend Speicher vorhanden ist.

Braunstein

push_back führt kein bound checking durch. Braucht es auch gar nicht, da es bei Bedarf neuen Speichern anfordern kann.

aber es muss überprüfen, ob Bedarf da ist.
Kann man das durch den [] operator einsparen?

Blue-Tiger

paddy@work schrieb:

aber es muss überprüfen, ob Bedarf da ist.
Kann man das durch den [] operator einsparen?

bist du sicher dass du grad an der richtigen Stelle optimierst? o_0

ja, denn es muss wirklich alles optimiert werden :-(((

Ich habe eine Vorgabe bekommen, da muss ich selbst sowas berücksichtigen....

Warum liest du nicht sofort in den vector ein? Oder benutz memcpy.

Knuddlbaer

Wie sieht denn die vorgabe im Detail aus ?
i.d.R. ist die STL doch schon optimiert. Man kann dann nurnoch für den Spezialfall optimieren und den sucht man sich meist mit einem Profiler ?!

finix

Hast du schon mal

// _Buffer & _Data sind ganz, ganz schlecht gewaehlte Bezeichner
_buffer.insert(_buffer.end(), _data, _data + numberOfBytes);

statt push_back versucht?

Und was ist mit deinem reserve - welchen Sinn soll das haben, und wieso genau 65536 hardcoded?

volkard

finix schrieb:

Und was ist mit deinem reserve - welchen Sinn soll das haben, und wieso genau 65536 hardcoded?

das drückt die laufzeit bei wiederholten aufrufen von O(n) auf O(n^2).

Knuddlbaer

eventuell soll das reserve verhindern, das ständig neuer speicher alloziiert werden muss.

Denn wenn die Elemente zu klein sind muss neuer speicher organisiert werden und alle Elemente müssen umkopiert werden (was z.B. auch iteratoren zerstört).

ich habe die passage aus dem kontext heraus kopiert, so dass die Namen echt nicht gut sind, allerdings machen sie im zusammenhang mit dem rest der methode mehr sinn.

Die 64KB sind hardgecoded, da ich durch regelmäßiges testen, zu dem Entschluss gekommen bin, dass das Verhältnis zwischen Speichergröße und der Anzahl der reserve aufrufe vernünftig ist. ich sollte mir nichts desto trotz eine Konstante dafür machen.

Was macht den Unterschied zwischen insert und push_back Schleife?

volkard

muß es denn ein vector sein? ich finde, hier riecht's nach queue.

leider ja, wird mir vom Interface vorgeschrieben....

finix

volkard schrieb:

finix schrieb:

Und was ist mit deinem reserve - welchen Sinn soll das haben, und wieso genau 65536 hardcoded?

das drückt die laufzeit bei wiederholten aufrufen von O(n) auf O(n^2), macht also fatal lahm. normales zwischenergebnis beim explorativen optimieren.

Hehe, ja. Effektiver Weg um das Storagemanagement von std::vector zu sabotieren.
Das reserve wäre ohnehin nur sinnvoll für sizeof(Data) >> buffer.capacity().

Also ich muss die Werte in einen vector von unsigned char (Also 1 byte) anbieten. Die daten kommen in ca. 50 - 200 leider aber selten auch in 4096 byte großen strömen bei mir an. Allerdings kommen sehr viele von diesen kleinen Datenmengen an.

wenn ich nicht mit reserve arbeiten würde, müsste doch für jedes byte immer wieder neu speicher reserviert werden (im push_back).

Das möchte ich verhindern, da es doch langsamer ist, 65536 mal 1 Byte speicher zu holen, als einmal 64 KB, oder sehe ich das falsch?

finix

paddy@work schrieb:

ich habe die passage aus dem kontext heraus kopiert, so dass die Namen echt nicht gut sind, allerdings machen sie im zusammenhang mit dem rest der methode mehr sinn.

Vielleicht ist dir aufgefallen dass ich in meinem Snippet lediglich von uppercase auf lowercase übergegangen bin:

Bezeichner die
mit Understriche + Großbuchstaben beginnen
zwei aufeinander folgende Unterstriche enthalten
im globalen Namensraum liegen und mit Unterstrich beginnen
sind reserviert. Google wird dir noch ein paar mehr Ausnahmen & konkrete Bezeichner liefern können, aber obiges ist eine nette Faustregel.

volkard

paddy@work schrieb:

Die 64KB sind hardgecoded, da ich durch regelmäßiges testen, zu dem Entschluss gekommen bin, dass das Verhältnis zwischen Speichergröße und der Anzahl der reserve aufrufe vernünftig ist.

war es nicht immer so, daß physikalischer speicher erst allokiert wird, wenn die mit new virtuell allokierten speicherseiten auch angefasst werden, weshalb int* pi=new int[1000000000]; auch so schnell geht und erst beim beschreiben geht die party los?
mal angenommen, das wäre so, wäre dann das reserven nicht unfug und insert bzw pushback einfach nur toll?

__HIRSCH_H__

Jester schrieb:

Auch beim Kopieren solltest Du mittels reserve für ausreichenden Platz sorgen. Ansonsten läßt sich da vermutlich nicht so viel machen. Das Kopieren kannste auch von std::copy erledigen lassen. Schneller ist das aber auch nicht.

Doch, der std::copy algorithmus ist spezialisiert für einige POD Typen und verwendet intern memmove bzw. memcpy.
Zumindest bei der stdc++ vom g++ iss das so.