Typed arrays — Manticore\Ds

Fixed-width, statically typed arrays over one native buffer. A PHP array stores every element as a tagged cell behind a hash/vector buffer; a Manticore\Ds array stores elements at their declared width in one contiguous block and reads them back as int, float or bool.

This is a superset feature: Zend has no such classes. The same source ships as a pure-PHP polyfill (below), so a program using them still runs under php.

use Manticore\Ds\Int32Array;

$offsets = new Int32Array(1024);
$offsets[0] = 17;
$offsets->insert(1, 2, -1);          // open two slots holding -1 before index 1
echo $offsets[0] + $offsets[1];      // 16

Classes#

All are final and extend Manticore\Ds\TypedArray, which implements ArrayAccess, Countable, IteratorAggregate and JsonSerializable.

There is no typed string array.

API#

Appending is amortised O(1) (capacity doubles); an insert or removal in the middle is one memmove of the tail.

Cost#

$a[$i] and $a[$i] = $v on a typed array held in a local compile to a bounds test plus one load / store of the element width — no call, no boxing. A 10M-iteration $a[$i] = $a[$i] + 1 loop over Int32Array runs about 4x faster than the same loop over a PHP array<int, int> (12 ms vs 47 ms, arm64 macOS). An index out of range, or a value outside a narrow kind's range, leaves the inline path and throws from the method.

Semantics#

Index — as SplFixedArray: an int; a canonical integer string ("12"), a float or a bool is converted; anything else is a TypeError("Cannot access offset of type <t> on <Class>"). Out of range is an OutOfBoundsException("Index invalid or out of range"). $a[] = $v appends; a value that fails the element rules throws and leaves the size alone.

Value — converted like a non-strict typed parameter, and never wrapped silently:

• int kinds take an int, a bool, an integral float (3.0), or a numeric string naming an integer ("12", "1e2"). A fractional float, a non-numeric string, null, an array or an object is a TypeError. A value outside the element range is a ValueError("Value 300 is out of range for Int8Array (-128..127)").
• float kinds take a float, an int, a bool or a numeric string. Float32Array stores the value rounded to binary32 (ties to even) and a read returns the rounded value: 0.1 reads back as 0.10000000149011612; a magnitude past the binary32 range stores INF.
• BitArray takes any scalar and stores its truthiness.

indexOf() answers -1 for a value outside the element range and throws the same TypeError as a store for a value of the wrong type.

isset / unset — a fixed-width slot cannot be absent: isset($a[$i]) is true for every in-range index, and unset($a[$i]) zeroes the element (0 / 0.0 / false).

Copies — an array is an object: assignment shares it, clone copies the buffer.

Dumps and serialization — var_dump, print_r, serialize / unserialize and json_encode (through jsonSerialize()) present the array as the list toArray() returns.

UInt64Array#

PHP has no unsigned 64-bit int, so a UInt64Array element reads as the int with the same 64 bits: a value of 2^63 or more reads negative. An int writes its bits, so $a[$i] = $a[$j] copies any value and hashes, masks and ids round-trip untouched. A numeric string or a float is a value:

$h = new UInt64Array(2);
$h[0] = '18446744073709551615';   // reads as -1
$h[1] = 2 ** 63;                  // reads as PHP_INT_MIN
echo $h->getString(0);            // 18446744073709551615
echo UInt64Array::toDecimal($h->max());

• min(), max() and UInt64Array::compare(int $a, int $b): int order unsigned; sum() wraps modulo 2^64.
• getString(int $index): string and UInt64Array::toDecimal(int $bits): string give the unsigned decimal value.
• A string or float outside 0..18446744073709551615 ('-1', 2.0 ** 64) is a ValueError; a fractional float is a TypeError.
• UInt64Array<T> takes a #[TypeDef(repr: 'u64')]; an i64 TypeDef does not fit, nor does a u64 one fit an Int64Array.

• JSON writes the value, not the bits. JSON numbers have no width, so json_encode($h) gives [18446744073709551615, …] — what a Go, Rust or JS-BigInt consumer expects. toArray(), var_dump(), print_r() and serialize() stay on bits (the in-program contract). The lossless way back is JSON_BIGINT_AS_STRING, whose decimal strings fromArray() accepts:

  $back = UInt64Array::fromArray(json_decode($json, true, 512, JSON_BIGINT_AS_STRING));

  Copy

  Without the flag, php decodes a value past PHP_INT_MAX as a float, which fromArray() accepts only when it is exact. Under Zend (the polyfill) the large values encode as quoted strings — nothing there can write them bare.

ByteBuffer#

A ByteBuffer is a typed array of bytes (0..255, as UInt8Array; a class of its own) — every method above works on it, $b[$i] is one byte — with typed reads and writes at a byte offset:

use Manticore\Ds\ByteBuffer;

$b = ByteBuffer::fromString($packet);
$length = $b->getUInt16(2, true);        // big-endian (network order)
$stamp  = $b->getInt64(4);               // little-endian by default
$b->setFloat32(12, 0.5);
$b->write(16, "tail");
fwrite($sock, $b->toString());

An access that runs past the end is an OutOfBoundsException("Index invalid or out of range"); nothing grows the buffer but setSize, push and $b[] = $byte. A typed read costs about 5 ns — the same as composing the value from ord() calls by hand, and some 60 times less than unpack() at an offset.

#[TypeDef] and typed arrays#

The repr set of #[TypeDef] (i8 … i64, u8 … u32, f32, f64) is the same set of machine widths, and a typed array can be bound to such a class: the element is stored at the array's width and read back AS the class — the same scalar, named, with its methods.

#[TypeDef(repr: 'u16')]
final class TokenKind
{
    public function __construct(public readonly int $value) {}
    public function isComment(): bool { return $this->value === 7 || $this->value === 8; }
}

final class Tokens
{
    /** @var UInt16Array<TokenKind> */
    public UInt16Array $kinds;
}

/** @var UInt16Array<TokenKind> $kinds */
$kinds = new UInt16Array($n);
$kinds[$i] = new TokenKind(7);        // a 2-byte store; no object exists
if ($kinds[$i]->isComment()) { … }    // a 2-byte load and a direct call
$last = $kinds->pop();                // a TokenKind

The binding is written in a docblock (@var on a local or a property, @param, @return), like every other generic. It costs nothing at run time: get_class($kinds) is still Manticore\Ds\UInt16Array. An array with no binding reads plain int / float, as before. foreach over a bound array still yields the plain scalar.

Map, Set, Vec#

Insertion-ordered containers over native tables (Map, Set) and a native buffer of boxed values (Vec). Unlike a PHP array the keys are strict.

use Manticore\Ds\{Map, Set, Vec};

$m = new Map();
$m->set('a', 1);
$m[2] = 'two';                 // int and string keys stay distinct: "2" !== 2
$m->set($obj, 'by identity');  // an object is a key
foreach ($m as $k => $v) { … } // insertion order

$m[] = $v is an Error("Cannot append to a Map; use set()").

unset($v[$i]) is an Error("Cannot unset a Vec element; use pop()").

Keys (Map, Set) — int, string or object. "1" and 1 are different keys; an object is its own key by identity. Anything else (float, bool, null, array) is a TypeError("Cannot use a key of type <t> in Map") (... in Set).

Order — iteration is insertion order. remove + re-insert moves the key to the end. Removing during foreach is fine. A compaction (triggered by an insert) or clear() during foreach throws RuntimeException("Map modified during iteration") / ("Set modified during iteration"). Vec iteration has no guard: it re-reads the length every step.

toArray() / JSON — Map::toArray() throws ValueError("Map::toArray(): keys collide in a PHP array") when 1 and "1" are both keys, and TypeError("Map::toArray(): object keys cannot be array keys") for an object key. json_encode($map) goes through (object) toArray(), so it is always an object ({} when empty). Set and Vec encode as JSON lists. var_dump / print_r show the entries (Map: a list of [key, value] pairs); serialize round-trips all three.

Copies — assignment shares, clone copies the table (shallow: keys and values are retained, not cloned).

Cycles — a cycle through a Map / Set / Vec ($m->set('self', $m)) is collected natively by gc_collect_cycles(). Under the Zend polyfill it is not (the buffers live in a static registry).

Callbacks#

Map, Set and Vec take each, map, filter, reduce, any, all and find. Callbacks get ($value, $key) (Set: ($value)); reduce gets ($carry, $value, $key) and an explicit initial value. map / filter return a new container of the same kind.

$total = $m->reduce(fn($c, $v) => $c + $v, 0);   // fused

A closure literal passed directly to one of these is fused into a loop at compile time (no closure call per element) when all hold: it is a literal (not a variable), captures nothing, its parameters are untyped, it has no return type, its body is safe to splice, and the receiver is statically a Map / Set / Vec. Anything else (a $f variable, typed parameters or a return type, a use capture, an untyped receiver) is called per element: correct, slower. An exception thrown inside a fused callback has no {closure} frame in its getTrace().

• find returns null when nothing matches, indistinguishable from a stored null match. Use any or has when that matters.
• A callback must not mutate the container it walks (the foreach rule).

foreach and the fast path#

foreach over a Map / Set / Vec is native: it walks the table directly, no iterator object. The mutation rule is the one under Order above.

• foreach over a null subject walks nothing.
• foreach ($m as &$v) throws the generator by-reference Exception (Zend's message); there is no by-ref walk.

Typed keys take the fast path with no annotation: the static type of the key operand (int, string, object) selects a specialised hash / compare inline; an untyped key goes through the generic path. The strict-key rule holds on both, including a bound map (/** @var Map<string,int> $m */): a wrong-typed key is the same TypeError.

Cost#

1,000,000 insert + lookup + remove, median of 5 runs per row, arm64 macOS (tools/bench/ds_map_bench.php). P1 was erased (a method call per operation); P2 specialises keys, inlines lookups and walks natively.

Run back to back (not interleaved) on a shared machine. The P1 column is from P1's own run. The three insert/lookup/remove rows are from a quiet run; a later run under load (other jobs running) scattered them by up to 40% but kept the ordering.

Map<string,int> (270 vs 284 ms, -5%) and Set<object> (93 vs 99, -6%) are at or below the array idiom, Map<int,int> (85 vs 82, +4%) just above: all three are parity within the run-to-run scatter. The remaining Map<int,int> gap is insert-miss cost: index growth and rehash, first-touch page faults, and entry dereferences on a miss probe. A hash tag in the index slot would remove the dereferences; that is a layout change, deferred.

Known open issues#

• #137: a bound V (Map<string,int>) is a static claim; a stored value that does not fit V is reinterpreted when read back.
• #140: by-ref foreach over a by-value Generator iterates instead of throwing (the Map case throws correctly).
• #143, #144, #145: general throw-path leaks (method-argument receiver, assignment RHS target, temporary call argument), visible through a map / reduce callback that throws (memory only; semantics are right).

Polyfill#

The classes are ordinary PHP (prelude/ds.php, prelude/ds_map.php) over a small set of buffer and table primitives. Natively those primitives are compiler builtins; under Zend they are PHP functions that keep each buffer in a PHP array. Both are generated from the same files, so the polyfill behaves identically by construction — it is the oracle the native implementation is tested against.

php tools/ds_polyfill.php            # writes build/ds-polyfill (composer package manticorephp/ds)

A program that requires the package's src/bootstrap.php (or installs it through Composer) runs unchanged under php and under the compiler; natively the bootstrap is a no-op because the classes are built in.

The polyfill is for portability, not speed: under Zend an element costs what a PHP array element costs. Map / Set / Vec keep their buffers in a static registry, so a cycle through one is not collected under Zend.

Current limits#

• The inline path needs a receiver held in a local variable, a property of a local, or a static property, an int index built from locals / constants / + -, and (for a store) a value of the element's own type with no call in it. Anything else is an ordinary offsetGet / offsetSet call — correct, slower.
• A #[TypeDef] binding covers the scalar reprs only; enum-backed ints and packed structs as elements are not supported yet.

Edit this page on GitHub