Multi-threaded quicksort! In PHP!

Yeah! In PHP!

Why would you do this?

Well, I went to a PHP meetup presenting some common implementations and comparing them to the speedy native PHP implementation of sort() and related functions.

I figured that while efficient sorting isn’t the most common use case for PHP – and in a web context you often don’t want to let each user spin up numerous threads – for command line cases this approach should be able to provide a real performance boost.

In particular, the already-PHP-favoured quicksort algorithm works with a divide and conquer approach that should be perfectly suited to divvying up work between threads.

Like all great half-formed ideas, the impetus to actually try this out was brought on by insomnia. The results were (forgive me, clickbait pioneers)… underwhelming.

Most of the info on why is summed up on the GitHub repository for my experiment, but the headline is that while threads seem to help my method very marginally, it’s not enough to stop it being 100 times slower than PHP’s approach, for 1-million item arrays.

I went for a Promise abstraction from ReactPHP (confusingly, no relation to React).

My main questions so far (detailed further on GitHub) are:

  • Was this library the right choice for threads here?
  • Is there something obvious we could steal from PHP’s own logic to make this better? And
  • Is my pivot choice stupid?

Pull requests welcome!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.