Intervall Heaps

Anhang

zur Studienarbeit vonThomas Schwanck

amInstitut fur Informationssysteme

Fachgebiet Programmiersprachen und UbersetzerProf. Dr. R. Parchmann

2004

auf Basis des ArtikelsInterval Heaps

von J. van Leeuwen and D. WoodThe Computer Journal Vol. 36 Nr. 3 1993 S.209-216

Intervall Heaps

A. Anhang:Untersuchung der d-dimensionalen Intervallheaps

In diesem Anhang soll versucht werden, die Ursachen der ”Zacken“ im Dia-gramm, das die zum Erzeugen eines d -Intervall Heaps in Abhangigkeit vonder Anzahl der Elemente benotigte Laufzeit zeigt, zu finden. Als erstes wur-de die Messung mit weiteren Zwischenwerten (Abstand der Messungen jetzt25000 Objekte statt 100000) und verschiedenen Dimensionen (1-4) wieder-holt:

• Mit 1 Dimension:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0250500750

100012501500175020002250250027503000325035003750

MinimumMittelwertMaximum

*25000 Objekte

msec

• Mit 2 Dimensionen:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0250500750

100012501500175020002250250027503000325035003750

MinimumMittelwertMaximum

*25000 Objekte

msec

1

Intervall Heaps

• Mit 3 Dimensionen:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0250500750

10001250150017502000225025002750300032503500375040004250

MinimumMittelwertMaximum

*25000 Objekte

msec

• Mit 4 Dimensionen:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0250500750

100012501500175020002250250027503000325035003750400042504500

MinimumMittelwertMaximum

* 25000 Objekte

msec

Es wurden d -Intervall Heaps mit bis 5 Millionen Objekten erzeugt, es wurdenjeweils 10 Messungen gemacht und davon Minimal-, Mittel- und Maximal-wert dargestellt.

2

Intervall Heaps

100 110 120 130 140 150 160 170 180 190 2001500

1750

2000

2250

2500

2750

3000

3250

3500

3750

4000

4250

Mittelwert (1 dim)Mittelwert (2 dim)Mittelwert (3 dim)Mittelwert (4 dim)

* 25000 Objekte

msec

Wie die Ubersicht zeigt, hangt die Form der Zacken nicht mit der Dimensionund damit mit der Große des benutzten Speichers ab.

3

Intervall Heaps

Als nachstes sollte getestet werden, ob die Form der Kurve von dem verwen-deten Prozesseor und oder Betriebssystem abhangt:Der zweite Rechner war ein Pentium M 1,4 Ghz und 768 MB RAM mitMicrosoft Windows XP Professional Version 2002 SP 2 und sonst denselbenSoftwareversionen/Einstellungen, Messung in in 2 Dimensionen:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

200

400

600

800

1000

1200

1400

1600

1800

2000

2200

2400

MinimumMittelwertMaximum

*25000 Objekte

msec

Die Messung wurde auf demselben Rechner unter Suse-linux 9.1 wiederholt:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

250

500

750

1000

1250

1500

1750

2000

2250

2500

MinimumMittelwertMaximum

*25000 Objekte

msec

Als dritter Rechner kam ein Pentium 4 mit 2,66 Ghz und 512 MB RAMmit Microsoft Windows XP Home mit SP 1 und Java 2 Version 1.4.2 zumEinsatz:

4

Intervall Heaps

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

200

400

600

800

1000

1200

1400

1600

1800

2000

MinimumMittelwertMaximum

*25000 Objekte

msec

Offensichtlich scheint die Form der Kurven weder von dem verwendeten x86Prozessor abzuhangen noch von dem verwendeten Betriebsystem. Im wei-teren soll deshalb nicht mehr zwischen den x86 Prozessoren unterschiedenwerden.ALs nachstes wurden Messungen auf zwei Apple Mac G5, einer Sun Enter-prise 220R (Sun E 220R), einer Sun Blade 1000 (Sun B1000) sowie einerSGI Octane (Irix) gemacht. Die Systeme waren wie folgt konfiguriert:

Name Prozessor [Mhz] Betriebssystem RAM [MB] Java 2 VersionMac G5 (1) PPC G5 1800 Mac OS X 512 1.4.2Mac G5 (2) 2xPPC G5 1800 Mac OS X 1024 1.4.2Sun E 220R 2xUltraSPARC II 360 Solaris 9 1024 1.5.0 Beta 4

Sun Blade 1000 2xUltraSPARC III 750 Solaris 9 2048 1.5.0 Beta 3-b58SGI Octane MIPS R10000 250 Irix 3.5 1024 1.4.1

5

Intervall Heaps

Die Messungen sind alle in 3 Dimensionen gemacht worden.Die Messung auf dem Mac G5 (1) ergab:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

250

500

750

1000

1250

1500

1750

2000

2250

2500

MinimumMittelwertMaximum

*25000 Objekte

msec

Die Messung auf dem Mac G5 (2) ergab:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

200

400

600

800

1000

1200

1400

1600

1800

2000

2200

2400

MinimumMittelwertMaximum

*25000 Objekte

msec

6

Intervall Heaps

Die Messung auf der Sun Enterprise 220R ergab:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

20000

MinimumMittelwertMaximum

*25000 Objekte

msec

Die Messung auf der Sun Blade 1000 ergab:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0500

10001500200025003000350040004500500055006000650070007500800085009000

MinimumMittelwertMaximum

*25000 Objekte

msec

7

Intervall Heaps

Die Messung auf der SGI Octane ergab:1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

2500

5000

7500

10000

12500

15000

17500

20000

22500

25000

27500

30000

MinimumMittelwertMaximum

*25000 Objekte

msec

Aus irgendwelchen Grunden war die erste Messreihe gestort, weshalb diesenicht mit fur das Diagramm ausgewertet wurde.Leider war die JVM auf der SGI Octane nicht ganz einsatzfahig und warnur im Kompatibilitatsmodus zum Ausfuhren des Test zu bringen, weshalbich die Messwerte nicht weiter betrachten werde.Zusammenfassend ein Uberblick uber die Kurvenformen aller gemessenenSysteme, die Kurven der schneller x86 und PowerPC Systeme sind leidersehr gestaucht, aber als Ubersicht sollte es ausreichen:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

2500

5000

7500

10000

12500

15000

17500

20000

22500

25000

27500

30000

x86MacSun E 220RSGI Octane

*25000 Objekte

msec

8

Intervall Heaps

Allen Messungen gemein war, das die JVM maximal 180 MByte Speicherfur die Messungen zur Verfugung stellte. Als letztes wurde die Abhangigkeitder Ergebnisse von dem der JVM zugeteilten minimalen / maximalen Spei-chergroße gemessen:

Messung auf Pentium M, maximale Speichergroße 150-350 MByte:1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

250

500

750

1000

1250

1500

1750

2000

2250

2500

150 MByte175 MByte200 MByte250 Mbyte300 MByte

*25000 Objekte

msec

Messung auf Sun Enterprise 220R, maximale Speichergroße 130-180 MByte:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

20000

130MB140MB150MB160MB170MB180MB

*25000 Objekte

msec

9

Intervall Heaps

Messung auf Sun Blade 1000, maximale Speichergroße 450-600 MByte:1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

210

220

230

240

250

260

270

280

290

300

310

320

330

340

350

360

370

380

390

400

410

420

430

440

450

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

20000

450M475M500M525M550M575M600M

*25000 Objekte

msec

Messung auf Sun Enterprise 220R, minimale Speichergroße 450-600 MByte:

1 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

160

170

180

190

200

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

20000

50 MB70 MB90 MB110 MB130 MB150 MB

*25000 Objekte

msec

Abschließend bleibt zu sagen, das die ”Zacken“ wohl von der Speicherver-waltung der JVM verursacht werden, Java kann also nicht fur Laufzeittestsvon Algorithmen bzw. deren Implementationen empfohlen werden.

10

Intervall Heaps

Samtliche Meßwerte liegen im Ordner ”Meßwerte“ auf der CD als Textda-teien im CSV-Format (Comma Separated Values) vor.Es folgt eine Ubersicht uber den Inhalt der Dateien:

Datei Inhalt

Ergebnisse Irix 9Messungen.txt SGI OctaneErgebnisse P4 W32.txt Pentium 4 mit Windows XP HomeErgebnisse Pentium III W32 1dim.txt Pentium II mit Windows XP Home, 1 DimensionErgebnisse Pentium III W32 2dim.txt Pentium II mit Windows XP Home, 2 DimensionErgebnisse Pentium III W32 3dim.txt Pentium II mit Windows XP Home, 3 DimensionErgebnisse Pentium III W32 4dim.txt Pentium II mit Windows XP Home, 4 DimensionErgebnisse PM 150MB.txt Pentium M, JVM-Speicher max. 150 MByteErgebnisse PM 175MB.txt Pentium M, JVM-Speicher max. 175 MByteErgebnisse PM 200MB.txt Pentium M, JVM-Speicher max. 200 MByteErgebnisse PM 250MB.txt Pentium M, JVM-Speicher max. 250 MByteErgebnisse PM 300MB.txt Pentium M, JVM-Speicher max. 300 MByteErgebnisse PM 350MB.txt Pentium M, JVM-Speicher max. 350 MByteErgebnisse PM Linux.txt Pentium M mit Suse-Linux 9.2Ergebnisse PPC G5 1.txt PowerPC G5 (1)Ergebnisse PPC G5 2.txt PowerPC G5 (2)Ergebnisse Sun Blade 1000 max 450MB.txt Sun B1000, JVM-Speicher max. 450 MByteErgebnisse Sun Blade 1000 max 475MB.txt Sun B1000, JVM-Speicher max. 475 MByteErgebnisse Sun Blade 1000 max 500MB.txt Sun B1000, JVM-Speicher max. 500 MByteErgebnisse Sun Blade 1000 max 525MB.txt Sun B1000, JVM-Speicher max. 525 MByteErgebnisse Sun Blade 1000 max 550MB.txt Sun B1000, JVM-Speicher max. 550 MByteErgebnisse Sun Blade 1000 max 575MB.txt Sun B1000, JVM-Speicher max. 575 MByteErgebnisse Sun Blade 1000 max 600MB.txt Sun B1000, JVM-Speicher max. 600 MByteErgebnisse Sun E220R max 130MB.txt Sun E220R, JVM-Speicher max. 130 MByteErgebnisse Sun E220R max 140MB.txt Sun E220R, JVM-Speicher max. 140 MByteErgebnisse Sun E220R max 150MB.txt Sun E220R, JVM-Speicher max. 150 MByteErgebnisse Sun E220R max 160MB.txt Sun E220R, JVM-Speicher max. 160 MByteErgebnisse Sun E220R max 170MB.txt Sun E220R, JVM-Speicher max. 170 MByteErgebnisse Sun E220R max 180MB.txt Sun E220R, JVM-Speicher max. 180 MByteErgebnisse Sun E220R min 50MB.txt Sun E220R, JVM-Speicher min. 50 MByteErgebnisse Sun E220R min 70MB.txt Sun E220R, JVM-Speicher min. 70 MByteErgebnisse Sun E220R min 90MB.txt Sun E220R, JVM-Speicher min. 90 MByteErgebnisse Sun E220R min 110MB.txt Sun E220R, JVM-Speicher min. 110 MByteErgebnisse Sun E220R min 130MB.txt Sun E220R, JVM-Speicher min. 130 MByteErgebnisse Sun E220R min 150MB.txt Sun E220R, JVM-Speicher min. 150 MByteMesswerte Irix.txt Messwerte SGI OctaneMesswerte P4 W32.txt Messwerte Pentium 4, Win32Messwerte PM 150MB.txt Messwerte Pentium M, JVM-Speicher max. 150 MByteMesswerte PM 175MB.txt Messwerte Pentium M, JVM-Speicher max. 175 MByteMesswerte PM 200MB.txt Messwerte Pentium M, JVM-Speicher max. 200 MByteMesswerte PM 250MB.txt Messwerte Pentium M, JVM-Speicher max. 250 MByteMesswerte PM 300MB.txt Messwerte Pentium M, JVM-Speicher max. 300 MByteMesswerte PM 350MB.txt Messwerte Pentium M, JVM-Speicher max. 350 MByteMesswerte Sun Blade 1000 max 450MB.txt Messwerte Sun B1000, JVM-Speicher max. 450 MByteMesswerte Sun Blade 1000 max 475MB.txt Messwerte Sun B1000, JVM-Speicher max. 475 MByteMesswerte Sun Blade 1000 max 500MB.txt Messwerte Sun B1000, JVM-Speicher max. 500 MByteMesswerte Sun Blade 1000 max 525MB.txt Messwerte Sun B1000, JVM-Speicher max. 525 MByteMesswerte Sun Blade 1000 max 550MB.txt Messwerte Sun B1000, JVM-Speicher max. 550 MByteMesswerte Sun Blade 1000 max 575MB.txt Messwerte Sun B1000, JVM-Speicher max. 575 MByteMesswerte Sun Blade 1000 max 600MB.txt Messwerte Sun B1000, JVM-Speicher max. 600 MByteMesswerte Sun E220R max 130MB.txt Messwerte Sun E220R, JVM-Speicher max. 130MByteMesswerte Sun E220R max 140MB.txt Messwerte Sun E220R, JVM-Speicher max. 140MByteMesswerte Sun E220R max 150MB.txt Messwerte Sun E220R, JVM-Speicher max. 150MByteMesswerte Sun E220R max 160MB.txt Messwerte Sun E220R, JVM-Speicher max. 160MByteMesswerte Sun E220R max 170MB.txt Messwerte Sun E220R, JVM-Speicher max. 170MByteMesswerte Sun E220R max 180MB.txt Messwerte Sun E220R, JVM-Speicher max. 180MByteMesswerte Sun E220R min 50MB.txt Messwerte Sun E220R, JVM-Speicher min. 50MByteMesswerte Sun E220R min 70MB.txt Messwerte Sun E220R, JVM-Speicher min. 70MByteMesswerte Sun E220R min 90MB.txt Messwerte Sun E220R, JVM-Speicher min. 90MByteMesswerte Sun E220R min 110MB.txt Messwerte Sun E220R, JVM-Speicher min. 110MByteMesswerte Sun E220R min 130MB.txt Messwerte Sun E220R, JVM-Speicher min. 130MByteMesswerte Sun E220R min 150MB.txt Messwerte Sun E220R, JVM-Speicher min. 150MByteMittelwerte Pentium III W32 1-4dim.txt Pentium II Win32, 1-4 DimensionenMittelwerte PM 150-350M.txt Pentium M, JVM-Speicher 150-350 MByteMittelwerte Sun Blade 1000 max 450-600MB.txt Sun B1000, JVM-Speicher max. 450-600 MByteMittelwerte Sun E220R max 130-180MB.txt Sun E220R, JVM-Speicher max. 130-180 MByteMittelwerte Sun E220R min 50-150MB.txt Sun E220R, JVM-Speicher min. 50-150 MByte

Mittelwerte x86 Sun E220R PPC SGI Octane.txt Ubersicht x86, Sun E220R, PPC, SGI Octane

Mittelwerte x86 W32 x86 linux PPC.txt Ubersicht x82/Win32, x86/Linux, PPC

11