C++ Suche kleinere Datentypen

T_55 · 23. April 2017

Hallo,

ich möchte eine Zeitangabe mit absolut minimalsten Platzbedarf speichern können.
Die Notierung ist YYYYMMDDHHMMSS.

Folgende Datentypen hab ich angeschaut:

std::string -> 40 byte
time_t -> 8 byte
QString -> 8 byte
QDateTime -> 8 byte

noch kleiner durch eigene Struktur:

struct zeit // -> 7byte
{
short Jahr;
char Monat;
char Tag;
char Stunde;
char Minute;
char Sekunde;
}

Man könnte das Jahr auch noch als char speichern und müsste dann den Wert 0 als zb Jahr 2000 interpretieren. Bei der Nutzung muss man dann eben immer + 2000 rechnen. So kann man Jahr 1872(2000-128) bis 2127 (2000+127) abdecken das sollte für die Lebenszeit reichen.

struct zeit // -> 6 byte
{
char Jahr; // +2000 in Anwendung rechnen
char Monat;
char Tag;
char Stunde;
char Minute;
char Sekunde;
}

Somit hab ich bis hier auf 6 byte reduziert.

Jetzt meine Frage geht es noch weniger?

Denn im Prinzip steht ja -128 bis +127 bzw unsigned 0 bis 255 zur Verfügung. Die benötigten Spannen sind aber meißt noch viel weniger:
Monat 1-12
Tag 1-31
Stunde 0-23
Minute 0-59
Sekunde 0-59

Kann man durch irgendwelche Tricks die Daten in noch weniger als 6 byte unterbringen ?
Gibt es Datentypen die noch kleiner sind als char also unter 1 byte bzw unter 8 bit ?

Grüße

ps: Ich kenne das Beispiel von std::vector<bool> womit es ja möglich ist 8 bool Werte in nur 1 Byte zu packen da für ein bool nur ein bit benötigt wird.

HominiLupus · 23. April 2017

Was du suchst ist Teil des C Standards und nennt sich time_t
http://en.cppreference.com/w/c/chrono/time_t

Größe: 4 Bytes.

Nerdovic · 23. April 2017

1 Byte ist die kleinste mögliche Einheit.
Du könntest höchstens in einer 1 Byte-Zahl zwei 4-Bit Zahlen speichern, bringt natürlich nichts, wenn du nur eine Zahl kleiner 15 hast.

T_55 · 23. April 2017

time_t hat aber 8 byte (64bit) wenn man sich nicht gerade das 2038 Problem ans bein hängen möchte

Ausserdem will ich nicht alles aus dem Unixzeitstempel per struct tm umrechnen müssen.

Nilson · 23. April 2017

Wenn du Bitmasken und so arbeiten willst, kannst du Monat(4 Bit), Tag(5 Bit), Stunden(5 Bit), Minuten (6Bit), Sekunden (6Bit) in 26 Bit unterbringen. Aufgerundet auf 32 Bit also 4 Byte. Plus ein Char fürs Jahr. So käme ich dann auf 5 Byte.

HominiLupus · 23. April 2017

256 Jahre in Sekunden sind etwas über 8 Billionen Sekunden. Also ist es möglich das in 33 Bit zu packen. Das ist das untere Limit.

the_nobs · 23. April 2017

T_55 schrieb:
time_t hat aber 8 byte (64bit) wenn man sich nicht gerade das 2038 Problem ans bein hängen möchte
Ausserdem will ich nicht alles aus dem Unixzeitstempel per struct tm umrechnen müssen.

hat aber den Vorteil das du
a) nicht selbst um die Umrechnung kümmern musst
b) das überall unterstützt wird und deswegen völlig klar ist was passiert

wenn dir 8 byte zu viel sind, dann kannst dir ja selber a Epoch definieren z.b. 1.1.2000, dann läuft es bis 2068 (oder noch später)

alternative du nimmst Bitmasken
für sekunden,minuten reichen 6 bit, für h und tag (im Monat) 5 bit, für Monat 4 bit und für das Jahr benötigst du dann mind 6 oder mehr bit (je nachdem wie weit du es haben willst)
Das sind dann 6+6+5+5+4+6 -> 32 bit -> 4 Byte
einzelne bits kannst sparen wenn du z.B. sek/Tag oder Tag im Jahr nimmst (sind dann auch 2-3 bits weniger...)
Aber dann bist du selbst zuständig für die ganzen Konvertierungs-Funktionen -> fehleranfällig

kuddlmuddl · 23. April 2017

Ich weiß, dass solche Antworten immer etwas nerven - aber bist du sicher, dass das sein muss?

ich möchte eine Zeitangabe mit absolut minimalsten Platzbedarf speichern können.

Ist das nur eine theoretische Fragestellung die du Untersuchst oder denkst du, dass du dadurch wirklich ein anderes Problem löst? Sollen wir nicht lieber bei dem eigentlichen Problem helfen?

jumpin · 23. April 2017

Wie HominiLupus und the_nobs bereits angedeutet haben: Präzision und Zeitraum geben ein Minimum an Bits/Bytes an, die du benötigst.

Sekunden/Minuten/Stunden einzeln speichern benötigt mehr Speicherplatz, da du unter Umständen Speicherplatz ungenutzt lässt.

Als Beispiel bei einem Jahr:
Monat 1-12 -> 4bits (0-15)
Tag 1-31 -> 5bits (0-31)
Stunde 0-23 -> 5bits (0-31)
Minute 0-59 -> 6bits (0-64)
Sekunde 0-59 -> 6bits (0-64)
-> Total 26bits

Aber:
Sekunden ab 1.1. 00:00:00: 60*60*24*366 = 31622400 (Sekunden in einem Schaltjahr) -> 25bits (2^25 = 33554432)

Fazit:
Minimal ist das Speichern der Anzahl Sekunden ab einem definierten Zeitpunkt T0. (Hm ... wie waren nochmal die Unix-Timestamps definiert?

)
Wie gross deine Zeit wird, hängt dann genau noch davon ab, wie viele Jahre du damit darstellen willst.
-> Du suchst dir deinen Zeitpunkt 0 aus und speicherst dann die Sekunden ab diesem Zeitpunkt. Was kleineres gibt es nicht!

Ein weiterer Vorteil dieser Lösung:
Du kannst die Standard-Zeitfunktionen benutzen indem du die Funktionen mit deiner Zeit plus Unix-Zeit von T0 verwendest.

Wofür benötigst du das überhaupt?

PS: Hab die Einleitung des Wikipedia-Artikel kurz überflogen, ist eigentlich genau dass was "the_nobs" auch vorgeschlagen hat (Epoch = Zeitpunkt T0) - nur ein bisschen Ausführlicher mit Begründung.

the_nobs schrieb:
wenn dir 8 byte zu viel sind, dann kannst dir ja selber a Epoch definieren z.b. 1.1.2000, dann läuft es bis 2068 (oder noch später)

T_55 · 24. April 2017

kuddlmuddl schrieb:
Ich weiß, dass solche Antworten immer etwas nerven - aber bist du sicher, dass das sein muss?

Ist das nur eine theoretische Fragestellung die du Untersuchst oder denkst du, dass du dadurch wirklich ein anderes Problem löst? Sollen wir nicht lieber bei dem eigentlichen Problem helfen?

Kein Problem das kann ich erklären es hat schon seinen Grund, es geht um ein Projekt wo ich anhand von historischen Daten eine Simulation mache. Hier der Thread https://www.computerbase.de/forum/t...uer-moeglichst-perfomante-simulation.1657866/

Kurz gesagt werden ein Haufen Daten in den RAM geladen damit die Simulation performant ist. Das die Daten in den RAM geladen werden ist der Grund warum ich versuche den Speicherbedarf der Zeitdaten möglichst zu minimieren. Die große Anzahl der Einträge multipliziert mit dem Speicherbedarf pro Datenpunkt führt dazu, dass sich auch wenige Byte bemerkbar machen.

Der Grund warum ich keine Unixzeit verarbeiten will ist, dass ich bei der Simulation Statistiken über Zeiträume (Monat Stunde usw) wo bestimmte Temperaturen auftreten rausziehen will. Der Weg über struct tm verursacht nach meinen Tests extreme Performanceeinbußen da ja permanent alles umgerechnet werden muss. Daher will ich, dass die Daten direkt so zur Verfügung stehen wie sie dann auch verarbeitet werden, das ist der Grund für die Notierung in YYYYMMDDHHMMSS.
Sonst wäre UnixSekundem ab definiertem Zeitraum wie es gesagt wurde wirklich am kleinsten aber die Umrechnungen per struct tm vermindert die Performance wirklich erheblich.

Das mit den Bitmasken klingt sehr interessant hab ich allerdings noch nie gemacht, kennt jemand ein Beispiel für C++ wie man das angeht?

HominiLupus · 24. April 2017

Wenn die Umrechnungszeit so wichtig ist, dann kannst du die structs nicht wirklich packen, weil das packen ja auch wieder Umrechnungszeit mit Bitpfriemeln und AND, OR, etc, braucht.
Da bleibt dann nur BCD oder so was, egal wieviel mehr RAM das verbrät. Wobei das ja "nur" 10-20% sein dürfte weil du ja nicht nur den Timestamp hast sondern auch die Daten pro Timestamp, und nur Timestamp vergrößert sich.

T_55 · 24. April 2017

Wenn die Sache über Bitmaske (ich bin immer noch am recherchieren) auch so langsam ist wie über struct tm dann lohnt es sich natürlich nicht aber das müsste ich mal prüfen.
Die Daten pro Timestamp sind zur Zeit geringer als der Timestamp selbst, es handelt sich um 4byte von einem float wo der Timestamp prozentual schon was ausmacht, daher interessiert mich das Thema so

Piktogramm · 24. April 2017

T_55 schrieb:
Kurz gesagt werden ein Haufen Daten in den RAM geladen damit die Simulation performant ist. Das die Daten in den RAM geladen werden ist der Grund warum ich versuche den Speicherbedarf der Zeitdaten möglichst zu minimieren. Die große Anzahl der Einträge multipliziert mit dem Speicherbedarf pro Datenpunkt führt dazu, dass sich auch wenige Byte bemerkbar machen.

Der Grund warum ich keine Unixzeit verarbeiten will ist, dass ich bei der Simulation Statistiken über Zeiträume (Monat Stunde usw) wo bestimmte Temperaturen auftreten rausziehen will. Der Weg über struct tm verursacht nach meinen Tests extreme Performanceeinbußen da ja permanent alles umgerechnet werden muss. Daher will ich, dass die Daten direkt so zur Verfügung stehen wie sie dann auch verarbeitet werden, das ist der Grund für die Notierung in YYYYMMDDHHMMSS.
Sonst wäre UnixSekundem ab definiertem Zeitraum wie es gesagt wurde wirklich am kleinsten aber die Umrechnungen per struct tm vermindert die Performance wirklich erheblich.

Was die Performance angeht gibt es wenig Besseres als 32 bzw. 64bit Integerwerte wie sie time_t bereitstellt. Wenn sich die Aufgabe vektorisieren lässt bekommst du da je nach Prozessor je Takt auch immer gleich mehrere Werte verarbeitet. Wenn du dir da jetzt eigene Lösungen baust, tauschst du eine minimal kleinere Datenmenge gegen deutlich verringerte Performance.

Der Problem der Konvertierung von Daten. Da würde sich mir die Frage stellen, wieso du überhaupt soviel Daten konvertierst? Das riecht sehr danach, dass du anstatt immer nur mit time_t zu rechnen irgendwo in deinem Code noch Typkonvertierung hast um irgendwelche Suchbereiche zu definieren. Das wäre aber wirklich sinnlos!

In der Annahme du willst die Temperaturen jeden Tages im Bereich 0 bis 1 Uhr auswerten. Dann legst du dir einfach zwei Variablen vom Typ time_t fest (uplimit u. lolimit) und addierst auf beide den Wert 86.400 (24h * 60min * 60s) und verschiebst so dein Auswertungsfenster um genau einen Tag. Das geht mit etwas Hirnschmalz recht effizient für alle regelmäßigen Muster.
Wenn das nicht dein Problem ist, wäre es trotzdem mal ein Ansatz zu überprüfen, wieso du soviel Datenkovertierung hast. Außer beim inititalem, einmaligem Laden der Rohdaten sollte das nicht vorkommen. Wobei hier ein Ansatz wäre die Rohdaten einmal in ein Binärformat zu überführen um nur noch dieses laden zu müssen. Bei der menschlichen Eingabe ist es dann auch kein Ding, das wird einmal von einem menschenlesbarem Format in der UI intern nach time_t überführt und bei der Ausgabe sollte es mich wundern, wenn du sinnvoll mehr als 1.000 Datensätze auf den Bildschirm wirfst. Wobei die 1.000 Konvertierungen schneller erfolgen als der nächste Refresh des Bildschirmes

T_55 · 24. April 2017

Bei der Nutzung der Unixzeit mit time_t ist die Konvertierung ja permanent erzwungen weil eben die abzufragenden Werte wie Stunde erst über struct tm ermittelt werden müssen. Daher will ich Unixtime eher nicht verwenden weil es zu der permanten Konvertierung per struct tm führt.

Bei jedem Messpunkt muss die Bedingung abgefragt werden, ich kann nicht sagen ich teste nur von x bis y sondern ich schleife alle Messpunkte durch und zähle das Auftreten von Ereignissen (zB Temp > 30°C) zb pro Stunde hoch und erhalte so eine durchschnittliche Verteilung.

Als Basis die Zeit im RAM jeweils als direkte Zahl nach dem Schema YYYYMMDDHHMMSS zu haben, macht die Abfrage viel einfacher denn ich muss nur die Zahl auslesen und es ist keine Konvertierung von der Unixzeit zur zb Stunde des Tages nötig.

Was die Bitmaske angeht scheint es mir soweit ich es bis jetzt erfasst habe recht aufwändig zu sein und auch mit vielen Rechenoperationen verbunden zu sein, also wahrscheinlich nicht schneller als über unix struct tm.

Ich denke das direkte Auslesen aus dem Struct mit char Werten ist noch der beste Kompromiss aus Performance und Speicherbedarf. Interessant ist aber auf jeden Fall das sich fast immer Performance und Speicherbedarf gegenläufig verhalten

Finalspace · 24. April 2017

Hast du schonmal daran gedacht, das selbst wenn du dein 6-byte struct nimmst, es im Speicher dann dennoch 8 Byte verwendet?

Der Grund ist, dein Struct wird je nach Compiler und je nach Platform nen zusätzliches Padding bekommen -> Alignment!
Dieses ist typischerweise 4 byte, kann aber auch 8 byte oder sogar 16 byte sein, je nach Platform/Compiler.

Das bedeutet schlicht und ergreifend, dein struct muss ein vielfaches von 4, 8 oder 16 sein.
Prüfe dazu einfach dein Standard-Alignment in den Compilereinstellungen!

Siehe dazu:
https://msdn.microsoft.com/en-us/library/dn956973.aspx
https://en.wikipedia.org/wiki/Data_structure_alignment

Es gibt allerdings Wege wie du das Alignment für Structs spezifisch ausschalten kannst, dies ist z.b. Sinnvoll wenn du das Binär auf die Platte speichern willst - aber dein Datum 6 Byte antatt 8 Byte speichern soll:

Code:

__declspec(align(1))

oder in Visual Studio gibts nen #pragma pack(1) und #pragma pack(pop)

Aber selbst wenn du das auf 1 stellst, dann mag zwar dein Struct 6 Byte haben - aber im Speichermanagement von C wirst du dann wieder zusätzliches Padding bekommen, damit er das Alignment welches vom OS/Platform vorgegeben ist einhält.
Für die Gesamtgröße gesehen, wenn du z.b. deine Datumsstempel in nem Array ablegst.

Aber spät. auf der CPU hast du dann aber nen Problem, weil diese kann mit 6 Byte etc. nichts anfangen und füllt dann dann die restlichen Bits so oder so mit 0 auf - sprich du verschwendest dann bei 6 Byte 2 Byte.

Und betreffend Performance:

Es nicht so wichtig wieviel Cycles die CPU für Matheoperationen benötigt, um z.b. ein paar poplige Datumsumrechnungen zu machen, denn CPU können eines sehr gut und das ist: Matheoperationen durchführen.

Speicherzugriff dagegen ist enorm teuer! Sieht dazu folgenden cpp-Con Talk:
https://www.youtube.com/watch?v=BP6NxVxDQIs

Fazit: Dann lieber doch time_t oder?

Korrigiert mich wenn ich falsch liege. Bin noch relativ müde, um 5 aufgestanden...

blöderidiot · 24. April 2017

T_55 schrieb:
Bei jedem Messpunkt muss die Bedingung abgefragt werden, ich kann nicht sagen ich teste nur von x bis y sondern ich schleife alle Messpunkte durch und zähle das Auftreten von Ereignissen (zB Temp > 30°C) zb pro Stunde hoch und erhalte so eine durchschnittliche Verteilung.

Als Basis die Zeit im RAM jeweils als direkte Zahl nach dem Schema YYYYMMDDHHMMSS zu haben, macht die Abfrage viel einfacher denn ich muss nur die Zahl auslesen und es ist keine Konvertierung von der Unixzeit zur zb Stunde des Tages nötig.

Nach Deinem anderen Link zu urteilen wäre das (Angst vor zu viel Rechnerei) wahrscheinlich Käse, da Du, wie Du sagst, eh "memory-bound" simulierst. Nimm 64bit time_t auf einem 64bit-aligned Vektor, dann liest Du am schnellsten vom RAM in die CPU-Register und hast trotzdem noch genug Zeit, alle möglichen Berechnungen zu machen, bis der nächste Block überhaupt im Cache angekommen ist.

Mach Dir hier nicht zu viele Gedanken, erstmal eine Prototyp-Simulation zuverlässig hinbekommen (auch langsam) und dann probieren, ein 32bit time_t-Äquivalent abzulegen und einen Rechenschritt zusätzlich einzuführen. Teste was schneller ist. ich würde nur im absoluten Ausnahmefall empfehlen, hier mit eigenen bitfield-structs herumzuspielen. Glaube nicht, daß das schneller würde. ausprobieren!

Aha, Finalspace hat das auch empfohlen ...

Edit: DDR3/1600 schafft "theoretisch" 12GB/sec. Wenn Du davon die Hälfte erreichst, könntest Du Deinen vollen Datensatz in einer Sekunde durchlaufen. Theoretisch ...

Piktogramm · 24. April 2017

T_55 schrieb:
Bei der Nutzung der Unixzeit mit time_t ist die Konvertierung ja permanent erzwungen weil eben die abzufragenden Werte wie Stunde erst über struct tm ermittelt werden müssen. Daher will ich Unixtime eher nicht verwenden weil es zu der permanten Konvertierung per struct tm führt.

Bei jedem Messpunkt muss die Bedingung abgefragt werden, ich kann nicht sagen ich teste nur von x bis y sondern ich schleife alle Messpunkte durch und zähle das Auftreten von Ereignissen (zB Temp > 30°C) zb pro Stunde hoch und erhalte so eine durchschnittliche Verteilung.

Ist doch aber ähnlich. Eine Stunde sind 60min * 60s = 3600s. Wenn du wissen willst in welcher Stunde ein Wert aufgetreten ist rechnest du:

Code:

time_t data = 89439327923789;
int sihour = 60 *60; // for one SI hour: minutes * seconds;
int hour;

hour = data / sihour;

Keine Typumwandlung, nur simpelste Arithmetik. Du musst halt aufhören in Jahr / Monat / Woche / Tag/ Stunde / Minute zu denken sondern einfach alles schön auf Sekunden normalisieren und damit rechnen. Das macht etwas mehr Aufwand wenn man das zum ersten mal macht, danach ist es aber einfach. Selbst Unregelmäßigkeiten wie die Länge der Monate und Schaltjahre bekommt man hin ohne komplexere Mathematik bemühen zu müssen. Die Differenz in der Ausfürungsgeschwindigkeit ist schnell mal um bis zu einer Größenordnung besser als mit Typkonvertierungen wie bei dir.
Selbst mit Bitmasken oder anderen Konstrukten verschenkst du Leistung, da du da aller Wahrscheinlichkeit da nicht auf einen Wert wie bei time_t vergleichen kannst sondern einzeln Jahr, Monat, Tag, Stunde prüfst, was im Zweifelsfall weit aufwendiger ist.

Als Basis die Zeit im RAM jeweils als direkte Zahl nach dem Schema YYYYMMDDHHMMSS zu haben, macht die Abfrage viel einfacher denn ich muss nur die Zahl auslesen und es ist keine Konvertierung von der Unixzeit zur zb Stunde des Tages nötig.

Falsch siehe oben. Um die Stunde des Tages herauszubekommen ist eine einzelne Division zweier Integer nötig. Nichts was du irgendwie bauen können wirst ist effizienter als das! Weder im Speicherverbrauch noch in der Performance.

Ergänzung (24. April 2017)

Finalspace schrieb:
Und betreffend Performance:

Es nicht so wichtig wieviel Cycles die CPU für Matheoperationen benötigt, um z.b. ein paar poplige Datumsumrechnungen zu machen, denn den CPU kann Matheoperationen rasend sehr schnell verarbeiten.

Speicherzugriff dagegen ist enorm teuer! Sieht dazu folgenden cpp-Con Talk:
<video>

Fazit: Dann lieber doch time_t oder?

Korrigiert mich wenn ich falsch liege. Bin noch relativ müde, um 5 aufgestanden...

Das Problem mit den Typkonvertierungen ist und Rechnen mit Stunden, Tagen, Monaten etc. ist, dass dabei oftmals verschachtelte Schleifen gebaut werden, die der Compiler oft nicht gescheit optimieren kann und die Sprungvorhersage der CPU (bei unsortierten Daten) oft auch deutlich an Effizienz einbüßt. Damit bekommt man wirklich wunderbar die Performance ruiniert.

T_55 · 24. April 2017

Vielen Dank das sind alles gute Argumente. Ich werde mal verschiedene Varianten vergleichen und die Zeit messen.

Zur Arithmetik hätte ich noch eine Frage.
Jetzt ist 12.42Uhr also laut http://www.unixtime.de/ 1493030532
Nach der Formel:
hour = 1493030532 / 3600 = 414730,70333
Inwiefern sagt mir jetzt 414730,70333 das wir in der 12. Stunde des Tages sind?

Gruß

Finalspace · 24. April 2017

T_55 schrieb:
Inwiefern sagt mir jetzt 414730,70333 das wir in der 12. Stunde des Tages sind?
Gruß

Modulo-Operator!

Nilson · 24. April 2017

Code:

414730,70333 Mod 24 = 11,05 (UTC) = 13,05 (UTC+2 = MESZ)

C++ Suche kleinere Datentypen

Lieutenant

Banned

Lieutenant

Lieutenant

Grand Admiral

Banned

Commander

Commander

Lt. Commander

Lieutenant

Banned

Lieutenant

Admiral

Lieutenant

Lt. Junior Grade

Captain

Admiral

Lieutenant

Lt. Junior Grade

Grand Admiral

Ähnliche Themen