Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:114686
Content-Type: multipart/alternative;
	boundary="Apple-Mail=_7A3FC4B3-93DE-49A8-AF2C-4F9338176753"
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.6\))
Message-ID: <CAC47A8B-EFA1-41C1-908B-065D399D396F@newclarity.net>
Date: Tue, 1 Jun 2021 18:34:08 -0400
Cc: "internals@lists.php.net" <internals@lists.php.net>
To: Nikita Popov <nikita.ppv@gmail.com>
Subject: Regarding array_shift()/array_unshift()
From: mike@newclarity.net (Mike Schinkel)

--Apple-Mail=_7A3FC4B3-93DE-49A8-AF2C-4F9338176753
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8

Hi Nikita,

>> On May 28, 2021, at 10:31 AM, Nikita Popov <nikita.ppv@gmail.com =
<mailto:nikita.ppv@gmail.com>> wrote:
>=20
>> I don't think there's much need for mutable operations. sort() and =
shuffle() would be best implemented by returning a new array instead. =
array_push() is redundant with $array[]. array_shift() and =
array_unshift() should never be used.=20
>=20
> Why do you say array_shift() and array_unshift() should never be used? =
 When I wrote the above questions the use-case I was thinking about most =
was $a->unshift($value) as I use array_unshift() more than most of the =
other array functions.
>=20
> Do you mean that these if applied as "methods" to an array should not =
be use immutably =E2=80=94 meaning in-place is bad but returning an =
array value that has been shifted would be okay =E2=80=94 or do you have =
some other reason you believe that shifting an array is bad?  Note the =
reason I have used them in the past is when I need to pass an array to a =
function written by someone else that expects the array to be ordered.
>=20
> Also, what about very large arrays?  I assume =E2=80=94 which could be =
a bad assumption =E2=80=94 that PHP internally can be more efficient =
about how it handles array_unshift() instead of just duplicating the =
large array so as to add an element at the beginning?
>=20
> Arrays only support efficient push/pop operations. Performing an =
array_shift() or array_unshift() requires going through the whole array =
to reindex all the keys, even though you're only adding/removing one =
element. In other words, array_shift() and array_unshift() are O(n) =
operations, not O(1) as one would intuitively expect. If you use =
shift/unshift as common operations, you're better off using a different =
data-structure or construction approach.

I appreciate your explanation regarding array_shift()/array_unshift().

It left me curious though to see how those functions and have been used =
in userland, and what use-cases they frequently solve.=20

I decided to focused on array_unshift() because I have found reason to =
use it numerous times in the past but rarely use array_shift().  I =
searched some of the most popular PHP projects on Github and found the =
following # of uses for array_unshift() while the last project was one =
of yours:

Phan:10
   =
https://github.com/search?q=3Darray_unshift+language%3APHP+repo%3Aphan%2Fp=
han&type=3DCode

Phabricator:27
   =
https://github.com/search?l=3D&p=3D1&q=3Darray_unshift+language%3APHP+repo=
%3Aphacility%2Fphabricator&type=3DCode

Laravel:8
   =
https://github.com/search?q=3Darray_unshift+language%3APHP+repo%3Alaravel%=
2Fframework&type=3DCode

Symfony:34
   =
https://github.com/search?q=3Darray_unshift+language%3APHP+repo%3Asymfony%=
2Fsymfony&type=3DCode

PHP-CS-Fixer:8
   =
https://github.com/search?q=3Darray_unshift+language%3APHP+repo%3AFriendsO=
fPHP%2FPHP-CS-Fixer&type=3DCode

Composer:7
   =
https://github.com/search?q=3Darray_unshift+language%3APHP+repo%3Acomposer=
%2Fcomposer&type=3DCode

Statamic:2
   =
https://github.com/search?q=3Darray_unshift+language%3APHP+repo%3Astatamic=
%2Fcms&type=3DCode

Magento2:75
   =
https://github.com/search?q=3Darray_unshift+language%3APHP+repo%3Amagento%=
2Fmagento2&type=3DCode

WordPress:22
   =
https://github.com/search?q=3Darray_unshift+language%3APHP+repo%3AWordPres=
s%2Fwordpress-develop&type=3DCode

PHPMailer:1
   =
https://github.com/search?q=3Darray_unshift+language%3APHP+repo%3APHPMaile=
r%2FPHPMailer&type=3DCode
  =20
PHPBackporter:1
   =
https://github.com/nikic/PHP-Backporter/blob/master/lib/PHPBackporter/Conv=
erter/Closure.php#L100 =
<https://github.com/nikic/PHP-Backporter/blob/master/lib/PHPBackporter/Con=
verter/Closure.php#L100>

=46rom a manual review of those usages I have found roughly the =
following use-case categories:

------
Testing =E2=80=94 It seems a lot of tests use array_unshift(), for a =
variety of pre- and post- test uses.

Path Manipulation =E2=80=94 Such as when relative paths are exploded, =
the base path is inserted, and path segments imploded.

Ordered Processing/Filtering =E2=80=94 Where a list of elements are =
filtered to insert values to be processed first such as loading =
"plugins", inserting regular expressions for URL route processing, =
"policy modes", adding optional positional arguments to default values =
for a "builder" (command line, SQL, etc.), inserting custom menu items =
in front of default menu items, inserting higher priority middleware, =
insert column definitions to be displayed, inserting custom paths to =
look for theme template in front of default paths, inserting mime-types =
into a list of default acceptable mime-types, inserting directories for =
autoloaders, etc.

Parsers/Tokenizers =E2=80=94 When writing a parser or tokenizer and the =
need to insert a value or token at the head of the list.

Parameter Delegation =E2=80=94 When a function accepts a list of =
parameter, especially when they include variadic, and then needs to pass =
on the same set of parameters to another function such as with =
call_user_func_array(), sprints(), etc.Additional similar uses are to =
insert $this into return value of func_get_args() to allow delegation to =
a global function, also using call_user_func_array().=20
------

There may be more but in general those were the main reasons I found for =
using array_unshift() that I am not sure could be replaced by another =
data structure to any advantage. It's hard to replace an array with =
something else when your source for the data is a function that returns =
an array. (BTW, Phabricator uses array_unshift() more than any other, =
but uses it in contexts that would be easily replaced with something =
more performant. Ironic given that the project is no longer being =
maintained.)

So I was also intrigued by your statement that "you're better off using =
a different data-structure or construction approach" since I think we =
mostly use these functions when we have to use an array, not because we =
chose to. Such as when we are either given an array by some function we =
are not in control of, or when we need to pass a value to an ordered =
function we are not in control of. In the above use-cases I would really =
like to know if you can envision other data structures or constructions =
being better and if so what they are?

Also, almost every one of the use-cases mentioned above generally deal =
with very short arrays, such as parameter delegation.  Is O(<n>) really =
problematic when <n> is rather small?

-----
But from all this I do agree with you that just returning an array would =
likely be acceptable.=20
-----

This would not be a great solution for really large arrays, but then we =
can't eliminate the need for a developer to have a reasonable level of =
knowledge, right?  So:

$unshifted =3D $array->unshift($new_element);
$shifted =3D $array->shift();

But, we could also possibly use better names for these:

$right_shifted =3D $array->shift_right(...$new_element(s));
$left_shifted =3D $array->shift_left([element_count]);

OR

$prepended =3D $array->prepend(...$new_element(s));	=09
$prebated =3D $array->prebate([element_count]);

-Mike=

--Apple-Mail=_7A3FC4B3-93DE-49A8-AF2C-4F9338176753--