Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:112751
MIME-Version: 1.0
References: <DM6PR07MB661828888483689A57256358F9D80@DM6PR07MB6618.namprd07.prod.outlook.com>
In-Reply-To: <DM6PR07MB661828888483689A57256358F9D80@DM6PR07MB6618.namprd07.prod.outlook.com>
Reply-To: Levi Morrison <levi.morrison@datadoghq.com>
Date: Mon, 4 Jan 2021 08:58:04 -0700
Message-ID: <CAAKU0u=ZdOke08NEujYTzUpQ835r598k5x4H+XTviykjzb3dnA@mail.gmail.com>
To: tyson andre <tysonandre775@hotmail.com>
Cc: "internals@lists.php.net" <internals@lists.php.net>
Content-Type: text/plain; charset="UTF-8"
Subject: Re: [PHP-DEV] Proposal: Adding SplFixedArray->push() and SplFixedArray->pop()
From: internals@lists.php.net ("Levi Morrison via internals")

On Tue, Dec 29, 2020 at 10:04 AM tyson andre <tysonandre775@hotmail.com> wrote:
>
> Hi Internals,
>
> Currently, PHP doesn't have a built in memory-efficient array type with convenient push, pop, and other operations, similar to a list/vector in other languages.
> The closest built in in SPL is [SplFixedArray](https://www.php.net/manual/en/class.splfixedarray.php)
>
> https://www.php.net/manual/en/class.splstack.php uses a doubly linked list, which uses much more memory and time than sequential memory.
>
> Contrary to the name and description in https://www.php.net/manual/en/class.splfixedarray.php, the class is already resizable.
> The resize method is setSize - https://www.php.net/manual/en/splfixedarray.setsize.php
> (increasing size is efficient - erealloc will extend the underlying array into free memory if there is nothing in the way)
>
> Many programming languages have a memory-efficient list/vector type that can be conveniently appended to and popped from.
>
> https://docs.python.org/3/tutorial/datastructures.html#more-on-lists
> https://www.cplusplus.com/reference/vector/vector/
> https://docs.ruby-lang.org/en/2.0.0/Array.html#method-i-push
>
> Is there any interest in adding this? It would be much more efficient to add these in C.

The size of SplFixedArray is fixed, as its name suggests. Pushing and
popping don't really make sense; it's not the point of the data
structure. It does have a resize, but it's something of an escape
hatch, not a main use-case.

As is, I think the SplStack should be soft-deprecated. I don't think
it was built with specific use-cases in mind; it was added because
"hey a stack can be implemented via linked list and so can queue, how
easy let's do it". I mean no disrespect to its original authors, but
exposing all those implementation details via inheritance means we
can't change it without breaking code. Note that Scala also deprecated
their Stack that was implemented around a List:
https://www.scala-lang.org/api/2.12.0/scala/collection/mutable/Stack.html.

I also understand why the principal author of ext-ds wants to develop
and maintain it out of core; there are a lot of benefits to doing it
that way.

-----

This is actually a common issue with the SPL. For instance,
ArrayIterator is basically ArrayObject and will almost always
duplicate the array, which is costly. It should only duplicate in a
write scenario, either through the iterator (which shouldn't be done,
but the API is there) or to the original array. However, it's
difficult to achieve because of the exposed API.

I have a work-in-progress branch for adding `Spl\ForwardArrayIterator`
and `Spl\ReverseArrayIterator` which only increase the refcount of the
array, rather than duplicating it:
https://github.com/php/php-src/compare/master...morrisonlevi:spl/ForwardArrayIterator.

If you can think about what stack operations you really need (for
instance, do you need to reserve capacity ahead of time?), I wouldn't
be opposed to adding `Spl\ArrayStack` or something similar depending
on your requirements. The key is that it needs to either expose
implementation details and own it in the name, or it needs to hide all
those details.