Array clearing

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

Array clearing

Ryan Joseph
As far as the compiler is concerned what’s the difference between clearing an array using a for-loop vs. FillChar? It seems like iterating the array would be slower but what does FillChar do exactly and is it faster? The primary concern here is that the memory originally allocated (using SetLength right?) remains in the same location.

var
  list: array of integer;

SetLength(list, 10);

for i := 0 to high(list) do
  list[i] := 0;

FillChar(list[0], Length(list) * sizeof(integer), 0);


Regards,
        Ryan Joseph

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

Re: Array clearing

Free Pascal - General mailing list

Am 01.04.2017 05:42 schrieb "Ryan Joseph" <[hidden email]>:
>
> As far as the compiler is concerned what’s the difference between clearing an array using a for-loop vs. FillChar? It seems like iterating the array would be slower but what does FillChar do exactly and is it faster? The primary concern here is that the memory originally allocated (using SetLength right?) remains in the same location.
>
> var
>   list: array of integer;
>
> SetLength(list, 10);
>
> for i := 0 to high(list) do
>   list[i] := 0;
>
> FillChar(list[0], Length(list) * sizeof(integer), 0);

It totally depends on the type. In case of primitive types like integers there is indeed only the performance difference (though if you know that the element size is four FillDWord could be even faster, depending on the implementation in the RTL).
If you have managed types however or class instances the result of the FillChar (or equivalent) would be memory leaks.

Plase also note that after a SetLength the new elements are already 0 (or equivalent).

Regards,
Sven


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

Re: Array clearing

Ryan Joseph

> On Apr 1, 2017, at 2:39 PM, Sven Barth via fpc-pascal <[hidden email]> wrote:
>
> It totally depends on the type. In case of primitive types like integers there is indeed only the performance difference (though if you know that the element size is four FillDWord could be even faster, depending on the implementation in the RTL).
> If you have managed types however or class instances the result of the FillChar (or equivalent) would be memory leaks.
>
>

Yeah, I was concerned with just compiler types or weakly retained classes where I’m just keeping the reference.

Thanks.

Regards,
        Ryan Joseph

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

Re: Array clearing

Ryan Joseph

> On Apr 1, 2017, at 2:50 PM, Ryan Joseph <[hidden email]> wrote:
>
> Yeah, I was concerned with just compiler types or weakly retained classes where I’m just keeping the reference.

Another question. Is it more efficient/faster to reallocate a new array of the same size or call FillChar on the existing array?

Regards,
        Ryan Joseph

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

Re: Array clearing

Free Pascal - General mailing list

Am 01.04.2017 10:35 schrieb "Ryan Joseph" <[hidden email]>:
>
>
> > On Apr 1, 2017, at 2:50 PM, Ryan Joseph <[hidden email]> wrote:
> >
> > Yeah, I was concerned with just compiler types or weakly retained classes where I’m just keeping the reference.
>
> Another question. Is it more efficient/faster to reallocate a new array of the same size or call FillChar on the existing array?

I think that FillChar should be faster as reallocating would need setting the array to Nil and recreating it (SetLength with the same length won't touch the existing elements) thus loosing any gain of reallocate and then there'd still be the internal FillChar of the array.

Regards,
Sven


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

Re: Array clearing

Jürgen Hestermann
I am wondering what the purpose of filling all
array elements with zero's could be.
If I want to discard all elements I would simply delete
the whole array (setlength(MyArray,0) ).

But when should it be useful to keep all elements and
just overwrite them all with zero's (which is also very time consuming)?
If the exisiting values are no longer valid then why not
simply delete these elements?
It's the fastest way to get rid of them.
If elements were zero before overwriting them with zero's
I cannot even distinguish between original and overwritten elements.

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

Re: Array clearing

Free Pascal - General mailing list

Am 01.04.2017 13:31 schrieb "Jürgen Hestermann" <[hidden email]>:
>
> I am wondering what the purpose of filling all
> array elements with zero's could be.
> If I want to discard all elements I would simply delete
> the whole array (setlength(MyArray,0) ).
>
> But when should it be useful to keep all elements and
> just overwrite them all with zero's (which is also very time consuming)?
> If the exisiting values are no longer valid then why not
> simply delete these elements?
> It's the fastest way to get rid of them.
> If elements were zero before overwriting them with zero's
> I cannot even distinguish between original and overwritten elements.
>

If you wouldn't change the size of the array then merely doing FillChar (if not working with managed types) is more performant then freeing the array and allocating it again (which will also zero out the elements).
Normally the performance difference isn't *that* important, but sometimes that difference can make or break something.

Regards,
Sven


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

Re: Array clearing

Ryan Joseph
In reply to this post by Jürgen Hestermann

> On Apr 1, 2017, at 6:31 PM, Jürgen Hestermann <[hidden email]> wrote:
>
> I am wondering what the purpose of filling all
> array elements with zero's could be.
> If I want to discard all elements I would simply delete
> the whole array (setlength(MyArray,0) ).

Because the array is being iterated and I need to know which values are set. Basically I have a dynamic array I grow to a certain size and this process happens in a loop. The options are to allocate/free the array every cycle or clear memory and allocate the array once.

Regards,
        Ryan Joseph

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

Re: Array clearing

Jürgen Hestermann
Am 2017-04-01 um 15:09 schrieb Ryan Joseph:
 > Because the array is being iterated and I need to know which values
are set.
 > Basically I have a dynamic array I grow to a certain size and this
process happens in a loop.
 > The options are to allocate/free the array every cycle or clear
memory and allocate the array once.

If you just need to reuse the same array and only need to zero its elements
then of course fillchar would be the fastest approach (it saves the memory
reallocation step).

But this works only for standard array element types (like integer etc.).
Managed types have to be reset element by element.

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

Re: Array clearing

wkitty42
In reply to this post by Jürgen Hestermann
On 04/01/2017 07:31 AM, Jürgen Hestermann wrote:
> I am wondering what the purpose of filling all
> array elements with zero's could be.
> If I want to discard all elements I would simply delete
> the whole array (setlength(MyArray,0) ).

consider this: when using a string var and writing to a binary file... you reuse
the string var for each value written... if you don't clear the string var
between fills then the binary will contain "garbage" in the unused positions of
the string var... you can see this "garbage" when you view the binary file in
hex mode... the "garbage" being older longer string data than the current string
data in the var... this var may be a global throwaway string var...

we've seen the above since back in the TP3 days, at least... in some cases,
we've been able to extract enough "garbage" to break security on a system...
especially when there was enough left to suss out the leading part...

--
  NOTE: No off-list assistance is given without prior approval.
        *Please keep mailing list traffic on the list* unless
        private contact is specifically requested and granted.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Array clearing

Jürgen Hestermann
Am 2017-04-01 um 19:42 schrieb [hidden email]:
 > consider this: when using a string var and writing to a binary file...
 > you reuse the string var for each value written...
 > if you don't clear the string var between fills then the binary will
 > contain "garbage" in the unused positions of the string var...
 > you can see this "garbage" when you view the binary file in hex mode...
 > the "garbage" being older longer string data than the current string
data in the var...
 > this var may be a global throwaway string var...

This can only happen for older string types where the actual length
can differ from the reserved memory (maximum string length).
With managed strings, this should never be possible as it would write
only the bytes of the current length.

I also don't see how this applies to an array of integers.

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

Re: Array clearing

wkitty42
On 04/01/2017 02:33 PM, Jürgen Hestermann wrote:

> Am 2017-04-01 um 19:42 schrieb [hidden email]:
>> consider this: when using a string var and writing to a binary file...
>> you reuse the string var for each value written...
>> if you don't clear the string var between fills then the binary will
>> contain "garbage" in the unused positions of the string var...
>> you can see this "garbage" when you view the binary file in hex mode...
>> the "garbage" being older longer string data than the current string data in
> the var...
>> this var may be a global throwaway string var...
>
> This can only happen for older string types where the actual length
> can differ from the reserved memory (maximum string length).
> With managed strings, this should never be possible as it would write
> only the bytes of the current length.

some situations call for fixed length records... this same "garbage" effect will
be seen in them...

> I also don't see how this applies to an array of integers.

it may not... the subject doesn't differentiate... it only says "array" so i
provided an example to your query about why this clearing may be desired... i
just happened to use an array of char that we loving know as string[255]...


--
  NOTE: No off-list assistance is given without prior approval.
        *Please keep mailing list traffic on the list* unless
        private contact is specifically requested and granted.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Array clearing

Ryan Joseph
In reply to this post by Jürgen Hestermann

> On Apr 1, 2017, at 9:25 PM, Jürgen Hestermann <[hidden email]> wrote:
>
> If you just need to reuse the same array and only need to zero its elements
> then of course fillchar would be the fastest approach (it saves the memory
> reallocation step).

Why is this “of course”? What’s the implementation of FillChar exactly? For all I know it has to iterate over a range of bytes and this could be slower than allocation of memory. Maybe some of the compiler people know these details.

Regards,
        Ryan Joseph

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

Re: Array clearing

Jonas Maebe-3
On 02/04/17 11:22, Ryan Joseph wrote:
>> On Apr 1, 2017, at 9:25 PM, Jürgen Hestermann <[hidden email]> wrote:
>>
>> If you just need to reuse the same array and only need to zero its elements
>> then of course fillchar would be the fastest approach (it saves the memory
>> reallocation step).
> Why is this “of course”? What’s the implementation of FillChar exactly? For all I know it has to iterate over a range of bytes and this could be slower than allocation of memory. Maybe some of the compiler people know these details.

Allocating new memory via setlength also clears the memory (+ the
overhead of allocating the memory).


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

Re: Array clearing

Free Pascal - General mailing list
In reply to this post by Ryan Joseph
On 02.04.2017 11:22, Ryan Joseph wrote:
>
>> On Apr 1, 2017, at 9:25 PM, Jürgen Hestermann <[hidden email]> wrote:
>>
>> If you just need to reuse the same array and only need to zero its elements
>> then of course fillchar would be the fastest approach (it saves the memory
>> reallocation step).
>
> Why is this “of course”? What’s the implementation of FillChar exactly? For all I know it has to iterate over a range of bytes and this could be slower than allocation of memory. Maybe some of the compiler people know these details.

The question is not about the implementation of FillChar. It's about
reallocating a dynamic array as to reallocate it you'd need to do

=== code begin ===

SetLength(arr, 0);
SetLength(arr, newlen);

=== code end ===

And that this is more complex than

=== code begin ===

FillChar(arr, SizeOf(arr[0]) * Length(arr), 0);

=== code end ===

can be easily seen by looking at the implementation of SetLength() in
$fpcdir/rtl/inc/dynarr.inc, fpc_dynarray_setlength().
Especially since line 220 (at least in the current revision) contains a
call to FillChar(), the whole ordeal can only be *more* complex than
FillChar().

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

Re: Array clearing

Ryan Joseph

> On Apr 2, 2017, at 11:02 PM, Sven Barth via fpc-pascal <[hidden email]> wrote:
>
> can be easily seen by looking at the implementation of SetLength() in
> $fpcdir/rtl/inc/dynarr.inc, fpc_dynarray_setlength().
> Especially since line 220 (at least in the current revision) contains a
> call to FillChar(), the whole ordeal can only be *more* complex than
> FillChar().

That’s good to know about SetLength.

Is it possible use FillChar on a multidimensional arrays?

arr: array of array of array of integer.
SetLength(arr, 3, 3, 3);
FillChar(arr[0], (3*3*3)*sizeof(integer), false);

I’m just getting crashes.

Regards,
        Ryan Joseph

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

Re: Array clearing

Free Pascal - General mailing list

Am 04.04.2017 06:55 schrieb "Ryan Joseph" <[hidden email]>:
>
>
> > On Apr 2, 2017, at 11:02 PM, Sven Barth via fpc-pascal <[hidden email]> wrote:
> >
> > can be easily seen by looking at the implementation of SetLength() in
> > $fpcdir/rtl/inc/dynarr.inc, fpc_dynarray_setlength().
> > Especially since line 220 (at least in the current revision) contains a
> > call to FillChar(), the whole ordeal can only be *more* complex than
> > FillChar().
>
> That’s good to know about SetLength.
>
> Is it possible use FillChar on a multidimensional arrays?
>
> arr: array of array of array of integer.
> SetLength(arr, 3, 3, 3);
> FillChar(arr[0], (3*3*3)*sizeof(integer), false);
>
> I’m just getting crashes.

That does only work with static arrays as dynamic arrays are in reality managed pointers, thus you override the pointers themselves with your FillChar. Not to mention that you're overwriting the memory behind the outermost array as that only has a size of Length(arr) * SizeOf(Pointer).

Regards,
Sven


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

Re: Array clearing

Free Pascal - General mailing list
In reply to this post by Ryan Joseph
On 04/04/17 05:25, Ryan Joseph wrote:
> Is it possible use FillChar on a multidimensional arrays?
>
> arr: array of array of array of integer.
> SetLength(arr, 3, 3, 3);
> FillChar(arr[0], (3*3*3)*sizeof(integer), false);
>
> I’m just getting crashes.

You can always use FillChar and its kin on specific 'nested' arrays like
this

type
   TIntArray = array of Integer;
   TIntIntArray = array of TIntArray;
   TIntIntIntArray = array of TIntIntArray;

   procedure FillArray(const anArray: TIntIntIntArray; aValue: DWord);
   var
     x, y: integer;
   begin
     for x:=0 to High(anArray) do
       for y:=0 to High(anArray[x]) do
         FillDWord(anArray[x][y][0], Length(anArray[x][y]), aValue);
   end;
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Array clearing

Mark Morgan Lloyd-5
In reply to this post by Jonas Maebe-3
On 02/04/17 10:00, Jonas Maebe wrote:

> Allocating new memory via setlength also clears the memory (+ the
> overhead of allocating the memory).

Jonas, is it still the case that if SetLength() results in existing data
being moved that the original- which might be e.g. an unencrypted
password- isn't cleared?

--
Mark Morgan Lloyd
markMLl .AT. telemetry.co .DOT. uk

[Opinions above are the author's, not those of his employers or colleagues]
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Array clearing

Jürgen Hestermann
Am 2017-04-04 um 12:51 schrieb Mark Morgan Lloyd:
 > On 02/04/17 10:00, Jonas Maebe wrote:
 >> Allocating new memory via setlength also clears the memory (+ the
 >> overhead of allocating the memory).
 > Jonas, is it still the case that if SetLength() results in existing data being moved that the original- which might be e.g. an unencrypted password- isn't cleared?

Only formerly not existing elements are overwritten via fillchar.
Already existing data is not changed of course (otherwise you would
loose them).
If you have a (dynamic) array of 5 elements and you extend it
to 7 elements via Setlength(MyArray,7) then only the last 2 (new) elements
are cleared (because otherwise they would contain garbage).

This is (and must be) independend from moving data or just extending the existing array.
If the existing elements are moved (because the allocated memory cannot be extended)
then they are not cleared (but moved).
Only formerly not existing elements are filled with zeros and
they are never moved because they did not exist before the SetLength command.

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