Loop Performance - GameCreators Forum

Author

Message

zoltar

14

Years of Service

User Offline

Joined: 2nd Mar 2011

Location:

Posted: 4th Dec 2013 17:29 Edited at: 6th Dec 2013 14:51

Link

Several moons ago I wrote some types and functions to work with tree structures and noticed a huge lag in performance while testing things in a loop. I was really puzzled when I found that going linearly through all items was faster than compartmentalizing items in hierarchies. At the time I thought it was caused by the way I was creating and handling the tree structure in itself and decided to use the faster approach without further research due to project deadlines.

Today that I had some spare time I decided to review the tree structure approach. The first thing to do was to test the three kinds of loop statements before anything else. What I found is that the WHILE and DO-WHILE loops are ridiculously slower than the FOR loop.

Creating and assigning the index value to 10,000 items in an array takes ~500 ms using a FOR loop while the same task takes ~5000 ms for both the WHILE and DO-WHILE loops.

The disproportionate performance between loop statements is very particular to DarkBASIC. To confirm the theory with real life experience I did the same test in PHP, Delphi, Java, C++ and JavaScript and all loop statements have a very uniform performance. And even more amazing is that it took ~18 ms to process 10,000,000 items in those languages!

I don't know what's the future of DarkBASIC Pro but in my humble opinion this is definitively something to look on very thoroughly for future releases. It'd be very interesting, and I'd really appreciate it, if somebody familiar with the development of DarkBASIC can comment on this subject.

Here's the code that I used for the test if anyone is interested.

+ Code Snippet

#CONSTANT CLoopStart = 1
#CONSTANT CLoopEnd = 10000

GLOBAL DIM G_List() AS INTEGER
GLOBAL G_TimeStart AS INTEGER
GLOBAL G_TimeEnd AS INTEGER

PRINT "Testing performance by creating " + STR$(CLoopEnd) + " items on each loop."
PRINT "Press any key to start test..."
WAIT KEY

EMPTY ARRAY G_List()
G_TimeStart = TIMER()
I = CLoopStart
WHILE I <= CLoopEnd
    AddItem(I)
    INC I
ENDWHILE
G_TimeEnd = TIMER()
PRINT "While loop performance: " + STR$(G_TimeEnd - G_TimeStart) + " ms."

EMPTY ARRAY G_List()
G_TimeStart = TIMER()
FOR I = CLoopStart TO CLoopEnd
    AddItem(I)
NEXT I
G_TimeEnd = TIMER()
PRINT "For loop performance: " + STR$(G_TimeEnd - G_TimeStart) + " ms."

EMPTY ARRAY G_List()
G_TimeStart = TIMER()
I = CLoopStart
REPEAT
    AddItem(I)
    INC I
UNTIL I >= CLoopEnd
G_TimeEnd = TIMER()
PRINT "Repeat loop performance: " + STR$(G_TimeEnd - G_TimeStart) + " ms."

WAIT KEY

END

FUNCTION AddItem(AValue AS INTEGER)
    ARRAY INSERT AT BOTTOM G_List()
    G_List() = I
ENDFUNCTION

Back to top

Profile PM

Sasuke

19

Years of Service

User Offline

Joined: 2nd Dec 2005

Location: Milton Keynes UK

Posted: 4th Dec 2013 18:23 Edited at: 4th Dec 2013 18:40

Link

This is interesting, though you need to include the INC command in your for next loop to make it a fair test. So I had a play myself...

The code:

+ Code Snippet

loopMaxCount = 10000

// while - endwhile
time = timer()
n = 0
while n <= loopMaxCount
    inc n
endwhile
print "While Loop Performance: "+str$(timer()-time) + " .ms"

// for - next
time = timer()
n = 0
for null = 0 to loopMaxCount
    inc n
next
print "For Loop Performance: "+str$(timer()-time) + " .ms"

// repeat - until
time = timer()
n = 0
repeat
    inc n
until n > loopMaxCount
print "Repeat Loop Performance: "+str$(timer()-time) + " .ms"

wait key
end

What is really interesting here is this:

+ Code Snippet

for null = 0 to loopMaxCount
    inc n
next

Is so insanely fast compared to the others I can only think there loop speed is capped for some reason. Seriously, I had to set loopMaxCount to a stupidly high figure and wait for 10 minutes before the first loop had finished and finally got the for - next loop to register 1 ms where others were in the hundred of thousands of ms. Based on the for-next loop results INC must be really fast and have hardly any affect on loop performance so if you can imagine the loops but with nothing inside, while and repeat loops must have a capped speed!

I luckily used for next loops for tree structures so this is good cause I don't have to edit anything

"Get in the Van!" - Van B

Back to top

Profile PM Email

Green Gandalf

VIP Member

20

Years of Service

User Offline

Joined: 3rd Jan 2005

Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.

Posted: 4th Dec 2013 19:33 Edited at: 4th Dec 2013 19:40

Link

I think you need to put sync on at the start to stop the system doing syncs behind the scenes during the loops. Otherwise you might get unfair comparisons.

Edit Minor correction.

You need to enclose each test in a sync on/sync off pair to stop the system syncs interfering. Here's the code I've used:

#CONSTANT CLoopStart = 1
#CONSTANT CLoopEnd = 10000

GLOBAL DIM G_List() AS INTEGER
GLOBAL G_TimeStart AS INTEGER
GLOBAL G_TimeEnd AS INTEGER

PRINT "Testing performance by creating " + STR$(CLoopEnd) + " items on each loop."
PRINT "Press any key to start test..."
WAIT KEY
sync on
EMPTY ARRAY G_List()
G_TimeStart = TIMER()
I = CLoopStart
WHILE I <= CLoopEnd
    AddItem(I)
    INC I
ENDWHILE
G_TimeEnd = TIMER()
sync off
PRINT "While loop performance: " + STR$(G_TimeEnd - G_TimeStart) + " ms."
sync on
EMPTY ARRAY G_List()
G_TimeStart = TIMER()
FOR I = CLoopStart TO CLoopEnd
    AddItem(I)
NEXT I
G_TimeEnd = TIMER()
sync off
PRINT "For loop performance: " + STR$(G_TimeEnd - G_TimeStart) + " ms."
sync on
EMPTY ARRAY G_List()
G_TimeStart = TIMER()
I = CLoopStart
REPEAT
    AddItem(I)
    INC I
UNTIL I >= CLoopEnd
G_TimeEnd = TIMER()

sync off
PRINT "Repeat loop performance: " + STR$(G_TimeEnd - G_TimeStart) + " ms."

WAIT KEY

END

FUNCTION AddItem(AValue AS INTEGER)
    ARRAY INSERT AT BOTTOM G_List()
    G_List() = I
ENDFUNCTION

+ Code Snippet

#CONSTANT CLoopStart = 1
#CONSTANT CLoopEnd = 10000

GLOBAL DIM G_List() AS INTEGER
GLOBAL G_TimeStart AS INTEGER
GLOBAL G_TimeEnd AS INTEGER

PRINT "Testing performance by creating " + STR$(CLoopEnd) + " items on each loop."
PRINT "Press any key to start test..."
WAIT KEY
sync on
EMPTY ARRAY G_List()
G_TimeStart = TIMER()
I = CLoopStart
WHILE I <= CLoopEnd
    AddItem(I)
    INC I
ENDWHILE
G_TimeEnd = TIMER()
sync off
PRINT "While loop performance: " + STR$(G_TimeEnd - G_TimeStart) + " ms."
sync on
EMPTY ARRAY G_List()
G_TimeStart = TIMER()
FOR I = CLoopStart TO CLoopEnd
    AddItem(I)
NEXT I
G_TimeEnd = TIMER()
sync off
PRINT "For loop performance: " + STR$(G_TimeEnd - G_TimeStart) + " ms."
sync on
EMPTY ARRAY G_List()
G_TimeStart = TIMER()
I = CLoopStart
REPEAT
    AddItem(I)
    INC I
UNTIL I >= CLoopEnd
G_TimeEnd = TIMER()

sync off
PRINT "Repeat loop performance: " + STR$(G_TimeEnd - G_TimeStart) + " ms."

WAIT KEY

END

FUNCTION AddItem(AValue AS INTEGER)
    ARRAY INSERT AT BOTTOM G_List()
    G_List() = I
ENDFUNCTION

That gives me 310 ms in each case.

I believe that the for/next loops inhibit the system syncs or something like that.

Powered by Free Banners

Back to top

Profile PM Email

Van B

Moderator

22

Years of Service

User Offline

Joined: 8th Oct 2002

Location: Sunnyvale

Posted: 4th Dec 2013 20:46

Link

I think your right, For..Next loops skip some updates (not sure exactly what). The concern I'd have is that a program might be a lot less stable with a For..Next main loop, maybe makes it tougher for the CPU to clean up memory and handle system processes.

I am the one who knocks...

Back to top

Profile PM Email

Sasuke

19

Years of Service

User Offline

Joined: 2nd Dec 2005

Location: Milton Keynes UK

Posted: 4th Dec 2013 21:08 Edited at: 4th Dec 2013 21:09

Link

But the result seem depended on the type of loop because maths seems to calculate faster in a for next loop:

+ Code Snippet

loopMaxCount = 100000

sync on
// while - endwhile
time = timer()
n = 0
while n <= loopMaxCount
    a# = 2819381.2353 * 123215.222 / 231213.222
    inc n
endwhile
sync off
print "While Loop Performance: "+str$(timer()-time) + " .ms"

sync on
// for - next
time = timer()
n = 0
for n = 0 to loopMaxCount
    a# = 2819381.2353 * 123215.222 / 231213.222
    inc i
next
sync off
print "For Loop Performance: "+str$(timer()-time) + " .ms"

sync on
// repeat - until
time = timer()
n = 0
repeat
    a# = 2819381.2353 * 123215.222 / 231213.222
    inc n
until n > loopMaxCount
sync off
print "Repeat Loop Performance: "+str$(timer()-time) + " .ms"

wait key
end

"Get in the Van!" - Van B

Back to top

Profile PM Email

zoltar

14

Years of Service

User Offline

Joined: 2nd Mar 2011

Location:

Posted: 4th Dec 2013 21:28

Link

@Sasuke:

Yes, the loops are fast. Not insanely fast as in other languages, as I already stated, but fast enough to be given some processing load in order to make them register a time above the 1 millisecond mark.

In my opinion, including an INC command within the FOR loop wouldn't be fair because it has an intrinsic statement that increments the reference variable so it would be an extra processing load for it. However, I think that's the key on why the WHILE and REPEAT loops slow down when the program is not in charge of the syncs as Green Gandalf wisely pointed out.

@Green Gandalf:

Thank you very much for pointing that out. Very spot on. That leveled the performance for the WHILE and REPEAT loops. All loops now take ~500 ms. And that means the performance lag is in how I am handling the tree structure in itself.

The only logic explanation I can infer from this is that the FOR loop isn't affected by the syncs behind the scenes because of its intrinsic incremental (decremental) statement for the reference variable. While the other loops might be giving DBPro the chance to sync as the loop passes over the INC statement needed to control the loop.

n.b. It worked fine for me with the SYNC ON at the very start of the program. No need to enclose each test individually.

In other matters and off topic. Placing the SYNC ON at the start of test brought up an issue I have with the SYNC command. Something I call the SYNC double tap.

If you take the code I posted and place the SYNC ON command at the very top of it and then you place a call to SYNC just before both WAIT KEY commands, you'll perhaps notice that the first two PRINT commands don't output any text to the screen as expected. However, if you put an extra SYNC before the first WAIT KEY then the text shows as expected.

In my case it does that for text and sprites. Sometimes it happens at the middle of the program within a function that gets call at certain point from the main loop. I think is some kind of bug but not sure because I don't really know how the behind the scene syncs are implemented. Do you have any explanation, thought or idea on why this happens? It has puzzled me for a while.

Back to top

Profile PM

zoltar

14

Years of Service

User Offline

Joined: 2nd Mar 2011

Location:

Posted: 4th Dec 2013 21:46

Link

@Sasuke:

Quote: "But the result seem depended on the type of loop because maths seems to calculate faster in a for next loop."

Yep, it seems it does.

Back to top

Profile PM

Green Gandalf

VIP Member

20

Years of Service

User Offline

Joined: 3rd Jan 2005

Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.

Posted: 5th Dec 2013 01:04

Link

Quote: "If you take the code I posted and place the SYNC ON command at the very top of it and then you place a call to SYNC just before both WAIT KEY commands, you'll perhaps notice that the first two PRINT commands don't output any text to the screen as expected. However, if you put an extra SYNC before the first WAIT KEY then the text shows as expected."

I think that's something to do with the double buffering used by DBPro - the first one initialises the buffer or something like that.

Quote: "n.b. It worked fine for me with the SYNC ON at the very start of the program. No need to enclose each test individually."

I'm sure you're right - I was being lazy and couldn't be bothered to find the neatest way of getting the results to show up.

Powered by Free Banners

Back to top

Profile PM Email

Kevin Picone

22

Years of Service

User Offline

Joined: 27th Aug 2002

Location: Australia

Posted: 5th Dec 2013 03:43

Link

While & Repeat loops poll messages where For/Next blocks don't. It's only necessary so the user can 'ESC' or [X] out of a program that's stuck in terminal loop nicely. Otherwise it'd be hang and you'd need Ctrl alt-delete to kill it.

Even with the message checks I doubt it's the loop structures at fault here, it's much more likely to be how the insertion/deletion works upon typed structures, as this has all the hall marks of memory thrashing 101.

What I suspect the insertion & deletion functions are doing is allocating and deleting (rebuilding) the structure perhaps not every time but more frequently than need be. With the array inserts included and sync on they all ran around 950 MS (here) and without the inserts they all flat line at zero milliseconds for the 10,000 iterations.

A potentially better solution in Dbpro is to build the structure in a mem bank, or raw allocated chunk of memory where the library manages where and when (or if ) the structure is expanded or collapsed. So a type of binary heap. If the chunk is fat enough to contain the the data set up front, there's zero allocation overhead beyond that. Which will be much faster.

Convert PlayBASIC To Machine Code

Back to top

Profile PM Website

zoltar

14

Years of Service

User Offline

Joined: 2nd Mar 2011

Location:

Posted: 5th Dec 2013 09:54 Edited at: 5th Dec 2013 09:55

Link

@Green Gandalf:

Thank you for the tip on the buffer initialization by the SYNC command.

@Kevin Picone:

An excellent observation. DBPro must pump messages to monitor the ESC key. However, I made a test and it seems users can simply close the window or escape their way out of FOR loops as well. It seems that in regard to message pumping the three loops are even.

I also made a test with two rounds, one with the escape key enabled and one disabled. There was no performance difference between the rounds.

As for the tree structures. The weird thing was that the performance lag presented while traversing a static tree structure within a loop regardless of it being mapped in an array or dynamically created in memory. It was just like going through a tight sequencial iteration over an array with a few dozens of items was faster than indirectly traversing no more than a dozen items in a tree. Testing the loops came as an idea because besides the difference in structures the only different thing was the loop statements used to traverse the structures.

@All:

When Green Gandalf suggested the use of the SYNC ON command I thought things were settled but the code posted by Sasuke proves that still is something else about the loop statements that hit their performance. This is getting weird.

Thanks to all for your replies so far. Very interesting and insightful. If anyone has any other idea, explanation, thought, secret codex or ancient script on the subject they are welcome to share it on this thread.

Back to top

Profile PM

Kevin Picone

22

Years of Service

User Offline

Joined: 27th Aug 2002

Location: Australia

Posted: 5th Dec 2013 15:00

Link

Quote: "An excellent observation. DBPro must pump messages to monitor the ESC key. However, I made a test and it seems users can simply close the window or escape their way out of FOR loops as well. It seems that in regard to message pumping the three loops are even.
"

It'll happily exit as message polling occurs in a number of places not just loop constructs. It's mostly called in commands like Sync though.

+ Code Snippet

Sync on

// infinite/stuck loop
For lp =1 to 10
 
    lp =5

next lp

The above creates an infinite loop. The ESC key and close gadgets [X] are of no help here.

Quote: "I also made a test with two rounds, one with the escape key enabled and one disabled. There was no performance difference between the rounds."

yep, won't make any difference as the code is generated with the message polls at compile time. It's still calling them even when break key is disabled.

The following would normally be an unbreakable loop, but in Dbpro the user can escape it to fight another day.

+ Code Snippet

Sync on

// infinite/stuck loop.. nope press esc or close gadget
repeat


until lp=45

The code bellow is actually what the compiler produces.

0 PUSH REGISTERS             ; PUSH REGISTERS   
0 MOV MEM4 ESP @$_ESP_       ; STORE STACK IN MEM   
    
   1 LINE : 
    
   2 LINE : 
    
   3 LINE : Sync on
    
3 MOV EBX IMM4 [1
3 CALL EBX                   ; CALL [dbprocore.dll ,?SyncOn@@YAXXZ 
3 MOV MEM IMM4 @$_SLN_, 3
3 MOV EAX MEM4 @$_ERR_
3 CMP EAX4 0
3 JNE $labelend              ; CALL Normal Runtime Error Hook  
    
   4 LINE : 
    
   5 LINE : :`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`
    
   6 LINE : repeat
    
6 MOV EBX IMM4 [2
6 CALL EBX                   ; CALL [dbprocore.dll ,?ProcessMessages@@YAKXZ    <<<<<<< HERE IS THE CALL 
6 CMP EAX4 1                 ; CONDITION COMPARE   
6 JE $labelend               ; JUMP IF EQUAL   
10 MOV EAX IMM4 , 45
10 PUSH EAX 
10 MOV EAX MEM4 @lp
10 MOV EBX EAX4 
10 POP EDX 
10 MOV EAX IMM4 0
10 CMP EDX EBX4 
10 SETE EAX 
10 MOV MEM4 EAX @$L0         ; EQUAL   
10 MOV EAX MEM4 @$L0
10 CMP EAX4 0                ; CONDITION COMPARE   
10 JE $label0[6]             ; JUMP IF EQUAL   
6 MOV MEM IMM4 @$_SLN_, 6
6 MOV EAX MEM4 @$_ERR_
6 CMP EAX4 0
6 JNE $labelend              ; CALL Normal Runtime Error Hook  
    
   7 LINE : 
    
   8 LINE : 
    
   9 LINE : 
    
   10 LINE : until lp=45
    
10 MOV EAX MEM4 @$_REK_
10 CMP EAX4 0
10 JNE LEAP
10 MOV EBX IMM4 [3
10 CALL EBX                  ; CALL [dbprocore.dll ,?Quit@@YAKXZ 
10 MOV ESP MEM4 @$_ESP_      ; RESTORE STACK FROM MEM   
10 POP REGISTERS             ; POP REGISTERS   
    
10 RET                       ; RETURN

+ Code Snippet


0 PUSH REGISTERS             ; PUSH REGISTERS   
0 MOV MEM4 ESP @$_ESP_       ; STORE STACK IN MEM   
    
   1 LINE : 
    
   2 LINE : 
    
   3 LINE : Sync on
    
3 MOV EBX IMM4 [1
3 CALL EBX                   ; CALL [dbprocore.dll ,?SyncOn@@YAXXZ 
3 MOV MEM IMM4 @$_SLN_, 3
3 MOV EAX MEM4 @$_ERR_
3 CMP EAX4 0
3 JNE $labelend              ; CALL Normal Runtime Error Hook  
    
   4 LINE : 
    
   5 LINE : :`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`:`
    
   6 LINE : repeat
    
6 MOV EBX IMM4 [2
6 CALL EBX                   ; CALL [dbprocore.dll ,?ProcessMessages@@YAKXZ    <<<<<<< HERE IS THE CALL 
6 CMP EAX4 1                 ; CONDITION COMPARE   
6 JE $labelend               ; JUMP IF EQUAL   
10 MOV EAX IMM4 , 45
10 PUSH EAX 
10 MOV EAX MEM4 @lp
10 MOV EBX EAX4 
10 POP EDX 
10 MOV EAX IMM4 0
10 CMP EDX EBX4 
10 SETE EAX 
10 MOV MEM4 EAX @$L0         ; EQUAL   
10 MOV EAX MEM4 @$L0
10 CMP EAX4 0                ; CONDITION COMPARE   
10 JE $label0[6]             ; JUMP IF EQUAL   
6 MOV MEM IMM4 @$_SLN_, 6
6 MOV EAX MEM4 @$_ERR_
6 CMP EAX4 0
6 JNE $labelend              ; CALL Normal Runtime Error Hook  
    
   7 LINE : 
    
   8 LINE : 
    
   9 LINE : 
    
   10 LINE : until lp=45
    
10 MOV EAX MEM4 @$_REK_
10 CMP EAX4 0
10 JNE LEAP
10 MOV EBX IMM4 [3
10 CALL EBX                  ; CALL [dbprocore.dll ,?Quit@@YAKXZ 
10 MOV ESP MEM4 @$_ESP_      ; RESTORE STACK FROM MEM   
10 POP REGISTERS             ; POP REGISTERS   
    
10 RET                       ; RETURN

There is a compiler switch to turn safe code generations off somewhere but I don't recall it now.

Convert PlayBASIC To Machine Code

Back to top

Profile PM Website

zoltar

14

Years of Service

User Offline

Joined: 2nd Mar 2011

Location:

Posted: 5th Dec 2013 16:44

Link

@Kevin Picone:

Brilliant post, thank you. So this proves that DBPro only pumps messages looking for the escape key on the WHILE and REPEAT loops but it doesn't actually affects their performance. At least not noticeably.

What about the behind the scenes syncs? Having SYNC ON levels the performance of all loops for some reason. There still is a difference but not as dramatic as having it off. Can you use, whatever it is you are using to get the assembler code, to see if there's a SYNC call within the loops when sync is off? That'd be very interesting.

At the bottom of the .dbpro files is a property called RemoveSafetyCode. Is that the switch you are talking about?

It'd be too much to ask what are you using to get the assembly code?

Back to top

Profile PM

Green Gandalf

VIP Member

20

Years of Service

User Offline

Joined: 3rd Jan 2005

Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.

Posted: 5th Dec 2013 18:30

Link

Quote: "It'd be too much to ask what are you using to get the assembly code? "

Look in your DBPro/Temp folder - it should be in the _Temp.dbm file along with some other stuff.

Powered by Free Banners

Back to top

Profile PM Email

Mobiius

Valued Member

22

Years of Service

User Offline

Joined: 27th Feb 2003

Location: The Cold North

Posted: 5th Dec 2013 18:32

Link

Quote: "RemoveSafetyCode. Is that the switch you are talking about?"

Yes.

Now Visit My Website

Back to top

Profile PM Email Website

zoltar

14

Years of Service

User Offline

Joined: 2nd Mar 2011

Location:

Posted: 6th Dec 2013 14:40

Link

@Green Gandalf:

It took me some time to figure out where the temp folder was but finally I found it. Thank you.

@All:

Thanks again to all for your replies.

Back to top

Profile PM

Sorry your browser is not supported!

DarkBASIC Professional Discussion / Loop Performance