Länge von Arrays einlesen

[HumeSikkins]

Ah,
hier unterhalten sich wieder die Freunde des gepflegten Vorurteils.

Nur mal so nebenbei: Bei vielen Implementationen wird malloc und new über exakt die gleichen Funktionen realisiert. Der Speicheranforderungsteil ist also exakt gleich schnell. Wenn man dann natürlich gleich noch Birnen (new-operator = Speicheranforderung + Objektkonstruktion + Speicherfreigabe im Falle einer Ctor-Exception) mit Äpfeln (malloc = Speicheranforderung) vergleicht, erhält man am Ende natürlich schnell Schimpansen.

Auch das ein vector langsamer ist als ein dynamisches Array ist in der Regel nicht richtig. Abhängig vom Inhalt kann ein vector deutlich schneller sein, als ein dynamisches Array. Packst du Objekte in ein Array hast du zwangsläufig Standard-Konstruktion + Zuweisung. Wohingegen beim vector eine direkte Initialisierung möglich ist. Arbeitest du auf der anderen Seite nur mit PODs, dann kann ein dynamisches Array natürlich Geschwindigkeitsvorteile bringen. Gleichzeitig erkaufst du dir die aber natürlich mit einer höheren Programmkomplexität (eigenes Memory-Mamangement) und häufig auch mit einer reduzierten Robustheit (Stichwort: Exceptionsicherheit).

Mir ist das malloc viel lieber, da man da mehr Freiheiten am Speicher hat.

Das ist z.B. nicht richtig. malloc ist eine globale Funktion, die sich nur schwer ersetzen lässt. Den operator new (zur Anforderung von Speicher) hingegen kannst du auf vielen verschiedenen Ebenen überladen und damit speziell an deine Bedürfnisse anpassen.

Weiterhin ist mir ein Geschwindigkeits unterschied zwischen malloc und z.B.
Vector aufgefallen, welcher mich bei Zeitkritischen Sachen immer zu malloc treibt.

Mir ist letztens auch der Geschwindigkeitsunterschied zwischen Birnen und Bienen aufgefallen. Während die Birnen nur faul rumliegen, sind die Bienen schon längst wieder zu Hause.
Wie? Birnen sind gar keine Insekten?
malloc ist eine Funktion zur Anforderung von Speicher. Das wars. vector hingegen ist eine intelligente Klasse zur Verwaltung von Objekten. Inklusive Größen- und Resource-Management. Das ist wohl nicht so ganz das gleiche.

Mir scheint einige wollen nicht einsehen, dass Optimierungen nicht Kontextunabhängig sind. Ein Programm wird nicht dadurch schneller, dass man es in Assembler, C oder C++ schreibt. Es wird auch nicht schneller durch das Ersetzen von new durch malloc. So einfach ist es leider nicht.
Bevor man sich also den Kopf über vermeintlich zeitkritische Dinge zerbricht, sollte man sicherstellen, dass man den Kontext genau kennt, in dem man sich gerade befindet.

[Bashar]

wie war die Grundregel ... erst messen, dann optimieren? Also ich kann hier meßtechnisch keine signifikanten Unterschiede zwischen new und malloc feststellen, mal ist das eine ein wenig schneller, mal das andere. Ich mache alloziere 1000 mal Platz für 500 ints, gebe das wieder frei, und mach das ganze 1000 mal. Dauer schwankt sowohl bei malloc als auch bei new zwischen 1.3 und 1.6 Sekunden im Userspace, etwa 3.7 Sekunden im Kernel.

new macht ne ganze menge mehr.

Effektiv nicht. Wenn du PODs allozierst, macht new das gleiche wie malloc. Wenn du nicht-PODs allozierst, ruft es die Konstruktoren auf. malloc tut das zwar nicht, aber wenn du die Objekte dann benutzen willst, mußt du sie von Hand via placement-new konstruieren.

[Helium]

Mir ist das malloc viel lieber, da man da mehr Freiheiten am Speicher hat.

Klar also vergleichen wir mal die Folgenden beiden Zeilen

void * foo = malloc (100);
void * bar = ::operator new (100);

@daishi:
Ich sehe grade den Unterschied nicht, aber du kannst ihn mir sicher erklären.

[daishi]

@Helium
Zeig mir mal bitte wie ich das mit new einfach machen kann.

int n=5;
int *feld;
feld=(int*)malloc(n*sizeof(int));
feld=(int*)realloc(feld,2*n*sizeof(int));

Es sollte Dir klar sein, daß zu malloc noch realloc, free, calloc ... gehören.
Bei new habe ich nur noch delete.

[Walli]

Und dir ist sicher auch klar, dass man sich ganz einfach ein Realloc für C++ schreiben kann und dass man malloc-Rückgabewerte nicht casten sollte?

[daishi]

Wenn man unter Windows Programme schreibt, ist es sicherer die Rückgabewerte zucasten.
Wegen der implementation von realloc, man kann das Rad auch neu erfinden.

[Artchi]

@daishi! Ich habe nie C gelernt, bin gleich in C++ eingestiegen - kenne mich mit malloc etc. nicht aus. Aber selbst ich sehe, das ein realloc doch den alten Speicherbereicht auf den feld zeigt, umkopieren muß, oder? Wenn es diesen nicht umkopiert, dann muß ich sagen, kann realloc zaubern. Ich kann dein Bsp. jetzt nicht ausprobieren, aber nach dem realloc zeigt feld sicherlich auf einen anderen Speicher, oder?

Jetzt willst du uns doch nicht erzählen, das das umkopieren eines Arrays über C schneller geht, als über ein new in C++ (welches überigens die gleiche Strategie fährt). Nur schlauerweise mache ich das mit std::vector, welches mir den ganzen Krempel von alleine re-newed (oh mein Gott, was für ein Wort - sorry), ohne das ich mich darum kümmern muß. Ganz davon abgesehen, das ein vector tausendmal sicherer ist und ich nicht in einen ungültigen Bereich schreiben kann.

[Helium]

int n=5; 
int *feld; 
feld=new int [n]; 
{
   int * temp = feld=new int [2*n]; 
   std::copy(feld, feld + n, temp);
   delete [] feld;
   feld = temp;
}

Natürlich in 'ne Funktion packen und fertig.

[Walli]

Hab was ähnliches mit memcpy gebastelt.

template<typename T>
	T* reallocpp(T* ptr, size_t oldsize, size_t newsize)
{
  T* rval = new T[newsize];
	memcpy(rval, ptr, oldsize * sizeof(T));
	delete[] ptr;
	return rval;
}

int main(void)
{
	int* x = new int[12];
	x[11] = 100;
	x = reallocpp(x, 12, 16);
	int c = x[11];
	x[15] = 1;

	return 0;
}

[daishi]

Artchi schrieb:

Jetzt willst du uns doch nicht erzählen, das das umkopieren eines Arrays über C schneller geht, als über ein new in C++ (welches überigens die gleiche Strategie fährt). Nur schlauerweise mache ich das mit std::vector, welches mir den ganzen Krempel von alleine re-newed (oh mein Gott, was für ein Wort - sorry), ohne das ich mich darum kümmern muß. Ganz davon abgesehen, das ein vector tausendmal sicherer ist und ich nicht in einen ungültigen Bereich schreiben kann.

Das realloc intern das Feld umkopiert steht außer Frage, aber die Bemerkung mit dem Vector hättest Du Dir sparen können, da ein paar Beiträge vorher schon geklärt wurde, das ein Vector bei Größenveränderungen zu langsam ist.

[Helium]

Wie wäre es eigentlich sich new einfach zu überladen, um eben diese aufgabe zu erledigen? Ich würde allerdings zu std::copy statt std::memcpy greifen, da man auch nicht-PODs verwenden könnte. Man kann ja nachher auch mit Traits optimieren, os dass bei PODs std::memcpy verwendet wird.

[Helium]

Das realloc intern das Feld umkopiert steht außer Frage, aber die Bemerkung mit dem Vector hättest Du Dir sparen können, da ein paar Beiträge vorher schon geklärt wurde, das ein Vector bei Größenveränderungen zu langsam ist.

Dann habe ich es nicht mitbekommen. Könntest du nochmal Zitieren, was genau du meinst. Wenn es um schnelle Größenänderungen geht, geht wohl nichts über verkettete Listen. Alles, was Vektoriell ist, ist viel zu lahm.

[daishi]

@Helium

RHBaum schrieb:

@MaSTaH

malloc/realloc/free ist C. In C++ verwendet man new/delete. Wenn man dynamisch langen Speicher braucht nimmt man kein realloc sondern einfach einen vector.

Wenn es um zeitkritische sachen geht, fliegst aber mit Vector auf die Nase ! Vector ist nun mal saulangsam, wenn es um Groessenaenderungen geht. Viele weichen aus dem Grunde auf C in solchen faellen aus.
das selbe ist mit new. new und malloc kannst ned vergleichen. new macht ne ganze menge mehr. Deshalb ists auch wirklich langsamer. Bei zeitkritischen sachen kann man auch dann auch wieder auf malloc ausweichen.
Es gibt in der Literatur auch Themen die sich mit dem Optimieren von C++ beschaeftigen, dort werden zum beispiel die new/delete operatoren von atomaren Klassen ueberschrieben und mit malloc realisiert, Gerade bei kleinen und vielen objekten bringt das nen performance boost.

Aber pronzipiell hast Du Recht, solchen "Schmutz" sollt man nur machen, wenn mans wirklich braucht. Lieber auf 3% Prozessorlast verzichten, dafuer sichereren und wiederverwertbareren code schreiben ... Dein projektmanager wird dirs danken :p

Ciao ...

Diesen Beitrag meinte ich, wenn du weiter im Forum suchst, findest Du auch eine genauere Beschreibung.
Du kannst die aber auch mal die Implementierung des Vectors ansehen, da wirst Du dann auch schlau.

[Bashar]

MaSTaH schrieb:

dass man malloc-Rückgabewerte nicht casten sollte?

Was erzählst du? Man *MUSS* malloc-Rückgabewerte in C++ casten, da es keine implizite Konvertierung von void* auf andere Pointertypen gibt.

daishi schrieb:

da ein paar Beiträge vorher schon geklärt wurde, das ein Vector bei Größenveränderungen zu langsam ist.

Es wurde behauptet, nicht geklärt.

[Artchi]

daishi schrieb:

aber die Bemerkung mit dem Vector hättest Du Dir sparen können, da ein paar Beiträge vorher schon geklärt wurde, das ein Vector bei Größenveränderungen zu langsam ist.

Ehem, behaupte ich etwa das ein vector langsamer als ein realloc ist??? Nö! Wie von mir bereits gesagt, steht in der Impelmetierungs-Vorgabe zur STL, das es keinen Performance-Verlust geben darf. Denn sonst macht das ganze keinen Sinn, die STL zu verwenden. In jedem STL-Buch und im Buch von Bjarne Stroustrup steht dies unmissverständlich drin.

Bjarne Stroustrup schrieb:

Most of these techniques are criticized unfairly for being inefficient. The assumption is that if it is elegant, if it is higher level, it must be slow. It could be slow in a few cases, so deal with those few cases at the lower level, but start at a higher level. In some cases, you simply don't have the overhead. For example, vectors really are as fast as arrays.

Quelle: http://www.artima.com/intv/goldilocks.html

Du kannst ja gerne Bjarne Stroustrup widersprechen.

Ich kann das Interview nur empfehlen, vorallem die erste Seite passt zu diesem Topic wie die Faust aufs Auge!

[daishi]

@Artchi
Da steht doch nur, da ein Vector genauso schnell wie ein Array ist.
Über den Aufwand, der für die Speicherallocierung nötig ist steht da nichts.

Ich habe mich ja auch nicht über die Geschwindigkeit des Vectors allgemein ausgelassen, sondern nur über die beim ver-größern/kleinern der Elementanzahl.

Aber gut. (und aus)

[RHBaum]

vorallem die erste Seite passt zu diesem Topic wie die Faust aufs Auge!

Genau, und was in den Buechern ned steht, ist der Zusammenhang wischen implementationsdetails und der Geschwindigkeit ...

Ok, bevor wir uns darueber den kopp einschlagen, sollte man das Getreu Bashar's Grundregel erst mal messen ...

Schreib nen Programm, das nen vector von nem anfang von 1000 elementen vom Typ int .... in 10er schritten auf 100000 erhoeht ... und dann wieder erniedrigt, so oft, bist laufzeiten im sekundenbereich bekommst, um gescheit messen zu koennen.

Dann ersetzt den vector durch nen Array, mit dem genau das selbe machst, von 1000 anfangen, in 10er schritten erhoehen , und wieder runter auf 1000.
Dabei das umkopieren der Werte nicht vergessen, die muessen ja gleich bleiben ...

Ich schatze mal genau hier wird Bashar dann zwischenrufen -> bei mir machts kaum nen unterschied ! :p
Aber teste es mal mit der M$ Impl, und dann ersetz die mal durch den STLport ...
Und es wird sogar ein oder mehrere Implementationen geben, wo der Vector enorm schneller ist als die Array Variante. (Dafuer aber im Zugriff auf die elemente selber etwas langsamer ) !!!

Ich denke die Unterschiede fallen ned so gravierend aus ... aber ich behaupte es gibt sie ... (u.a. nutze ich deswegen den stlport)

steht in der Impelmetierungs-Vorgabe zur STL, das es keinen Performance-Verlust geben darf.

Aehm, warum gibts bei den Implementierungen dann unterschiede ? Wenn alle Implementierungen gleich sind, warum gibts dann unterschiedliche Implementierungen ? Wenn sich keiner an die Statdards haelt ... ists dann nen wunder das sich die Standards net wie gewuenscht verbreiten ???

Vector ist eh nen eigenes Problem. Das Problem liegt eigentlich im Komfort. Die leute nehmen Vector, weil sie zu "bequem" sind, ist ja auch ok, dafuer isser ja auch da ...
Dann stellens fest, das ihre SW zu lahm ist, und merken, das bei ihrem Vector ne ganze Menge CPU Waerme verbraten wird. Aber anstatt weiter zu ueberlegen, und den Vector zu optimieren, sprich ihm die Zuegel aus der Hand zu nehmen, wenns um die Groessenanpassung geht, steigens lieber gleich auf Arrays um.

So ist leider die Praxis. Die Leute, die die Container falsch einsetzen, statt ner Liste nen vector nehmen etc. noch gar nicht zugerechnet.

Mit dem Geschwindigkeitsunterschied von Array und Vector duerften sich eigentlich nur Leute rausreden, wo es wirklich um auf jeden rechentakt ankommt. Treiber werden eh fast nur in C geschrieben, SW fuer kleinere Microcontroller aus aehnlichen gruenden auch ...
Also sollte man sowas in erwaegung ziehen, wenn es um frameraten geht ... sonst eher nich ...
Wobei es dann immer noch eine Erwaegung wert ist, den zeitkritischen Anteil in ne eigene Lib auszulagern und die komplett in C zu schreiben ...

Ciao ...

[Walli]

Bashar schrieb:

Was erzählst du? Man *MUSS* malloc-Rückgabewerte in C++ casten, da es keine implizite Konvertierung von void* auf andere Pointertypen gibt.

Mir ist schon klar, dass es in C++ sonst nicht geht (ganz im Gegensatz zu C, wo dies implizit geschieht). Wie denn auch? Ich meinte nur, dass man in C++ in jedem Fall malloc vermeiden sollte, weil es unsicher ist von void* nach X* zu casten. Das sind nämlich Stellen an denen man leicht auf die Schautze fällt. Ich meine das auch in den Stroustrup FAQ gelesen zu haben. Ich lasse mich aber gerne eines besseren belehren, wenn jemand den Beweis antritt, dass malloc wirklich so viel schneller als new ist, wie behauptet wird.

[Bashar]

Das ist ja ein anderes Thema. Klar sollte man malloc meiden. Aber wenn man es benutzt, dann muss man casten.

[Walli]

Ok, ist vielleicht nicht ganz rüber gekommen .