rfc:cachediterable
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
rfc:cachediterable [2021/06/13 16:15] – tandre | rfc:cachediterable [2021/06/29 14:24] (current) – tandre | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== PHP RFC: ImmutableKeyValueSequence | + | ====== PHP RFC: ImmutableIterable |
- | * Version: 0.3 | + | * Version: 0.4 |
* Date: 2021-02-06 | * Date: 2021-02-06 | ||
* Author: Tyson Andre, tandre@php.net | * Author: Tyson Andre, tandre@php.net | ||
- | * Status: | + | * Status: |
* Implementation: | * Implementation: | ||
* First Published at: https:// | * First Published at: https:// | ||
Line 11: | Line 11: | ||
Currently, PHP does not provide a built-in way to store the state of an arbitrary iterable for reuse later (when the iterable has arbitrary keys, or when keys might be repeated). It would be useful to do so for many use cases, such as: | Currently, PHP does not provide a built-in way to store the state of an arbitrary iterable for reuse later (when the iterable has arbitrary keys, or when keys might be repeated). It would be useful to do so for many use cases, such as: | ||
- | - Creating a rewindable copy of a non-rewindable Traversable (e.g. a '' | + | - Creating a rewindable copy of a non-rewindable Traversable (e.g. a '' |
- Generating an '' | - Generating an '' | ||
- Providing internal or userland helpers such as '' | - Providing internal or userland helpers such as '' | ||
Line 20: | Line 20: | ||
===== Proposal ===== | ===== Proposal ===== | ||
- | Add a class '' | + | Add a class '' |
<code php> | <code php> | ||
- | final class ImmutableKeyValueSequence | + | final class ImmutableIterable |
+ | | ||
+ | | ||
+ | | ||
{ | { | ||
public function __construct(iterable $iterator) {} | public function __construct(iterable $iterator) {} | ||
Line 29: | Line 32: | ||
public function count(): int {} | public function count(): int {} | ||
// [[$key1, $value1], [$key2, $value2]] | // [[$key1, $value1], [$key2, $value2]] | ||
- | public static function fromPairs(array $pairs): | + | public static function fromPairs(array $pairs): |
// [[$key1, $value1], [$key2, $value2]] | // [[$key1, $value1], [$key2, $value2]] | ||
public function toPairs(): array{} | public function toPairs(): array{} | ||
public function __serialize(): | public function __serialize(): | ||
public function __unserialize(array $data): void {} | public function __unserialize(array $data): void {} | ||
+ | public static function __set_state(array $array): ImmutableIterable {} | ||
// useful for converting iterables back to arrays for further processing | // useful for converting iterables back to arrays for further processing | ||
Line 48: | Line 52: | ||
</ | </ | ||
- | ImmutableKeyValueSequences | + | ImmutableIterables |
<code php> | <code php> | ||
- | $x = new ImmutableKeyValueSequence([0 => 100, ' | + | $x = new ImmutableIterable([0 => 100, ' |
foreach ($x as $key1 => $value1) { | foreach ($x as $key1 => $value1) { | ||
echo "$key1 $value1: | echo "$key1 $value1: | ||
Line 68: | Line 72: | ||
</ | </ | ||
- | ==== ImmutableKeyValueSequences | + | ==== ImmutableIterables |
- | ImmutableKeyValueSequences | + | ImmutableIterables |
In comparison to php's '' | In comparison to php's '' | ||
Line 87: | Line 91: | ||
} | } | ||
- | $x = new ImmutableKeyValueSequence(my_generator()); | + | $x = new ImmutableIterable(my_generator()); |
foreach ($x as $k => $v) { | foreach ($x as $k => $v) { | ||
printf(" | printf(" | ||
Line 109: | Line 113: | ||
</ | </ | ||
- | ==== ImmutableKeyValueSequences | + | ==== ImmutableIterables |
- | ImmutableKeyValueSequence | + | ImmutableIterable |
- | Dynamic properties are forbidden on ImmutableKeyValueSequences. | + | Dynamic properties are forbidden on ImmutableIterables. |
- | The keys and values of the ImmutableKeyValueSequence | + | The keys and values of the ImmutableIterable |
This makes it useful for returning to wrap the keys and values that would be returned by a generator or single-use '' | This makes it useful for returning to wrap the keys and values that would be returned by a generator or single-use '' | ||
- | ==== ImmutableKeyValueSequences | + | ==== ImmutableIterables |
This can be done imperatively, | This can be done imperatively, | ||
<code php> | <code php> | ||
- | $it = ImmutableKeyValueSequence:: | + | $it = ImmutableIterable:: |
foreach ($it as $key => $value) { | foreach ($it as $key => $value) { | ||
printf(" | printf(" | ||
Line 134: | Line 138: | ||
var_dump($it); | var_dump($it); | ||
/* | /* | ||
- | object(ImmutableKeyValueSequence)#2 (1) { | + | object(ImmutableIterable)#2 (1) { |
[0]=> | [0]=> | ||
array(2) { | array(2) { | ||
Line 148: | Line 152: | ||
</ | </ | ||
- | ImmutableKeyValueSequences | + | ImmutableIterables |
<code php> | <code php> | ||
- | php > $reversedIt = ImmutableKeyValueSequence:: | + | php > $reversedIt = ImmutableIterable:: |
php > echo json_encode($reversedIt-> | php > echo json_encode($reversedIt-> | ||
[[{" | [[{" | ||
Line 158: | Line 162: | ||
===== Benchmarks ===== | ===== Benchmarks ===== | ||
- | ==== ImmutableKeyValueSequences | + | ==== ImmutableIterables |
- | Similarly to how '' | + | Similarly to how '' |
<code php> | <code php> | ||
Line 175: | Line 179: | ||
gc_collect_cycles(); | gc_collect_cycles(); | ||
$before = memory_get_usage(); | $before = memory_get_usage(); | ||
- | // create a ImmutableKeyValueSequence | + | // create a ImmutableIterable |
- | $result = new ImmutableKeyValueSequence(array_flip(range(10, | + | $result = new ImmutableIterable(array_flip(range(10, |
$after = memory_get_usage(); | $after = memory_get_usage(); | ||
- | printf(" | + | printf(" |
} | } | ||
foreach ([1, 8, 12, 16, 2**16] as $n) { | foreach ([1, 8, 12, 16, 2**16] as $n) { | ||
Line 185: | Line 189: | ||
} | } | ||
/* | /* | ||
- | array memory: | + | array memory: |
- | ImmutableKeyValueSequence | + | ImmutableIterable |
- | array memory: | + | array memory: |
- | ImmutableKeyValueSequence | + | ImmutableIterable |
- | array memory: | + | array memory: |
- | ImmutableKeyValueSequence | + | ImmutableIterable |
- | array memory: | + | array memory: |
- | ImmutableKeyValueSequence | + | ImmutableIterable |
- | array memory: | + | array memory: |
- | ImmutableKeyValueSequence | + | ImmutableIterable |
*/ | */ | ||
</ | </ | ||
- | ==== ImmutableKeyValueSequences | + | ==== ImmutableIterables |
For a simple example, this uses much less time to construct. It is almost 6 times faster to iterate over and process results than a polyfill in that example, and uses half as much additional memory. | For a simple example, this uses much less time to construct. It is almost 6 times faster to iterate over and process results than a polyfill in that example, and uses half as much additional memory. | ||
Line 205: | Line 209: | ||
<?php | <?php | ||
/* | /* | ||
- | Time to construct | + | Time to construct |
Time to iterate: 0.183351, memory usage: 67117328 | Time to iterate: 0.183351, memory usage: 67117328 | ||
result: | result: | ||
- | Time to construct | + | Time to construct |
Time to iterate: 0.021905, memory usage: 32002128 | Time to iterate: 0.021905, memory usage: 32002128 | ||
result: | result: | ||
Line 219: | Line 223: | ||
* Barely any of the functionality in the proposal is implemented. | * Barely any of the functionality in the proposal is implemented. | ||
* This is just here to compare a fast (in terms of time to iterate) userland polyfill | * This is just here to compare a fast (in terms of time to iterate) userland polyfill | ||
- | * against | + | * against |
* | * | ||
* Not an IteratorAggregate for simplicity. | * Not an IteratorAggregate for simplicity. | ||
*/ | */ | ||
- | class PolyfillKeyValueSequence | + | class PolyfillImmutableIterator |
public $i = 0; | public $i = 0; | ||
public $count = 0; | public $count = 0; | ||
Line 267: | Line 271: | ||
gc_collect_cycles(); | gc_collect_cycles(); | ||
$memory_usage_2 = memory_get_usage(); | $memory_usage_2 = memory_get_usage(); | ||
- | printf(" | + | printf(" |
$class, $t2 - $t1, $t3 - $t2, $memory_usage_2 - $memory_usage_1, | $class, $t2 - $t1, $t3 - $t2, $memory_usage_2 - $memory_usage_1, | ||
} | } | ||
- | benchmark(PolyfillKeyValueSequence::class); | + | benchmark(PolyfillImmutableIterator::class); |
- | benchmark(ImmutableKeyValueSequence::class); | + | benchmark(ImmutableIterable::class); |
</ | </ | ||
- | ==== ImmutableKeyValueSequences | + | ==== ImmutableIterables |
- | ImmutableKeyValueSequences | + | '' |
For example, it is possible to do binary search on keys (and/or values) without using any additional time or memory to create a copy of the keys. | For example, it is possible to do binary search on keys (and/or values) without using any additional time or memory to create a copy of the keys. | ||
(Same for values). | (Same for values). | ||
Line 285: | Line 289: | ||
* Returns count($it) if all keys are smaller than $target. | * Returns count($it) if all keys are smaller than $target. | ||
*/ | */ | ||
- | function do_binary_search_on_key(ImmutableKeyValueSequence | + | function do_binary_search_on_key(ImmutableIterable |
$lowOffset = 0; | $lowOffset = 0; | ||
$highOffset = count($it) - 1; | $highOffset = count($it) - 1; | ||
Line 299: | Line 303: | ||
} | } | ||
} | } | ||
- | echo " | + | echo " |
": | ": | ||
return $lowOffset; | return $lowOffset; | ||
Line 311: | Line 315: | ||
} | } | ||
ksort($data); | ksort($data); | ||
- | $it = new ImmutableKeyValueSequence($data); | + | $it = new ImmutableIterable($data); |
do_binary_search_on_key($it, | do_binary_search_on_key($it, | ||
Line 330: | Line 334: | ||
===== Backward Incompatible Changes ===== | ===== Backward Incompatible Changes ===== | ||
- | None, except that the class name '' | + | None, except that the class name '' |
===== Proposed PHP Version(s) ===== | ===== Proposed PHP Version(s) ===== | ||
Line 337: | Line 341: | ||
===== Future Scope ===== | ===== Future Scope ===== | ||
- | * This will enable adding internal iterable functions such as '' | + | * This will enable adding internal iterable functions such as '' |
- | * More methods may be useful to add to '' | + | * More methods may be useful to add to '' |
* This may or may not be useful for future data types, e.g. a '' | * This may or may not be useful for future data types, e.g. a '' | ||
- | * A new '' | + | * A new '' |
- | ===== Proposed Voting Choices | + | ===== Vote ===== |
- | Yes/No, requiring a 2/3 majority. | + | This is a Yes/ |
+ | |||
+ | <doodle title=" | ||
+ | * Yes | ||
+ | * No | ||
+ | </ | ||
+ | |||
+ | ==== Poll: Reason for voting against this RFC ==== | ||
+ | |||
+ | <doodle title=" | ||
+ | * Object to the namespace choice | ||
+ | * Object to the name | ||
+ | * Object to the implementation | ||
+ | * Don't see a use case | ||
+ | * Other | ||
+ | </ | ||
===== References ===== | ===== References ===== | ||
* [[https:// | * [[https:// | ||
- | * [[rfc: | + | * [[rfc: |
+ | * https:// | ||
+ | * [[https:// | ||
===== Rejected Features ===== | ===== Rejected Features ===== | ||
+ | |||
+ | ==== Rejected: Alternative namespaces ==== | ||
+ | |||
+ | [[rfc: | ||
+ | |||
==== Rejected: ArrayAccess ==== | ==== Rejected: ArrayAccess ==== | ||
Line 361: | Line 387: | ||
==== Rejected: Lazy Evaluation ==== | ==== Rejected: Lazy Evaluation ==== | ||
- | '' | + | '' |
- | * Exceptions | + | * If this is generated from a data structure, the behavior may be unintuitive if the underlying data is modified while iterating over the sequence of keys and values if this were to be evaluated lazily instead of eagerly. |
+ | * Evaluating the entire iterable in the constructor ensures that exceptions | ||
* This is easier to understand, debug, serialize, and represent | * This is easier to understand, debug, serialize, and represent | ||
* If the underlying iterable (e.g. a Generator) has side effects, having those side effects take place immediately instead of being interleaved with other parts of the program may be easier to reason about. | * If the underlying iterable (e.g. a Generator) has side effects, having those side effects take place immediately instead of being interleaved with other parts of the program may be easier to reason about. | ||
* The majority of use cases of '' | * The majority of use cases of '' | ||
* Eagerly evaluating iterables reduces the memory needed by the implementation. The amount of memory needed to represent this is much lower (without the need to store the underlying iterable, potentially the most recent exception(s) thrown by the undlying iterable, etc). | * Eagerly evaluating iterables reduces the memory needed by the implementation. The amount of memory needed to represent this is much lower (without the need to store the underlying iterable, potentially the most recent exception(s) thrown by the undlying iterable, etc). | ||
+ | |||
The addition of an iterable library class that evaluates arguments on-demand is mentioned in the " | The addition of an iterable library class that evaluates arguments on-demand is mentioned in the " | ||
Line 387: | Line 415: | ||
to make code harder to understand. | to make code harder to understand. | ||
- | 4) It is possible to implement a lazy alternative to (ImmutableKeyValueSequence) that only loads values as needed. | + | 4) It is possible to implement a lazy alternative to (ImmutableIterable) that only loads values as needed. |
However, I hadn't proposed it due to doubts that 2/3 of voters would consider it widely useful | However, I hadn't proposed it due to doubts that 2/3 of voters would consider it widely useful | ||
enough to be included in php rather than as a userland or PECL library. | enough to be included in php rather than as a userland or PECL library. | ||
Line 435: | Line 463: | ||
* 0.2: Use optimized build with opcache enabled for benchmark timings | * 0.2: Use optimized build with opcache enabled for benchmark timings | ||
- | * 0.3: Rename from CachedIterable to ImmutableKeyValueSequence (the lack of clarity about the functionality associated with the name CachedIterable being eagerly evalulated was mentioned *after* most of the responses to the straw poll were already submitted) | + | * 0.3: Rename from '' |
+ | * 0.3.1: Add '' | ||
+ | * 0.4.0: Rename from '' | ||
rfc/cachediterable.txt · Last modified: 2021/06/29 14:24 by tandre