AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Bitstruct optimieren

Ein Thema von Zacherl · begonnen am 20. Nov 2016 · letzter Beitrag vom 21. Nov 2016
Antwort Antwort
Benutzerbild von Zacherl
Zacherl

Registriert seit: 3. Sep 2004
4.629 Beiträge
 
Delphi 10.2 Tokyo Starter
 
#1

Bitstruct optimieren

  Alt 20. Nov 2016, 17:46
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
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#2

AW: Bitstruct optimieren

  Alt 20. Nov 2016, 18:06
  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.
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.

Geändert von BUG (20. Nov 2016 um 18:42 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Zacherl
Zacherl

Registriert seit: 3. Sep 2004
4.629 Beiträge
 
Delphi 10.2 Tokyo Starter
 
#3

AW: Bitstruct optimieren

  Alt 20. Nov 2016, 18:47
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.
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#4

AW: Bitstruct optimieren

  Alt 20. Nov 2016, 19:51
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
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.
  Mit Zitat antworten Zitat
mensch72

Registriert seit: 6. Feb 2008
829 Beiträge
 
#5

AW: Bitstruct optimieren

  Alt 20. Nov 2016, 23:51
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)
  Mit Zitat antworten Zitat
Benutzerbild von Zacherl
Zacherl

Registriert seit: 3. Sep 2004
4.629 Beiträge
 
Delphi 10.2 Tokyo Starter
 
#6

AW: Bitstruct optimieren

  Alt 21. Nov 2016, 10:13
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
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +2. Es ist jetzt 19:03 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf