Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

Hi Levi Morrison,

> > "Maximum size" shouldn't be an issue for `Deque` specifically, it's a 
> > `size_t`. It isn't an issue for SplFixedArray and ArrayObject.
> > (or for
> > PHP would just encounter a fatal error due to either
> 
> You wrote a lot, but unfortunately it was based on a misunderstanding.
> In some languages you can set the maximum allowed number of items a
> specific Deque can hold. For example (pseudo-code):
> 
>     let deque = new Deque(max_capacity: 3)
>     deque.push_back(1)
>     deque.push_back(2)
>     deque.push_back(3) # okay, it's now full
> 
>     deque.push_back(4) # !
> 
> In this condition, they either error or remove the earliest.
> 
> It's okay if the proposed Deque doesn't add this capability, but it's
> the only remaining major functionality which some languages have but
> not the others; it should at least be discussed, I think.

Oh, I hadn't remembered seeing that before. That makes sense.
All of the implementations I'd remembered were unlimited.
(https://cplusplus.com/reference/deque/deque/max_size/ was a system limit, for 
example)

I can't think of a common use case for that in php.
If there was one, though, I strongly believe it shouldn't be the same class 
(and shouldn't be a subclass),
in order to ensure the behavior of push or other operations remains easy to 
reason about.
This can be done in userland as a userland class.

- (e.g. with a Deque instance property and runtime `count() < 
$this->maxCapacity` checks,
  to choose their own desired return value or Throwable subclass (or manual 
array and circular buffer in PHP)

Thanks,
Tyson

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] RFC: Add `final class Vector` to PHP

[tyson andre]

Hi Mike Shinkel,

> >> Hmm. I must have missed that thread as I was definitely following the list 
> >> at that time. 
> >> 
> >> But I found the thread, which only had three (3) comments from others:
> >> 
> >> https://externals.io/message/112639
> >> 
> >> From Levi Morrison it seems his objection was to adding `push()` and 
> >> `pop()` to a class including the name "Fixed."  Levi suggested 
> >> soft-deprecating `SplStack` because it was implemented as a linked-list, 
> >> but he proposed adding `Spl\ArrayStack` or similar, so it seems he was 
> >> open to iterating on the `Spl` classes in general (no pun intended.) 
> >> 
> >> From Nikita is seemed that he did not object so much as comment on Levi's 
> >> suggestion of adding `Spl\ArrayStack` and suggested instead an `SqlDeque` 
> >> that would handle queue usage more efficiently that plain PHP arrays.
> >> 
> >> So I think those responses were promising, but that you did not followed 
> >> up on them. I mean no disrespect — we all get busy, our priorities change, 
> >> and things fall off our radar

I said that **in response to you suggesting adding functionality to 
`SplFixedArray`** as the reason why I am not adding functionality to 
`SplFixedArray`.
Those responses were promising for functionality that is not about 
`SplFixedArray`.

The `Vector` is a name choice. `SplArrayStack` and a `Vector` would have very 
similar performance characteristics and probably identical internal 
representations.
However, a more expansive standard library such as `contains`, `map`, `filter`, 
`reduce`, etc. makes more sense on a List/Vector
than a `Stack` if you're solely going based on the name - when you hear 
`Stack`, you mostly think of pushing or popping from it.

As you said also below in your followup response, I am following up on the 
suggestion for a `Deque`.

>  — but it feels to me like you might have more success pursing your use-cases 
> related to the `Spl` classes than via a pure `Vector` class.

It's hard to know which approach (namespaces such as Collection\, SplXyz, or 
short names) will succeed without actually creating an RFC.
I'd mentioned my personal reasons for expecting Spl not to be the best choice.
Any email discussion only has comments from a handful of people with different 
arguments and preferences,
and many times more people might vote on the final RFC

> > Experience in past RFCs gave me the impression that if:
> > 
> > 1. All of the responses are suggesting using a different approach(php-ds, 
> > arrays),
> > 2. Other comments are negative or uninterested.
> > 3. None of the feedback on the original idea is positive or interested in 
> > it.
> > 
> > When feedback was like that, voting would typically have mostly "no" 
> > results.
> 
> Understood, but for clarity I was implying that wanting to change 
> `SplFixedArray` was an "XY problem" and that maybe the way to address your 
> actually use-cases was to pursue other approaches that people were 
> suggesting, which _is_ what you did yesterday.  :-)
>
> >> Maybe propose an `SplVector` class that extends `SplFixedArray`, or 
> >> something similar that addresses the use-case and with a name that people 
> >> can agree on?
> > 
> > I'd be stuck with all of the features in `SplFixedArray` that get 
> > introduced later and its design deisions.
> 
> You wouldn't be stuck with all the feature of `SplFixedArray` if you did 
> "something similar." 

> (I make this point only as it seems you have dismiss one aspect of my 
> suggestion while not acknowledging the alternatives I present. Twice now, at 
> least.)

I'm not sure which of the multiple suggestions you brought up was  you're 
referring to as "something similar".
Your original suggestion I responded to was to modify "SplFixedArray",
I assumed you were suggesting that I change my RFC to focus on SplFixedArray,
I had the impression after feedback those changes to SplFixedArray would 
overwhelmingly fail especially due to being named "Fixed".

I don't consider making it a subclass of SplFixedArray a good design decision.
It's possible to invoke methods on base classes with `ReflectionMethod` so I 
can't make `Vector` a subclass of `SplFixedArray` with an entirely different 
implementation.
So any memory SplFixedArray wastes (e.g. to mitigate bugs already found or 
found in the future) is also wasted in any subclass of SplFixedArray.


- Additionally, this has the same problem as `SplDoublyLinkedList` and its 
subclasses.
  It prevents changing the internal representation of adding certain types of 
functionality if that wouldn't work with the base class.
- Additionally, this would make deprecating and removing `SplFixedArray` 
significantly harder or impractical,
  if it ever seemed appropriate in the future due to lack of use.

Additionally, I'm proposing a final class: SplFixedArray already exists and 
can't be converted to a final class because code already extends it.
See https://wiki.php.net/rfc/deque#final_class for the 

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Levi Morrison via internals]

> "Maximum size" shouldn't be an issue for `Deque` specifically, it's a 
> `size_t`. It isn't an issue for SplFixedArray and ArrayObject.
> (or for
> PHP would just encounter a fatal error due to either

You wrote a lot, but unfortunately it was based on a misunderstanding.
In some languages you can set the maximum allowed number of items a
specific Deque can hold. For example (pseudo-code):

let deque = new Deque(max_capacity: 3)
deque.push_back(1)
deque.push_back(2)
deque.push_back(3) # okay, it's now full

deque.push_back(4) # !

In this condition, they either error or remove the earliest.

It's okay if the proposed Deque doesn't add this capability, but it's
the only remaining major functionality which some languages have but
not the others; it should at least be discussed, I think.

-- 
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

Hi Levi Morrison,

> The name "deque" is used in the standard library of these languages:
> 
>  - C++: std::deque
>  - Java: java.util.Deque (interface)
>  - Python: collections.deque
>  - Swift: Collections.Deque (not standard lib, apparently, but Apple
> official? Don't know Swift)
>  - Rust: std::collections::VecDeque
> 
> And these don't have it in the standard library:
>  - Go
>  - C#
>  - C
>  - JavaScript
>
> Anyway, it's pretty decent evidence that:
>  1. This functionality is pretty widely used across languages.
>  2. This functionality should have "deque" be in the name, or be the
> complete name.

Thanks for putting that together.

For anyone wondering about the languages that don't have it:
The first 3 are compiled languages so there's the same performance for a 
standard library 
and third-party library code written in those libraries. 
For C and Go, the standard libraries of C and Go are written in C and Go.
C and Go also have a very minimal standard library as a design goal.
Everything in C and Go is a "native library", so a third-party library and a 
standard library would have the same performance.
(The standard library of C and Go use or allow embedding assembly for 
platform-dependent functionality or optimizations. 
Third party libraries in C or Go can also use inline assembly 
https://stackoverflow.com/a/23796420)
(Not familiar with C#'s standard library, I assume it's similar?)

And browser vendors have put immense amounts of effort on optimizing JavaScript
and the JIT compilers for JavaScript for low memory usage,
supporting inlining, working efficiently on various platforms, etc.

> Discussion naming for "vector" I can understand, as it's less widely
> used or sometimes means something specific to numbers, but there's
> little point in discussing the name "deque." It's well established in
> programming, whether PHP programmers are aware of it or not.

Yes, I'd agree.

It's a well established term in programming, and using a non-standard or more 
verbose term
would make it harder to find/remember this functionality for users moving to 
php from 
other programming languages, 
or for users moving from php to other programming languages.

Learning programming inevitably has unfamiliar terms such as `array`, `printf`, 
etc.
that are not commonly used in mathematics or daily life.

> As I see it, the discussion should be centered around:
>  1. The API Deque provides.
>  2. The package that provides it.
>  3. Whether Deque's API is consistent with other structures in the same 
> package.
>  4. Whether this should be included in php-src or left to extensions.
> 
> I suggest that we try to make PHP as homogenous in each bullet as we
> can with other languages:
>  1. Name it "Deque."
>  2. Put it in the namespace "Collections" (and if included in core,
> then "ext/collections").
>  3. Support common operations on Deque (pushing and popping items to
> both front and back, subscript operator works, iteration, size, etc)
> and add little else (don't be novel here). To me, the biggest thing
> left to discuss is a notion of a maximum size, which in my own
> experience is common for circular buffers (the implementation chosen
> for Deque) but not all languages have this.
>  4. This is less clear, but I'm in favor as long as we can provide a
few other data structures at the same time. Obviously, this a voter
judgement call on the yes/no.

I had planned on a minimal API for Deque.

"Maximum size" shouldn't be an issue for `Deque` specifically, it's a `size_t`. 
It isn't an issue for SplFixedArray and ArrayObject.
(or for 
PHP would just encounter a fatal error due to either

1. Hitting the `memory_limit` or available memory limit
while constructing or appending to the `Deque`
2. Seeing a fatal error due to integer overflow, which would only matter on 
32-bit php.
   (The `Deque` API doesn't have a setSize)
   The `safe_erealloc` macros allow you to do that.

For additions such as `Vector` and `Deque`, because we **can** choose a 
`size_t` (type large enough to store any size of memory) (and because 32-bit 
systems are increasingly rare),
I currently think always emitting an uncatchable fatal error (and exiting 
immediately) for impossibly large values
would be the most consistent (e.g. applications wouldn't reach `catch 
(Throwable $t)` 
blocks meant for a different purpose in an unexpected way, if they failed to 
validate inputs).
This is already done in array and SPL types.

```
php > var_dump(new SplFixedArray(PHP_INT_MAX));
Fatal error: Possible integer overflow in memory allocation 
(9223372036854775807 * 16 + 0) in php shell code on line 1

php > var_dump(array_fill(0, 2**31 - 2, null));

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to 
allocate 68719476744 bytes) in php shell code on line 1
php > var_dump(array_fill(0, 2**31, null));

Warning: Uncaught ValueError: array_fill(): Argument #2 ($count) is too large 
in php shell code:1
...

// Without memory_limit
php > 

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Levi Morrison via internals]

The name "deque" is used in the standard library of these languages:

 - C++: std::deque
 - Java: java.util.Deque (interface)
 - Python: collections.deque
 - Swift: Collections.Deque (not standard lib, apparently, but Apple
official? Don't know Swift)
 - Rust: std::collections::VecDeque

And these don't have it in the standard library:
 - Go
 - C#
 - C
 - JavaScript

Anyway, it's pretty decent evidence that:
 1. This functionality is pretty widely used across languages.
 2. This functionality should have "deque" be in the name, or be the
complete name.

Discussion naming for "vector" I can understand, as it's less widely
used or sometimes means something specific to numbers, but there's
little point in discussing the name "deque." It's well established in
programming, whether PHP programmers are aware of it or not.

As I see it, the discussion should be centered around:
 1. The API Deque provides.
 2. The package that provides it.
 3. Whether Deque's API is consistent with other structures in the same package.
 4. Whether this should be included in php-src or left to extensions.

I suggest that we try to make PHP as homogenous in each bullet as we
can with other languages:
 1. Name it "Deque."
 2. Put it in the namespace "Collections" (and if included in core,
then "ext/collections").
 3. Support common operations on Deque (pushing and popping items to
both front and back, subscript operator works, iteration, size, etc)
and add little else (don't be novel here). To me, the biggest thing
left to discuss is a notion of a maximum size, which in my own
experience is common for circular buffers (the implementation chosen
for Deque) but not all languages have this.
 4. This is less clear, but I'm in favor as long as we can provide a
few other data structures at the same time. Obviously, this a voter
judgement call on the yes/no.

Given that I've suggested the most common options for these across
many languages, it shouldn't be very controversial. The worst bit
seems like picking the namespace "Collections" as this will break at
least one package: https://github.com/danielgsims/php-collections. We
should suggest that they vendor it anyway, as "collections" is common
e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see
a good alternative here to "Collections", as we haven't agreed on very
much on past namespace proposals.

Anyway, that's what I suggest.

-- 
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Mike Schinkel]

> On Sep 21, 2021, at 1:12 PM, Pierre Joye  wrote:
> On Tue, Sep 21, 2021, 11:56 PM Mike Schinkel  > wrote:
> > On Sep 21, 2021, at 3:45 AM, Pierre Joye  > > wrote:
> > 
> > On Tue, Sep 21, 2021 at 11:21 AM Mike Schinkel  > > wrote:
> > 
> >> Honestly, at first I confused `Deque` with `Dequeue` and was wondering why 
> >> we would name a class with a verb?  It wasn't until Rowan's comment that I 
> >> realized `Deque` is an abbreviation.
> >> 
> >> Which begs the question: how many other PHP developers will know computer 
> >> science terms like this well enough to know `Deque` is a noun when they 
> >> see it, and more importantly how many PHP developers will think to search 
> >> for `Deque` when they need a queue?
> > 
> > Unlike the Vector name which is really confusing as it is not a
> > vector, Deque is actually relatively known for anyone needing a double
> > ended queue. It even comes first in google search, wikipedia or java
> > implementations, which matches this implementation.
> 
> Being able to google what Deque means is one thing, but thinking to search 
> for it when you don't know it exists *and* you don't know that Deque is the 
> term you would need to be searching for.
> 
> > We expect our
> > users to know all weird names of different patterns, I trust them to
> > be able to learn what a Deque is. :)
> 
> So we expect PHP developers to have a computer science background? Maybe you 
> are assuming everyone minimally has your expertise?  Have we as a group 
> decided to forsake beginners? 
> 
> 
> It is not what I was trying to explain.
> 
> However if one looks at the php documentation looking for specific things 
> like these, the Deque will be there. 
> 
> So I am not expecting anyone to have a CS background (btw, I don't), however 
> I do have a minimal trust in users reading the docs and doing a minimum of 
> research. 

And what I was trying to explain is that given my past experience working with 
other PHP developers, I believe that trust is misplaced for many.  

And why make it harder than it needs to be? For PHP, jargon is Bad(tm), IMHO 
anyway.

-Mike

Re: [PHP-DEV] RFC: Add `final class Vector` to PHP

[Mike Schinkel]

> On Sep 19, 2021, at 8:55 AM, tyson andre  wrote:
> 
> Hi Mike Schinkel,
>> 
>> Hmm. I must have missed that thread as I was definitely following the list 
>> at that time. 
>> 
>> But I found the thread, which only had three (3) comments from others:
>> 
>> https://externals.io/message/112639
>> 
>> From Levi Morrison it seems his objection was to adding `push()` and `pop()` 
>> to a class including the name "Fixed."  Levi suggested soft-deprecating 
>> `SplStack` because it was implemented as a linked-list, but he proposed 
>> adding `Spl\ArrayStack` or similar, so it seems he was open to iterating on 
>> the `Spl` classes in general (no pun intended.) 
>> 
>> From Nikita is seemed that he did not object so much as comment on Levi's 
>> suggestion of adding `Spl\ArrayStack` and suggested instead an `SqlDeque` 
>> that would handle queue usage more efficiently that plain PHP arrays.
>> 
>> So I think those responses were promising, but that you did not followed up 
>> on them. I mean no disrespect — we all get busy, our priorities change, and 
>> things fall off our radar — but it feels to me like you might have more 
>> success pursing your use-cases related to the `Spl` classes than via a pure 
>> `Vector` class.
> 
> Experience in past RFCs gave me the impression that if:
> 
> 1. All of the responses are suggesting using a different approach(php-ds, 
> arrays),
> 2. Other comments are negative or uninterested.
> 3. None of the feedback on the original idea is positive or interested in it.
> 
> When feedback was like that, voting would typically have mostly "no" results.

Understood, but for clarity I was implying that wanting to change 
`SplFixedArray` was an "XY problem" and that maybe the way to address your 
actually use-cases was to pursue other approaches that people were suggesting, 
which _is_ what you did yesterday.  :-)

>> Maybe propose an `SplVector` class that extends `SplFixedArray`, or 
>> something similar that addresses the use-case and with a name that people 
>> can agree on?
> 
> I'd be stuck with all of the features in `SplFixedArray` that get introduced 
> later and its design deisions.

You wouldn't be stuck with all the feature of `SplFixedArray` if you did 
"something similar." 

(I make this point only as it seems you have dismiss one aspect of my 
suggestion while not acknowledging the alternatives I present. Twice now, at 
least.)

>> I wavered on whether or not to propose a configurable growth factor, but 
>> ironically I did so to head off the potential complaint from anyone who 
>> cares deeply about memory usage (isn't that you?) that not allowing the 
>> growth factor to be configurable would mean that either the class would use 
>> too much memory for some use-cases, or would need to reallocate more memory 
>> too frequently for other use-cases, depending on what the default growth 
>> factor would be.
>> 
>> That said, I don't see how a configurable growth factor should be 
>> problematic for PHP? For those who don't need/care to optimize memory usage 
>> or reallocation frequency they can simply ignore it; no harm done. But for 
>> those who do care, it would give them the ability to fine tune their memory 
>> usage, which for selected use-cases could mean the difference between being 
>> able to implement something in PHP, or not.
>> 
>> Note that someone could easily argue that adding a memory-optimized data 
>> structure when we already have a perfectly flexible data structure with PHP 
>> arrays that can be used for the same algorithms is "excessive for a 
>> high-level language."  But then I don't think you would make that argument, 
>> so why make it for a configurable growth factor? #honestquestion
> 
> The growth factor is even lower level than shrinkToFit/reserve, and requires 
> extra memory to store the float,
> extra cpu time to do floating point multiplication rather than doubling,
> and additional API methods for something that 99% of applications wouldn't 
> use.
> I consider it more suitable for a low level language.

I respect your points here, but disagree.

> And if we discover a different resizing strategy is better, it prevents us 
> from changing it.

This is not true. 

We could easily no-op the GrowthFactor method and it would not break anything 
in 99.9...% percent of use-cases.

The relevant question here should be, what is the likelihood of us discovering 
a better resizing strategy that would not benefit at all from a growth factor?  
Is there evidence of one anywhere else?  I know that Go — designed to be 
performant to the extent it does not add complexity — uses a growth factor.

>> And finally I think when you conveyed the intent of the author of `ext-ds` 
>> you omitted part of his full statement. When seen in full I believe his 
>> statement conveys a different interest than the partial one implies:
>> 
>> https://github.com/php-ds/ext-ds/issues/156
>> 
>> While he did say "My long-term intention has been to not merge this 
>> 

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Pierre Joye]

On Tue, Sep 21, 2021, 11:56 PM Mike Schinkel  wrote:

> > On Sep 21, 2021, at 3:45 AM, Pierre Joye  wrote:
> >
> > On Tue, Sep 21, 2021 at 11:21 AM Mike Schinkel 
> wrote:
> >
> >> Honestly, at first I confused `Deque` with `Dequeue` and was wondering
> why we would name a class with a verb?  It wasn't until Rowan's comment
> that I realized `Deque` is an abbreviation.
> >>
> >> Which begs the question: how many other PHP developers will know
> computer science terms like this well enough to know `Deque` is a noun when
> they see it, and more importantly how many PHP developers will think to
> search for `Deque` when they need a queue?
> >
> > Unlike the Vector name which is really confusing as it is not a
> > vector, Deque is actually relatively known for anyone needing a double
> > ended queue. It even comes first in google search, wikipedia or java
> > implementations, which matches this implementation.
>
> Being able to google what Deque means is one thing, but thinking to search
> for it when you don't know it exists *and* you don't know that Deque is the
> term you would need to be searching for.
>
> > We expect our
> > users to know all weird names of different patterns, I trust them to
> > be able to learn what a Deque is. :)
>
> So we expect PHP developers to have a computer science background? Maybe
> you are assuming everyone minimally has your expertise?  Have we as a group
> decided to forsake beginners?



It is not what I was trying to explain.

However if one looks at the php documentation looking for specific things
like these, the Deque will be there.

So I am not expecting anyone to have a CS background (btw, I don't),
however I do have a minimal trust in users reading the docs and doing a
minimum of research.

best,

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Mike Schinkel]

> On Sep 21, 2021, at 3:45 AM, Pierre Joye  wrote:
> 
> On Tue, Sep 21, 2021 at 11:21 AM Mike Schinkel  wrote:
> 
>> Honestly, at first I confused `Deque` with `Dequeue` and was wondering why 
>> we would name a class with a verb?  It wasn't until Rowan's comment that I 
>> realized `Deque` is an abbreviation.
>> 
>> Which begs the question: how many other PHP developers will know computer 
>> science terms like this well enough to know `Deque` is a noun when they see 
>> it, and more importantly how many PHP developers will think to search for 
>> `Deque` when they need a queue?
> 
> Unlike the Vector name which is really confusing as it is not a
> vector, Deque is actually relatively known for anyone needing a double
> ended queue. It even comes first in google search, wikipedia or java
> implementations, which matches this implementation.

Being able to google what Deque means is one thing, but thinking to search for 
it when you don't know it exists *and* you don't know that Deque is the term 
you would need to be searching for.

> We expect our
> users to know all weird names of different patterns, I trust them to
> be able to learn what a Deque is. :)

So we expect PHP developers to have a computer science background? Maybe you 
are assuming everyone minimally has your expertise?  Have we as a group decided 
to forsake beginners?  

-Mike
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Pierre Joye]

On Tue, Sep 21, 2021 at 11:21 AM Mike Schinkel  wrote:

> Honestly, at first I confused `Deque` with `Dequeue` and was wondering why we 
> would name a class with a verb?  It wasn't until Rowan's comment that I 
> realized `Deque` is an abbreviation.
>
> Which begs the question: how many other PHP developers will know computer 
> science terms like this well enough to know `Deque` is a noun when they see 
> it, and more importantly how many PHP developers will think to search for 
> `Deque` when they need a queue?

Unlike the Vector name which is really confusing as it is not a
vector, Deque is actually relatively known for anyone needing a double
ended queue. It even comes first in google search, wikipedia or java
implementations, which matches this implementation. We expect our
users to know all weird names of different patterns, I trust them to
be able to learn what a Deque is. :)

best,
-- 
Pierre

@pierrejoye | http://www.libgd.org

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php