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.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.
Thanks,
- Tyson
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 SplFixedArrayhttps://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-pushIs there any interest in adding this? It would be much more efficient to
add these in C.Thanks,
- Tyson
Hi Tyson,
Did you have a look at ext-ds? It provides several very efficient data
structures:
https://github.com/php-ds/ext-ds
I would love if this extension could find its way into core, actually.
Kind regards,
Benjamin
Hi Benjamin Morel,
Did you have a look at ext-ds? It provides several very efficient data structures:
https://github.com/php-ds/ext-dsI would love if this extension could find its way into core, actually.
Yes, I have looked at ext-ds. I asked the maintainer about that a 3 months ago.
They'd intended to develop the extension separately from php's release cycle at the time.
https://github.com/php-ds/ext-ds/issues/156
SplFixedArray is still more efficient than array, and unrelatedly,
I had a proposal to reduce memory usage a bit more: https://github.com/php/php-src/pull/6552
Thanks,
- Tyson
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 SplFixedArrayhttps://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-pushIs 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.
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 SplFixedArrayhttps://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-pushIs 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
andSpl\ReverseArrayIteratorwhich 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 addingSpl\ArrayStackor 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