Somebody explain this one to me...

[SMcNeill]

Code: QB64: [Select]

1. Screen _NewImage(1024, 720, 32)
2. Do: Loop Until _ScreenExists
3. _ScreenMove _Middle
4.  
5.  
6. TestLimit = 100
7. Radius = 350
8.  
9. Randomize Timer
10. t# = Timer
11. For i = 1 To TestLimit
12.     'Cls , &HFF000000 + Int(Rnd * &HFFFFFF)
13.     k& = &HFF000000 + Int(Rnd * &HFFFFFF)
14.  
15.     Circle (512, 360), Radius, k&
16.     Fill 512, 360, k&, 0
17. Next
18.  
19. t1# = Timer
20. For i = 1 To TestLimit
21.     'Cls , &HFF000000 + Int(Rnd * &HFFFFFF)
22.     k& = &HFF000000 + Int(Rnd * &HFFFFFF)
23.  
24.     Circle (512, 360), Radius, k&
25.     Fill 512, 360, k&, -1
26. Next
27. t2# = Timer
28.  
29. Print Using "###.#### seconds for Fill."; t1# - t#
30. Print Using "###.#### seconds for Fill Method -1."; t2# - t1#
31.  
32.  
33.  
34.  
35.  
36. Sub Fill (Passx, Passy, kolor As Long, METHOD)
37.     $Checking:Off
38.     B = _Blend
39.     _DontBlend
40.  
41.     Dim TempGrid(0 To _Width - 1, 0 To _Height - 1) As Long
42.     Dim As _MEM m, m1: m = _Mem(TempGrid()): m1 = _MemImage(0)
43.     Dim o As _Offset
44.     If METHOD Then
45.         _MemCopy m1, m1.OFFSET, m1.SIZE To m, m.OFFSET
46.     End If
47.     o = 0
48.     Do Until o >= m.SIZE
49.         If _MemGet(m1, m1.OFFSET + o, _Unsigned Long) = kolor Then
50.             _MemPut m, m.OFFSET + o, -1 As LONG
51.             'Else
52.             '_MemPut m, m.OFFSET + o, 0 As LONG
53.         End If
54.         o = o + 4
55.     Loop
56.  
57.     TempGrid(Passx, Passy) = 1
58.     startx = Passx: finishx = Passx
59.     starty = Passy: finishy = Passy
60.  
61.     Do Until finished
62.         pass = pass + 1
63.         finished = -1
64.         For x = startx To finishx
65.             For y = starty To finishy
66.                 'If TempGrid(x, y) <> 0 Then Print x, y, TempGrid(x, y): Sleep
67.  
68.                 If TempGrid(x, y) = pass Then
69.                     tempx = x
70.                     Do Until tempx = 0
71.                         If TempGrid(tempx - 1, y) = 0 Then
72.                             TempGrid(tempx - 1, y) = pass + 1
73.                             tempx = tempx - 1
74.                             If tempx < startx Then startx = tempx
75.                             finished = 0
76.                         Else
77.                             tempx = 0
78.                         End If
79.                     Loop
80.  
81.                     tempx = x
82.                     Do Until tempx = _Width - 1
83.                         If TempGrid(tempx + 1, y) = 0 Then
84.                             TempGrid(tempx + 1, y) = pass + 1
85.                             tempx = tempx + 1
86.                             If tempx > finishx Then finishx = tempx
87.                             finished = 0
88.                         Else
89.                             tempx = _Width - 1
90.                         End If
91.                     Loop
92.  
93.                     tempy = y
94.                     Do Until tempy = 0
95.                         If TempGrid(x, tempy - 1) = 0 Then
96.                             TempGrid(x, tempy - 1) = pass + 1
97.                             tempy = tempy - 1
98.                             If tempy < starty Then startx = tempy
99.                             finished = 0
100.                         Else
101.                             tempy = 0
102.                         End If
103.                     Loop
104.  
105.                     tempy = y
106.                     Do Until tempy = _Height - 1
107.                         If TempGrid(x, tempy + 1) = 0 Then
108.                             TempGrid(x, tempy + 1) = pass + 1
109.                             tempy = tempy + 1
110.                             If tempy > finishy Then finishy = tempy
111.                             finished = 0
112.                         Else
113.                             tempy = _Height - 1
114.                         End If
115.                     Loop
116.                 End If
117.         Next y, x
118.     Loop
119.  
120.     o = 0
121.     Do Until o >= m.SIZE
122.         If _MemGet(m, m.OFFSET + o, _Unsigned Long) <> 0 Then _MemPut m1, m1.OFFSET + o, kolor As _UNSIGNED LONG
123.         o = o + 4
124.     Loop
125.     _MemFree m: _MemFree m1
126.     $Checking:On
127.     If B Then _Blend
128. End Sub

  [ You are not allowed to view this attachment ]  

Now, if you guys look, there's only one difference in the code:

    If METHOD Then
        _MemCopy m1, m1.OFFSET, m1.SIZE To m, m.OFFSET
    End If

The main process here works like this:

First, we make an array the size of the screen.
Then where the color exists that we want to use as a paint boundary, we assign a value of -1 to the grid in that position.
Then we do a little pathfinding style routine counting passes to fill in from the point we choose to the end of those boundaries...

Both routines work flawlessly.  Neither has any issues doing what they're supposed to do. 

In one (where we pass a method value of 0), the array has starts out empty with values of in it, and we assign a value of -1 to any point where the chosen color is... 

In the other (where we pass a method value of anything but 0), we copy the whole array of screen colors over, and assign a value of -1 to any point where the chosen color is..  (Note, this can only work as long as our screen doesn't have any bright white characters printed on it, as it doesn't have in these instances here.)

Now, logically speaking, it would seem that one method would, indeed, be faster than the other.  Wouldn't it be faster to go with a blank array, rather than first having to copy and alter every pixel from the screen onto the array?  You'd think so...

...and, as the screenshot above illustrates, YOU'D BE WRONG!!

It's faster to copy the whole screen into our array -- a LOT faster -- than it is to NOT copy the screen.  WTH?!!  WHY??

Why is it faster to do MORE work than it is to SKIP that work???

I find the differences in the speed runs here to be mind boggling, and I can't sort out why the heck it's faster to do more work than it is to NOT do it.

Anyone want to take a shot at explaining why this has such different speed results with it?  I'm completely baffled here.

[Petr]

It does not make any sense. The only thing I can think of, but I'm really guessing, is the organization of bytes in memory and in the field. Is it the same or is it the other way around?

[SMcNeill]

It does not make any sense. The only thing I can think of, but I'm really guessing, is the organization of bytes in memory and in the field. Is it the same or is it the other way around?

It doesn't make any sense to me either. 

The first has a blank array the size of our screen width and height.

The second is that exact same array, with the screen values copied over.

Then we set the boundary color to -1 and process that array in the exact same manner for either of those two methods....

The second is doing more work than the first, adding in an extra, unneeded step -- but it's finishing up 10x faster than the original!

It makes no sense to me.  I'm utterly baffled by these results.

[Petr]

Wait. First run is WITH METHOD = 0 so MEMCOPY on row 46 is not used and duration (here) is 15 seconds. Second run use MEMCOPY and duration is 0.6 second here. If is MEMCOPY commented, then both run durations are 15 seconds on my computer.

Code: QB64: [Select]

1. Screen _NewImage(1024, 720, 32)
2. Do: Loop Until _ScreenExists
3. _ScreenMove _Middle
4.  
5.  
6. TestLimit = 100
7. Radius = 350
8.  
9. Randomize Timer
10. t# = Timer
11. For i = 1 To TestLimit
12.     'Cls , &HFF000000 + Int(Rnd * &HFFFFFF)
13.     k& = &HFF000000 + Int(Rnd * &HFFFFFF)
14.  
15.     Circle (512, 360), Radius, k&
16.     Fill 512, 360, k&, 0
17. Next
18.  
19. t1# = Timer
20. For i = 1 To TestLimit
21.     'Cls , &HFF000000 + Int(Rnd * &HFFFFFF)
22.     k& = &HFF000000 + Int(Rnd * &HFFFFFF)
23.  
24.     Circle (512, 360), Radius, k&
25.     Fill 512, 360, k&, -1
26. Next
27. t2# = Timer
28.  
29. Print Using "###.#### seconds for Fill."; t1# - t#
30. Print Using "###.#### seconds for Fill Method -1."; t2# - t1#
31.  
32.  
33.  
34.  
35.  
36. Sub Fill (Passx, Passy, kolor As _Unsigned Long, METHOD)
37.     $Checking:Off
38.     B = _Blend
39.     '_DontBlend
40.  
41.     ReDim TempGrid(0 To _Width - 1, 0 To _Height - 1) As _Unsigned Long
42.     Dim As _MEM m, m1: m = _Mem(TempGrid()): m1 = _MemImage(0)
43.     Dim o As _Offset
44.  
45.     If METHOD Then 'this is second run
46.         _MemCopy m1, m1.OFFSET, m1.SIZE To m, m.OFFSET
47.     End If
48.     o = 0
49.  
50.     If METHOD = 0 Then 'this is first run
51.         Do Until o >= m.SIZE
52.             If _MemGet(m1, m1.OFFSET + o, _Unsigned Long) = kolor Then
53.                 _MemPut m, m.OFFSET + o, -1 As _UNSIGNED LONG
54.                 'Else
55.                 '_MemPut m, m.OFFSET + o, 0 As LONG
56.             End If
57.             o = o + 4
58.         Loop
59.     End If
60.  
61.     TempGrid(Passx, Passy) = 1
62.     startx = Passx: finishx = Passx
63.     starty = Passy: finishy = Passy
64.  
65.     Do Until finished
66.         pass = pass + 1
67.         finished = -1
68.         For x = startx To finishx
69.             For y = starty To finishy
70.                 'If TempGrid(x, y) <> 0 Then Print x, y, TempGrid(x, y): Sleep
71.  
72.                 If TempGrid(x, y) = pass Then
73.                     tempx = x
74.                     Do Until tempx = 0
75.                         If TempGrid(tempx - 1, y) = 0 Then
76.                             TempGrid(tempx - 1, y) = pass + 1
77.                             tempx = tempx - 1
78.                             If tempx < startx Then startx = tempx
79.                             finished = 0
80.                         Else
81.                             tempx = 0
82.                         End If
83.                     Loop
84.  
85.                     tempx = x
86.                     Do Until tempx = _Width - 1
87.                         If TempGrid(tempx + 1, y) = 0 Then
88.                             TempGrid(tempx + 1, y) = pass + 1
89.                             tempx = tempx + 1
90.                             If tempx > finishx Then finishx = tempx
91.                             finished = 0
92.                         Else
93.                             tempx = _Width - 1
94.                         End If
95.                     Loop
96.  
97.                     tempy = y
98.                     Do Until tempy = 0
99.                         If TempGrid(x, tempy - 1) = 0 Then
100.                             TempGrid(x, tempy - 1) = pass + 1
101.                             tempy = tempy - 1
102.                             If tempy < starty Then startx = tempy
103.                             finished = 0
104.                         Else
105.                             tempy = 0
106.                         End If
107.                     Loop
108.  
109.                     tempy = y
110.                     Do Until tempy = _Height - 1
111.                         If TempGrid(x, tempy + 1) = 0 Then
112.                             TempGrid(x, tempy + 1) = pass + 1
113.                             tempy = tempy + 1
114.                             If tempy > finishy Then finishy = tempy
115.                             finished = 0
116.                         Else
117.                             tempy = _Height - 1
118.                         End If
119.                     Loop
120.                 End If
121.         Next y, x
122.     Loop
123.  
124.     o = 0
125.     Do Until o >= m.SIZE
126.         If _MemGet(m, m.OFFSET + o, _Unsigned Long) <> 0 Then _MemPut m1, m1.OFFSET + o, kolor As _UNSIGNED LONG
127.         o = o + 4
128.     Loop
129.     _MemFree m: _MemFree m1
130.     Erase TempGrid
131.     $Checking:On
132.     If B Then _Blend
133. End Sub
134.  
135.  

So - it is ok, or not?

[SMcNeill]

That's the question: Why is the _MEMCOPY speeding it up so much?  It's a completely unnecessary step and is just extra processing being done...  and yet it's sooo much faster than not using it??

How can we do more work and yet end up with faster times?  Much faster times to boot?

Note -- unlike your change below Petr, the original is running that process in both runs:
 
    If METHOD = 0 Then 'this is first run
        Do Until o >= m.SIZE
            If _MemGet(m1, m1.OFFSET + o, _Unsigned Long) = kolor Then
                _MemPut m, m.OFFSET + o, -1 As _UNSIGNED LONG
                'Else
                '_MemPut m, m.OFFSET + o, 0 As LONG
            End If
            o = o + 4
        Loop
    End If


So how is it running it faster with _MEMCOPY in play?

[Cobalt]

something similar to how LINE()-(),,BF is faster than just plain LINE()-(), ?

by the way _SCREENMOVE _MIDDLE  is not working on my machine, unless its supposed to put the window about half off the screen.

[SMcNeill]

something similar to how LINE()-(),,BF is faster than just plain LINE()-(), ?

by the way _SCREENMOVE _MIDDLE  is not working on my machine, unless its supposed to put the window about half off the screen.

Add a huge ass delay in front of it.  0.25 used to work for me, but now I have to pump it up to about 2 seconds before it works right.

Or use this: https://www.qb64.org/forum/index.php?topic=3659.msg130063#msg130063

[Petr]

Probably because MEMCOPY does not compare anything, it just takes a block of memory and copies it elsewhere, while the second method compares all the values with each other, which is unnecessary because the next part of the program selects it anyway. There is no better explanation. Probably too many comparisons and the length of the loop slows it down, in the slower method it is 786,432 comparisons 40 times in a row, so that's 31,457,280 comparisons in 15 seconds, that means 2,097,152 comparisons of values per second, it seems to me really enough.

[Cobalt]

Add a huge ass delay in front of it.  0.25 used to work for me, but now I have to pump it up to about 2 seconds before it works right.

Or use this: https://www.qb64.org/forum/index.php?topic=3659.msg130063#msg130063

oh so _MIDDLE still needs a delay? _SCREENMOVE 5,5 works fine without, so I thought all the _SCREENMOVEs were fixed.

anyway,

Why is the second run always faster than the first? if you rem out the IF THEN so the MEMCOPY always runs the second time is always faster than the first by a fair amount. What would cause that as well?

[SMcNeill]

Why is the second run always faster than the first? if you rem out the IF THEN so the MEMCOPY always runs the second time is always faster than the first by a fair amount. What would cause that as well?

That's the question I've been having, and why I posted this topic.  :P

I'm beginning to think that QB64 may not be reserving memory when we DIM an array, but is instead using memory as we place information into an array.

Try this as an example:

Code: QB64: [Select]

1. Dim a(1000000000) As String * 1
2. Print "1 GB of memory used in main program"
3. Pause
4. foo
5. foo2
6.  
7.  
8. Sub foo
9.     Dim a(1000000000) As String * 1
10.     Print "1 GB of memory used in SUB foo"
11.     Pause
12. End Sub
13.  
14. Sub foo2
15.     Dim a(1000000000) As String * 1
16.     Dim m As _MEM: m = _Mem(a())
17.     _MemFill m, m.OFFSET, m.SIZE, 65 As _UNSIGNED _BYTE
18.     Print a(1000000000)
19.     Print "1 GB of memory used in SUB foo2"
20.     Pause
21. End Sub
22.  
23.  
24.  
25.  
26. Sub Pause
27.     Print "Press <SPACE> to continue.  Check your mem usage in Task Manager as you go."
28.     _KeyClear
29.     Do
30.         _Limit 10
31.     Loop Until _KeyHit = 32
32. End Sub

Now, the above expects your machine to have 2 GB of available ram to run it.  If you don't, or if you're compiling on a 32-bit version of QB64, drop a zero from each of those arrays...

When you first run it, you use 1GB of memory for your program.
Hit space, and the second array inside the SUB *should* use another GB of memory.   **IT DOESN'T.**
Hit space, and the third array inside the last SUB dims the array AND puts something in it...  It uses an extra GB of memory.

Arrays dimmed in our main program seem to reserve memory for their usage.  Arrays dimmed in SUB/FUNCTIONs don't seem to do this -- they allocate memory as the array gets used and filled.

For my program, I think the difference in speed is coming from this allocation of "memory on the fly".  With the _MEMCOPY, we fill the array all at once, without it, the routine is filling the array a single element at a time and is constantly resizing and moving itself in memory as needed...

_MEMCOPY might be an overall unnecessary step, but just the fact that it's allocating the space and holding it in memory all at once seems to be what's making the noticeable difference in speed here.

[SMcNeill]

That's *exactly* what's happening here!

Code: QB64: [Select]

1. Dim a(1000000000) As String * 1
2. Print "1 GB of memory used in main program"
3. Pause
4. foo
5.  
6.  
7. Sub foo
8.     Dim a(1000000000) As String * 1
9.     Dim m As _MEM: m = _Mem(a())
10.     Print "1 GB of memory used in SUB foo"
11.     Pause
12.     For i = 1 To 1000000000 Step 100000000
13.         _MemFill m, m.OFFSET, i, 65 As _UNSIGNED _BYTE
14.         Print "Inside the SUB, with "; i; " in use."
15.         Pause
16.     Next
17. End Sub
18.  
19. Sub Pause
20.     Print "Press <SPACE> to continue.  Check your mem usage in Task Manager as you go."
21.     _KeyClear
22.     Do
23.         _Limit 10
24.     Loop Until _KeyHit = 32
25. End Sub

Somehow, arrays are allocated differently in memory if they're inside a sub or in the main module.  Arrays used in the main module reserve space for themselves in memory as we DIM them, whereas arrays inside a SUB are constantly resizing and growing to fit how much information we've actually put in them. 

The _MEMCOPY in this case is filling the array completely all in one go, while without it, the array is constantly regrowing, resizing, and repositioning itself in memory. 

Who knew?!!

When I need speed from now on, I may need to create a static dummy array for a program and then simply _MEMCOPY it over all at once to fix this type problem inside a SUB/FUNCTION.  :P

[SMcNeill]

Here's another quick test for you guys:

    Dim TempGrid(0 To _Width - 1, 0 To _Height - 1) As Long

Move that DIM statement from the SUB and place it at the top of your code as a DIM SHARED statement, right after the SCREEN statement.  See the difference in the timed results then!

[bplus]

I changed a few things and Method -1 still fast but doesn't look right:

Code: QB64: [Select]

1. Screen _NewImage(1024, 700, 32)
2. _ScreenMove 150, 40
3.  
4. TestLimit = 1
5.  
6. Randomize Timer
7. t# = Timer
8. Cls
9. For i = 1 To TestLimit
10.     For Radius = 340 To 0 Step -1
11.         k& = &HFF000000 + Int(Rnd * &HFFFFFF)
12.         Circle (512, 350), Radius, k&
13.         Fill 512, 350, k&, -1
14.     Next
15. Next
16.  
17. t1# = Timer
18. Cls
19. For i = 1 To TestLimit
20.     For Radius = 340 To 0 Step -1
21.         k& = &HFF000000 + Int(Rnd * &HFFFFFF)
22.         Circle (512, 350), Radius, k&
23.         Fill 512, 350, k&, 0
24.     Next
25. Next
26. t2# = Timer
27. Cls
28. Print Using "###.#### seconds for Fill."; t2# - t1#
29. Print Using "###.#### seconds for Fill Method -1."; t1# - t#
30.  
31.  
32.  
33.  
34.  
35. Sub Fill (Passx, Passy, kolor As Long, METHOD)
36.     $Checking:Off
37.     B = _Blend
38.     _DontBlend
39.  
40.     Dim TempGrid(0 To _Width - 1, 0 To _Height - 1) As Long
41.     Dim As _MEM m, m1: m = _Mem(TempGrid()): m1 = _MemImage(0)
42.     Dim o As _Offset
43.     If METHOD Then
44.         _MemCopy m1, m1.OFFSET, m1.SIZE To m, m.OFFSET
45.     End If
46.     o = 0
47.     Do Until o >= m.SIZE
48.         If _MemGet(m1, m1.OFFSET + o, _Unsigned Long) = kolor Then
49.             _MemPut m, m.OFFSET + o, -1 As LONG
50.             'Else
51.             '_MemPut m, m.OFFSET + o, 0 As LONG
52.         End If
53.         o = o + 4
54.     Loop
55.  
56.     TempGrid(Passx, Passy) = 1
57.     startx = Passx: finishx = Passx
58.     starty = Passy: finishy = Passy
59.  
60.     Do Until finished
61.         pass = pass + 1
62.         finished = -1
63.         For x = startx To finishx
64.             For y = starty To finishy
65.                 'If TempGrid(x, y) <> 0 Then Print x, y, TempGrid(x, y): Sleep
66.  
67.                 If TempGrid(x, y) = pass Then
68.                     tempx = x
69.                     Do Until tempx = 0
70.                         If TempGrid(tempx - 1, y) = 0 Then
71.                             TempGrid(tempx - 1, y) = pass + 1
72.                             tempx = tempx - 1
73.                             If tempx < startx Then startx = tempx
74.                             finished = 0
75.                         Else
76.                             tempx = 0
77.                         End If
78.                     Loop
79.  
80.                     tempx = x
81.                     Do Until tempx = _Width - 1
82.                         If TempGrid(tempx + 1, y) = 0 Then
83.                             TempGrid(tempx + 1, y) = pass + 1
84.                             tempx = tempx + 1
85.                             If tempx > finishx Then finishx = tempx
86.                             finished = 0
87.                         Else
88.                             tempx = _Width - 1
89.                         End If
90.                     Loop
91.  
92.                     tempy = y
93.                     Do Until tempy = 0
94.                         If TempGrid(x, tempy - 1) = 0 Then
95.                             TempGrid(x, tempy - 1) = pass + 1
96.                             tempy = tempy - 1
97.                             If tempy < starty Then startx = tempy
98.                             finished = 0
99.                         Else
100.                             tempy = 0
101.                         End If
102.                     Loop
103.  
104.                     tempy = y
105.                     Do Until tempy = _Height - 1
106.                         If TempGrid(x, tempy + 1) = 0 Then
107.                             TempGrid(x, tempy + 1) = pass + 1
108.                             tempy = tempy + 1
109.                             If tempy > finishy Then finishy = tempy
110.                             finished = 0
111.                         Else
112.                             tempy = _Height - 1
113.                         End If
114.                     Loop
115.                 End If
116.         Next y, x
117.     Loop
118.  
119.     o = 0
120.     Do Until o >= m.SIZE
121.         If _MemGet(m, m.OFFSET + o, _Unsigned Long) <> 0 Then _MemPut m1, m1.OFFSET + o, kolor As _UNSIGNED LONG
122.         o = o + 4
123.     Loop
124.     _MemFree m: _MemFree m1
125.     $Checking:On
126.     If B Then _Blend
127. End Sub
128.  
129.  

[Cobalt]

That's the question I've been having, and why I posted this topic.  :P

I'm beginning to think that QB64 may not be reserving memory when we DIM an array, but is instead using memory as we place information into an array.

no I mean if you make the 2 loops the same (method -1 on both) so they both use the _MEMCOPY, the second timed loop is still faster than the first by .15 to .25 seconds faster.

[Petr]

Here's another quick test for you guys:

    Dim TempGrid(0 To _Width - 1, 0 To _Height - 1) As Long

Move that DIM statement from the SUB and place it at the top of your code as a DIM SHARED statement, right after the SCREEN statement.  See the difference in the timed results then!

@SMcNeill

Hi, here is my results after replacing DIM
0.7 seconds (before 15 seconds)
0.6 seconds (the same as before)

Let me express my deep respect for you, because I would not really look for the problem in this. This is an absolutely crucial finding. I am very glad that you have alerted us to this matter. Great job!