PHP SplStack vs SplQueue vs Array

[u/live627]

<?php

declare(strict_types=1);

namespace PhpBenchmarks;

use SplQueue;
use SplStack;

const NUM_TEST_ITEMS = 100_000;
const DATA_SIZE = 32; // Bytes.

/**
 * Runs a benchmark and reports the elapsed time.
 */
function benchmark(string $label, callable $operation): void
{
    echo 'Testing ' . $label . ' ... ';

    $start = hrtime(true);

    $operation();

    $elapsed = hrtime(true) - $start;

    echo number_format(NUM_TEST_ITEMS)
        . ' items in '
        . number_format($elapsed / 1_000_000_000, 6)
        . " seconds.\n";
}

/**
 * Generates the benchmark data.
 *
 * @return list<string>
 */
function generateData(): array
{
    $data = [];

    for ($i = 0; $i < NUM_TEST_ITEMS; ++$i) {
        $data[] = random_bytes(DATA_SIZE);
    }

    return $data;
}

$data = generateData();

// Stack push.
benchmark('SplStack (Push)', static function () use ($data): void {
    $stack = new SplStack();

    foreach ($data as $item) {
        $stack->push($item);
    }
});

benchmark('Array (Push)', static function () use ($data): void {
    $array = [];

    foreach ($data as $item) {
        $array[] = $item;
    }
});

echo "\n";

// Stack pop.
benchmark('SplStack (Pop)', static function () use ($data): void {
    $stack = new SplStack();

    foreach ($data as $item) {
        $stack->push($item);
    }

    for ($i = 0; $i < NUM_TEST_ITEMS; ++$i) {
        $stack->pop();
    }
});

benchmark('Array (Pop)', static function () use ($data): void {
    $array = $data;

    for ($i = 0; $i < NUM_TEST_ITEMS; ++$i) {
        array_pop($array);
    }
});

echo "\n";

// Queue push.
benchmark('SplQueue (Push)', static function () use ($data): void {
    $queue = new SplQueue();

    foreach ($data as $item) {
        $queue->enqueue($item);
    }
});

benchmark('Array (Push)', static function () use ($data): void {
    $array = [];

    foreach ($data as $item) {
        $array[] = $item;
    }
});

echo "\n";

$queue = new SplQueue();

foreach ($data as $item) {
    $queue->enqueue($item);
}

// Queue dequeue.
benchmark('SplQueue (Dequeue)', static function () use ($queue): void {
    for ($i = 0; $i < NUM_TEST_ITEMS; ++$i) {
        $queue->dequeue();
    }
});

benchmark('Array (Shift)', static function () use ($data): void {
    $array = $data;

    for ($i = 0; $i < NUM_TEST_ITEMS; ++$i) {
        array_shift($array);
    }
});

benchmark('Array (Null + Head)', static function () use ($data): void {
    $array = $data;
    $head = 0;

    for ($i = 0; $i < NUM_TEST_ITEMS; ++$i) {
        $item = $array[$head];
        $array[$head] = null;
        ++$head;
    }
});

My results on PHP 8.5:

Testing SplStack (Push) ... 100,000 items in 0.005546 seconds.

Testing Array (Push) ... 100,000 items in 0.001904 seconds.

Testing SplStack (Pop) ... 100,000 items in 0.007191 seconds.

Testing Array (Pop) ... 100,000 items in 0.003424 seconds.

Testing SplQueue (Push) ... 100,000 items in 0.005190 seconds.

Testing Array (Push) ... 100,000 items in 0.001699 seconds.

Testing SplQueue (Dequeue) ... 100,000 items in 0.003384 seconds.

Testing Array (Shift) ... 100,000 items in 4.463150 seconds.

Testing Array (Null + Head) ... 100,000 items in 0.002862 seconds.

That last one is from my own implementation.

Is there any point in using these data structures over an array? Could these data structures be further optimized by the PHP devs?

[u/birdspider]

apart from semantics (stack/queue vs array) they are more memory efficient

[u/Mastodont_XXX]

No one sane pays attention to these minor differences in the benchmarks. When do you actually work with a array that has 100,000 entries?

[u/obstreperous_troll]

SPL is nigh useless: try the DS extension, which has specializations for primitive types. It's not super-optimized even then, but it should be smaller and faster from having fewer zval allocations alone.

[u/mike_a_oc]

I feel like your stack pop test isn't fair, because you're including the time taken to populate the SPLStack as well as popping it. So in reality, the time taken could be much closer here.

Also:

Testing Array (Shift) ... 100,000 items in 4.463150 seconds.

That alone probably explains why these structures exist.

The head null method is interesting.

The other method I use something along the lines of;

krsort($array);

while (!empty($array)) {
   array_pop($array);
}

That might be worth benchmarking as well