Text Only | Text with Attachments

QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: SMcNeill on November 05, 2021, 09:10:54 am

Title: Somebody explain this one to me...
Post by: SMcNeill on November 05, 2021, 09:10:54 am
Code: QB64: [Select]
  1. Screen _NewImage(1024, 720, 32)
  4.  
  5.  
  6. TestLimit = 100
  7. Radius = 350
  8.  
  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
  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
  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)
  38.     B = _Blend
  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
  127.     If B Then _Blend

  [ This attachment cannot be displayed inline in 'Print Page' view ]  

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.
Title: Re: Somebody explain this one to me...
Post by: Petr on November 05, 2021, 09:48:40 am
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?
Title: Re: Somebody explain this one to me...
Post by: SMcNeill on November 05, 2021, 09:57:33 am
Quote from: Petr on November 05, 2021, 09:48:40 am
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.
Title: Re: Somebody explain this one to me...
Post by: Petr on November 05, 2021, 10:16:38 am
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)
  4.  
  5.  
  6. TestLimit = 100
  7. Radius = 350
  8.  
  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
  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
  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)
  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
  132.     If B Then _Blend
  134.  
  135.  

So - it is ok, or not?
Title: Re: Somebody explain this one to me...
Post by: SMcNeill on November 05, 2021, 10:36:09 am
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?
Title: Re: Somebody explain this one to me...
Post by: Cobalt on November 05, 2021, 10:44:52 am
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.
Title: Re: Somebody explain this one to me...
Post by: SMcNeill on November 05, 2021, 10:57:14 am
Quote from: Cobalt on November 05, 2021, 10:44:52 am
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
Title: Re: Somebody explain this one to me...
Post by: Petr on November 05, 2021, 11:00:03 am
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.
Title: Re: Somebody explain this one to me...
Post by: Cobalt on November 05, 2021, 11:04:44 am
Quote from: SMcNeill on November 05, 2021, 10:57:14 am
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?
Title: Re: Somebody explain this one to me...
Post by: SMcNeill on November 05, 2021, 11:33:12 am
Quote from: Cobalt on November 05, 2021, 11:04:44 am
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
  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
  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

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.
Title: Re: Somebody explain this one to me...
Post by: SMcNeill on November 05, 2021, 11:54:15 am
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
  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

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
Title: Re: Somebody explain this one to me...
Post by: SMcNeill on November 05, 2021, 12:34:41 pm
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!

Title: Re: Somebody explain this one to me...
Post by: bplus on November 05, 2021, 01:08:24 pm
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.  
  7. t# = Timer
  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
  16.  
  17. t1# = Timer
  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
  26. t2# = Timer
  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)
  37.     B = _Blend
  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
  126.     If B Then _Blend
  128.  
  129.  
Title: Re: Somebody explain this one to me...
Post by: Cobalt on November 05, 2021, 01:44:12 pm
Quote from: SMcNeill on November 05, 2021, 11:33:12 am
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.
Title: Re: Somebody explain this one to me...
Post by: Petr on November 06, 2021, 04:41:54 am
Quote
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!
Title: Re: Somebody explain this one to me...
Post by: SMcNeill on November 06, 2021, 03:18:09 pm
Quote from: Petr on November 06, 2021, 04:41:54 am
@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!

The code as written is kind of buggy (it only works with a clear background), but it does a good job illustrating how arrays work in subs/functions.  In the main part of the program, they reserve memory when we DIM them.  In SUB/FUNCTION they don't -- the memory is allocated dynamically as needed.  This difference can produce quite a speed/performance difference, so there may be times when it's better to DIM SHARED an array and let it stay in memory than it is to DIM it and free it repeatedly in a SUB.

It's a shame that STATIC won't work with an array in a sub.  At least, I can't get it to work.  When I try I just get a crash to desktop. 

Just something to keep in the back of the mind from now on for speed optimizations.
Title: Re: Somebody explain this one to me...
Post by: Richard on December 05, 2021, 01:20:09 am
@SMcNeill





I offer the following explanation as to how it is possible that by addition of one extra line of code, significant reduction in timing results rather than expected an increase.


This reply assumes you understand the background information as per the link below



https://www.qb64.org/forum/index.php?topic=2276.msg138538#msg138538 (https://www.qb64.org/forum/index.php?topic=2276.msg138538#msg138538)
Reply 184



Firstly, very roughly when determining the size of your code (i.e. a program containing no code (untitled.exe) subtracted from your program.exe) - your actual running code (.exe) is about 10.2 Kbytes (I get 2094080 -2083840 =~10.2 Kbytes) . If your computer (which runs almost exactly 2x faster than mine) is of similar/related architecture (eg INTEL >= i7) - then the 10K of .exe code is a candidate for L1.

On my laptop, L1 is 32K - but from my observations Windows background processes are using all processors (4 physical, 8 logical) even when CPU useage (Task Manager) is only say 30%. So at any time, a fairly large percentage of L1 is being "hogged" by Windows and you would be lucky to have any where near 10 Kbytes of "your" code in L1 (similar considerations for L2 and L3).


When, for a clearer understanding, I reduce your program (supplied below) to minimal requirements, the active code (.exe) is (2092032 - 2083840) =~ 8.2 Kbytes. To me, although the difference (10.2 - 8.2 Kb) may not seem much, in relative terms for L1 location (which is being "butchered" in useage by Windows background processes) - it is apparent that even a relatively slight change in .exe code can yield wildly differing timing results (because of Windows).


So your.exe (heavily referred part = 10.2 Kbytes) is only partly residing in L1 (similarly for L2 and L3) at any instance of time. When the _MemCopy code is acted on - some (_WIDTH * _HEIGHT  =~ 730,000) memory accesses are efficiently at machine level being processed, which is a very large number, which means L1 (after a setup time) is preloaded with the relevant _MemCopy machine Code. Also probably the _MemCopy is relatively small (say << 1K bytes) and has a high chance of 'displacing' not-so-much utilized Windows background processes that are "lying around still in L1". By virtue of the fact that _MemCopy machine code is "resident" in L1, any future references to m and m1 _MEM BLOCKS  (i.e. the rest of your program) would benefit from MEM code being in L1. In fact, with your test limit value of 100, some 73 million MEM operations (over about 10 seconds) would have speed improvement simply because the fact that _MEMCOPY was utilized once. HAD all of your 10.2 Kbyte of code been resident in L1 then POSSIBLY there may not be any significant between (with _MEMCOPY) versus (without _MEMCOPY). I do not know how to measure what is L1, L2, L3 at any time but as far as L1 goes it seems very apparent that windows is very aggressive in "hogging" L1, leaving much less than 10K bytes for anything else, and ONLY when a highly repetitive "small" amount of code (_MemCopy), in this case >730,000 iterations, is when some of L1 being "hogged" by windows is released for other applications (your program). In the first running part of your program (before _MemCopy), it is apparent that the relevant code is "too large" for what is immediately free in L1 and even a billion iterations of that code set may not "displace Windows background processes". In conclusion, _MEMCOPY (machine code small) performing 730000 iterations of memory referencing, is the winner.


Now it is interesting when running the code below, which is a drastically reduced version of your program (and there is NOTHING ACTUALLY TO SEE WHEN RUNNING), that the timing differences (with _MEMCOPY) versus (without _MEMCOPY) are relatively minor and may not even warrant discussion. But now we are taking about a smaller program (8.2 Kbyte) which has a much higher chance of being "resident" in L1 than the 10.2 Kbyte (your program). Now if you ran this shortened program many times, AND also with varying applications installed/removed (eg other instances of QB64, EDGE, etc) - then you will get "widely varied results" including sometimes (with _MEMCOPY) taking LONGER than (without _MEMCOPY) and relative timing ratios approaching 3:1. It appears that the "erratic behaviour" (i.e. non-consistent) of Windows background processes is the reasoning of this.


As a side note, referring to the reply #184 mentioned above, it would appear (without proper study/analysis) that anything running in L1 is approaching being 10x faster than the first time code is being performed. One has to wait for the setup times for preloading L1 before taking advantage of this.



Code: QB64: [Select]
  2. TestLimit = 100
  3. Dim TempGrid(0 To _Width - 1, 0 To _Height - 1) As Long
  4. dim TempGridn(0 To _Width - 1, 0 To _Height - 1) As Long
  5. Dim As _MEM m, m1: m = _Mem(TempGrid()): m1 = _MemImage(0)
  6. Dim As _MEM n, n1: n = _Mem(TempGridn()): n1 = _MemImage(0)
  7. Dim o As _Offset:o = 0
  8.  
  9. tb#=timer
  10.  
  11. for trials%=1 to TestLimit
  12.     o = 0
  13.     Do Until o >= m.SIZE
  14.         If _MemGet(m, m.OFFSET + o, _Unsigned Long) <> 0 Then _MemPut m1, m1.OFFSET + o, kolor As _UNSIGNED LONG
  15.         o = o + 4
  16.     Loop
  18.  
  19. t0#=timer:
  20.  
  21. _MemCopy n1, n1.OFFSET, n1.SIZE To n, n.OFFSET '*** this _MemCopy line added
  22. for trials%=1 to TestLimit
  23.     o = 0
  24.     Do Until o >= n.SIZE
  25.         If _MemGet(n, n.OFFSET + o, _Unsigned Long) <> 0 Then _MemPut n1, n1.OFFSET + o, kolor As _UNSIGNED LONG
  26.         o = o + 4
  27.     Loop
  29.  
  30. t2#=timer
  31.  
  33. Print  "(without   _MemCopy)"; t0# - tb#
  34. Print  "(including _MemCopy)"; t2# - t0#:print
  35. print "# of MEM references GRAND TOTAL =";
  36. print using "###,###,###";_WIDTH*_HEIGHT*Testlimit;
  37.  
  38.  
  39.  
  40.  
Title: Re: Somebody explain this one to me...
Post by: TempodiBasic on December 05, 2021, 12:16:41 pm
Wow you're following the path of crucial difference in results of translator into C++.
No  bad BASIC code but bad final  C++ code.
The issue moves from coder's ability  to ability of translator into C++.
Title: Re: Somebody explain this one to me...
Post by: SMcNeill on December 05, 2021, 03:08:17 pm
The issue for us isn't one to do with L1 or L2 memory.  It has to do with how QB64 allocates memory

DIM foo(1000), if used in the main module, creates and reserves space in memory foryour 1001 elements from the moment you DIM it.

DIM foo(1000), if used in a SUB or FUNCTION, doesn't create or reserve any space, until you put values into each element.

And the difference in these two behaviors is one which affects performance quite a bit, if called repeatedly.  It's this difference that creates our difference in speed and performance. 

And, I suppose it makes sense.  DIM, in the main module, creates a permanent array.  We never free it, unless we do so manually with ERASE or CLEAR, or whatnot.  All variables and such, however, end up being temporary when created for a SUB/FUNCTION, unless we specifically declare it as STATIC.

It's the STATIC vs DYNAMIC creation of memory which is the difference in speed in the xamples here..
Title: Re: Somebody explain this one to me...
Post by: Richard on January 04, 2022, 08:00:45 am
@SMcNeill


I understand your reply regarding differences in memory allocation for arrays (Main_Program)  versus  (SUBS) and how this affects timings in using these techniques for array work.


I attempted to time the big DIM array


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


for the two "passes"  of your circle program and did not see any significant changes (minor ones exist) between your two methods as far as DIM being setup.

I attempted to slightly modify your program (my alterations shown with "*** at the end of each relevant line) and is supplied below.

Perhaps you are correct - in which case there is a a coding problem in my alterations to your program.
Would you be kind enough to point out any coding problems in my alterations to establish correct timing results to support your last reply?



Code: QB64: [Select]
  1.  
  2. DECLARE DYNAMIC LIBRARY "kernel32"                                             '***
  3.     SUB QueryPerformanceCounter (BYVAL lpPerformanceCount AS _UNSIGNED _OFFSET)'***
  4.     SUB QueryPerformanceFrequency (BYVAL lpFrequency AS _UNSIGNED _OFFSET)     '***
  5. END DECLARE                                                                    '***
  6. DIM SHARED PerformanceCount AS _INTEGER64                                      '***
  7. DIM SHARED Frequency AS _INTEGER64                                             '***
  8. DIM SHARED StartingCount AS _INTEGER64                                         '***
  9. DIM SHARED dElapsedTime AS DOUBLE                                              '***
  10. DIM SHARED dElapsedTimeOLD AS DOUBLE                                           '***
  11. DIM SHARED CumulativeTime AS DOUBLE                                            '***
  12. QueryPerformanceFrequency (_OFFSET(Frequency))                                 '***
  13. QueryPerformanceCounter (_OFFSET(StartingCount))                               '***
  14. CumulativeTime#=0                                                              '***
  15.  
  16.  
  17. Screen _NewImage(1024, 720, 32)
  20.  
  21.  
  22. TestLimit = 100
  23. Radius = 350
  24.  
  26. t# = Timer
  27. For i = 1 To TestLimit
  28.     'Cls , &HFF000000 + Int(Rnd * &HFFFFFF)
  29.     k& = &HFF000000 + Int(Rnd * &HFFFFFF)
  30.  
  31.     Circle (512, 360), Radius, k&
  32.     Fill 512, 360, k&, 0
  34.  
  35. t1# = Timer
  36. CumulativeTime_T1_T#=CumulativeTime#                                           '***
  37. CumulativeTime#=0                                                              '***
  38.  
  39. For i = 1 To TestLimit
  40.     'Cls , &HFF000000 + Int(Rnd * &HFFFFFF)
  41.     k& = &HFF000000 + Int(Rnd * &HFFFFFF)
  42.  
  43.     Circle (512, 360), Radius, k&
  44.     Fill 512, 360, k&, -1
  46. t2# = Timer
  47. CumulativeTime_T2_T1#=CumulativeTime#                                          '***
  48.  
  49. Print Using "###.#### seconds for Fill."; t1# - t#;
  50. COLOR &HFF00FF00~&                                                             '***
  51. print "             ";                                                        '***
  52. print using "#,###";CumulativeTime_T1_T#;                                      '***
  53. print " microseconds to DIM array"                                            '***
  54. COLOR &HFFFFFFFF~&
  55.  
  56.  
  57. Print Using "###.#### seconds for Fill Method -1."; t2# - t1#;
  58. COLOR &HFF00FF00~&                                                             '***
  59. print "   ";                                                                  '***
  60. print using "#,###";CumulativeTime_T2_T1#;                                     '***
  61. print " microseconds to DIM array"                                            '***
  62. COLOR &HFFFFFFFF~&                                                             '***
  63.  
  64.  
  65.  
  66.  
  67. Sub Fill (Passx, Passy, kolor As Long, METHOD)
  69. B = _Blend
  71.  
  72.  
  73. TIMERe:dElapsedTimeOLD = dElapsedTime                                          '***
  74. Dim TempGrid(0 To _Width - 1, 0 To _Height - 1) As Long
  75. TIMERe                                                                         '***
  76. CumulativeTime#=CumulativeTime#+(dElapsedTime - dElapsedTimeOLD)*1000000       '***
  77.  
  78.  
  79. Dim As _MEM m, m1: m = _Mem(TempGrid()): m1 = _MemImage(0)
  81. If METHOD Then
  82.     _MemCopy m1, m1.OFFSET, m1.SIZE To m, m.OFFSET
  84. o = 0
  85. Do Until o >= m.SIZE
  86.     If _MemGet(m1, m1.OFFSET + o, _Unsigned Long) = kolor Then
  87.         _MemPut m, m.OFFSET + o, -1 As LONG
  88.         'Else
  89.         '_MemPut m, m.OFFSET + o, 0 As LONG
  90.     End If
  91.     o = o + 4
  93.  
  94. TempGrid(Passx, Passy) = 1
  95. startx = Passx: finishx = Passx
  96. starty = Passy: finishy = Passy
  97.  
  98. Do Until finished
  99.     pass = pass + 1
  100.     finished = -1
  101.     For x = startx To finishx
  102.         For y = starty To finishy
  103.             'If TempGrid(x, y) <> 0 Then Print x, y, TempGrid(x, y): Sleep
  104.  
  105.             If TempGrid(x, y) = pass Then
  106.                 tempx = x
  107.                 Do Until tempx = 0
  108.                     If TempGrid(tempx - 1, y) = 0 Then
  109.                         TempGrid(tempx - 1, y) = pass + 1
  110.                         tempx = tempx - 1
  111.                         If tempx < startx Then startx = tempx
  112.                         finished = 0
  113.                     Else
  114.                         tempx = 0
  115.                     End If
  116.                 Loop
  117.  
  118.                 tempx = x
  119.                 Do Until tempx = _Width - 1
  120.                     If TempGrid(tempx + 1, y) = 0 Then
  121.                         TempGrid(tempx + 1, y) = pass + 1
  122.                         tempx = tempx + 1
  123.                         If tempx > finishx Then finishx = tempx
  124.                         finished = 0
  125.                     Else
  126.                         tempx = _Width - 1
  127.                     End If
  128.                 Loop
  129.  
  130.                 tempy = y
  131.                 Do Until tempy = 0
  132.                     If TempGrid(x, tempy - 1) = 0 Then
  133.                         TempGrid(x, tempy - 1) = pass + 1
  134.                         tempy = tempy - 1
  135.                         If tempy < starty Then startx = tempy
  136.                         finished = 0
  137.                     Else
  138.                         tempy = 0
  139.                     End If
  140.                 Loop
  141.  
  142.                 tempy = y
  143.                 Do Until tempy = _Height - 1
  144.                     If TempGrid(x, tempy + 1) = 0 Then
  145.                         TempGrid(x, tempy + 1) = pass + 1
  146.                         tempy = tempy + 1
  147.                         If tempy > finishy Then finishy = tempy
  148.                         finished = 0
  149.                     Else
  150.                         tempy = _Height - 1
  151.                     End If
  152.                 Loop
  153.             End If
  154.     Next y, x
  156.  
  157. o = 0
  158. Do Until o >= m.SIZE
  159.     If _MemGet(m, m.OFFSET + o, _Unsigned Long) <> 0 Then _MemPut m1, m1.OFFSET + o, kolor As _UNSIGNED LONG
  160.     o = o + 4
  166.  
  167. '***
  168. SUB TIMERe                                                                     '***
  169. QueryPerformanceCounter (_OFFSET(PerformanceCount))                            '***
  170. dElapsedTime = (CDBL(PerformanceCount - StartingCount)) / Frequency            '***
  171. END SUB                                                                        '***
  172.  
  173.  





Text Only | Text with Attachments