schnellste Vergleichsmöglichkeit für 32stellige Zahlen
Hallo,
eine sehr allgemeine Frage: Was geht schneller? Einen String oder eine Zahl auf Gleihcheit zu prüfen?
In meinem Programm müssen ca. 32 stellige Zahlen - /Strings wie z.b. 102132 .... verglichen werden.
Vielen Dank
Oliver
Hallo Teletabi,
für 32-stellige Zahlen gibt es in .NET keinen vordefinierten Datentyp. Daher erübrigt sich die Frage eigentlich gleich wieder.
herbivore
Wenn man beide zahlen als strings vorliegen hat, müsste man ja beide erst umwandeln.
Also müsste es,wenn man es geschickt macht direkt im string schneller gehen. Wenn man die zahlen binär vorliegen hat, geht es binär natürlich schneller. Aber das vergleichen von zahlen dauert eh nicht besonders lange. Wenn duu mit den zahlen weiterrechnen willst, musst du so oder so in binär umrechnen.
Zahlen in strings vergleichen:
- vorzeichen prüfen und abbrechen, falls vorzeichen unterschiedlich.
- anzahl der ziffern vor dem komma vergleichen und abbrechen, falls unterschiedlich. führende nullen und sonderzeichen dabei nicht mitzählen und ignorieren.
- ziffer für ziffer vergleichen, beginnend mit der höchstwertigen (z.b. der "1" in 1.000.000,002) alles außer ziffern dabei ignorieren.
Stichwort BigInteger.
Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...
ok, aber was ist denn jetzt nun scheller? der vergleich als string oder als zahl?
Hallo Teletabi,
als was für eine Zahl? Ich habe ja oben schon auf einen gewissen Problematik hingewiesen.
herbivore
wie lang weiß ich noch nicht endgültig, aber eigentlich hat die zahl nicht mehr als 20 stellen (hab grad noch mal genau nachgerechnet 😉 )
Hallo Teletabi,
dann könntest du decimal verwenden. Es ist davon auszugehen, dass ein Vergleich eines decimals (ca. 12 Byte), schneller ist als ein Vergleich von zwei Strings (ca. 40 Bytes, bei einer 20 stelligen Zahl).
herbivore
Beim string kommen sogar noch mehr Bytes dazu, der braucht schon mal 4 Byte um überhaupt zu wissen, dass er ein string ist und nochmal vier Byte, um die Länge zu speichern. Ich hab mir sogar sagen lassen, dass string so implementiert ist, dass er nochmal weitere 4 Byte verbrät (vorgehaltenes Array?), macht also summa summorum 52Byte.
Aber eben 52Byte auf dem Heap, bei decimal sind es 12Byte auf dem wesentlich schnelleren Stack (bei strings muss man ja erst an die entsprechende Speicheradresse gehen und da die Sachen nachschlagen, bei decimals sind die Daten schon da, wo man sie braucht), das macht imho den Hauptunterschied.
Hallo onlinegurke,
was einen gewissen Overhead bei Strings angeht, hast du recht. Deshalb schrieb ich ja auch ca. 40 Bytes. 😃
Was aber die Einschätzung angeht, dass der Zugriff auf den Heap deutlich langsamer ist als auf den Stack, kann ich nicht zustimmen. Wenn man die Adresse der Daten hat, ist es egal, ob das eine Adresse ist, die auf den Heap oder auf den Stack zeigt. Der Zugriff ist gleich schnell. Natürlich benötigt man bei Zugriff auf Referenztypen ein Indirektionsstufe mehr. Das macht aber bei den in der Praxis vorkommenden Zugriffen keinen wesentlichen Unterschied. Schon gar nicht sollte man sich jetzt dazu verleiten lassen, immer struct statt class zu verwenden, nur weil man fälschlicherweise denkt, das dadurch die Programm wesentlich schneller würden. Das ist nicht der Fall.
herbivore
eine zahl vom 10 ins 2ersystem umszwandeln, nur um sie zu vergleichen, ist aber auch ein ganzschöner overhead. In umgekehrter Richtung narürlich noch extremer.
Immer Strukturen statt Klassen zu verwenden ist mit Sicherheit Blödsinn, auch von der Geschwindigkeit her, keine Frage.
Aber was den Zugriff angeht, sicherlich ist der Unterschied weniger als marginal, aber auf der anderen Seite, selbst die kompletten Strings zu vergleichen brauch, naja, wie lange so ein Rechner so halt braucht um ganze 52Byte zu vergleichen. Wir reden hier also irgendwo schon von extrem geringen Zeiten, da macht das meiner Meinung nach schon einen Unterschied, ob die Variablen dann noch in den Stack kopiert werden müssen, oder nicht.
Aber eigentlich ist es egal, weil wir glaub ich einfach festhalten können, dass Decimals vergleichen auf alle Fälle kürzer dauert als Strings zu vergleichen. Wenn man aber die Zahlen wirklich als String hat und die sonst nicht braucht, dann wird es wirklich wie floste sagt schon schneller sein direkt einen Stringvergleich zu machen (evtl mit Nullen wegtrimmen).
Hallo onlinegurke,
da macht das meiner Meinung nach schon einen Unterschied, ob die Variablen dann noch in den Stack kopiert werden müssen, oder nicht.
müssen sie doch gar nicht. Allenfalls müssen die Werte in Register kopiert werden. Dabei ist es aber egal, ob die Werte aus dem Heap oder von Stack kommen. Beides ist normaler Hauptspeicher.
herbivore
Hi,
der Ergänzung halber, hier ein paar Erklärungsversuche, warum der Zugriff auf Stack-Variablen doch schneller sein könnte als auf Heap-Variablen.
Wegen des Caching-Verhaltens der CPUs liegt der Stack höchst wahrscheinlich im CPU-Cache. Somit ist ein Zugriff wesentlich schneller (da der Wert eben schon im schnellen Cache ist und nicht meht vom langsameren DRAM geholt werden muss)
Weil nun das "holen" aus dem RAM über unterschiedliche Op-Codes geschieht und wir hier eine unterschiedliche Indirektionsstufe haben.
Greifen wir auf Variablen auf dem Stack zu, so erfolgt der Zugriff wahrscheinlich über:
([Aktueller Stackpointerwert + Offsest]) und der Stackpointer liegt schon in einem CPU-Register. Somit müssen wir als CPU, um den Wert zu holen, zwar erst noch eine Addition/Subtraktion ausführen aber insgesamt dann nur genau eine Speicherzelle abfragen. (Der Speicherzugriff ist aber das eigentlich langsame)
Greifen wir auf eine Variable auf dem Heap zu, (Wir haben also einen Zeiger/Referenz auf einen Wert im Heap) dann müssen wir das wohl über:
([[Zeiger]]) machen. Also als CPU erst den Wert des Zeigers (der wahrscheinlich als Variable auf dem Stack liegt) aus dem RAM holen und daraufhin den Wert von der Stelle holen, auf den der Zeiger nun zeigt. (wir haben also zwei Zugriffe)
(in weiteren Zugriffen liegt der Wert dann wahrscheinlich immernoch in einem der Register, oder zumindest noch im Cache, sodass die beobachtbaren Latenzen wohl nur beim ersten Zugriff auftreten)
beste Grüße
zommi
Hi zommi!
Diese Argumente sind aber sehr weit hergeholt. Denn der managed Heap eines .Net Programmes besitzt ebenfalls gewisse Lokalitätseigenschaften und wird vermutlich häufig im CPU-Cache liegen. Auch der Zugriff auf die Variablen selber ist vernachlässigbar, denn wie der Compiler schlussendlich die Variablen lädt hängt von vielen Parametern ab und lässt sich so nicht verallgemeinern.
Der Geschwindigkeitsunterschied hängt vielmehr davon ab, wie der Speicher allokiert wird.
Denn um n Bytes auf dem Stack zu reservieren reicht eine simple Subtraktion. Um Speicherplatz auf dem Heap zu reservieren müssen je nach Implementierung bei traditionellen Speicherverwaltungen(malloc/free) eine Freelists durchlaufen, und unter Umständen Speicherblöcke gesplittet oder vereinigt werden, was wesentlich mehr Zeit erfordert.
Hi marsgk,
das ganze wird zwar verdammt offtopic, aber es ist ja nich uninteressant 😃
Warum findest du, dass die Argumente weit hergeholt sind?
Es ging doch darum, warum Zugriffe auf den Stack schneller sein könnten als auf den Heap.
Da spielt doch die Methode der Allozierung gar keine Rolle.
(Natürlich sind Stack-Allokierungen schnell, weil eben festgelegt ist in welche Reihenfolge man allokieren und freigeben darf/muss)
Allerdings übernimmt ja .Net nun auch das Speichermanagement, also sollte auch "schneller" heap-Speicher zu holen sein als bei traditionellen Speicherverwaltungen.
@Cache: Der Stack ist doch aber garantiert im Cache enthalten. Beim Heap... eben nur "vermutlich häufig" 😃 . Das ist doch ein Unterschied. (Vielleicht stellt ja Windows sogar sicher, dass der Stack immer im Cache liegt...muss ich mal recherchieren)
@Instruktion-unterschied:
Auch der Zugriff auf die Variablen selber ist vernachlässigbar, denn wie der Compiler schlussendlich die Variablen lädt hängt von vielen Parametern ab und lässt sich so nicht verallgemeinern.
Doch ich find schon. Lokale Structs liegen auf dem Stack. Und wenn ich nen Reference-Type mit new() erstelle, liegt der auf dem Heap. Und bevor der Code ausgeführt wird, wird er ja just in time in CPU-Instruktionen umgewandelt.
Nun ist aber die Position der lokalen Struct durch diesen Code fest definiert. (Durch die Reihenfolge der Instruktionen) Allerdings ist die Position des Reference-Types nicht fest, ja sie MUSS sogar variabel sein, weil ja die CLR vielleicht mal den Heap defragmentiert und dabei das Objekt verschiebt.
Da kann also garnix clever vom compiler "reingestrickt" werden. Zugriff auf Heap erfordert immer eine Indirektion mehr. Zugriff auf Stack nicht. Und mehr = langsamer.
beste Grüße
zommi
Ich wollte damit verdeutlichen, dass die Geschwindigkeitsunterschiede beim Zugriff vernachlässigbar sofern vorhanden sind. Der wirkliche Geschwindigkeitsunterschied liegt beim Allokieren von Speicher. Wobei das Erzeugen eines Objektes am managed Heap wesentlich schneller ist, als bei traditionellen Speicherverwaltungen.
Der Stack ist doch aber garantiert im Cache enthalten. Beim Heap... eben nur "vermutlich häufig" ...
Ich wäre da vorsichtiger mit Äußerungen wie "garantiert", denn der Stack eines Threads kann defaultmäßig bis zu 1MB betragen somit bezweifle ich stark, das der ganze Stack im Cache liegt. Ich gehe zwar auch davon aus, dass mindestens der aktuelle Stackframe im Cache liegt, allerdings dürfte - wie bereits gesagt - auch der managed heap relativ gute Eigenschaften bezüglich Cache besitzen.
@Instruktion-unterschied:
Lokale Structs liegen zwar auf dem Stack, sobald du allerdings dieses struct an eine Funktion übergeben willst, übergibst du meistens einen Pointer, somit sind deine tollen Eigenschaften dahin. Auch für den Fall dass du die struct per value übergibst musst du diese erst kopieren, was auch wieder Performance kostet.
Da kann also garnix clever vom compiler "reingestrickt" werden.
Ich habe auch nie gesagt, dass es nur am Compiler liegt. Es kommt auf die CPU-Architektur, die Aufrufkonventionen, die Verwendung der Variablen durch den Programmierer(passing by reference) und natürlich auch auf den Compiler an, denn eventuell wird der Rückgabewert von new() nur in einem Register gespeichert und nicht am Stack, sodass die weitere Indirektionsstufe entfällt.
Kurz gesagt, der Geschwindigkeitsunterschied zwischen Stack und Heap ist beim Zugriff vernachlässigbar und kann auch nicht so allgemein beantwortet werden.
Lg
sobald du allerdings dieses struct an eine Funktion übergeben willst, übergibst du meistens einen Pointer
ehrlich gesagt hab ich bislang eher die Erfahrung gemacht, dass Parameter eher selten ref Parameter sind. Und man Strukturen auch als solche erwartet - nicht als Schnittstellenparameter oder noch schlimmer Object. Dann werden gar keine Pointer kopiert, sondern die ganze Struktur. Und da reden wir immernoch von 12Byte, gut, das sind zugegebenermaßen mehr als 4Byte, aber wir wollen ja auch keine Unmengen Funktionsaufrufe machen, sondern die Teile nur vergleichen.