Hallo,
ich habe ein Problem, ich muss eine relativ große Anzahl an Paketen
(maximal 2^32) prüfen. Falls ein Paket nicht vorhanden oder fehlerhaft
ist, muss es neu angefordert werden können, dafür ist die entsprechende
Paketnummer (Position) erforderlich. Es ist aus diversen Gründen
erforderlich bis zum vollständigen Prüfen aller Pakete die komplette
Paketliste zu speichern.
Hierfür habe ich mir überlegt aus Platzgründen eine 2^32 Bit große
Datenstruktur, in Ermangelung eines Bit Arrays, als uint32_t Array
anzulegen. Die Position ergibt sich dann als Arrayindize * 32 +
Bitposition. Irgendwie habe ich aber das Gefühl das man dies besser als
mit dem nachfolgenden Beipielcode machen kann. Vorschläge hierzu sind
willkommen.
1 | uint32_t liste[4294967296/32];
| 2 | uint32_t max_makroblocks = 4294967296/32;
| 3 | uint32_t mask;
| 4 |
| 5 | for(i=0; i<max_makroblocks; i++)
| 6 | {
| 7 | if (liste[i] == 0) continue; //Kein Fehler im 32er Block, nächster Block
| 8 | else //mindestens ein Fehler im 32er Block, Feinauswertung
| 9 | {
| 10 | for(j=0, mask=0x00000001; j<32; j++, mask<<=1)
| 11 | {
| 12 | if((liste[i] & mask) != 0) foo(32*i+j);
| 13 | }
| 14 | }
| 15 | }
|
Achja, irgendwelche Bemerkung zur Byteorder oder Arrayfeinheiten sind
egal, in Wirklichkeit ist es einfach ein Stück Arbeitsspeicher und die
Byteorder ist fix definiert.
Tim T. schrieb:
> uint32_t liste[4294967296/32];
4 GIGA-Byte für so eine Datenstruktur.
<Durch die Zähne pfeif>
Wieviele Fehler erwartest du denn so?
Tim T. schrieb:
> Irgendwie habe ich aber das Gefühl das man dies besser als
> mit dem nachfolgenden Beipielcode machen kann. Vorschläge hierzu sind
> willkommen.
Wenn du nur wenige Fehler erwartest (oder fast nur Fehler), dann
könntest du mit einer einfachen RLE-Kodierung einiges an Speicher und
auch etwas Laufzeit sparen. Da speicherst du nicht jedes Bit einzeln ab,
sondern immer nur einen Bitwert zusammen mit der Anzahl an folgenden
Bits, die diesen Wert haben.
Karl Heinz Buchegger schrieb:
> Tim T. schrieb:
>
>> uint32_t liste[4294967296/32];
>
> 4 GIGA-Byte für so eine Datenstruktur.
Ne, sind "nur" 4 Gigabit, also 512MB für die Bitmap. Nur frage ich mich,
wieviel Speicher der Rechner wohl haben wird, wenn er damit 4 Giga
Pakete behandeln will. Entweder sind die Pakete eher klein, oder er
hat jenseits von 1TB RAM zur Verfügung.
Rolf Magnus schrieb:
>>> uint32_t liste[4294967296/32];
>>
>> 4 GIGA-Byte für so eine Datenstruktur.
>
> Ne, sind "nur" 4 Gigabit, also 512MB für die Bitmap.
Hast recht. Ich war so schockiert, dass ich mich glatt verrechnet hab.
Ein uint32_t hat ja keine 32 Byte sondern 4.
> Nur frage ich mich,
> wieviel Speicher der Rechner wohl haben wird, wenn er damit 4 Giga
> Pakete behandeln will. Entweder sind die Pakete eher klein, oder er
> hat jenseits von 1TB RAM zur Verfügung.
Oder die Aufgabenstellung misverstanden.
Ich würde zb auf jeden Fall ausnutzen, dass Pakete (üblicherweise)
sequentiell hereinkommen und das wenige Pakete fehlen werden.
D.h. so etwas wie eine Liste in der fehlende Paketnummern geführt
werden, zusammen mit der Nummer des zuletzt empfangenen Pakets. Hat das
nächste Paket die erwartete Nummer, dann wird einfach nur die letzte
Nummer entsprechend erhöht und eventuell die Liste der fehlenden Pakete
durchgesehen und die Nummer entfernt. Hat das nächste Paket eine Nummer
die mehr als 1 höher als das zuletzt empfangene Paket ist, so werden
entsprechende fehlt-Einträge in die Liste gemacht.
Bsp
letztes Paket fehlende Pakete
10 -
das Paket 11 kommt rein. 11 = 10 + 1. Also 'in sequence'
11 -
das Paket 15 kommt rein. 15 <> 11 + 1. Also fehlen noch die Pakete 12,
13 und 14
15 12, 13, 14
das Paket 16 kommt rein. 16 = 15 + 1. Also in Sequence
16 12, 13, 14
dsa Paket 14 kommt rein. 14 < 16. Es handelt sich also um ein altes
Paket. 14 ist in der Liste -> austragen
16 12, 13
usw.
Die Annahmen waren: Die Pakete kommen einigermassen in der richtigen
Reihenfolge. Es gibt wenige Fehler. Je nachdem wieviele Fehler so
erwartet werden, kann man statt der Liste auch einfach ein fixes Array
(heftig dimensioniert) nehmen.
Wenn diese Annahmen stimmen, würd ich das so ungefähr macchen.
Ohne jede Kenntnis des zu erwartenden Verhaltens von Paketen lässt sich
keine Aussage treffen, welche Implementierung effizient oder ineffizient
ist. So ist eine 4Gbit Bitmap ziemlich ineffizient, wenn nur sehr wenige
Pakete fehlen, weil die Suche nach den Löchern quer durch eine grosse
Speichermenge fegt. Andererseits kann das erwähnte RLE Verfahren bei
manchen Verhaltensweisen von Paketen derart vor die Wand fahren, dass
die Kiste quasi stehen bleibt.
Also dann:
1. Haben die Rechner 4GB Ram, also für die Paketverwaltung ausreichend
da "nur" 512MB maximal gebraucht werden.
2. Werden die Pakete selber auf Festplatte gespeichert da es hier bis in
den TByte Bereich gehen kann.
3. Die Anzahl der Fehler ist nicht bekannt und kann sich je nach
Umgebungsparametern drastisch ändern.
4. Kann nicht immer von sequentieller Paketfolge ausgegangen werden und
es kann nichts bestätigt werden.
5. Wenn mit einer (verketteten-)Liste gearbeitet wird (war auch meine
erste Idee), kann schnell wegen dem Overhead der Arbeitsspeicher zu
klein werden (8 Byte pro Pointer + 4 Byte für Paketnummer). Denke auch
das es wesentlich langsamer wird beim durchsuchen. Die Idee von KHB mit
der Liste funktioniert wohl für die Clients nur nicht für den Master, da
dieser alle Fehler aller Clients (unsepariert) nachhalten muss.
Wenn Performance ein Kriterium ist, dann kann es sinnvoll sein, die
Bitmap zu segmentieren und zu den einzelnen Segmenten Metainformationen
zu cachen, wie beispielsweise "fehlt hier drin was?".
A. K. schrieb:
> Wenn Performance ein Kriterium ist, dann kann es sinnvoll sein, die
> Bitmap zu segmentieren und zu den einzelnen Segmenten Metainformationen
> zu cachen, wie beispielsweise "fehlt hier drin was?".
Das war auch schon die Idee bei der Wahl von 32 Bit Dateneinträgen, da
hier schnell auf 0 getestet werden kann ohne alle Bits einzeln
anzufassen.
Nur je größer diese Metastruktur gewählt wird, desto größer ist die
Wahrscheinlichkeit das dort eben doch etwas drin fehlt.
Tim T. schrieb:
> Nur je größer diese Metastruktur gewählt wird, desto größer ist die
> Wahrscheinlichkeit das dort eben doch etwas drin fehlt.
Wenn die Bitmap beispielsweise in 1024 Segmente aufgeteilt wird, dann
ist die Wahrscheinlichkeit gross, dass sich in einem überschaubaren
Zeitraum in 90% davon nichts ändert - vorausgesetzt, die IDs sind nicht
dauerhaft zufällig verteilt, sondern können es auch mal sein. Also kann
man jedem Segment ein Flag verpassen, dass darüber informiert, ob sich
eine Suche darin überhaupt lohnt.
> 32 Bit Dateneinträgen
Dass wir im Zeitalter von 64-Bit Systemen leben ist dir entgangen? Bei
solchen Aufgaben würde ich gar nicht erst mit 32-Bit Systemen anfangen.
In krassen Fällen kann sich sogar SSE/AVX lohnen.
A. K. schrieb:
> Wenn die Bitmap beispielsweise in 1024 Segmente aufgeteilt wird, dann
> ist die Wahrscheinlichkeit gross, dass sich in einem überschaubaren
> Zeitraum in 90% davon nichts ändert - vorausgesetzt, die IDs sind nicht
> dauerhaft zufällig verteilt, sondern können es auch mal sein. Also kann
> man jedem Segment ein Flag verpassen, dass darüber informiert, ob sich
> eine Suche darin überhaupt lohnt.
Das könnte für die Clients funktionieren, nur eben nicht für den Master,
da beim Rückmelden aus verschiedensten Segmenten Änderungen kommen.
> Dass wir im Zeitalter von 64-Bit Systemen leben ist dir entgangen? Bei
> solchen Aufgaben würde ich gar nicht erst mit 32-Bit Systemen anfangen.
Jein, es sind nicht alle Rechner 64-Bit Systeme und ich hab noch nicht
nachgesehen ob 32-Bit Systeme nativ (Befehlssatzerweiterungen) mit
64-Bit Daten umgehen können oder ob ein long long wieder zu Register
herumschieberei führt.
Tim T. schrieb:
> Das könnte für die Clients funktionieren, nur eben nicht für den Master,
> da beim Rückmelden aus verschiedensten Segmenten Änderungen kommen.
Anfangs kommt eine harmlose erscheinende Frage, die aber mangels
bekannter Randbedingungen nicht klar beantwortet werden kann. Kommt man
dann mit einem Vorschlag, dann kommt ein paar neue Randbedingungen, die
diesen Vorschlag nicht sinnvoll machen. Kannst du dir nicht vorstellen,
dass diese Salamitaktik nervt? Zumal niemand hier weiss, welche Gedanken
du dir dabei bereits gemacht und verworfen hast.
A. K. schrieb:
>
> Anfangs kommt eine harmlose erscheinende Frage, die aber mangels
> bekannter Randbedingungen nicht klar beantwortet werden kann. Kommt man
> dann mit einem Vorschlag, dann kommt ein paar neue Randbedingungen, die
> diesen Vorschlag nicht sinnvoll machen. Kannst du dir nicht vorstellen,
> dass diese Salamitaktik nervt? Zumal niemand hier weiss, welche Gedanken
> du dir dabei bereits gemacht und verworfen hast.
Durchaus und es tut mir leid wenn ich damit deine Zeit verschwendet
habe. Denke aber es sollten jetzt alle wesentlichen Randbedingungen
bekannt sein. Was die Master Segmentierung angeht, dachte ich das wäre
schon aus dem letzten Satz meiner 1. Antwort hervorgegangen:
> Die Idee von KHB mit der Liste funktioniert wohl für die Clients nur nicht
> für den Master, da dieser alle Fehler aller Clients (unsepariert)
> nachhalten muss.
Tim T. schrieb:
> bekannt sein. Was die Master Segmentierung angeht, dachte ich das wäre
> schon aus dem letzten Satz meiner 1. Antwort hervorgegangen:
Nicht wirklich, weil die Begriffe Master und Client keine sonderlich
präzise Vorstellung vermitteln, was damit gemeint ist. Für ein
realistisches Vorgehen müsstest du die ganze Struktur von
Master/Client-Systemen/Prozessen/???, bestehenden oder zu beschaffenden
Systemen usw vermitteln, was hier zu weit führt.
A. K. schrieb:
>
> Nicht wirklich, weil die Begriffe Master und Client keine sonderlich
> präzise Vorstellung vermitteln, was damit gemeint ist. Für ein
> realistisches Vorgehen müsstest du die ganze Struktur von
> Master/Client-Systemen/Prozessen/???, bestehenden oder zu beschaffenden
> Systemen usw vermitteln, was hier zu weit führt.
Stimmt auch wieder.
Dann werde ich einfach mal über das nachdenken was bislang hier
rausgekommen ist, bin erstmal froh das ich nichts grundlegendes
übersehen habe. Werde mal überlegen ob nicht doch eine
Lauflängencodierung in Betracht kommt oder ob man die Listen, bei
eventueller Einschränkung der maximal erlaubten Fehler verwenden kann
und ob auf die 32-Bit Systeme verzichtet werden kann.
Obacht bei RLE: Wenn sich ein RLE-Array von einigen hundert MB angesammt
haben sollte und sich am vorderen Ende ein Bit ändert, dann kannst du
vor der Aufgabe stehen, den gesamten Salat ein paar Bytes zu
verschieben. Mach das öfter und die Kiste steht praktisch still. Du
kriegst so ein unkalkulierbares worst case verhalten.
Wenn ich auf so ein Problem stoße, schaue ich mir immer erst
mal die Schritte vorher genauer an. Ist es wirklich notwendig
so viele Werte zu verarbeiten ?
Prinzipiell gehen so große Arrays schon, geht halt in die
Laufzeit ;)
Die Sequenznummer steckt nicht in den Daten ?
Kann ein Block gleich 0 sein ?
A. K. schrieb:
> Obacht bei RLE: Wenn sich ein RLE-Array von einigen hundert MB angesammt
> haben sollte und sich am vorderen Ende ein Bit ändert, dann kannst du
> vor der Aufgabe stehen, den gesamten Salat ein paar Bytes zu
> verschieben. Mach das öfter und die Kiste steht praktisch still. Du
> kriegst so ein unkalkulierbares worst case verhalten.
Sowas ging mir auch durch den Kopf, würde die RLE aus diesem Grund dann
als Liste bauen, aber wie gesagt das ist nur eine Denkrichtung.
Joachim Drechsel schrieb:
> Wenn ich auf so ein Problem stoße, schaue ich mir immer erst
> mal die Schritte vorher genauer an. Ist es wirklich notwendig
> so viele Werte zu verarbeiten ?
Im worstcase ja. Es werden in der Regel die 4 Gigapakete nicht
ausgeschöpft könnte aber bei kleiner Paketgröße passieren.
Zwischenbestätigungen/Teilprüfungen sind aus Netztopologischen Gründen
nicht sinnvoll/möglich.
> Die Sequenznummer steckt nicht in den Daten ?
Nein, die steckt zwar in den Paketen, aber es wird nur der Paketinhalt
auf Disk gespeichert und an der entsprechenden Stelle im Ram-Array das
Bit für erfolgreichen Empfang gesetzt.
> Kann ein Block gleich 0 sein ?
Nein, ein Paket hat immer die gleiche Länge und ist größer als 0.
Ach so ...
Es geht darum, die Information "der Block ist korrekt angekommen"
zu speichern. Jetzt wird mir das etwas klarer. Das Eintragen dürfte
klar sein, Pointer berechnen und Bit setzen.
Ich kann mir dann folgende Abfragen vorstellen:
* Sind alle Blöcke da ?
* Welche/Wieviele fehlen ?
Da könnte ich mir die Sache mit der Segmentierung gut vorstellen.
Beim Schreiben der Bits Flags des Segments setzen: "n fehlen noch".
Zur Ermittlung der Segmentgröße würde ich da mal einen Problelauf
ohne Segmentierung genauer ansehen.
Joachim Drechsel schrieb:
> Ach so ...
>
> Es geht darum, die Information "der Block ist korrekt angekommen"
> zu speichern. Jetzt wird mir das etwas klarer. Das Eintragen dürfte
> klar sein, Pointer berechnen und Bit setzen.
>
> Ich kann mir dann folgende Abfragen vorstellen:
>
> * Sind alle Blöcke da ?
> * Welche/Wieviele fehlen ?
>
> Da könnte ich mir die Sache mit der Segmentierung gut vorstellen.
> Beim Schreiben der Bits Flags des Segments setzen: "n fehlen noch".
> Zur Ermittlung der Segmentgröße würde ich da mal einen Problelauf
> ohne Segmentierung genauer ansehen.
So in etwa ist es gedacht. Nachdem alle Blöcke rausgesendet sind, wird
ein "meldet Übertragungsstatus/fehlende Pakete"-Kommando vom Master
abgesetzt und das Netz auf Empfangsmodus geschaltet. Daraufhin sendet
jeder Client eine Liste mit der ihm fehlenden Paketnummern gestaffelt
nach Client ab. Der Master trägt jedes fehlende Paket in seine Fehlende
Paketeliste maximal einmal ein. Nach der Rückmeldung des letzten Clients
wird das Netz wieder auf Sendemodus geschaltet und die fehlenden Pakete
an alle Clients verteilt wo sich jeder Client die ihm fehlenden Pakete
raussucht. usw.
Bislang wurden die Daten mit Zwischenstationen verteilt die nun
wegfallen sollen. Es arbeiten 3 Personen an dem Problem die verschiedene
Ansätze verfolgen: Vorwärtsfehlerkorrektur, Nachkorrektur und ein
Torrentansatz.
Meine Variante ist die Nachkorrekturvariante und sieht bislang am
vielversprechensten aus da die FEC zu groß wird und Torrent mit der
Netztopologie nicht besonders gut klarkommt.
Schade, ich kenne die Aufgabenstellung nicht ;)
Das Problem scheint mir aber nur ein Detail eines größeren Problems
zu sein - vielleicht könnte man das Konzept noch mal genauer unter die
Lupe nehmen.
Ich habe das bei Kunden öfter dass sie das Kind mit dem Bade
ausschütten.
Aktuell XML-Daten mit angehängten PDF und klitzekleinen Fehlern die
sich kein Mensch erklären kann. Ca 1 TB wilder Mischmasch pro Jahr.
Im Konzept des Kunden ist noch sehr viel Platz nach oben ...
Statt einer großen Tabelle, wo für jedes mögliche Paket schon ein Bit
vorgesehen ist, geht doch auch eine mehrstufige Tabelle.
Also als Beispiel 128 Bytes zusammenfassen, entspricht einem Block aus
1024 Bits. Dann ein Array aus Zeigern auf diese Blöcke, zum Beispiel 256
Zeiger, mit der Besonderheit, dass Null-Zeiger im Array bedeuten, dass
der zugehörige Block komplett 0 Bits enthält. So ein Block wiederum muss
nicht im Speicher existieren. Darüber noch ein Array aus Zeigern auf das
vorherige Array aus Zeigern, wieder mit der Sonderbedeutung für
Null-Zeiger. Usw. bis insgesamt genügend Bits abgedeckt sind.
Im Endeffekt halt so, wie Seitentabellen von MMUs funktionieren.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
|
Thread beobachten
Seitenaufteilung abschalten