Bitstruct optimieren

[Zacherl]

Hallo zusammen,

ich möchte programmatisch die Reihenfolge von Feldern in einem Bitstruct optimieren (Felder werden in einer Liste, welche jeweils die Größe in Bits enthält reingegeben und werden um das berechnete Offset ergänzt). Hierbei beachte ich momentan drei Kriterien (absteigende Priorität):

1. Das Struct muss so klein wie möglich sein
2. Möglichst wenige Felder sollen Byte-Grenzen überlappen
3. Möglichst viele Felder sollen an Byte-Grenzen aligned sind

Mein Ansatz basiert bisher auf Bruteforce, was bei wenigen Feldern auch kein Problem ist, aber ab einer gewissen Anzahl wird die Laufzeit natürlich recht hoch.

Gibt es irgendeinen Algorithmus, mit dem ich mein Vorhaben effizienter umsetzen kann?

Viele Grüße
Zacherl

[BUG]

Zitat von Zacherl:

1. Das Struct muss so klein wie möglich sein
2. Möglichst wenige Felder sollen Byte-Grenzen überlappen
3. Möglichst viele Felder sollen an Byte-Grenzen aligned sind

Wie sieht es denn mit der Zielfunktion aus?

1. kann ich immer erreichen wenn ich alle Felder einfach hintereinander pappe. 2. und 3. kann ich immer erreichen wenn ich alle Felder Byte-aligne. Wie willst du das abgewägt haben?
Ich vermute du möchtest kein Padding einfügen (also immer 1. erfüllen) und dabei 2. und 3. optimieren.

[Zacherl]

Zitat von BUG:

Ich vermute du möchtest kein Padding einfügen (also immer 1. erfüllen) und dabei 2. und 3. optimieren.

Genau. Also die Kriterien sollen in absteigender Reihenfolge erfüllt sein, wobei 1. das Wichtigste ist. Padding darf nur dann vorkommen, solange kein neues Byte angefangen werden müsste.

Hintergrund zu 2. und 3. ist, dass ich mir überlegt habe, dass im Falle von:
2) Zugriffe immer über eine einzelne Read-Operation (+ggfls. AND und SHR) durchgeführt werden können
3) Man sich zusätzlich noch das Shiften spart, sofern das Least-Significant-Bit des Feldes mit dem LSB des entsprechenden Bytes zusammen fällt

Wenn mir kein Denkfehler unterlaufen ist, müsste man damit die optimale Performance erreichen können.

[BUG]

Zitat von Zacherl:

Wenn mir kein Denkfehler unterlaufen ist, müsste man damit die optimale Performance erreichen können.

Da bin ich skeptisch. Da müsste man Zugriffzeit und Platzbedarf/Cacheverhalten abwägen, was auch von den Zugriffsmustern abhängt ... usw.


Meine erste Überlegung bei solchen Problemen, die noch gut mit Brute-Force gelöst werden können, ist immer Branch-and-Bound. Du findest mit einer Tiefensuche oder Heuristik eine gute Lösung, dann kannst du schon früh alle Lösungen ausschließen, die nicht besser werden können.

Potenzial sehe ich auch darin, das man bei den Kombinationen mit Größenklassen arbeitet und nicht mit einzelnen Feldbezeichnungen: Das kann zum Beispiel bei vielen einzelnen Bits viel ausmachen.
Vielleicht macht es Sinn, sich die Größenklassen modulo 8 jeweils für Längen unter und über 8bit angucken. Die unteren Größenklassen könnte man nehmen, um Bytes voll zu machen. Mit den Größeren müsste man vorsichtiger sein

[mensch72]

Auch wir arbeiten tatsächlich in unserer DB und im RAM mit eigenen Datentypen, in welchen wir per Propertys auf die SubFelder bitweise zugreifen und per Operatoren sogar rechnen

Unser Ansatz manueller Ansatz:
- wir arbeiten nich mit Delphi "BitFeldern", sondern im DelphiRecord mit Array(s) of UINT64,UINT32,UINT16,BYTE
- wir platzieren zuerst alle Subfelder mit einer ganzen "8er" Bitgröße an INT64..BYTE grenzen (und "optimieren" hier schon das erste Mal)
- wir prüfen, ob es 2 Subfelder kleiner ganzer BYTE..INT64 gibt
- wir fangen für 1..7Bit SubFelder so an: wir platzieren dann immer 2 der längsten unrunden Subfelder so, das eines linksbündig und eines rechtsbündig an einer BYTE..INT64 Grenze ist und dazwischen der nun "zusammenhängende Platz" ist und füllen diesen mit den kleinen SubFeldern auf
- dann für 9..15Bit usw... verteilen und/oder optimieren

Das ist deterministisch und damit bekommt man schon sehr kleine Records bei "guter" Feldverteilung.

-aber manuell optimieren wir das teils noch etwas besser
-manuell können wir drauf achten, das es sogar sortierbar wird, wel z.B. die "wichtigen" Bits der Schlüsselinformationen "vorne MSB->LSB" stehen
-negative Werte speichern wir positiv mit einem extra Zusatz "SignBit", weil das beim (Aus)maskieren mit SHL,SHR,AND,OR einfacher zu setzen/prüfen ist, als fehlende negative EinserBits nach Schieben über TypGrenzen wier aufzufüllen
-sehr große oder sehr kleine Zahlen speichern wir mit einem FaktorIndex z.B. 4Bit für 10^(-8..0..7), "Stichwort: eigener FixCommaDatentyp"
-im Idealfall brauchen wir beim LeseZugriff pro SubFeld nur 1x AND und eventuell einmal SHL bzw SHR... das geht wirklich sehr schnell und ist Mutithread auf AMD CPUs sogar viel schneller wie deren lahmer DOUBLE-FPU Flaschenhals


Auch wenn es sich in der Anfrage eventuell nur um "typenlose" Bitfelder handelt, glaube ich das man dies per SoftwareAlgo so angehen könnte.
(Ich mache es weiter manuell, denn ohne die Datenkodierung bei mehr als 100Mio Datensätzen hätten wir wirklich auch heute noch ein Platzproblem sowohl im RAM als auch im Storage. Ausserdem ist es zusätzlich ein guter Schutz gegen Fremddatenzugriff, denn Scriptkiddys können mit so bitweise verwurschtelten Daten nix anfangen, und wenn eventuell noch ein Paritätsbit spendiert wird, ist das sogar ein Sicherheitsargument)

[Zacherl]

Danke euch, da habe ich auf jeden Fall mal etwas Stoff zum Nachdenken

Der deterministische Ansaztz ist auf jeden Fall sehr interessant. Vielleicht kann ich Teile davon zuerst ausführen und dann die restlichen Felder durch einen Branch-and-Bound Algo jagen. Werde ich mal testen müssen, ob ich damit irgendwie meine Min-Size Anforderung zuverlässig erfüllen kann