32Bit unter 64Bit OS, Speicherverbrauch, Aliasing
-
Hehe lustig, ich versteh nur Bahnhof bei deinem Post
Ich schieb's mal auf die Uhrzeit..unskilled schrieb:
zu aller erst mal:
Speicherverbrauch
Bestimmt nicht, weil die Vektor-Größe (die jedes Mal neu berechnet wird!!!) einen größeren Wertebereich hat... size () sollte vereinfacht in etwa so aussehen:
template <class T> size_type std::vector <T>::size () const { size_type R (0); for (std::vector <T>::const_iterator i (begin ()), e (end ()); i != e; ++i, ++R); return R; }Welchen quote meinst du? ich versteh die Antwort nicht weil ich die Frage nicht kenne
Was size() aussagt weiss ich doch, die Anzahl Elemente die ich ansprechen kann.unskilled schrieb:
LudiKalell schrieb:
Zudem wüsst ich gern ob ein Set wie ein Vector eine Art Buffer benutzt, nehms aber mal nich an sonst würde wohl eine capacity() Funktion vorhanden sein
MSDN schrieb:
template<class _TYPE, class _A>
size_type vector::capacity( ) const;Ich hab mal den von dir ausgelassenen Teil meiner Frage wieder eingefügt
Ich weiss dass Vector capacity besitzt, sonst würde ich nicht schreiben "ich nehmes es aber nicht an sonst würde (bei set) wohl eine capacity funktion vorhanden sein". Es ging mir um set. Aber das hat sich eh erledigt, hab nochmal drüber nachgedacht.unskilled schrieb:
LudiKalell schrieb:
Und wenn es irgendwie geht bringt das bei 64 Bit Systemen was oder verbraucht dort ein set<32 Bit Typ> durch Aliasing eh quasi den Speicher eines 64Bit sets?
(auch wenn ich nicht glaube, dass das iwie geht)
nein, es würde denke ich nicht sehr viel bringen - das wurde glaube schon mal diskutiert (da gings glaub um short vs int - aber is ja das gleiche)
Gut das hab ich verstanden.
unskilled schrieb:
LudiKalell schrieb:
Ich frage weil meines Wissens nach durch Aliasing die theoretische Grösse von
sizeof(value_type) * foo.size() überschritten wirdversteh ich nicht
1. was willst du damit rausbekommen? Oo Meines Wissens wird der Index der Einträge nirgendwo gespeichert...
2. nat. könnte da die Größe überschritten werden... - immer, wenn foo.size () größer ist, als value_type::max / sizeof (value_type)Vielleicht undeutlicher Code. Ich weiss wie groß ein Element eines sets sein sollte(sagen wir 12 Byte, ein struct). Ich weiss es gibt Aliasing, das OS will also, und da bin ich mir nicht sicher, Sachen in 8, 16 oder 32 , vielleicht sogar 64Bit Abständen anordnen, und wie gesagt mir geht es auch hauptsächlich um 64 Bit Systeme. sizeof() liefert zur Compilezeit ja die Grösse, zB 12 Byte. Wenn ich nen zB nen vector v hätte, mit 8 Elemente, dann wäre size() == 8, sizeof(v[0])==12. Glaub ich zumindest.
Das heisst aber mitnichten dass der vector 8*12 Byte groß sein muss, vielleicht ist er ja 8*16 groß, und genau darum geht's hier
Ich will EINFACH nur die Anzahl byte die die gesamte Datenstruktur belegt.unskilled schrieb:
aber kannst ja so was machen:
unsigned long long size = static_cast <unsigned long long> (sizeof (value_type)); size *= foo.size();wenn du denkst, dass du mehr, als 18 * 10^18 Byte belegst, dann nimm halt float oder gleich double ^^
Jo genau das hab ich oben geschrieben und wegen Aliasing funzt das nich. Weil du damit das padding nicht betrachtest. Zumindest ist das meine Annahme.
unskilled schrieb:
Falls du so was meinst:
std::vector <size_t>;und willst unbedingt nen 32bit großen typen dort musst du halt
std::vector <unsigned __int32>; //zumindest der MSVC kann das : )nehmen
bb...Nope __uint32 kennt der gnu Compiler nicht, deswegen das "plattformübergreifende", ich programmiere unter 32Bit Linux, auf dem Cluster haben wir zB 64Bit Solaris. Aber danke für die Mühe, ich weiss es zu schätzen
-
LudiKalell schrieb:
Nope __uint32 kennt der gnu Compiler nicht
Dafür kennt er aber uint32_t.
-
Subbi.. und da gcc quasi überall läuft wär das ne Lösung, danke. Muss zugeben das hätt ich mit Fleiss auch rausbekommen sollen. Aber nun nochmal zu dem interessanten, der Aliasingsache.. irgendeine verlässliche Speichermessung, evtl. auch über externe Profiling tools bzw. wie machen das die Profis wenns hart auf hart um Speicherersparnis geht. Denn wenn ich zB bei mir in nem struct nen double in ein float verwandle und dann noch nen size_t in nen unsigned short.. tja, die sizeof() verändert sich genau 0.. wtf?
Hab da mal was aufgeschnappt dass man struts und Klassen auffüllen soll ("padding") so dass man genau auf zB 32 Bit kommt oder nen Vielfaches davon. Wäre die Frage ob das, wenn die STL Container eh partout die Sachen auf nen vielfaches von zB 16 oder 32 auffüllen, Sinn macht und wenn ja obs Performance bringt. Ist quasi das was die STL Implementation da macht quasi genau dasselbe aus diesem Grund?
-
Aliasing is was anderes.
Was du meinst ist Alignment.
Und nein, das ist in dem Fall kein Problem. Wenn es einen 4 Byte Typen gibt, dann ist sizeof() von dem genau 4 Byte (kann auch numerisch auch "1" sein wenn char z.B. schon 4 Byte gross wäre), und sizeof muss das Alignment schon beinhalten. Sonst würden Arrays z.B. nichtmehr funktionieren.z.T. set<uint32_t>: lol rofl rofl lol rofl
Dir ist schon klar dass viele malloc Implementierungen bis zu 2 Pointergrössen Overhead haben pro Allokation. Und dass set<> nochmal zusätzlich Overhead mitbringt. Nimm einen std::vector<uint32_t> und sortier den, dann kannst du binär suchen da drinnen.
-
hustbaer schrieb:
Aliasing is was anderes.
Was du meinst ist Alignment.Ich schieb's auf die Uhrzeit..
hustbaer schrieb:
Und nein, das ist in dem Fall kein Problem. Wenn es einen 4 Byte Typen gibt, dann ist sizeof() von dem genau 4 Byte (kann auch numerisch auch "1" sein wenn char z.B. schon 4 Byte gross wäre), und sizeof muss das Alignment schon beinhalten. Sonst würden Arrays z.B. nichtmehr funktionieren.
Hrmm gut zu wissen. Darum gings mir.
hustbaer schrieb:
z.T. set<uint32_t>: lol rofl rofl lol rofl
Dir ist schon klar dass viele malloc Implementierungen bis zu 2 Pointergrössen Overhead haben pro Allokation. Und dass set<> nochmal zusätzlich Overhead mitbringt. Nimm einen std::vector<uint32_t> und sortier den, dann kannst du binär suchen da drinnen.
ololol roflmao! Ok und wo kann ich das nachlesen? Hätte das gern genauer, vor allem leuchtet mir nicht ein
a) warum set 2 Pointergrössen mehr brauchen soll
b) wodurch der Speicheroverhead bei set verursacht wird.. ist map besser? glaub's ja nicht.Ich meine ein set ist im Endeffekt nichts weiter als ein ständig sortiert gehaltener Vektor. Da der Vektor definitiv Alignment verwendet.. wieviel grösser ist denn dann set?
-
LudiKalell schrieb:
Ich meine ein set ist im Endeffekt nichts weiter als ein ständig sortiert gehaltener Vektor.
Da täuschst du dich. Vektor speichert seine Elemente intern als Array, also nacheinander im Speicher. Set hingegen ist sehrwahrscheinlich ein binärer Baum.
-
Gut den Grössenunterschied müsste man dann ja angeblich folgendermassen berechnen können:
set<int> s; vector<int> v(10); for( ....... // fülle set mit 10 werten cout << sizeof(*s.begin()) * s.size() << " ist byte Grösse von set und " << sizeof(*v.begin()) * v.size() << " ist die theoretische Grösse von v, aber tatsächlich wird von v "<<sizeof(*v.begin()) * v.capacity())<< " bytes belegt."<<endl;Na dann schaun wir mal.. wenn jetzt jemand meint "nö so kann man die Grösse von set nicht berechnen" dann bitte: wie geht's?
-
LudiKalell schrieb:
dann bitte: wie geht's?
Das lässt sich nur mit Kenntnis deiner Implementierung beantworten.
Ein Knoten in einer Set-Stuktur kann z.B. so aussehen (red/black tree):
template <typename T> struct Node { T t; Node* left; Node* right; bool color; }
-
Na dann schaun wir mal.. wenn jetzt jemand meint "nö so kann man die Grösse von set nicht berechnen"
Genau. So kann man den Speicherverbrauch wirklich nicht berechnen, was du da berechnest sind Hausnummern.
dann bitte: wie geht's?
Garnicht.
Ok und wo kann ich das nachlesen?
Pfuh, was weiss ich? Sowas weiss man halt
Hätte das gern genauer, vor allem leuchtet mir nicht ein
a) warum set 2 Pointergrössen mehr brauchen soll
b) wodurch der Speicheroverhead bei set verursacht wird.. ist map besser? glaub's ja nicht.a) hab ich nie geschrieben. ich hab geschrieben malloc (nicht std::set) braucht MEIST BIS ZU 2 pointergrössen mehr. genauer: oft ist das was minimal angefordert wird 2*sizeof(void*), auch wenn du bloss "new char" sagst.
allerdings nicht jede implementierung macht das, es gibt durch aus allokatoren die bei "new char" mit einem byte (+ minimalem overhead, vielleicht 1 byte auf overhead 100 angeforderte) auskommen.
b) durch die zeiger die verwendet werden um den red-black tree der sogut wie überall verwendet wird zusammenzuknoten. set muss bestimmte garantien erfüllen die sich mit einem vektorisierten baum AFAIK nicht erfüllen lassen (was komplexität gewisser funktionen angeht und die iteratoren spielen auch mit rein). kann mich aber auch täuschen. guck einfach in deine STL implementierung rein, dann siehst du ja wie es implementiert ist.
-
"40 ist byte Grösse von set und 40 ist die theoretische Grösse von v, aber tatsächlich wird von v 40 bytes belegt." Muss ich dir wohl recht geben.
hustbaer schrieb:
dann bitte: wie geht's?
Garnicht.
Ok und wo kann ich das nachlesen?
Pfuh, was weiss ich? Sowas weiss man halt
is halt schwer zu beweisen dass es etwas nicht gibt
Ne Quelle wär mir lieber..
Kommt Leute, es kann doch nicht unmöglich sein den Speicherverbrauch eines sets zu bestimmen.. das wär irgendwie wie das tappen im dunkeln.edit: schonmal meinen Glauben betreffend präventiv gefragt: kennt jemand eine Art "effizienteste" Binärsuche? Ich meine so richtig schnell, das Ding kann ich auch schreiben ohne Rekursion mit while schleife, ist halt die frage ob compilertechnisch irgendwas besonders effizient ist oder irgend eine Bibliothek was effizientes schon anbietet.
-
Kommt Leute, es kann doch nicht unmöglich sein den Speicherverbrauch eines sets zu bestimmen..
Doch. Zeig mir die Stelle im Standard wo steht wie es geht, und ich fress nen Besen. Du kannst ja nichtmal bestimmen wieviel Speicher "new char[1]" braucht, wie willst du dann den Speicherverbrauch von soetwas wie einem std::set bestimmen?
Du hast da einfach ganz falsche Vorstellungen.das wär irgendwie wie das tappen im dunkeln.
Ja. Und?
kennt jemand eine Art "effizienteste" Binärsuche? Ich meine so richtig schnell, das Ding kann ich auch schreiben ohne Rekursion mit while schleife, ist halt die frage ob compilertechnisch irgendwas besonders effizient ist oder irgend eine Bibliothek was effizientes schon anbietet.
Eine binäre Suche ist eine binäre Suche, da gibts nix zu drehen. Wenn man nicht extra Zeit verschwendet wird eine Implementierung so schnell sein wie die andere. Nimm einfach std::binary_search.
Und zum wahrscheinlich 10. mal heute: premature optimization is the root of all evil in programming.
-
hustbaer schrieb:
Kommt Leute, es kann doch nicht unmöglich sein den Speicherverbrauch eines sets zu bestimmen..
Doch. Zeig mir die Stelle im Standard wo steht wie es geht, und ich fress nen Besen. Du kannst ja nichtmal bestimmen wieviel Speicher "new char[1]" braucht, wie willst du dann den Speicherverbrauch von soetwas wie einem std::set bestimmen?
Wir müssen hier nicht esoterisch werden, ich weiss genau dass nen char aufm Cluster 1byte ist und auf meiner Kiste ebenso. Eine Zahl die das vielfache des chars angibt würde mir "schon reichen".
Du hast da einfach ganz falsche Vorstellungen.
Vielleicht. Du verstehst mich glaube ich Falsch. Mir geht es nicht um eine Formel, sonder um eine Methode die Grösse herauszubekommen. Ich hab die Vorstellung dass:
- irgendwer unter den ganzen Pros das Problem mal hatte und ne Lösung gefunden hat, und der gerade das liest; unglaublich aber wahr, so funktioniert das ganze Forum hier, Erfahrung; und nein deine Erfahrung alleine reicht mir nicht wenn nur ein "das weiss man einfach" kommt
- dass es evtl. Speicher profiling tools gibt die sowas messen können (valgrind etc. pp.)
- dass irgendwelche pros nix dem Zufall überlassen und zumindest nen Speicherverbrauch in O Notation kennen bzw. dann nich drauf rumhacken sondern nach ner Lösung mitsuchen
- ...Ja. Und?
Ich muss vorher wissen wieviele Elemente ich für den Algo nutzen kann bevor der Speicher voll ist. Der Algo allokiert nur einmal anfangs. Ein Teil meiner Ergebnisse für die Diplomarbeit ist die Angabe bis zu welchem n der ganze Kram in den Speicher passt damit ich im Umkehrschluss bestimmen kann welche Problemgrösse lösbar ist auf unserem Cluster. Je nach Zeit die mir bleibt hab ich Zeit das alles nochmal für Vektor umzuschreiben bevors auf den Cluster geht, sonst bleibt's beim set, jeder Run aufm Cluster dauert ca. nen Tag. Und ich steh unter ziemlichem Zeitdruck. Das war die extralange Antwort zu deinem netten, ernstgemeinten, unrhetorischen "Und?".
Eine binäre Suche ist eine binäre Suche, da gibts nix zu drehen. Wenn man nicht extra Zeit verschwendet wird eine Implementierung so schnell sein wie die andere.
....
Nimm einfach std::binary_search.
Danke.
Und zum wahrscheinlich 10. mal heute:
Drückt wohl aus dass dir das tierisch aufn Sack geht, ich trink dann meistens Tee, entspannt die Nerven.
premature optimization is the root of all evil in programming.
Mir fehlt da der Zusammenhang, erklär mal bitte. Meines Verständnisses nach wird mein Speicherverbrauch mit nem vector statt set + binärer Suche doch geringer, demzufolge der Algo besser.
"premature" ist da auf den ersten Blick nix.
-
LudiKalell schrieb:
Vielleicht. Du verstehst mich glaube ich Falsch. Mir geht es nicht um eine Formel, sonder um eine Methode die Grösse herauszubekommen.
Hast du meinen Beitrag gelesen?
Wenn du es für deinen konkreten Compiler auf deiner konkreten Plattform mit deiner konkreten STL-Implementierung wissen willst -
dann öffne den Header deiner STL-Implementierung und schaue dir an, wie set und vector implementiert sind. Daraus kannst du mit entsprechendem Aufwand 100% exakt ableiten, wieviel Speicher ein set allokieren wird.
Als Faustregel kannst du rechnen (machen viele Implementierungen so):
vector: 3 * sizeof(pointer) [start, end, end_of_storage] + capacity * sizeof(T)
set: size [# elemente] * (sizeof(T) + 2 * sizeof(pointer) [+ je nach implementierung z.b. + sizeof(bool)])Das ist eine ganz grobe Abschätzung nach meinem Kenntnisstand über einige Implementierungen und nicht durch den C++-Standard garantiert. Wie gesagt, wenn du es exakt wissen willst, führt dich kein Weg an deiner STL-Implementierung vorbei.
-
Jupp danke, werd's dann mal rausfinden und hier posten. Ja ich hatte deinen Post gelesen aber auf was konkreteres gehofft. In den header schaun ist nunmal der letzte Schritt, obwohls eigentlich offensichtlich ist und wohl der erste sein sollte. lazy me..
-
Anders geht es leider nicht. Und die Antwort ist weder portabel noch allgemeingültig. Du solltest daran denken, dass insbesondere die Node-Strkturen des sets noch ein Aliasing verpasst bekommen, also real größer sein können als die Summe der Größen ihrer Elemente.
