32Bit unter 64Bit OS, Speicherverbrauch, Aliasing
-
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.
