Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:112762
MIME-Version: 1.0
References: <DM6PR07MB661828888483689A57256358F9D80@DM6PR07MB6618.namprd07.prod.outlook.com>
 <CAAKU0u=ZdOke08NEujYTzUpQ835r598k5x4H+XTviykjzb3dnA@mail.gmail.com>
In-Reply-To: <CAAKU0u=ZdOke08NEujYTzUpQ835r598k5x4H+XTviykjzb3dnA@mail.gmail.com>
Date: Tue, 5 Jan 2021 14:27:03 +0100
Message-ID: <CAF+90c__QQ-9cvLuaA_KnDmvXFuhWBcTpmdOuLTopFHi-16U9Q@mail.gmail.com>
To: Levi Morrison <levi.morrison@datadoghq.com>
Cc: tyson andre <tysonandre775@hotmail.com>, 
	"internals@lists.php.net" <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="0000000000008ab5d905b8272a0c"
Subject: Re: [PHP-DEV] Proposal: Adding SplFixedArray->push() and SplFixedArray->pop()
From: nikita.ppv@gmail.com (Nikita Popov)

--0000000000008ab5d905b8272a0c
Content-Type: text/plain; charset="UTF-8"

On Mon, Jan 4, 2021 at 4:58 PM Levi Morrison via internals <
internals@lists.php.net> wrote:

> 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.
>

Rather than SplArrayStack, it might make sense to go for SplDeque, which is
a structure that supports both stack and queue usage efficiently. I find
that a normal PHP array serves well-enough for stacks (and is probably the
most efficient way to do this in PHP), but queue and deque structures are
somewhat inconvenient to implement efficiently using plain arrays as the
base.

Regards,
Nikita

--0000000000008ab5d905b8272a0c--