Was ist die ideale Wachstumsrate für ein dynamisch zugewiesenes Array?

83

C ++ hat std :: vector und Java hat ArrayList, und viele andere Sprachen haben ihre eigene Form eines dynamisch zugewiesenen Arrays. Wenn einem dynamischen Array der Speicherplatz ausgeht, wird es einem größeren Bereich neu zugewiesen und die alten Werte werden in das neue Array kopiert. Eine zentrale Frage für die Leistung eines solchen Arrays ist, wie schnell das Array an Größe zunimmt. Wenn Sie immer nur groß genug werden, um dem aktuellen Push zu entsprechen, werden Sie jedes Mal neu zugewiesen. Es ist also sinnvoll, die Array-Größe zu verdoppeln oder mit etwa dem 1,5-fachen zu multiplizieren.

Gibt es einen idealen Wachstumsfaktor? 2x? 1,5x? Mit Ideal meine ich mathematisch begründete, beste Ausgleichsleistung und verschwendeten Speicher. Ich erkenne, dass theoretisch, da Ihre Anwendung eine mögliche Verteilung von Pushs haben könnte, dies etwas anwendungsabhängig ist. Aber ich bin gespannt, ob es einen Wert gibt, der "normalerweise" am besten ist oder innerhalb einer strengen Einschränkung als der beste angesehen wird.

Ich habe gehört, dass es irgendwo ein Papier darüber gibt, aber ich konnte es nicht finden.

Joseph Garvin
quelle

Antworten:

43

Dies hängt vollständig vom Anwendungsfall ab. Interessieren Sie sich mehr für die Zeit, die beim Kopieren von Daten (und beim Neuzuweisen von Arrays) oder für den zusätzlichen Speicher verschwendet wird? Wie lange wird das Array dauern? Wenn es nicht lange dauern wird, ist die Verwendung eines größeren Puffers möglicherweise eine gute Idee - die Strafe ist von kurzer Dauer. Wenn es herumhängen wird (z. B. in Java, in immer ältere Generationen), ist das offensichtlich eher eine Strafe.

Es gibt keinen "idealen Wachstumsfaktor". Es ist nicht nur theoretisch anwendungsabhängig, es ist definitiv anwendungsabhängig.

2 ist ein ziemlich häufiger Wachstumsfaktor - Ich bin mir ziemlich sicher , dass das , was ArrayListund List<T>in .NET Anwendungen. ArrayList<T>in Java verwendet 1.5.

BEARBEITEN: Wie Erich Dictionary<,>betont, verwendet .NET in .NET "doppelte Größe, dann auf die nächste Primzahl erhöhen", damit Hash-Werte angemessen auf Buckets verteilt werden können. (Ich bin sicher, ich habe kürzlich eine Dokumentation gesehen, die besagt, dass Primzahlen für die Verteilung von Hash-Buckets nicht so gut geeignet sind, aber das ist ein Argument für eine andere Antwort.)

Jon Skeet
quelle
102

Ich erinnere mich, dass ich vor vielen Jahren gelesen habe, warum 1.5 gegenüber zwei bevorzugt wird, zumindest in Bezug auf C ++ (dies gilt wahrscheinlich nicht für verwaltete Sprachen, in denen das Laufzeitsystem Objekte nach Belieben verschieben kann).

Der Grund ist folgender:

  1. Angenommen, Sie beginnen mit einer 16-Byte-Zuordnung.
  2. Wenn Sie mehr benötigen, weisen Sie 32 Bytes zu und geben dann 16 Bytes frei. Dies hinterlässt ein 16-Byte-Loch im Speicher.
  3. Wenn Sie mehr benötigen, weisen Sie 64 Bytes zu, wodurch die 32 Bytes frei werden. Dies hinterlässt ein 48-Byte-Loch (wenn die 16 und 32 benachbart wären).
  4. Wenn Sie mehr benötigen, weisen Sie 128 Bytes zu, wodurch die 64 Bytes frei werden. Dies hinterlässt ein 112-Byte-Loch (vorausgesetzt, alle vorherigen Zuordnungen sind benachbart).
  5. Und so und so weiter.

Die Idee ist, dass es bei einer 2-fachen Erweiterung keinen Zeitpunkt gibt, an dem das resultierende Loch jemals groß genug sein wird, um für die nächste Zuordnung wiederverwendet zu werden. Bei einer 1,5-fachen Zuordnung haben wir stattdessen Folgendes:

  1. Beginnen Sie mit 16 Bytes.
  2. Wenn Sie mehr benötigen, weisen Sie 24 Byte zu und geben Sie die 16 frei, sodass ein 16-Byte-Loch verbleibt.
  3. Wenn Sie mehr benötigen, weisen Sie 36 Bytes zu, und geben Sie die 24 frei, sodass ein 40-Byte-Loch verbleibt.
  4. Wenn Sie mehr benötigen, weisen Sie 54 Byte zu, und geben Sie die 36 frei, sodass ein Loch von 76 Byte verbleibt.
  5. Wenn Sie mehr benötigen, weisen Sie 81 Byte zu, geben Sie dann die 54 frei und lassen Sie ein Loch von 130 Byte übrig.
  6. Wenn Sie mehr benötigen, verwenden Sie 122 Bytes (aufgerundet) aus dem 130-Byte-Loch.
Chris Jester-Young
quelle
5
Ein zufälliger Forumsbeitrag, den ich ( objectmix.com/c/… ) gefunden habe, hat ähnliche Gründe. Ein Poster behauptet, dass (1 + sqrt (5)) / 2 die Obergrenze für die Wiederverwendung ist.
Naaff
19
Wenn diese Behauptung richtig ist, ist phi (== (1 + sqrt (5)) / 2) tatsächlich die optimale Zahl.
Chris Jester-Young
1
Ich mag diese Antwort, weil sie die Begründung von 1,5x gegenüber 2x enthüllt, aber Jons ist technisch am korrektesten für die Art und Weise, wie ich es angegeben habe. Ich hätte nur fragen sollen, warum 1.5 in der Vergangenheit empfohlen wurde: p
Joseph Garvin
6
Facebook verwendet 1.5 in seiner FBVector-Implementierung. Der Artikel hier erklärt, warum 1.5 für FBVector optimal ist.
Csharpfolk
2
@jackmott Richtig, genau wie in meiner Antwort angegeben: "Dies gilt wahrscheinlich nicht für verwaltete Sprachen, in denen das Laufzeitsystem Objekte nach Belieben verschieben kann."
Chris Jester-Young
47

Idealerweise (im Grenzwert als n → ∞) ist es der goldene Schnitt : ϕ = 1,618 ...

In der Praxis möchten Sie etwas Nahes wie 1.5.

Der Grund dafür ist, dass Sie ältere Speicherblöcke wiederverwenden, das Caching nutzen und vermeiden möchten, dass das Betriebssystem Ihnen ständig mehr Speicherseiten zur Verfügung stellt. Die Gleichung, die Sie lösen würden, um dies sicherzustellen, reduziert sich auf x n - 1 - 1 = x n + 1 - x n , dessen Lösung sich x = ϕ für großes n nähert .

user541686
quelle
15

Ein Ansatz bei der Beantwortung solcher Fragen besteht darin, nur zu "schummeln" und zu betrachten, was populäre Bibliotheken tun, unter der Annahme, dass eine weit verbreitete Bibliothek zumindest nichts Schreckliches tut.

Ruby (1.9.1-p129) verwendet beim Anhängen an ein Array nur das 1,5-fache und Python (2.6.2) das 1,125-fache plus eine Konstante (in Objects/listobject.c):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsizeoben ist die Anzahl der Elemente im Array. Beachten Sie, dass dies newsizehinzugefügt wird new_allocated, sodass der Ausdruck mit den Bitverschiebungen und dem ternären Operator wirklich nur die Überzuordnung berechnet.

Jason Creighton
quelle
Das Array wächst also von n auf n + (n / 8 + (n <9? 3: 6)), was bedeutet, dass der Wachstumsfaktor in der Terminologie der Frage das 1,25-fache (plus eine Konstante) beträgt.
ShreevatsaR
Wäre es nicht 1,125x plus eine Konstante?
Jason Creighton
10

Angenommen, Sie vergrößern das Array um x. Nehmen wir also an, Sie beginnen mit der Größe T. Wenn Sie das Array das nächste Mal vergrößern, wird es größer T*x. Dann wird es sein T*x^2und so weiter.

Wenn Sie den zuvor erstellten Speicher wiederverwenden möchten, möchten Sie sicherstellen, dass der neu zugewiesene Speicher geringer ist als die Summe des zuvor freigegebenen Speichers. Deshalb haben wir diese Ungleichung:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

Wir können T von beiden Seiten entfernen. Also bekommen wir folgendes:

x^n <= 1 + x + x^2 + ... + x^(n-2)

Informell sagen wir, dass bei der nthZuweisung der gesamte zuvor freigegebene Speicher größer oder gleich dem Speicherbedarf bei der n-ten Zuweisung sein soll, damit wir den zuvor freigegebenen Speicher wiederverwenden können.

Wenn wir dies beispielsweise im dritten Schritt (dh n=3) tun möchten, haben wir

x^3 <= 1 + x 

Diese Gleichung gilt für alle x so, dass 0 < x <= 1.3(grob)

Sehen Sie unten, welches x wir für verschiedene n erhalten:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

Beachten Sie, dass der Wachstumsfaktor geringer sein muss als 2seitdem x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

CEGRD
quelle
Sie scheinen zu behaupten, dass Sie den zuvor freigegebenen Speicher bereits bei der 2. Zuweisung mit einem Faktor von 1,5 wiederverwenden können. Dies ist nicht wahr (siehe oben). Lass es mich wissen, wenn ich dich missverstanden habe.
awx
Bei der 2. Zuweisung weisen Sie 1,5 * 1,5 * T = 2,25 * T zu, während die gesamte Freigabe, die Sie bis dahin vornehmen, T + 1,5 * T = 2,5 * T beträgt. 2,5 ist also größer als 2,25.
CEGRD
Ah, ich sollte genauer lesen; Alles, was Sie sagen, ist, dass der gesamte freigegebene Speicher bei der n-ten Zuweisung größer ist als der zugewiesene Speicher, und nicht, dass Sie ihn bei der n-ten Zuweisung wiederverwenden können.
awx
4

Es kommt wirklich darauf an. Einige Leute analysieren häufige Anwendungsfälle, um die optimale Anzahl zu finden.

Ich habe 1,5x 2,0x Phi x und eine Potenz von 2 gesehen.

Unbekannt
quelle
Phi! Das ist eine schöne Nummer. Ich sollte es von nun an benutzen. Vielen Dank! +1
Chris Jester-Young
Ich verstehe nicht ... warum Phi? Welche Eigenschaften macht es dafür geeignet?
Jason Creighton
4
@Jason: phi ergibt eine Fibonacci-Sequenz, daher ist die nächste Zuordnungsgröße die Summe aus der aktuellen Größe und der vorherigen Größe. Dies ermöglicht eine moderate Wachstumsrate, schneller als 1,5, aber nicht 2 (siehe meinen Beitrag, warum> = 2 keine gute Idee ist, zumindest für nicht verwaltete Sprachen).
Chris Jester-Young
1
@ Jason: Laut einem Kommentator meines Beitrags ist jede Zahl> phi in der Tat eine schlechte Idee. Ich habe selbst nicht nachgerechnet, um dies zu bestätigen, also nimm es mit einem Körnchen Salz.
Chris Jester-Young
2

Wenn Sie eine Verteilung über Array-Längen haben und über eine Utility-Funktion verfügen, die angibt, wie gerne Sie Speicherplatz oder Zeit verschwenden, können Sie auf jeden Fall eine optimale Strategie für die Größenänderung (und die anfängliche Größenänderung) auswählen.

Der Grund, warum das einfache konstante Vielfache verwendet wird, ist offensichtlich, dass jeder Anhang eine konstante Zeit amortisiert hat. Dies bedeutet jedoch nicht, dass Sie für kleine Größen kein anderes (größeres) Verhältnis verwenden können.

In Scala können Sie loadFactor für die Standardbibliotheks-Hash-Tabellen mit einer Funktion überschreiben, die die aktuelle Größe anzeigt. Seltsamerweise verdoppeln sich die veränderbaren Arrays nur, was die meisten Leute in der Praxis tun.

Ich kenne keine doppelten (oder 1,5 * ing) Arrays, die tatsächlich Speicherfehler auffangen und in diesem Fall weniger wachsen. Es scheint, dass Sie das tun möchten, wenn Sie ein riesiges einzelnes Array hätten.

Ich möchte weiter hinzufügen, dass es sinnvoll sein kann, die Größe der Arrays zu ändern, wenn Sie die Größe der Arrays lange genug beibehalten und den Speicherplatz im Laufe der Zeit bevorzugen erledigt.

Jonathan Graehl
quelle
2

Noch zwei Cent

  • Die meisten Computer haben virtuellen Speicher! Im physischen Speicher können Sie überall zufällige Seiten haben, die als ein zusammenhängender Bereich im virtuellen Speicher Ihres Programms angezeigt werden. Die Auflösung der Indirektion erfolgt durch die Hardware. Die Erschöpfung des virtuellen Speichers war auf 32-Bit-Systemen ein Problem, aber es ist wirklich kein Problem mehr. Das Füllen des Lochs ist also kein Problem mehr (außer in speziellen Umgebungen). Seit Windows 7 unterstützt sogar Microsoft 64 Bit ohne zusätzlichen Aufwand. @ 2011
  • O (1) wird mit jedem r > 1-Faktor erreicht. Der gleiche mathematische Beweis funktioniert nicht nur für 2 als Parameter.
  • r = 1,5 kann mit berechnet werden, old*3/2sodass keine Gleitkommaoperationen erforderlich sind. (Ich sage, /2weil Compiler es durch Bitverschiebung im generierten Assemblycode ersetzen, wenn sie es für richtig halten.)
  • MSVC hat sich für r = 1,5 entschieden, daher gibt es mindestens einen Hauptcompiler , der 2 nicht als Verhältnis verwendet.

Wie von jemandem erwähnt, fühlt sich 2 besser an als 8. Und auch 2 fühlt sich besser an als 1.1.

Mein Gefühl ist, dass 1,5 ein guter Standard ist. Davon abgesehen hängt es vom konkreten Fall ab.

Notinlist
quelle
2
Es wäre besser, n + n/2den Überlauf zu verzögern. Durch n*3/2die Verwendung wird Ihre mögliche Kapazität halbiert.
Owacoder
@owacoder Richtig. Aber wenn n * 3 nicht passt, aber n * 1.5 passt, sprechen wir über viel Speicher. Wenn n 32-Bit-Unsigend ist, läuft n * 3 über, wenn n 4G / 3 ist, das sind ca. 1,333G. Das ist eine riesige Zahl. Das ist viel Speicher in einer einzigen Zuordnung. Evern mehr, wenn Elemente nicht 1 Byte, sondern beispielsweise jeweils 4 Byte sind. Fragen Sie sich über den Anwendungsfall ...
Notinlist
3
Es ist wahr, dass es ein Randfall sein kann, aber Randfälle sind das, was normalerweise beißt. Es ist nie eine schlechte Idee, sich daran zu gewöhnen, nach möglichen Überläufen oder anderen Verhaltensweisen zu suchen, die auf ein besseres Design hindeuten, auch wenn dies in der Gegenwart weit hergeholt erscheint. Nehmen Sie als Beispiel 32-Bit-Adressen. Jetzt brauchen wir 64 ...
Owacoder
1

Ich stimme Jon Skeet zu, sogar mein theoretischer Freund besteht darauf, dass dies als O (1) nachgewiesen werden kann, wenn der Faktor auf 2x gesetzt wird.

Das Verhältnis zwischen CPU-Zeit und Speicher ist auf jedem Computer unterschiedlich, daher variiert der Faktor ebenso stark. Wenn Sie einen Computer mit Gigabyte RAM und einer langsamen CPU haben, ist das Kopieren der Elemente in ein neues Array viel teurer als auf einem schnellen Computer, der möglicherweise weniger Speicher hat. Diese Frage kann theoretisch für einen einheitlichen Computer beantwortet werden, was Ihnen in realen Szenarien überhaupt nicht hilft.

Tom
quelle
2
Wenn Sie die Array-Größe verdoppeln, erhalten Sie amotisierte O (1) -Einsätze. Die Idee ist, dass Sie jedes Mal, wenn Sie ein Element einfügen, auch ein Element aus dem alten Array kopieren. Nehmen wir an, Sie haben ein Array der Größe m mit m Elementen. Wenn Sie das Element m + 1 hinzufügen , ist kein Platz vorhanden, sodass Sie ein neues Array mit der Größe 2 m zuweisen . Anstatt alle ersten m Elemente zu kopieren, kopieren Sie jedes Mal eines, wenn Sie ein neues Element einfügen. Dadurch wird die Varianz minimiert (außer für die Zuweisung des Speichers). Sobald Sie 2 Millionen Elemente eingefügt haben, haben Sie alle Elemente aus dem alten Array kopiert.
Hvidgaard
-1

Ich weiß, dass es eine alte Frage ist, aber es gibt einige Dinge, die jeder zu vermissen scheint.

Erstens ist dies eine Multiplikation mit 2: Größe << 1. Dies ist eine Multiplikation mit etwas zwischen 1 und 2: int (Gleitkomma (Größe) * x), wobei x die Zahl ist, * Gleitkomma-Mathematik ist und der Prozessor hat um zusätzliche Anweisungen zum Gießen zwischen float und int auszuführen. Mit anderen Worten, auf Maschinenebene erfordert das Verdoppeln eine einzige, sehr schnelle Anweisung, um die neue Größe zu finden. Das Multiplizieren mit etwas zwischen 1 und 2 erfordert mindestenseine Anweisung zum Umwandeln der Größe in einen Float, eine Anweisung zum Multiplizieren (was eine Float-Multiplikation ist, sodass es wahrscheinlich mindestens doppelt so viele Zyklen dauert, wenn nicht vier- oder sogar achtmal so viele) und eine Anweisung zum Zurückwandeln in int. Dies setzt voraus, dass Ihre Plattform Float-Mathematik für die Allzweckregister durchführen kann, anstatt die Verwendung spezieller Register zu erfordern. Kurz gesagt, Sie sollten erwarten, dass die Mathematik für jede Zuordnung mindestens zehnmal so lange dauert wie eine einfache Linksverschiebung. Wenn Sie jedoch während der Neuzuweisung viele Daten kopieren, macht dies möglicherweise keinen großen Unterschied.

Zweitens und wahrscheinlich der große Kicker: Jeder scheint anzunehmen, dass der Speicher, der freigegeben wird, sowohl an sich selbst als auch an den neu zugewiesenen Speicher angrenzt. Dies ist mit ziemlicher Sicherheit nicht der Fall, es sei denn, Sie weisen den gesamten Speicher selbst vorab zu und verwenden ihn dann als Pool. Das Betriebssystem kann gelegentlichAm Ende tun Sie dies, aber die meiste Zeit wird es genug Fragmentierung des freien Speicherplatzes geben, damit jedes halbwegs anständige Speicherverwaltungssystem ein kleines Loch finden kann, in das Ihr Speicher gerade passt. Sobald Sie wirklich kleine Stücke bekommen, werden Sie mit größerer Wahrscheinlichkeit zusammenhängende Teile erhalten, aber bis dahin sind Ihre Zuweisungen groß genug, dass Sie sie nicht häufig genug ausführen, damit es nicht mehr darauf ankommt. Kurz gesagt, es macht Spaß, sich vorzustellen, dass die Verwendung einer idealen Zahl die effizienteste Nutzung des freien Speicherplatzes ermöglicht. In Wirklichkeit wird dies jedoch nur geschehen, wenn Ihr Programm auf Bare Metal ausgeführt wird (wie in, es gibt kein Betriebssystem) darunter alle Entscheidungen treffen).

Meine Antwort auf die Frage? Nein, es gibt keine ideale Zahl. Es ist so anwendungsspezifisch, dass es niemand wirklich versucht. Wenn Ihr Ziel die ideale Speichernutzung ist, haben Sie ziemlich viel Pech. Für die Leistung sind weniger häufige Zuweisungen besser, aber wenn wir nur so weitermachen, könnten wir mit 4 oder sogar 8 multiplizieren! Wenn Firefox auf einmal von 1 GB auf 8 GB springt, werden sich die Leute beschweren, so dass dies nicht einmal Sinn macht. Hier sind einige Faustregeln, nach denen ich mich richten würde:

Wenn Sie die Speichernutzung nicht optimieren können, verschwenden Sie zumindest keine Prozessorzyklen. Das Multiplizieren mit 2 ist mindestens eine Größenordnung schneller als das Gleitkomma-Rechnen. Es mag keinen großen Unterschied machen, aber es wird zumindest einen Unterschied machen (besonders früh, während der häufigeren und kleineren Zuteilungen).

Überdenken Sie es nicht. Wenn Sie nur 4 Stunden damit verbracht haben, herauszufinden, wie Sie etwas tun können, was bereits getan wurde, haben Sie nur Ihre Zeit verschwendet. Ganz ehrlich, wenn es eine bessere Option als * 2 gegeben hätte, wäre dies vor Jahrzehnten in der C ++ - Vektorklasse (und an vielen anderen Orten) geschehen.

Wenn Sie wirklich optimieren möchten, sollten Sie die kleinen Dinge nicht ins Schwitzen bringen. Heutzutage kümmert sich niemand mehr darum, dass 4 KB Speicher verschwendet werden, es sei denn, sie arbeiten an eingebetteten Systemen. Wenn Sie 1 GB Objekte zwischen 1 MB und 10 MB erreichen, ist das Verdoppeln wahrscheinlich viel zu viel (ich meine, das sind zwischen 100 und 1.000 Objekte). Wenn Sie die erwartete Expansionsrate schätzen können, können Sie sie an einem bestimmten Punkt auf eine lineare Wachstumsrate ausgleichen. Wenn Sie ungefähr 10 Objekte pro Minute erwarten, ist es wahrscheinlich in Ordnung, mit 5 bis 10 Objektgrößen pro Schritt (einmal alle 30 Sekunden bis zu einer Minute) zu wachsen.

Es kommt darauf an, nicht zu überlegen, zu optimieren, was Sie können, und bei Bedarf an Ihre Anwendung (und Plattform) anzupassen.

Rybec Arethdar
quelle
11
Natürlich n + n >> 1ist das gleiche wie 1.5 * n. Es ist ziemlich einfach, ähnliche Tricks für jeden praktischen Wachstumsfaktor zu finden, den Sie sich vorstellen können.
Björn Lindqvist
Das ist ein guter Punkt. Beachten Sie jedoch, dass sich außerhalb von ARM die Anzahl der Anweisungen mindestens verdoppelt. (Viele ARM-Anweisungen, einschließlich der Add-Anweisung, können eine optionale Verschiebung für eines der Argumente vornehmen, sodass Ihr Beispiel in einer einzelnen Anweisung arbeiten kann. Die meisten Architekturen können dies jedoch nicht.) Nein, in den meisten Fällen wird die Anzahl verdoppelt Die Anzahl der Anweisungen von eins bis zwei ist kein wesentliches Problem, aber bei komplexeren Wachstumsfaktoren, bei denen die Mathematik komplexer ist, kann dies für ein sensibles Programm einen Leistungsunterschied bedeuten.
Rybec Arethdar
@ Rybec - Obwohl es einige Programme gibt, die durch ein oder zwei Anweisungen empfindlich auf Zeitschwankungen reagieren, ist es sehr unwahrscheinlich, dass ein Programm, das dynamische Neuzuweisungen verwendet, jemals davon betroffen sein wird. Wenn das Timing so genau gesteuert werden muss, wird wahrscheinlich stattdessen statisch zugewiesener Speicher verwendet.
Owacoder
Ich mache Spiele, bei denen ein oder zwei Anweisungen am falschen Ort einen signifikanten Leistungsunterschied bewirken können. Das heißt, wenn die Speicherzuweisung gut gehandhabt wird, sollte dies nicht häufig genug vorkommen, damit einige Anweisungen einen Unterschied bewirken.
Rybec Arethdar