Algorithms in PHP: Deques (circular buffers & linked lists)

In the previous post, I talked about priority queues. But in my explanation of an alternative implementation, I neglected to mention a few things:

1. The alternative implementation isn’t for production; there are edge cases and unhandled errors.
2. The alternative implementation is meant for a short queue, not an infinite one, such as the one you may deal with in a single request.
3. The performance of the alternative implementation may be misleading, in the worst case, it would perform far worse than the STL implementation. However, in my experience, priorities tend to bunch up vs. complete random priorities.

In this post, we’re going to go into Deques (pronounced “decks”), how they are usually implemented, and an alternative implementation that is specific to PHP. If you aren’t aware, PHP is getting a native Deque implementation in 8.2. A Deque is a double-ended queue that you can insert and remove from either end.

Deques are extremely powerful anytime you require a “queue of a bounded length” where the older items are dropped (like an undo buffer). However, this is one of those things where you really shouldn’t implement this in native PHP. STL Queues and Stacks can be used as a Deque and perform far better than anything you can implement in PHP. The reason for this should be evident if you’ve ever tried to prepend to an array; it is slow and gets slower the more items you add to the array.

A naive implementation

A naive PHP implementation of a Deque would probably look something like this:

<?php

namespace Withinboredom\Algorithms\Deque;

class Naive
{
    private array $buffer = [];

    /**
     * Append to the end
     *
     * @param mixed $value
     *
     * @return void
     */
    public function push(mixed $value): void
    {
        array_push($this->buffer, $value);
    }

    /**
     * Get from the end of the array
     * @return mixed
     */
    public function pop(): mixed
    {
        return array_pop($this->buffer);
    }

    /**
     * Get from the beginning
     * @return mixed
     */
    public function shift(): mixed
    {
        return array_shift($this->buffer);
    }

    /**
     * Append to the beginning
     *
     * @param mixed $value
     *
     * @return void
     */
    public function unshift(mixed $value): void
    {
        array_unshift($this->buffer, $value);
    }
}

This naive implementation is so bad that I wouldn’t use it unless I dealt with less than a few dozen items. Here’s a chart of how bad it gets as the number of items gets larger:

Deques using circular buffers

Highly performant Deques use circular buffers to accomplish their goals, along with sophisticated logic to automatically grow and shrink the buffers to allow for an infinite number of items. You can imagine a circular buffer as being a clock-type structure. If you were to insert 12 items, it would look like a clock. For a Deque, we’d want two “pointers” to represent the “head” and the “tail” of our Deque, much like the hands on a clock.

We’ll imagine the hour hand to be our “head” and the minute hand to be our “tail” while discussing insertions and deletions. To prepend, we move the hour hand back and insert our new value. To append, we move the minute hand forward and insert our value. To remove from the head, we take the value from the hour hand and move it forward. To remove the tail, we take the value from the minute hand and move it backward.

We aren’t going to cover growing or shrinking circular buffers here to keep it simple.

So, let’s build our class:

<?php

namespace Withinboredom\Algorithms\Deque;

class CircularBuffer
{
    private array $buffer = [];
    private int $head = -1;
    private int $tail = 0;

    public function __construct(private int $size)
    {
    }
}

First thing, we need a buffer to store items in, a head/tail pointer, and a max-size of the buffer. The reason for the strange head/tail initial values is to give us an easy way to tell whether we’re inserting an initial value or whether or not the buffer is full. Here’s how that works:

    public function isFull(): bool
    {
        return ($this->head === 0 && $this->tail === $this->size - 1) || $this->head === $this->tail + 1;
    }

    public function isEmpty(): bool
    {
        return $this->head === -1;
    }

Push

To push onto the buffer, we need to handle several states:

    public function push(mixed $value): void
    {
        if ($this->isFull()) {
            throw new \Exception();
        }

        if ($this->head === -1) {
            $this->head = 0;
            $this->tail = 0;
        } elseif ($this->tail === $this->size - 1) {
            $this->tail = 0;just a tiny
        } else {
            $this->tail += 1;
        }
        $this->buffer[$this->tail] = $value;
    }

1. our initial state
2. wrapping around the circular buffer
3. appending normally

Pop

To pop, we also need to handle several states:

    public function pop(): mixed
    {
        if ($this->isEmpty()) {
            throw new \Exception();
        }

        $return = $this->buffer[$this->tail];

        if ($this->head === $this->tail) {
            $this->head -= 1;
            $this->tail -= 1;
        } elseif ($this->tail === 0) {
            $this->tail = $this->size - 1;
        } else {
            $this->tail -= 1;
        }

        return $return;
    }

1. when the buffer is full
2. wrapping around the circular buffer
3. popping normally

Shift and Unshift

Shifting and unshifting are handled the same, but in reverse:

    public function shift(): mixed
    {
        if ($this->isEmpty()) {
            throw new \Exception();
        }

        $return = $this->buffer[$this->head];

        if ($this->head === $this->tail) {
            $this->head -= 1;
            $this->tail -= 1;
        } elseif ($this->head === $this->size - 1) {
            $this->head = 0;
        } else {
            $this->head += 1;
        }

        return $return;
    }

    public function unshift(mixed $value): void
    {
        if ($this->isFull()) {
            throw new \Exception();
        }

        if ($this->head === -1) {
            $this->head = 0;
            $this->tail = 0;
        } elseif ($this->head === 0) {
            $this->head = $this->size - 1;
        } else {
            $this->head -= 1;
        }
        $this->buffer[$this->head] = $value;
    }

The downside to this implementation is that a pre-determined size limits it, however, it is still pretty performant:

It’s a bit slower than the STL implementation (~86 vs. ~50 microseconds with a list size of 2,000). There are still several things to implement even to be close to being on par with the STL implementation:

• ArrayAccess to access arbitrary elements
• Growing/shrinking the circular buffer

Linked Lists

Another potential possibility to traditionally implement a Deque is to use a doubly linked list. To accomplish that, we’ll need a “Node” class to represent each item in the list:

<?php

namespace Withinboredom\Algorithms\Deque;

class Node
{
    public function __construct(public Node|null $previous, public Node|null $next, public mixed $value)
    {
    }
}

We can also add a few helpful behaviors: setNext(), setPrevious(), resetNext(), resetPrevious(), removeMeNext() and removeMePrevious().

setNext() and setPrevious() set the $next/$previous variable and return $this:

    public function setNext(Node $next): Node
    {
        $this->next = $next;
        return $this;
    }

    public function setPrevious(Node $previous): Node
    {
        $this->previous = $previous;
        return $this;
    }

resetNext() and resetPrevious() both unset next/previous:

    public function resetPrevious(): Node
    {
        $this->previous = null;
        return $this;
    }

    public function resetNext(): Node
    {
        $this->next = null;
        return $this;
    }

removeMeNext() and removeMePrevious() deletes itself from the chain and returns the next/previous Node:

    public function removeMeNext(): Node|null
    {
        $return = $this->next?->resetPrevious();
        $this->resetNext();
        return $return;
    }

    public function removeMePrevious(): Node|null
    {
        $return = $this->previous?->resetNext();
        $this->resetPrevious();
        return $return;
    }

From there, the operations a pretty straightforward:

class LinkedList
{
    public Node|null $head = null;
    public Node|null $tail = null;

    /**
     * Append to the tail
     *
     * @param mixed $value
     * @return void
     */
    public function push(mixed $value): void
    {
        $this->tail =
            $this->tail?->setNext(new Node($this->tail, null, $value))->next
            ?? $this->head = new Node(null, null, $value);
    }

    /**
     * Get from the end of the array
     *
     * @return mixed
     */
    public function pop(): mixed
    {
        $return = $this->tail?->value ?? throw new \Exception();
        $this->tail = $this->tail->removeMePrevious();
        return $return;
    }

    /**
     * Prepend
     *
     * @return mixed
     */
    public function unshift(mixed $value): void
    {
        $this->head =
            $this->head?->setPrevious(new Node(null, $this->head, $value))->previous
            ?? $this->tail = new Node(null, $this, $value);
    }

    /**
     * Get from the beginning of the array
     *
     * @return mixed
     */
    public function shift(): mixed
    {
        $return = $this->head?->value ?? throw new \Exception();
        $this->head = $this->head->removeMeNext();
        return $return;
    }
}

The performance is linear, just like before:

However, it still performs worse than a circular buffer or any STL implementation.

Php Specific implementation

If you’ve had to work extensively with PHP arrays, you’d probably guess why the naive implementation is so terrible. It’s not that bad, as long as you never unshift the array. Shifting/unshifting to a PHP array has terrible performance implications and should be avoided as much as possible. If you a bulk-prepending, it is usually faster to reverse the array, append your values, then flip the array again.

To avoid prepending to an array, we will use two arrays and only append to them. We’ll call these arrays “front” and “back”; appending to the “front” array is like prepending, and appending to the “back” array is just like regular appending. We pull from the end of each array to take from the “front” and “back,” respectively. Once the appropriate array is empty, we shift from the beginning of the other array until it is empty, which is still incredibly performant.

This implementation is really for when you need something custom, and the other types of algorithms wouldn’t work.

<?php

namespace Withinboredom\Algorithms\Deque;

class DoubleList
{
    private array $front = [];
    private array $back = [];
}

To prepend, we append to $front, and to append; we append to $back:

    public function unshift(mixed $value): void
    {
        $this->front[] = $value;
    }

    public function push(mixed $value): void
    {
        $this->back[] = $value;
    }

When we pop, we check to see if $back is empty; if it is, we take it from the start of $front. Otherwise, we take it from the back of $back:

    public function pop(): mixed
    {
        if (empty($this->back)) {
            // take the first item from the front and remove the item
            return array_shift($this->front);
        }
        return array_pop($this->back);
    }

We similarly do the reverse for the shift:

    public function shift(): mixed
    {
        if (empty($this->front)) {
            // take the first item from the back and remove the item
            return array_shift($this->back);
        }
        return array_pop($this->front);
    }

This allows us to get around prepending by appending, almost as performant as the circular buffer implementation.

STL and when to use it

The STL implementations of Stacks and Queues can be used as Deque. Their performance (wall-clock time) will beat the crap out of these implementations; alternatively, if you are targeting PHP 8.2+, using the native Deque would be an even better solution — though we don’t know what that performance will look like yet.

For 99% of cases, you won’t need to implement your own Deque or any other basic algorithms. However, there are times when implementing your own can allow more business freedoms. For example, Beanstalkd implements its Priority Queue to do some things, such as removing items from the middle of the queue and adding a TTL for jobs. WordPress implements its Priority Queue (actions/filters) to support removal/insertion while iterating the queue and preventing infinite loops. Many other projects also end up embedding certain logic into these algorithms to support business logic in a performant way.

DS\Deque

There’s also the DS\Deque class, which is a proper Deque implementation; however, it requires being installed separately and does not come bundled with PHP. It is a little faster than using the STL libraries as a Deque. If you are looking for raw speed, this is the one you’re looking for.

When to use these algorithms

As I mentioned, sometimes you need to implement low-level algorithms to support high-performance business cases. It’s unlikely, but knowing how they work and some PHP-specific implementations can significantly impact when it matters.