how does $#array work internally?

[Helmut Tessarek]

I'm wondering how the $#array construct works internally.

Does perl iterate through the array and return the highest index or does perl
use some meta data within the array structure?

The reason why I ask is the following:

I need the number of elements in a certain array several times throughout my
code. I build the array at the beginning and after that it does not change
anymore.
So I can use a variable which I increment during the construction of the array
or I could use $#array+1 to get the number of elements.

I need the number of elements several times in my code, so if perl has to
iterate through the array every time I use $#array, it is better for
performance to use a separate variable which I increment while building the
array....

Cheers,
Helmut

[Rainer Weikusat]

Helmut Tessarek <tess...@evermeet.cx> writes:
> I'm wondering how the $#array construct works internally.
>
> Does perl iterate through the array and return the highest index or does perl
> use some meta data within the array structure?
>
> The reason why I ask is the following:
>
> I need the number of elements in a certain array several times throughout my
> code. I build the array at the beginning and after that it does not change
> anymore.
> So I can use a variable which I increment during the construction of the array
> or I could use $#array+1 to get the number of elements.

Assuming that @array would be the array in question, you can get the
number of elements by evaluating that in scalar context, eg
scalar(@array). $#array is a more complex operation because it is
possible to assign to $#array in order to change the array
length. Depending on your version of perl, it will either just return
the 'array fill pointer' value (according to
http://www.perlmonks.org/?node_id=801691, since 5.12) or it will
create a 'magic SV' return value whose vtable has a get and a set
operation with the get-operation returns the fill ptr/ highest used
index in the array and the set-operation presumably changing it (very
likely, but I haven't checked that).

The short answer is 'meta data'.

[Ben Morrow]

Quoth Helmut Tessarek <tess...@evermeet.cx>:

> I'm wondering how the $#array construct works internally.
>
> Does perl iterate through the array and return the highest index or does perl
> use some meta data within the array structure?

Perl knows how long arrays are, and that information is stored directly
in the array structure. Even for tied arrays, they have to implement
FETCHSIZE, so $#array will be as efficient as the tie implementation can
make it.

Ben

[Helmut Tessarek]

On 08.11.12 13:33 , Rainer Weikusat wrote:
> Assuming that @array would be the array in question, you can get the

my bad, yes, 'array' is the name of the array.

> number of elements by evaluating that in scalar context, eg
> scalar(@array). $#array is a more complex operation because it is

it is a well-formed array (no holes), so I thought $#array (if using meta
data) is less expensvce than 'scalar @array' or does scalar @array also use
meta data?

> possible to assign to $#array in order to change the array
> length. Depending on your version of perl, it will either just return
> the 'array fill pointer' value (according to
> http://www.perlmonks.org/?node_id=801691, since 5.12) or it will
> create a 'magic SV' return value whose vtable has a get and a set
> operation with the get-operation returns the fill ptr/ highest used
> index in the array and the set-operation presumably changing it (very
> likely, but I haven't checked that).

thanks for detailed explanation.

[Helmut Tessarek]

On 08.11.12 13:54 , Ben Morrow wrote:
> Perl knows how long arrays are, and that information is stored directly
> in the array structure. Even for tied arrays, they have to implement
> FETCHSIZE, so $#array will be as efficient as the tie implementation can
> make it.

thx for the info.

[Keith Thompson]

Rainer Weikusat <rwei...@mssgmbh.com> writes:
[...]

> Assuming that @array would be the array in question, you can get the
> number of elements by evaluating that in scalar context, eg
> scalar(@array). $#array is a more complex operation because it is
> possible to assign to $#array in order to change the array
> length.

[...]

Yes, but assigning to $#array also changes the result of
scalar(@array). (I'm sure you know that, I'm just trying to avoid
confusion.)

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[J. Gleixner]

On 11/08/12 13:56, Helmut Tessarek wrote:
> On 08.11.12 13:33 , Rainer Weikusat wrote:
>> Assuming that @array would be the array in question, you can get the
>
> my bad, yes, 'array' is the name of the array.
>
>> number of elements by evaluating that in scalar context, eg
>> scalar(@array). $#array is a more complex operation because it is
>
> it is a well-formed array (no holes), so I thought $#array (if using meta
> data) is less expensvce than 'scalar @array' or does scalar @array also use
> meta data?

Use either. In many cases 'scalar' isn't needed.

perldoc perlintro
...
You might be tempted to use "$#array + 1" to tell you how many
items there are in an array. Don't bother. As it happens,
using @array where Perl expects to find a scalar value
("in scalar context") will give you the number of elements
in the array:

if (@animals < 5) { ... }



Seriously though, if your code is slow, it's not because you are
using $# or scalar @arr. Either one is not going to be *that*
'expensvce' [expensive].

"premature optimization is the root of all evil." -- Donald Knuth

[Rainer Weikusat]

Helmut Tessarek <tess...@evermeet.cx> writes:
> On 08.11.12 13:33 , Rainer Weikusat wrote:
>> Assuming that @array would be the array in question, you can get the
>
> my bad, yes, 'array' is the name of the array.
>
>> number of elements by evaluating that in scalar context, eg
>> scalar(@array). $#array is a more complex operation because it is
>
> it is a well-formed array (no holes), so I thought $#array (if using meta
> data) is less expensvce than 'scalar @array' or does scalar @array also use
> meta data?

NB: The description below is only true for 'real' arrays.

Both calculations are done based on the structure member which holds
the highest used index in the array. Evaluating the array in scalar
context is actually less expensive for two reason:

1. In Perl versions prio to 5.12, no intermediate 'magic SV' is
created because the result of this evaluation is not an
lvalue.

2. Calculating the number of elements is done by adding 1 to
the 'highest used index' value. But calcluating $#array
requires adding the current 'first index' value ($[, =>
perval(3pm)).

NB: On the computer where I tested this, the difference was about
0.000002s (2E-6).

-------------------
use Benchmark;

my @a = 1 .. 200;

timethese(-5,
{
len => sub {
my $l;

$l = @a;
return $l;
},

last => sub {
my $l;

$l = $#a;
return $l
}});

[Ben Morrow]

Quoth Helmut Tessarek <tess...@evermeet.cx>:

> On 08.11.12 13:33 , Rainer Weikusat wrote:
> > Assuming that @array would be the array in question, you can get the
>
> my bad, yes, 'array' is the name of the array.
>
> > number of elements by evaluating that in scalar context, eg
> > scalar(@array). $#array is a more complex operation because it is
>
> it is a well-formed array (no holes), so I thought $#array (if using meta
> data) is less expensvce than 'scalar @array' or does scalar @array also use
> meta data?

Perl arrays never have holes. Scalar @array uses the same metadata as
$#array, so it is just as cheap (cheaper sometimes, as Rainer pointed
out).

Ben

[Helmut Tessarek]

On 08.11.12 16:21 , J. Gleixner wrote:
> Seriously though, if your code is slow, it's not because you are
> using $# or scalar @arr. Either one is not going to be *that* 'expensvce'
> [expensive].

My code is not slow, but I agree with your statement. I still wanted to know
which one is more expensive.

> "premature optimization is the root of all evil." -- Donald Knuth

I disagree - to a certain extent. There is a difference between premature
optimization and performance aware coding.
Methinks it was Donald who suggested to use rather a prefix incrementer
instead of a postfix incrementer (once upon a time when compilers did not do
these things under the covers (if possible, because semantically valid)).

[Ben Morrow]

Quoth Rainer Weikusat <rwei...@mssgmbh.com>:

> Helmut Tessarek <tess...@evermeet.cx> writes:
> >
> > it is a well-formed array (no holes), so I thought $#array (if using meta
> > data) is less expensvce than 'scalar @array' or does scalar @array also use
> > meta data?
>
> NB: The description below is only true for 'real' arrays.
>
> Both calculations are done based on the structure member which holds
> the highest used index in the array. Evaluating the array in scalar
> context is actually less expensive for two reason:
>
> 1. In Perl versions prio to 5.12, no intermediate 'magic SV' is
> created because the result of this evaluation is not an
> lvalue.

It's perhaps worth pointing out that even after 5.12, $#array still
returns a magic SV if it's evaluated in lvalue context. Since subs are
allowed to modify their arguments, this means a call like foo($#array)
will have to create a magic SV, even if foo() isn't in fact going to
modify the length.

> 2. Calculating the number of elements is done by adding 1 to
> the 'highest used index' value. But calcluating $#array
> requires adding the current 'first index' value ($[, =>
> perval(3pm)).

As of 5.16 this is no longer true: $[ no longer exists, not even as the
lexically-scoped pragma it has been since (IIRC) 5.6.

scalar(@array) will still (probably) be slightly faster, since $#array
requires two ops (rv2av followed by av2arylen):

~% perl -MO=Concise,-exec -e'$#a'
-e syntax OK
1 <0> enter
2 <;> nextstate(main 1 -e:1) v:{
3 <$> gv(*a) s
4 <1> rv2av[t1] sKR/1
5 <1> av2arylen vK/1
6 <@> leave[1 ref] vKP/REFC

whereas scalar(@array) is implemented by rv2av directly:

~% perl -MO=Concise,-exec -e'scalar @a'
-e syntax OK
1 <0> enter
2 <;> nextstate(main 1 -e:1) v:{
3 <$> gv(*a) s
4 <1> rv2av[t1] sK/1
5 <@> leave[1 ref] vKP/REFC

Ben

[Rainer Weikusat]

"J. Gleixner" <glex_n...@qwest-spam-no.invalid> writes:

[...]

> You might be tempted to use "$#array + 1" to tell you how many
> items there are in an array. Don't bother. As it happens,
> using @array where Perl expects to find a scalar value
> ("in scalar context") will give you the number of elements
> in the array:
>
> if (@animals < 5) { ... }

This is also a stupid thing to do because evaluating @animals in
scalar context means perl will do the + 1 in compiled code, as opposed
to execuing Perl (perl?) bytecode to perform the same operation.

> Seriously though, if your code is slow, it's not because you are
> using $# or scalar @arr. Either one is not going to be *that*
> expensvce' [expensive].

... and if you just insert a

for my $i (1 .. 100) {
my $j = $i * 938289897227;
}

between any two lines of the 'productive' code, that's probably also
not going to have much of a detrimental effect. But that's not a good
reason to actually do that.

> "premature optimization is the root of all evil." -- Donald Knuth

In 1943, Joseph Goebbels held an infamous speech in the so-called
'Sportpalast' in Berlin where he repeatedly asked his (carefully
selected) audience whether they wanted to have 'the total war' and
elicited enthusiatic 'Yes! Yes!' shoutings from the audience. Since
this has been recorded on film, the affirmative part of this event
really ought to be useful as generic answer to any question aka
'everything can be proven with the help of a set of suitable
out-of-context quotes'.

In the given case, this 'quote' used to be a piece of advice to people
writing machine code supposed to be executed in the fairly byzantine
(by today's standards) CISC CPUs Knuth happened to be intimately
familiar with: "Don't worry about making maximally clever use of the
instruction set of the machine. Rather build a working 'inefficient'
solution and improve that afterwards". Translated to the 'Perl
universe', it should roughly become "Don't use the 'Perl golf'
approach for solving actual problems". Rather different from the use
you put it to, isn't it?

[bugbear]

Helmut Tessarek wrote:
> I'm wondering how the $#array construct works internally.
>
> Does perl iterate through the array and return the highest index or does perl
> use some meta data within the array structure?

The latter. It's more like a Pascal string than a 'C' String.

BugBear

[Ben Morrow]

Quoth Rainer Weikusat <rwei...@mssgmbh.com>:

>
> In 1943, Joseph Goebbels held an infamous speech in the so-called

Godwin. You lose.

Ben

[Rainer Weikusat]

To quote myself: Everything can be proven with a suitable set of out
of context quotes. Of course, when 'we' add 'intentional misquotation'
to the repertoire, as in "As an online discussion grows longer, the
probability of a comparison involving Nazis or Hitler approaches 1."
vs an explanation of the background (hundreds of men shouting "Yes!"
at the top of their lungs) I needed to get an absurd example for a
totally 'generic' quote, possibilities become infinite. But you can
just use "Just say no" in place of the example I used without really
changing the meaning.

[Rainer Weikusat]

Rainer Weikusat <rwei...@mssgmbh.com> writes:
> Ben Morrow <b...@morrow.me.uk> writes:
>> Quoth Rainer Weikusat <rwei...@mssgmbh.com>:
>>>
>>> In 1943, Joseph Goebbels held an infamous speech in the so-called
>>
>> Godwin. You lose.
>
> To quote myself: Everything can be proven with a suitable set of out
> of context quotes. Of course, when 'we' add 'intentional misquotation'
> to the repertoire

[...]

> possibilities become infinite.

Since this is sort of serious topic, I suggest that you should also
have a look at this:

http://www.jewcy.com/arts-and-culture/i_seem_be_verb_18_years_godwins_law

[Ben Morrow]

Quoth Rainer Weikusat <rwei...@mssgmbh.com>:

...which is why you should have picked a different analogy, or, better,
considered whether that sort of offensive hyperbole is appropriate in a
technical newsgroup.

Ben

[Rainer Weikusat]

This was neither an analogy nor an 'offensive hyperbole': Just a film
scene I happened to remember at that moment which is - in hindsight -
rather ridicolous than anything else which provided an example for a
quote taken out of context (because - obviously - not every question
asked in every other context generates a response of this kind).

I wasn't originally planning to write more on this because it really
doesn't belong here but - alas - ... The essence behind "Godwin's law"
(as also explained in the text I posted a hyperlink to) is that people
shouldn't publically claim that other people who disagree with them on
some kind of 'internet petty problem' would act "like Nazis" because -
considering the 'industrialized' killing of millions of people for no
particular reason which the Nazis conducted in Europe last century -
this is totally over the top for any kind of discussion, no matter how
opinionated. And wrongly accusing people of having done this, again,
because of some kind of petty disagreement, is not much better, Mr
Morrow.
#

[Keith Thompson]

Rainer Weikusat <rwei...@mssgmbh.com> writes:
> Ben Morrow <b...@morrow.me.uk> writes:
>> Quoth Rainer Weikusat <rwei...@mssgmbh.com>:
>>> Ben Morrow <b...@morrow.me.uk> writes:
>>> > Quoth Rainer Weikusat <rwei...@mssgmbh.com>:
>>> >>
>>> >> In 1943, Joseph Goebbels held an infamous speech in the so-called
>>> >
>>> > Godwin. You lose.
>>>
>>> To quote myself: Everything can be proven with a suitable set of out
>>> of context quotes.

[snip]

>> ...which is why you should have picked a different analogy, or, better,
>> considered whether that sort of offensive hyperbole is appropriate in a
>> technical newsgroup.
>
> This was neither an analogy nor an 'offensive hyperbole':

[snip]

Rainer, consider this. You introduced a Nazi reference into a
discussion of how $#array and scalar(@array) work. Regardless of
whether it was an apt analogy or not, and regardless of the true
meaning of Godwin's Law and whether it applies in this case, did
you really expect it to advance the discussion?