Nochmal Gleitkommazahlen, 32bit Float geeignet für Ganzzahlendarstellung bis 64bit?

[Assarbad]

Moin moin,

in WDS möchte ich versuchen soviel Information wie möglich in so wenige Bits wie möglich zu quetschen. Nun ist es so, daß in der Praxis weit weniger Dateien die adressierbare Dateigröße von rund 4 GiB überschreiten. Es gibt aber eben auch diese Fälle. Da ich für jede Datei Informationen im Speicher halten muß, böte es sich an beim Typ der für das Vorhalten der Dateigröße benutzt wird einzusparen.

WDS ist zwar in C++ geschrieben, aber das spielt ja keine Rolle, da wir auch hier über Gleitkommazahlen nach IEEE sprechen. Ist mir also absolut egal ob ihr die Delphitypen für Gleitkommazahlen oder die C/C++-Typen in euren Antworten benutzt :zwinker:

Es gäbe nun mehrere Szenarien:

1. Ich bilde eine Union aus einer 32bit Ganzzahl und einer 32bit Gleitkommazahl und bestimme über ein externes Bit (irgendwo in der Objektinstanz) welcher Typ wirklich drinsteht
2. Ich benutze nur 32bit Gleitkommazahlen
3. Ich benutze eine komplett andere Methode, bei der ebenfalls ein extra Bit eine Rolle spielt, aber 64bit Ganzzahlen dynamisch alloziert werden, wenn 32bit nicht reichen

So, und jetzt meine Frage. Sind die ersten beiden Szenarien überhaupt machbar? Die Frage zielt darauf ab, ob die Genauigkeit der 32bit Gleitkommazahl eine Genauigkeit bietet die groß genug ist um später beim Runden in eine Ganzzahl korrekt die Werte darzustellen die man mit Ganzzahlen bis 64bit ohne Probleme darstellen kann.

Nach meinen Berechnungen soweit könnte es klappen, aber die Genauigkeit bei Gleitkommazahlen ist so eine Wissenschaft für sich. Daher wollte ich gern eure Meinung einholen.

Danke schonmal für's Lesen.

NB: Effizienz ist insofern irrelevant als der Flaschenhals derzeit ohnehin die Festplatten- und Dateisystemgeschwindigkeit sind. Abgesehen davon geht es allein um die Speicherung und das Extrahieren der Zahl mittels Rundung auf eine Ganzzahl - Berechnungen werden nach wie vor mit Ganzzahlen vorgenommen.

[Namenloser]

Ich weiß nicht, was WDS ist aber könntest du nicht eine UTF-8-ähnliche Kodierung benutzen? Im EBML-Format, das u.a. die Grundlage für den Matroska-Container bildet, macht man es beispielsweise so.

[Assarbad]

Zitat:

Zitat von NamenLozer (Beitrag 1062863)

Ich weiß nicht, was WDS ist

WinDirStat

Zitat:

Zitat von NamenLozer (Beitrag 1062863)

aber könntest du nicht eine UTF-8-ähnliche Kodierung benutzen? Im EBML-Format, das u.a. die Grundlage für den Matroska-Container bildet, macht man es beispielsweise so.

Hmm, verstehe. Codepunkte festlegen und ab da mehr Bits verwenden. Aber dann komme ich nicht umhin weiter 64bit-Ganzzahlen (und größer) einzusetzen. Denn auch bei UTF-8 werden ja die Bits nicht wirklich eingespart. Im Grunde ist dein Vorschlag das gleiche wie mein Szenario Nummer 3, nur eben mit extra Rechenaufwand, da dort mehr als nur ein Bit geprüft werden muß um den Wert zu "dekodieren".

EBML sieht gut aus, zielt wohl aber mehr auf die eigentliche Speicherung auf Festplatten usw. ab.

[toms]

Zitat:

Zitat von NamenLozer (Beitrag 1062863)

Ich weiß nicht, was WDS ist

WinDirStat

Edit: Roter Kasten funktioniert nicht...

[Namenloser]

Zitat:

Zitat von Assarbad (Beitrag 1062867)

Zitat:

Zitat von NamenLozer (Beitrag 1062863)

Ich weiß nicht, was WDS ist

WinDirStat

Achso :wall:

Zitat:

Zitat von Assarbad (Beitrag 1062867)

Aber dann komme ich nicht umhin weiter 64bit-Ganzzahlen (und größer) einzusetzen. Denn auch bei UTF-8 werden ja die Bits nicht wirklich eingespart.

Naja, aber du meintest ja eingangs, dass die meisten Dateien <4GB sind. Wenn ich mir meine Festplatte so anschaue, sind die meisten Dateien wohl auch <2GB. Insofern spart das schon Platz, weil eben nur noch für einen Teil der doppelte Speicherplatz benötigt wird.

Außerdem werden auch bei Gleitkommazahlen keine Bits "eingespart". Man erkauft sich die geringere Größe eben durch geringere Genauigkeit. Du kannst mit einer Gleitkommazahl nicht mehr Stellen speichern als mit einer Festkommazahl, nur größere Wertebereiche abdecken. In einer 32Bit-Gleitkommazahl kannst du also niemals alle Werte speichern, die in einen 64-Bit-Integer-Wert passen. Genauergesagt sogar weniger als in einem 32-Bit-Integer, da für den Exponenten ja auch noch mal Platz draufgeht. Da wäre es noch eine "genauere" Lösung einen 32-Bit-Integer zu nehmen und den Inhalt beim Anzeigen mit dem Faktor 2 zu multiplizieren. Würde nur bei kleineren Dateien stärker auffallen - dafür wären die Ungenauigkeiten bei großen Dateien mit Gleitkommazahlen noch höher.

[Assarbad]

Zitat:

Zitat von NamenLozer (Beitrag 1062871)

Naja, aber du meintest ja eingangs, dass die meisten Dateien <4GB sind. Wenn ich mir meine Festplatte so anschaue, sind die meisten Dateien wohl auch <2GB. Insofern spart das schon Platz, weil eben nur noch für einen Teil der doppelte Speicherplatz benötigt wird.

Jupp, habe auch gerade gedacht, vielleicht sogar was abgestuftes wie du ja mit deinem UTF-8 so schön gemeint hattest. Also auch wenn ich als kleinsten Wert 32bit reservieren würde, könnte man vielleicht dennoch oberhalb dieses Bereichs abstufen. Meines Wissens nach gibt es bisher noch immer keinen Festspeicher der auch nur annähernd an das heranreicht was man mit 64bit adressieren kann.

Selbst bei CPUs schummeln die Hersteller ja ;)

Also danke erstmal für deinen Kommentar. Ich warte mal ob vielleicht noch jemand eine kreative Idee hat. Und das mit dem "mehr Speichern" ist so eine Sache. Wenn du "Programming Pearls" von Jon Bentley gelesen hast, weißt du was ich meine. Ansonsten kann ich nur empfehlen daß du dir dieses Buch auf dem Wunschzettel für Geburtstag oder Weihnachten vormerkst.

Zitat:

Zitat von NamenLozer (Beitrag 1062871)

Außerdem werden auch bei Gleitkommazahlen keine Bits "eingespart". Man erkauft sich die geringere Größe eben durch geringere Genauigkeit. Du kannst mit einer Gleitkommazahl nicht mehr Stellen speichern als mit einer Festkommazahl, nur größere Wertebereiche abdecken. In einer 32Bit-Gleitkommazahl kannst du also niemals alle Werte speichern, die in einen 64-Bit-Integer-Wert passen. Genauergesagt sogar weniger als in einem 32-Bit-Integer, da für den Exponenten ja auch noch mal Platz draufgeht. Da wäre es noch eine "genauere" Lösung einen 32-Bit-Integer zu nehmen und den Inhalt beim Anzeigen mit dem Faktor 2 zu multiplizieren. Würde nur bei kleineren Dateien stärker auffallen - dafür wären die Ungenauigkeiten bei großen Dateien mit Gleitkommazahlen noch höher.

Gut, eine definitive Aussage war es auch die ich wollte. Alternativen gibt es im Zweifelsfall immer. Ich wollte nur nicht einer falschen Fährte folgen.

[Satty67]

Angenommen 99% der Dateien liegen unter 2 GiB (also 31 Bit), könnte man Bit 32 (signed) als Indikator für erweiterte Daten zur Dateigröße verwenden (ein angehängter 64 Bit Wert). Bei 1% dann 96 Bit, beim Rest 32 Bit gespart

€: Sehe gerade, Dein eigener Vorschlag 3)... der wird wohl am sinnvollsten sein.

[Assarbad]

Zitat:

Zitat von Satty67 (Beitrag 1062874)

Angenommen 99% der Dateien liegen unter 2 GiB (also 31 Bit), könnte man Bit 32 (signed) als Indikator für erweiterte Daten zur Dateigröße verwenden (ein angehängter 64 Bit Wert). Bei 1% dann 96 Bit, beim Rest 32 Bit gespart

Eine exakte Wissenschaft ist das ohnehin nicht, aber wie kommst du auf die 96bit?

Es gäbe ja sogar noch eine Variation von Nummer 3 die ohne extra Bit auskommt. Ich könnte eine abstrakte Basisklasse deklarieren und dann in der Implementation entweder eine 32bit oder 64bit Ganzzahl verwenden. Da ja alle Funktionen auf den Accessor zugreifen würden, könnte das funktionieren. Muß ich mir aber noch angucken, nicht daß mir dann die Vererbung extra Kosten draufschlägt :mrgreen:

[Satty67]

Zitat:

Zitat von Assarbad (Beitrag 1062880)

aber wie kommst du auf die 96bit?

Bin von einer einfachen Lösung ausgegangen, bei der nur ein 64 Bit Wert angehängt wird und die 31Bit im kleinen Integer brach liegen.

€: Schlechter Satzbau in Post #7, denke Du hast es als 96 Bit gespart gelesen, so hatte ich das nicht gemeint.

[Assarbad]

Zitat:

Zitat von Satty67 (Beitrag 1062882)

Bin von einer einfachen Lösung ausgegangen, bei der nur ein 64 Bit Wert angehängt wird und die 31Bit im kleinen Integer brach liegen.

Plus sizeof(Pointer), oder?

Aber ihr beide habt mich auf eine andere Idee gebracht. Sozusagen ganz im Sinne von Jon Bentley's "Programming Pearls". Also schonmal danke. Mal sehen wieviel Einsparung ich hinbekomme ;)

[jfheins]

Hi,

um auch mal bei WinDirStat zu helfen (tolles Programm btw) meine Meinung: Es sollten die 32 bit Gleitkommawerte reichen. Nicht immer muss man die sauberste Lösung wählen. Und da der Wert eh nur als 777,7 MB angezeigt wird (völlig ausreichend, wozu sollte ich die Größe bis auf das letzte Byte wissen wollen?) reichen die 7 Ziffern Genauigkeit hin. Falls das für die internen Berechnung und die Grafik ebenfalls reicht, gibt es keinen Grund da noch mehr Komplexität reinzustecken ;)

[Assarbad]

Zitat:

Zitat von jfheins (Beitrag 1062886)

Und da der Wert eh nur als 777,7 MB angezeigt wird (völlig ausreichend, wozu sollte ich die Größe bis auf das letzte Byte wissen wollen?) reichen die 7 Ziffern Genauigkeit hin.

Hmm, aber die Berechnung der Gesamtgrößen erfordert schon Genauigkeit auf ein Byte genau. Ansonsten wird es bei Millionen von Dateien auch bei Anzeige von MiB oder GiB durchschlagen. Denkste nicht?

[jfheins]

Okay, ja bei Millionen von Dateien könnte das passieren :stupid:
Du könntest dir einen 48bit Ganzzahltypen geklarieren - das sollte für die meisten Dateien ausreichen :mrgreen:

Hast du schonmal ausprobiert, wie schlimm das ist wenn du immer 64bit hernimmst? ich meine, selbst bei 10 Millionen Dateien kostet das dann nur 40MB mehr. So viel ist das auch nicht mehr ;)

[Assarbad]

Zitat:

Zitat von jfheins (Beitrag 1062894)

Hast du schonmal ausprobiert, wie schlimm das ist wenn du immer 64bit hernimmst? ich meine, selbst bei 10 Millionen Dateien kostet das dann nur 40MB mehr. So viel ist das auch nicht mehr ;)

Sagen wir so, es gab Beschwerden von Benutzern die auf Servern arbeiten und ich will nicht einfach nur auf auf 64bit wechseln, sondern auch ein wenig optimieren. Bernhard hatte da schon einiges Versucht, was aber bei modernen Systemen auch schon nicht mehr so toll funktioniert.

Ich denke mal, daß die Dateinamen auch noch ein Problem darstellen, aber bin noch nicht ganz sicher wie man das angehen kann. Neben Kompression käme auch in Frage, daß man immer dann den Namen abfragt und speichert, wenn er irgendwo angezeigt werden muß und stattdessen die 48-bittige File-ID speichert.

[jfheins]

Zitat:

Zitat von Assarbad (Beitrag 1062898)

Sagen wir so, es gab Beschwerden von Benutzern die auf Servern arbeiten und ich will nicht einfach nur auf auf 64bit wechseln, sondern auch ein wenig optimieren. Bernhard hatte da schon einiges Versucht, was aber bei modernen Systemen auch schon nicht mehr so toll funktioniert.

Es arbeiten Leute damit? (Nichts für ungut, ich finde es ungemein praktisch den Festplattenplatz schön visualisiert zu haben, aber sonst ...)

Zitat:

Ich denke mal, daß die Dateinamen auch noch ein Problem darstellen, aber bin noch nicht ganz sicher wie man das angehen kann. Neben Kompression käme auch in Frage, daß man immer dann den Namen abfragt und speichert, wenn er irgendwo angezeigt werden muß und stattdessen die 48-bittige File-ID speichert.

Du könntest auch intern erstmal mit 64bit rechnen und dann (z.B. wenn alles abgegrast wurde) sämtliche Werte auf 32bit Gleitkomma runden. Aber wenn du zu jeder Datei auch noch den Namen im ASCII Format speicherst, würde ich erstmal da optimieren...

[Assarbad]

Zitat:

Zitat von jfheins (Beitrag 1062908)

Du könntest auch intern erstmal mit 64bit rechnen und dann (z.B. wenn alles abgegrast wurde) sämtliche Werte auf 32bit Gleitkomma runden. Aber wenn du zu jeder Datei auch noch den Namen im ASCII Format speicherst, würde ich erstmal da optimieren...

Pah, ASCII? Unicode ... UTF-16 um genau zu sein. Da ist meiner Meinung nach auch ganz ohne Kompression schon ein Sparpotential :stupid:

Die ASCII-Version wird wie schon angekündigt eingestellt.