Bitmaps scheller als Arrays?

[Illumany]

Hallo Leute,

inzwischen habe ich schon eine Menge über PureBasic dazugelernt und bin mächtig beeindruckt.
Folgendes kann ich mir derzeit nicht erklären: Kann Bitmap-Handling tatsächlich schneller sein, als Array-Handling?
Wenn ich experimentell mit einer For-Next-Schleife eine Bitmap durchsuche, bin ich deutlich schneller, als in einem
zweidimensionalen Array. Wie kann das sein? Arrays sind doch Basic-intern und für Bitmaps müssen
Betriebssystem-Unterroutinen aufgerufen werden, oder nicht? Oder mache ich einen anderen Fehler?
Bei mir braucht die Bitmap-Schleife 156 Millisekunden, die Array-Schleife 281 Millisekunden. Debug-Modus ist aus.

Code: Alles auswählen

#size = 4096
#size_1 = #size -1
; x.u = 0
; y.u = 0
; p.w = 0

OpenConsole()
PrintN("Konsole")

CreateImage(bitmap, #size, #size)   ; Bitmap-Test
StartDrawing(ImageOutput(bitmap))

t = ElapsedMilliseconds()
For y = 0 To #size_1 					; ImageHeight(bitmap) -1
	For x = 0 To #size_1 				; ImageWidth(bitmap) -1
		p = Point( x, y)
	Next x
Next y
t = ElapsedMilliseconds() - t

StopDrawing()

; Debug("Bitmap")
; Debug(t)

PrintN("Bitmap")
PrintN(Str(t))

Dim tafel.w(#size, #size)				; Array-Test

t = ElapsedMilliseconds()
For y = 0 To #size_1
	For x = 0 To #size_1
		p = tafel( x, y)
	Next x
Next y
t = ElapsedMilliseconds() - t

StopDrawing()

; Debug("Tafel")
; Debug(t)

PrintN("Tafel")
PrintN(Str(t))
Delay(5000)

[Mr.L]

Den Geschwindigkeitsunterschied kann ich bestätigen.
Bitmap: 125ms, Array 188ms.

Bei einem eindimensionalen Array wird es schneller (45ms):

Code: Alles auswählen

Dim tafel.w(#size * #size)            ; Array-Test

t = ElapsedMilliseconds()
o = 0
For y = 0 To #size_1
   For x = 0 To #size_1
   	p = tafel(o)
   	o + 1
   Next x
Next y
t = ElapsedMilliseconds() - t

[Illumany]

Den Geschwindigkeitsunterschied kann ich bestätigen.
Bitmap: 125ms, Array 188ms.

Bei einem eindimensionalen Array wird es schneller (45ms): ...

Ja, erstaunlich. Auch erstaunlich ist, dass dieser Geschwindigkeitsvorteil erhalten bleibt,
wenn man ein 2D-Array aus einem 1D-Array nachbaut.
Scheinbar ist die interne Verarbeitungsgeschwindigkeit von 2D-Arrays in PureBasic langsamer,
als eine in Hochsprache handgestrickte. Kann das wirklich stimmen?

Bitmap: 156 Millisekunden
2D-Array: 265 Millisekunden
emuliertes 2D-Array (1D-Array): 78 Millisekunden

Code: Alles auswählen

; 
; Geschwindigkeitstest für 2D-Zugriff
; 1. Bitmap, 2. echtes 2D-Array, 3. emuliertes 2D-Array
; 

#size = 4096 : #size_1 = #size -1

OpenConsole()								; Bitmap-Test
PrintN("Konsole")
CreateImage(bitmap, #size, #size)   
StartDrawing(ImageOutput(bitmap))
t = ElapsedMilliseconds()
For y = 0 To #size_1 					; ImageHeight(bitmap) -1
	For x = 0 To #size_1 				; ImageWidth(bitmap) -1
		p = Point( x, y)
	Next x
Next y
t = ElapsedMilliseconds() - t
StopDrawing()
PrintN("2D-Bitmap")
PrintN(Str(t))


Dim tafel.w(#size, #size)				; 2D-Array
t = ElapsedMilliseconds()
For y = 0 To #size_1
	For x = 0 To #size_1
		p = tafel( x, y)
	Next x
Next y
t = ElapsedMilliseconds() - t
PrintN("Echtes 2D-Array")
PrintN(Str(t))


Dim tafel2.w(#size * #size)			; emuliertes 2D-Array
t = ElapsedMilliseconds()
For y = 0 To #size_1
	For x = 0 To #size_1
		p = tafel2( x + y * #size)    ; y * size = Zeile
	Next x
Next y
t = ElapsedMilliseconds() - t
PrintN("2D-Array-Emulation")
PrintN(Str(t))
Delay(5000)

[NicTheQuick]

Die Schleife mit dem 2D-Array ist nicht Cache-optimal. Das ist das ganze Problem. Folgender Code beweist es euch:

Code: Alles auswählen

; Geschwindigkeitstest für 2D-Zugriff
; 1. Bitmap, 2. echtes 2D-Array, 3. emuliertes 2D-Array
;

#size = 4096 : #size_1 = #size -1

OpenConsole()                        ; Bitmap-Test
PrintN("Konsole")
CreateImage(bitmap, #size, #size)   
If StartDrawing(ImageOutput(bitmap))
	t = ElapsedMilliseconds()
	For y = 0 To #size_1                ; ImageHeight(bitmap) -1
		For x = 0 To #size_1             ; ImageWidth(bitmap) -1
			p = Point( x, y)
		Next
	Next
	t = ElapsedMilliseconds() - t
	StopDrawing()
EndIf
PrintN("2D-Bitmap (Cache optimal): " + Str(t))

If StartDrawing(ImageOutput(bitmap))
	t = ElapsedMilliseconds()
	For x = 0 To #size_1                ; ImageHeight(bitmap) -1
		For y = 0 To #size_1             ; ImageWidth(bitmap) -1
			p = Point( x, y)
		Next
	Next
	t = ElapsedMilliseconds() - t
	StopDrawing()
EndIf
PrintN("2D-Bitmap (nicht Cache optimal): " + Str(t))


Dim tafel.i(#size, #size)            ; 2D-Array
t = ElapsedMilliseconds()
For x = 0 To #size_1
	For y = 0 To #size_1
		p = tafel( x, y)
	Next
Next
t = ElapsedMilliseconds() - t
PrintN("2D-Array (Cache optimal): " + Str(t))

t = ElapsedMilliseconds()
For y = 0 To #size_1
	For x = 0 To #size_1
		p = tafel( x, y)
	Next
Next
t = ElapsedMilliseconds() - t
PrintN("2D-Array (nicht Cache optimal): " + Str(t))

Delay(5000) 

Der Unterschied ist die Reihenfolge, in der das Array durchlaufen wird.

Wenn das Array so durchlaufen wird wie es wirklich im Speicher vorliegt, kann der Prozessor gleich einen ganzen Schwung in den Cache laden und schnell verarbeiten. In der "falsche" Reihenfolge wird immer im Speicher hin und her gesprungen, ohne dass wirklich etwas am Stück in den Cache geladen werden kann. Das macht diese Unterschiede aus.

Hier noch die Ausgabe:

Code: Alles auswählen

2D-Bitmap (Cache optimal): 195
2D-Bitmap (nicht Cache optimal): 1054
2D-Array (Cache optimal): 103
2D-Array (nicht Cache optimal): 288

[STARGÅTE]

Um NicTheQuicks Beispiel noch etwas näher zu bringen hier ein anderes Beispiel:

Code: Alles auswählen

Dim Beispiel.l(2,2)

Beispiel(0,0) = 1
Beispiel(1,0) = 2
Beispiel(2,0) = 3

ShowMemoryViewer(@Beispiel(), 9*4)

Hier kann man schön sehen, dass das Array also (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2) speichert (also in dem Fall spaltenweise), und nicht wie ein Bild, immer Zeilenweise.

Um so mehr hat es mich schon immer gewundert, warum man bei ReDim nur die letzte Dimension erweitern kann, was ja ein kompletten Umbau erzeugt. Einfacher und leichter wäre es ja die erste Dimension zu erweitern, dann brauch nichts verschoben werden, sondern einfach verlängert werden.

[Illumany]

Super! Vielen Dank für die Informationen.
Das mit der Cache-Optimalität habe ich kapiert.
Offenbar lohnt sich das Aufpassen an solchen Stellen.

Ich habe NicTheQuicks Beispiel noch um die "2D-Array-Emulation" erweitert, die Bitmap fairerweise auf 32 Bit umgestellt
und nochmal die Sache mit den unterschiedliche Arrays untersucht.
Auch wenn alle Schleifen Cache-optimal ablaufen, scheint es konstante erkennbare Unterschiede zwischen den Methoden zu geben:

Code: Alles auswählen

2D-Bitmap (Cache optimal): 156
2D-Array       "         :  94
2D-Array-Emulation    "  :  78 

Der handgestrickter Arrayzugriff scheint ein wenig schneller zu sein,
als der in PB implementierte Arrayzugriff

Bei der Gelegenheit: Wie kann ich die Konsolenausgabe kopieren?

Code: Alles auswählen

; Geschwindigkeitstest für 2D-Zugriff
; 1. Bitmap, 2. echtes 2D-Array, 3. emuliertes 2D-Array
;

#size = 4096 : #size_1 = #size -1

OpenConsole()                        ; Bitmap-Test
PrintN("Konsole")
CreateImage(bitmap, #size, #size, 32)   
If StartDrawing(ImageOutput(bitmap))
   t = ElapsedMilliseconds()
   For y = 0 To #size_1                ; ImageHeight(bitmap) -1
      For x = 0 To #size_1             ; ImageWidth(bitmap) -1
         p = Point( x, y)
      Next
   Next
   t = ElapsedMilliseconds() - t
   StopDrawing()
EndIf
PrintN("2D-Bitmap (Cache optimal): " + Str(t))

If StartDrawing(ImageOutput(bitmap))
   t = ElapsedMilliseconds()
   For x = 0 To #size_1                ; ImageHeight(bitmap) -1
      For y = 0 To #size_1             ; ImageWidth(bitmap) -1
         p = Point( x, y)
      Next
   Next
   t = ElapsedMilliseconds() - t
   StopDrawing()
EndIf
PrintN("2D-Bitmap (nicht Cache optimal): " + Str(t))


Dim tafel.i(#size, #size)            ; 2D-Array
t = ElapsedMilliseconds()
For x = 0 To #size_1
   For y = 0 To #size_1
      p = tafel( x, y)
   Next
Next
t = ElapsedMilliseconds() - t
PrintN("2D-Array (Cache optimal): " + Str(t))

t = ElapsedMilliseconds()
For y = 0 To #size_1
   For x = 0 To #size_1
      p = tafel( x, y)
   Next
Next
t = ElapsedMilliseconds() - t
PrintN("2D-Array (nicht Cache optimal): " + Str(t))

Dim tafel2.i(#size * #size)			; emuliertes 2D-Array
t = ElapsedMilliseconds()
For y = 0 To #size_1
	For x = 0 To #size_1
		p = tafel2( x + y * #size)    ; y * size = Zeile
	Next x
Next y
t = ElapsedMilliseconds() - t
PrintN("2D-Array-Emulation (Cache optimal): " + Str(t))

; emuliertes 2D-Array
t = ElapsedMilliseconds()
For x = 0 To #size_1
	For y = 0 To #size_1
		p = tafel2( x + y * #size)    ; y * size = Zeile
	Next y
Next x
t = ElapsedMilliseconds() - t
PrintN("2D-Array-Emulation (nicht Cache optimal): " + Str(t))

Delay(10000) 

[Illumany]

Um NicTheQuicks Beispiel noch etwas näher zu bringen hier ein anderes Beispiel:

Code: Alles auswählen

Dim Beispiel.l(2,2)

Beispiel(0,0) = 1
Beispiel(1,0) = 2
Beispiel(2,0) = 3

ShowMemoryViewer(@Beispiel(), 9*4)

Hier kann man schön sehen, dass das Array also (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2) speichert (also in dem Fall spaltenweise), und nicht wie ein Bild, immer Zeilenweise.

Um so mehr hat es mich schon immer gewundert, warum man bei ReDim nur die letzte Dimension erweitern kann, was ja ein kompletten Umbau erzeugt. Einfacher und leichter wäre es ja die erste Dimension zu erweitern, dann brauch nichts verschoben werden, sondern einfach verlängert werden.

Aha, offenbar werden Arrays im Format ARRAY(Zeile, Spalte) abgespeichert. Also auf eine Bitmap übertragen: ARRAY(y, x).
Ja, wenn sich sonst kein Denkfehler eingeschlichen hat, scheint ReDim irgendwie merkwürdig implementiert zu sein.