Where is the best place to declare an array?

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Where is the best place to declare an array?

Bihar Anwar
If I remember this correctly, I've formerly ever read somewhere (in my Delphi days) that array should be declared globally (not inside a function or procedure) so that access to the array will be faster. Is this correct? If yes, does this also true in FPC?

Thanks in advance.



     
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Where is the best place to declare an array?

Jonas Maebe-2

On 06 May 2010, at 16:43, Bihar Anwar wrote:

> If I remember this correctly, I've formerly ever read somewhere (in  
> my Delphi days) that array should be declared globally (not inside a  
> function or procedure) so that access to the array will be faster.  
> Is this correct?

No.


Jonas
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Where is the best place to declare an array?

Werner Van Belle
Jonas Maebe wrote:
>
> On 06 May 2010, at 16:43, Bihar Anwar wrote:
>
>> If I remember this correctly, I've formerly ever read somewhere (in
>> my Delphi days) that array should be declared globally (not inside a
>> function or procedure) so that access to the array will be faster. Is
>> this correct?
> No.
That's a brief answer. How is what he is saying not true ?

A global variable can be allocated in the datasegment, meaning that the
compiler knows at comiletime what address to look for. If you allocate
things dynamically then you need to follow an extra pointer, so placing
an array in the datasegment would indeed speed up things afaik ? If not,
more than a blunt 'no' would be appreciated,

With kind regards,

--
http://werner.yellowcouch.org/



_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal

signature.asc (268 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Where is the best place to declare an array?

Jonas Maebe-2

On 06 May 2010, at 18:12, Werner Van Belle wrote:

> Jonas Maebe wrote:
>>
>> On 06 May 2010, at 16:43, Bihar Anwar wrote:
>>
>>> If I remember this correctly, I've formerly ever read somewhere (in
>>> my Delphi days) that array should be declared globally (not inside a
>>> function or procedure) so that access to the array will be faster. Is
>>> this correct?
>> No.
> That's a brief answer. How is what he is saying not true ?

I don't have the faintest idea why it would be true. This is a bit like asking someone to explain "how is the statement that bytes are faster than chars not true?"

> A global variable can be allocated in the datasegment, meaning that the
> compiler knows at comiletime what address to look for. If you allocate
> things dynamically then you need to follow an extra pointer,

Local variables (including arrays) are allocated on the stack and are accessed without any kind of indirection (except for dynamic arrays, but the same goes for globally defined dynamic arrays). In fact, it's accesses to global variables that may incur an extra indirection (in case position-independent code is used).

> so placing
> an array in the datasegment would indeed speed up things afaik ? If not,
> more than a blunt 'no' would be appreciated,

I don't know how to explain this briefly. I suggest you to simply try it out by compiling with -al, then you can see what kind of code the compiler generates for the different kind of variables.


Jonas_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re[2]: Where is the best place to declare an array?

José Mejuto
In reply to this post by Werner Van Belle
Hello FPC-Pascal,

Thursday, May 6, 2010, 7:12:46 PM, you wrote:

>>> If I remember this correctly, I've formerly ever read somewhere (in
>>> my Delphi days) that array should be declared globally (not inside a
>>> function or procedure) so that access to the array will be faster. Is
>>> this correct?
>> No.
WVB> That's a brief answer. How is what he is saying not true ?
WVB> A global variable can be allocated in the datasegment, meaning that the
WVB> compiler knows at comiletime what address to look for. If you allocate
WVB> things dynamically then you need to follow an extra pointer, so placing
WVB> an array in the datasegment would indeed speed up things afaik ? If not,
WVB> more than a blunt 'no' would be appreciated,

Static arrays.

Main difference is the scope. If you declare it in the function, the
array is not accesible outside while the global one is errrr... global
:) Both have not allocation time, the global is allocated at compile
time and the local one is allocated when calling the function
increasing the stack pointer, but as the stack pointer must be
increased also to perform the call, there is no penalty. Dynamic
arrays are different or arrays that needs an initialization, but
anyway using global ones you must initialize them to be reused.

--
Best regards,
 José

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Where is the best place to declare an array?

Werner Van Belle
In reply to this post by Jonas Maebe-2
Jonas Maebe wrote:
> I don't have the faintest idea why it would be true.
I'll explain below
> Local variables (including arrays) are allocated on the stack and are accessed without any kind of indirection (except for dynamic arrays, but the same goes for globally defined dynamic arrays).
This is not true. You must take your current stackframe into account,
which adds an indirection.

> I don't know how to explain this briefly. I suggest you to simply try it out by compiling with -al, then you can see what kind of code the compiler generates for the different kind of variables.
>  
Good I did so, thanks for the tip. Below you will see why I believe one
is faster than the other.

# Var local located at ebp-20
# local[2]:=2;
        movw    $2,-18(%ebp)
# global[2]:=2;
        movw    $2,U_P$PROGRAM_GLOBAL+2

In this case the global accessors address U_P$PROGRAM_GLOBAL+2 (which is
a constant for the assembler), while the local variable must work in a
register indirect fashion (ebp-20). This is why I believe one would
indeed be faster than the other. In 'human' (haha) terms:

- global variable access: write data into 'ds+constant'
- local variables: write data into 'ss+bp+constant'.

Since the latter involves a term more I assume it is bound to take more
time. Sadly enough I could not verify this and finding clockccounts on
this type of instructions is far from simple.

Of course, this indirection matters little since the biggest bottleneck
has always been the memory access itself.

Wkr,

--
http://werner.yellowcouch.org/



_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal

signature.asc (268 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Where is the best place to declare an array?

Jonas Maebe-2

On 06 May 2010, at 23:28, Werner Van Belle wrote:

> In 'human' (haha) terms:
>
> - global variable access: write data into 'ds+constant'
> - local variables: write data into 'ss+bp+constant'.
>
> Since the latter involves a term more I assume it is bound to take more
> time.

That was true in the days of the 8086 (the former took 6 cycles while the latter took 9 cycles). On the i386 and i486, both expressions were already calculated in a single cycle; they only suffered an extra single cycle penalty in case the address expression used an index (your example only contains a base). On the Pentium, address expressions containing an index were also evaluated in a single cycle. On today's deeply pipelined processors it is extremely unlikely that there is any difference whatsoever in the number of steps used to evaluate both address expressions (even if the time required by the i386/i386/Pentium wasn't documented).

If you wish to read the outdated details of the old Intel processors:
* http://www.inf.puc-rio.br/~inf1018/material/intel.txt (search for "8088/8086  Effective Address (EA) Calculation")
* http://www.gamedev.net/reference/articles/article205.asp (search for "Choice of Index Versus Base Register")

Moreover, the first instruction takes up 10 bytes while the second one takes up only 7 bytes, which means that the "global array instruction" takes up more space in the icache (and that's something which actually /is/ very bad from a performance point-of-view). Combined with how global variables require indirection (as in "an extra memory load instruction") on RISC processors and if position-independent code is used (except under some specific circumstances on the x86-64), often slow down program startup (when the dynamic linker has to relocate them), and often behave very badly in terms of data locality (they are often surrounded by unrelated data, as opposed to local variables where the surrounding data will probably also be used by the same function), in general my bias would be much more against than in favour of global variables from a speed perspective (and when not talking about arrays, an additional advantage of local variables is that they often can be kept in registers rather than in memory, which is seldom the case for global variables).


Jonas_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Where is the best place to declare an array?

etrusco
On Thu, May 6, 2010 at 7:34 PM, Jonas Maebe <[hidden email]> wrote:

>
> On 06 May 2010, at 23:28, Werner Van Belle wrote:
>
>> In 'human' (haha) terms:
>>
>> - global variable access: write data into 'ds+constant'
>> - local variables: write data into 'ss+bp+constant'.
>>
>> Since the latter involves a term more I assume it is bound to take more
>> time.
>
> That was true in the days of the 8086 (the former took 6 cycles while the latter took 9 cycles). On the i386 and i486, both expressions were already calculated in a single cycle; they only suffered an extra single cycle penalty in case the address expression used an index (your example only contains a base). On the Pentium, address expressions containing an index were also evaluated in a single cycle. On today's deeply pipelined processors it is extremely unlikely that there is any difference whatsoever in the number of steps used to evaluate both address expressions (even if the time required by the i386/i386/Pentium wasn't documented).
>
> If you wish to read the outdated details of the old Intel processors:
> * http://www.inf.puc-rio.br/~inf1018/material/intel.txt (search for "8088/8086  Effective Address (EA) Calculation")
> * http://www.gamedev.net/reference/articles/article205.asp (search for "Choice of Index Versus Base Register")
>
> Moreover, the first instruction takes up 10 bytes while the second one takes up only 7 bytes, which means that the "global array instruction" takes up more space in the icache (and that's something which actually /is/ very bad from a performance point-of-view). Combined with how global variables require indirection (as in "an extra memory load instruction") on RISC processors and if position-independent code is used (except under some specific circumstances on the x86-64), often slow down program startup (when the dynamic linker has to relocate them), and often behave very badly in terms of data locality (they are often surrounded by unrelated data, as opposed to local variables where the surrounding data will probably also be used by the same function), in general my bias would be much more against than in favour of global variables from a speed perspective (and when not talking about arrays, an additional advantage of local variables is that they often can be kept in registers rather than in memory, which is seldom the case for global variables).
>
>
> Jonas_______________________________________________


Now that's a fantastic explanation, and I guess the OP will be satisfied :-)

-Flávio
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Where is the best place to declare an array?

Bihar Anwar
In reply to this post by Jonas Maebe-2
Thanks Jose, Werner, and Jonas for the fantastic discussion and explanation.



     

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Where is the best place to declare an array?

spir ☣
In reply to this post by Jonas Maebe-2
[OT -- not fpc-related -- just a side note]

On Fri, 7 May 2010 00:34:11 +0200
Jonas Maebe <[hidden email]> wrote:

> in general my bias would be much more against than in favour of global variables from a speed perspective

In _some_ dynamic languages using a virtual machine at least (eg Lua), local variables are actually stored in an array, after a one->one replacement from name to index at "compile"-time. While global ones are still looked up in a symbol table (associative array implemented as hash table) by name.
This indeed makes some speed difference ;-) (~ 50% in Lua) For instance:

<code lang=lua>
require "os" ; time = os.time
format = string.format
N = 333333333

f = function()
   a = 1 -- implicitely global
   local b = 0
   for i = 1,N do b=a end
end
g = function()
   local a = 1
   local b = 0
   for i = 1,N do b=a end
end

-- global case
t = time()
f()
t = time() - t
print(format("global : %2.0fs", t)) -- 25s
-- local case
t = time()
g()
t = time() - t
print(format("local  : %2.0fs", t)) -- 13s
</code>


Denis
________________________________

vit esse estrany ☣

spir.wikidot.com
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal