* * *

Author Topic: Lazarus / delphi loop efficiency: continue or begin..end?  (Read 4358 times)

JernejL

  • New member
  • *
  • Posts: 13
Lazarus / delphi loop efficiency: continue or begin..end?
« on: March 12, 2018, 05:37:23 pm »
I believe i read somewhere that the 2nd variant (early continue instead of begin..end ) is not supported for optimization in lazarus / freepascal.
 
If possible.. can someone explain what is better from compiler optimization perspective? the 2nd option is surely more readable, but i'm more interested in raw performance - what will perform better, what will optimize better in compiler - and if there's difference between lazarus and delphi regarding how this works.

Code: Pascal  [Select]
  1. for i := 0 to Actors.MaxObject-1 do begin
  2.  
  3.         if Actors.State[i] = stat_used then
  4.         with Tactor(Actors.Data[i]) do
  5.         begin
  6.  
  7.                 if (AIclass = AI_NOBRAIN) then begin // near players only.
  8.  
  9.                 end;
  10.         end;
  11. end;
  12.  

or..

Code: Pascal  [Select]
  1. for i := 0 to Actors.MaxObject-1 do begin
  2.  
  3.         if Actors.State[i] <> stat_used then continue;
  4.  
  5.         with Tactor(Actors.Data[i]) do
  6.         begin
  7.  
  8.                 if (AIclass <> AI_NOBRAIN) then continue;
  9.  
  10.         end;
  11.        
  12. end;

Thaddy

  • Hero Member
  • *****
  • Posts: 6130
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #1 on: March 12, 2018, 06:50:22 pm »
It is supported but why do you do not write else instead of continue in the first continue statement: that is a single instruction on most CPU's? It is simply silly code.
I might not give the answer that you want me to.. Peter Green 1969

JernejL

  • New member
  • *
  • Posts: 13
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #2 on: March 12, 2018, 07:52:07 pm »
It is supported but why do you do not write else instead of continue in the first continue statement: that is a single instruction on most CPU's? It is simply silly code.

 
I'm genuinely confused on where would i use else instead of continue.. that makes no sense, can you write this on my example?
 

RAW

  • Hero Member
  • *****
  • Posts: 664
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #3 on: March 12, 2018, 09:27:56 pm »
I would definitely prefer the first version...much more common...
ELSE ? I don't see why there must be an ELSE...  :)
Windows 7 Pro (x64 Sp1) And Windows XP Pro (x86 Sp3) - LAZARUS 1.8.2 FPC 3.0.4 // 1.7 FPC 3.1.1

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 4596
    • wiki
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #4 on: March 12, 2018, 09:33:11 pm »
This kind of optimization questions do not usually have a general answer.

The issue with question like "which code is better optimized by fpc?" is that "fpc" is an exact specification.

It may be that fpc 2.x does better optimization on one code, but fpc 3.0.x on the other, and no one knows what fpc 3.2 will do.

It may also be that one code performs better on intel, and the other on arm... Or 64 vs 32 bit ...

So all you can do is answer the question for one specific version of fpc, at one platform, for a given set of compiler settings.

If you want to know which version works better on your PC, just compile it, and compare.
If you know how your processor handles asm (including prediction and what not), then compile with -al, and compare the result.

------------------------------
About your problem:

If you have speed problems in a loop like yours, your problem is not to make the loop a few ticks faster.

You need a different approach.

I assume the list is potentially large, and many entries are NOT of state "stat_used"? Because if there are only a few actors, or if 99% of them are stat_used, then there is not much to gain.

You could maintain a 2nd list, with only actors of state "stat_used". Every time the state of an actor changes, it adds or removes itself.
Of course a normal list is not suited. Adding may be fast, but removal requires a search and be slow...
Use a double linked list, insertion, removal and iteration are fast.


Iteration may even be faster, than your for loop. Following a linked list, means just to read one pointer (and a check if it is nil, to end the loop)

Looping over a classic list, requires an index variable, increasing it, depending on optimization multiply it with the pointer size (that is part of one asm instruction to read the pointer), and reading the pointer.


Mr.Madguy

  • Sr. Member
  • ****
  • Posts: 294
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #5 on: March 13, 2018, 08:22:32 am »
Answer is simple: View->Debug windows->Assembler
DynamicData 2.0 Released! Many optimizations: 15% smaller sources, 10% smaller code! Improved scalability!
Developing version 2.1.
Crazy unit testing

User137

  • Hero Member
  • *****
  • Posts: 1746
    • Nxpascal home
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #6 on: March 13, 2018, 12:47:03 pm »
Is this optimal if assuming the data is referred to in multiple occasions in code?
Code: Pascal  [Select]
  1. with TActor(Actors.Data[i]) do

Or was pointer reference faster?
Code: Pascal  [Select]
  1. pActor:=PActor(@Actors.Data[i]);

RayoGlauco

  • Jr. Member
  • **
  • Posts: 62
  • Beers: 1567
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #7 on: March 13, 2018, 02:15:52 pm »
I suggest implementing, executing and timing every possible option.

Code: Pascal  [Select]
  1. starttick := GetTickCount;
  2. { ... loop ... }
  3. endtick := GetTickCount:
  4. elapsed := endtick - starttick;
To err is human, but to really mess things up, you need a computer.

Nitorami

  • Sr. Member
  • ****
  • Posts: 308
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #8 on: March 13, 2018, 02:56:48 pm »
My personal opinion - stop wasting effort on such considerations. As Martin_fr said, first try to reduce the frequency of calls by an intelligent lookup algorithm, rather by saving one or two CPU instructions in a loop that is called 100 million times per second.
As to the code, I personally have never used a continue statement, and don't think it will ever be required, it is mostly a patch to get yourself out of poorly constructed loops. Use the language as it is meant to be, i.e. begin - end - else, and in general this will also give you the best performance. The same is true for array indexing, there is absolutely no need to confuse yourself by recurring to C style pointer arithmetics, with the only execption of multi dimensional arrays where the compiler is not (yet) smart enough to calculate addresses only once.
And don't do premature timing tests. Simplistic micro-loop benchmarks will not at all deliver results representative for the application, modern processors just don't work this linear way.

JernejL

  • New member
  • *
  • Posts: 13
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #9 on: March 13, 2018, 03:58:44 pm »
Is this optimal if assuming the data is referred to in multiple occasions in code?
Code: Pascal  [Select]
  1. with TActor(Actors.Data[i]) do

Or was pointer reference faster?
Code: Pascal  [Select]
  1. pActor:=PActor(@Actors.Data[i]);

 
This is a good question, i wonder too which approach is better.
 
The reason i have to use continue statements is, to provide readability of code, some of conditions get a lot of depth and that after a while makes it hard to follow / maintain, it's a huge fsm machine with a lot of conditions, some of it is impractical to refactor.
 

Nitorami

  • Sr. Member
  • ****
  • Posts: 308
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #10 on: March 13, 2018, 06:09:49 pm »
I suggest to use the simple "with" solution, it is easier to read and is native pascal style. Why would the developers be so stupid as to make native array indexing slower than a protracted pointer construction ? It is an old claim that pointer indexing is faster, and this may have been true long ago, but in my own benchmarks I always found the native approach a bit faster... but we are talking almost unmeasurable quantitities, +/-5% maybe. As said above, with the only exception of multidimensional arrays.
A to the "continue"... I have a certain understanding why ony would use a "break" command to quit a loop, but I am not convinced why anybody would need "continue". I don't find the complexity argument convincing, but it's your choice after all.

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 4596
    • wiki
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #11 on: March 13, 2018, 06:56:28 pm »
Why would the developers be so stupid as to make native array indexing slower than a protracted pointer construction ? It is an old claim that pointer indexing is faster, and this may have been true long ago, but in my own benchmarks I always found the native approach a bit faster... but we are talking almost unmeasurable quantitities, +/-5% maybe. As said above, with the only exception of multidimensional arrays.

First of all "using pointer" can refer to many different things. In my previous post, I referred to a pointer in a linked list. That is different from replacing the loop index by a pointer.

Replacing the loop index by a pointer (to the list) may or may not gain speed, and if it does it may gain just very little, and it may in future fpc versions even loose speed.
But speed differences between list-index and list-pointer have nothing to do with "the developers making it so" or "being stupid". It would simple mean that they hadn't have time to implement certain optimizations.

Unoptimized access to the loop looks approx like this:
// i starts at 0
- i := i +1
- element from loop := memory at "list_start_address + sizeof(element) * i"
  // Note that some cpu may optimize this multiplication, and it may not cost (measurable) time at all

Optimized access may look like this (depends on the cpu):
// p start at list_start_address
- p := p + sizeof(element)
- element from loop := memory at "p"

You can see the optimize version has less math to do in the loop.

I do not know how far fpc currently takes that optimization.
I also do not know how well modern CPU (with prediction, and all their tricks) compensate for the math.

--------------------------------------------------------------
A completely different approach is a linked list.

A linked list can be maintained that already is filtered. This saves time of filtering.

The code
Code: Pascal  [Select]
  1. if Actors.State[i] = stat_used then
Means that each object in the list (since the class data is not stored in the list own memory, but accessed by pointer) needs to be fetched from memory.
If there are many objects, they are likely not in the CPU cache. And fetching them becomes an expensive operation.

As I said: the link list is already filtered. No need to fetch any objects, just to find out that they can be skipped. If the percentage of stat_used objects is small, then this saves a lot of time.

And as a side effect, the linked list pointer is part of the object. So there is no separate memory for a list that needs to be in the CPU cache.
In fact, if the object itself is cleverly designed, each cache line read burst of the cpu can fetch more of the data that the loop needs, and you gain speed here too.

And one more, using a linked list, there is on index (nor a pointer to the list). Only the current object.
This saves one variable. Therefore it saves one cpu register, that can be used for something else.



« Last Edit: March 13, 2018, 06:59:56 pm by Martin_fr »

Nitorami

  • Sr. Member
  • ****
  • Posts: 308
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #12 on: March 13, 2018, 07:27:52 pm »
Quote
First of all "using pointer" can refer to many different things.

Agreed, but I did not refer to your linked list example which is an entirely different issue and meant to reduce the number of accesses in the first place. You already explained that but the OP did not pick it up.

And I insist I would find pascal rather stupid if it forced me to use extra pointers instead of indexed access for best performance. Luckily, this is not the case for onedimensional loops.

RAW

  • Hero Member
  • *****
  • Posts: 664
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #13 on: March 13, 2018, 07:54:18 pm »
What about "Binary Trees", "HashTables" or "Linked List of Dynamic Arrays" or "Databases"... I guess I read this on stackoverflow or somewhere else...
Or some ready to use FreePascal Lists: TFPList or TFPHashList ...
Windows 7 Pro (x64 Sp1) And Windows XP Pro (x86 Sp3) - LAZARUS 1.8.2 FPC 3.0.4 // 1.7 FPC 3.1.1

Paul_

  • Full Member
  • ***
  • Posts: 101
Re: Lazarus / delphi loop efficiency: continue or begin..end?
« Reply #14 on: March 13, 2018, 08:33:05 pm »
What about "Binary Trees", "HashTables" or "Linked List of Dynamic Arrays" or "Databases"... I guess I read this on stackoverflow or somewhere else...
Or some ready to use FreePascal Lists: TFPList or TFPHashList ...

Good point, it's not only about loop/iteration over the list but also about data structure, what is TActor and what is the list Actors.Data ? How big is their memory footprint? Are you adding and removing list content often?

I had similar questions here: https://forum.lazarus.freepascal.org/index.php/topic,39495.90.html


« Last Edit: March 13, 2018, 08:40:37 pm by Paul_ »

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus