Beschreibungen und Ergebnisse

Bitte stellen Sie uns folgende Zeugnisse aus:
Rainer Rabenstein, E-881, 9025614: 185.922 PS
Martin Exler, E-881, 9126090: 185.450 SE

Es wurden5 Testprogramme gemessen:

  1. Kopieren des Speichers durch MEMCPY
  2. Kopieren des Speichers durch GC
  3. Lineare Liste mit 5 Referenzen auf Nachfolgeglied
  4. Fragmentierung des Speichers durch verschachteltes Erstellen mehrer Listen
  5. Stack-ähnliche Operationen

1. Kopieren des Speichers durch MEMCPY

Ein Speicherbereich bestimmter Größe wird mit der C-Function MEMCPY mehrmals kopiert.

Ergebnisse:

                                                           	Zeit

Met. Memory 	   #Elemente    Durchgänge    Elementgröße       u      s

     320.000	   10.000       300           1		       0.3    0.3
     320.000       20.000	300           1		       0.5    0.3
     320.000       40.000       300           1 	       1.2    0.3
Wie erwartet, steigt der Aufwand proportional zur Anzahl der kopierten Elemente.

2. Kopieren des Speichers durch GC

Es wird wie bei MEMCPY der Speicher mit einer bestimmten Anzahl von Elementen gefüllt, und dann eine GC ausgeführt.

Ergebnisse:

                                                           	Zeit

Met. Memory 	   #Elemente    Durchgänge    Elementgröße       u      s

C    320.000	   10.000       300           1		       6.6    0.3
C    320.000       20.000       300           1               15.5    0.7
C    320.000	   40.000       300           1	              34.3    1.4

W    160.000	   10.000       300           1		       1.7    0.1
W    160.000       20.000       300           1                3.9    0.2
W    160.000	   40.000       300           1                9.8    0.3
Der größere Aufwand beim Cheney-Algorithmus (CA) erklärt sich durch den Umstand, daß bei jedem GC-Aufruf der gesamte LIVE-Speicher kopiert wird, obwohl der in diesem Fall kompakt vorliegt. .
Beim Wegbreit-Algorithmus(WA) wird nur markiert, der dafür notwendige Aufwand fällt beim CA ebenfalls an.
Die Zeiten sind ungefähr proportional zur Anzahl der bearbeiteten Speicherzellen.
Die Zeiten fuer das reine Kopieren entsprechen den Ergebnissen des ersten Tests (siehe oben).

3. Lineare Liste mit 5 Referenzen auf Nachfolgeglied


Es wird eine lineare Liste im Speicher angelegt, mit der Besonderheit, daß jedes Listenelement 5 Referenzen auf seinen Nachfolger enthält.
Ist die Liste voll, d.h., ist die als Parameter angegebene Anzahl der Elemente erreicht, so wird die Liste wieder gelöscht, und hinterlaßst im Speicher ein "Loch", das von neu angelegten Speicherzellen nicht mehr belegt werden kann. Dadurch kommt es fru"her oder später zur GC, die wieder freien Speicher schafft.
Im Fall der GC muessen alle 5 Referenzen aktualisert werden.

Ergebnisse:

                                                           	Zeit

Met. Memory 	   #Elemente    Durchgänge    Elementgröße       u      s

C     80.000	   100          10.000        5		       8.3    0.6
C    160.000       200          10.000        5               10.0    0.5
C    320.000	   400          10.000        5	              22.0    1.6

W     40.000	   100          10.000        5		       5.5    0.2
W     80.000       200          10.000        5               12.0    0.3
W    160.000	   400          10.000        5               26.8    1.5
Der (wenn auch geringe) Zeitvorteil beim CA erklärt sich durch den Umstand, daß der WA bei der Aktualisierung der Referenzen die neue Adresse jedes Datensatzes in der Tabelle suchen muß, wogegen der CA die Adresse direkt Über den Forward-Pointer erfährt.

4. Fragmentieren des Speichers durch verschachteltes Erstellen mehrerer Listen

Zweihundert Listen mit verschiedner Elemet-Größe werden inneinander verschachtelt. Ist eine Liste völlig gefüllt, d.h. sind alle #Elemente angelegt, so wird diese Liste wieder geloescht, und somit Speicher ungenützt, der zwischen LIVE-Zellen liegt, aber nicht verwendet werden kann. Die GC ¨schiebt¨ diesen Fragmentierten Speicher zusammen, und gibt die unbenutzten ¨Flecken¨ zwischen den LIVE-Zellen wieder frei.

Ergebnisse:

                                                           	Zeit

Met. Memory 	   #Elemente    Durchgänge    Elementgröße       u      s

C    80.000	   10x200       10.000        1/10            11.3    1.1
C   160.000        20x200       10.000        1/10            12.4    0.6
C   320.000	   40x200       10.000        1/10            16.6    0.7

W    40.000	   10x200       10.000        1/10	      13.2    0.3
W    80.000        20x200       10.000        1/10            16.1    0.7
W   160.000	   40x200       10.000        1/10            20.4    2.0
Der CA ist nicht fÄhig, ganze Speicherblöcke zu verschieben, der WA schon. Dieser Umstand verschafft dem WA einen relativen Vorteil, wenn bei der GC ganze (große) zusammenhängende Blöcke kopiert werden sollen (siehe 5.), bei diesem Testprogramm liegt der LIVE-Speicher allerdings fragmentiert vor, was einen Performance-Nachteil für den WA bringt.

5. Stack-ähnliche Operationen

Es werden PUSH und POP-Operationen ausfegührt, bei denen die ungenützten Speicherzellen nicht wieder freigegeben werden, dadurch kommt es zum Auslösen einer GC.

Ergebnisse:

                                                           	Zeit

Met. Memory 	   #Elemente    Durchgänge    Elementgröße       u      s

C    80.000	   2.000        1000          1		       6.6    0.3
C    80.000        4.000        1000          1               15.5    0.7
C    80.000	   8.000        1000          1	              34.3    1.4
 
W    40.000	   2.000        1000          1		       1.7    0.1
W    40.000        4.000        1000          1                3.9    0.2
W    40.000	   8.000        1000          1                9.8    0.3
Bei dieser Variante liegt der LIVE-Speicherbereich in einem Block vor.
Der WA erkennt zusammenhängende Speicherblöcke und kopiert sie auch in einem Durchgang, deshalb auch diese relativ zum CA sehr kurzen Zeiten. Der Ca muß jede LIVE-Zelle untersuchen und einzeln kopieren.
Der große Vorteil des Wegbreit-Algorithmus liegt sicher im halben Speicherbedarf im Vergleich zum Cheney-Algorithmus.
Materialordner

HTML-Anleitung