Significant speed improvements by using implode instead of string concat

[JohnathanWTF]

I was looking at the generated files from Mustache.php which it outputs to the cache folder. Inside these files I noticed that the result is produced using successive string concatenations, i.e.:

$buffer = '';
$buffer .= $value;
$buffer .= $value;
$buffer .= $value;
return $buffer;

I've done some speed tests and found it can execute up to 50% faster by imploding an array instead, i.e.:

$buffer = [];
$buffer[] = $value;
$buffer[] = $value;
$buffer[] = $value;
return implode('',$buffer);

The amount of gain is dependent on the size and complexity of the template. For simple templates with very short strings it doesn't make much difference, but for templates with a large number of concats or long strings then the speed improvement is noticeable.

I'd like to suggest that Mustache.php is updated to to use implode instead of concat for this reason.

Below is a simple PHP speed test which I used to compare the timings of the two methods. The results vary based on the number and length of strings concated/imploded, but I've found that implode is faster in almost all scenarios.

<?php

$shortString = 'short';
$medString = 'This is a medium length string';
$longString = 'This string is intentionally long for testing purposes. How long should it be, how long is long enough? How long is a piece of string?';

function concatTest($string)
{
    $output = '';
    for ($i = 0; $i < 50; $i++)
        $output .= $string;
    return $output;
}

function implodeTest($string)
{
    $output = [];
    for ($i = 0; $i < 50; $i++)
        $output[] = $string;
    return implode('',$output);
}

$start = microtime(true);
$results = [];
for ($i = 0; $i < 10000; $i++)
    $results[] = implodeTest($medString);
$time_elapsed_secs = microtime(true) - $start;
echo 'implode: ' . $time_elapsed_secs . ' seconds<br>';

$start = microtime(true);
$results = [];
for ($i = 0; $i < 10000; $i++)
    $results[] = concatTest($medString);
$time_elapsed_secs = microtime(true) - $start;
echo 'concat: ' . $time_elapsed_secs . ' seconds<br>';

As a side note, there could also be speed improvements if there was an option to ignore indentations (i.e. exclude the '$indent' variable) in the generated PHP code.

[bobthecow]

Thanks for taking the time to look at this and write it up!

I mean this in the best possible way: it literally doesn't matter how we concatenate strings 😉

I ran your benchmark against a bunch of versions of PHP, and got wildly different results:

Output for 8.3.9 | released 2024-07-04 | took 58 ms, 26.77 MiB
implode short string:  0.0022540092468262 seconds
implode med string:    0.0024290084838867 seconds
implode long string:   0.0054459571838379 seconds
concat short string:   0.0024230480194092 seconds
concat med string:     0.0022139549255371 seconds
concat long string:    0.0058000087738037 seconds

Output for 5.3.29 | released 2014-08-14 | took 69 ms, 26.77 MiB
implode short string:  0.017403125762939 seconds
implode med string:    0.015048027038574 seconds
implode long string:   0.014576196670532 seconds
concat short string:   0.003169059753418 seconds
concat med string:     0.0047581195831299 seconds
concat long string:    0.005824089050293 seconds

Full results here:

``` Output for 8.3.9 | released 2024-07-04 | took 58 ms, 26.77 MiB implode short string: 0.0022540092468262 seconds implode med string: 0.0024290084838867 seconds implode long string: 0.0054459571838379 seconds concat short string: 0.0024230480194092 seconds concat med string: 0.0022139549255371 seconds concat long string: 0.0058000087738037 seconds Output for 8.2.21 | released 2024-07-04 | took 50 ms, 27.94 MiB implode short string: 0.0023789405822754 seconds implode med string: 0.0023479461669922 seconds implode long string: 0.0033318996429443 seconds concat short string: 0.0020618438720703 seconds concat med string: 0.0021650791168213 seconds concat long string: 0.0074000358581543 seconds Output for 8.1.29 | released 2024-06-06 | took 52 ms, 26.77 MiB implode short string: 0.0023021697998047 seconds implode med string: 0.0023679733276367 seconds implode long string: 0.0034539699554443 seconds concat short string: 0.0021388530731201 seconds concat med string: 0.0021960735321045 seconds concat long string: 0.0062639713287354 seconds Output for 8.0.30 | released 2023-08-03 | took 72 ms, 26.77 MiB implode short string: 0.0052909851074219 seconds implode med string: 0.004770040512085 seconds implode long string: 0.015379190444946 seconds concat short string: 0.0027861595153809 seconds concat med string: 0.0022389888763428 seconds concat long string: 0.0038669109344482 seconds Output for 7.4.33 | released 2022-11-03 | took 54 ms, 26.77 MiB implode short string: 0.0026350021362305 seconds implode med string: 0.0025701522827148 seconds implode long string: 0.0076498985290527 seconds concat short string: 0.0026791095733643 seconds concat med string: 0.0023548603057861 seconds concat long string: 0.007066011428833 seconds Output for 7.3.33 | released 2021-11-18 | took 64 ms, 26.77 MiB implode short string: 0.0025398731231689 seconds implode med string: 0.0040409564971924 seconds implode long string: 0.012350082397461 seconds concat short string: 0.00301194190979 seconds concat med string: 0.0019941329956055 seconds concat long string: 0.0030331611633301 seconds Output for 7.2.34 | released 2020-10-01 | took 56 ms, 26.77 MiB implode short string: 0.0030338764190674 seconds implode med string: 0.0031788349151611 seconds implode long string: 0.0065069198608398 seconds concat short string: 0.0037100315093994 seconds concat med string: 0.0032248497009277 seconds concat long string: 0.0064640045166016 seconds Output for 7.1.33 | released 2019-10-24 | took 51 ms, 26.97 MiB implode short string: 0.0032191276550293 seconds implode med string: 0.0033481121063232 seconds implode long string: 0.0082428455352783 seconds concat short string: 0.0032341480255127 seconds concat med string: 0.0031468868255615 seconds concat long string: 0.0041928291320801 seconds Output for 7.0.33 | released 2018-12-06 | took 49 ms, 26.81 MiB implode short string: 0.0043280124664307 seconds implode med string: 0.0046901702880859 seconds implode long string: 0.0055379867553711 seconds concat short string: 0.0038402080535889 seconds concat med string: 0.0037031173706055 seconds concat long string: 0.0044970512390137 seconds Output for 5.6.40 | released 2019-01-10 | took 80 ms, 26.77 MiB implode short string: 0.0096168518066406 seconds implode med string: 0.011432886123657 seconds implode long string: 0.012564897537231 seconds concat short string: 0.0026910305023193 seconds concat med string: 0.0027790069580078 seconds concat long string: 0.0054049491882324 seconds Output for 5.5.38 | released 2016-07-21 | took 74 ms, 26.77 MiB implode short string: 0.0088880062103271 seconds implode med string: 0.011152029037476 seconds implode long string: 0.017924785614014 seconds concat short string: 0.0048229694366455 seconds concat med string: 0.0030980110168457 seconds concat long string: 0.0034852027893066 seconds Output for 5.4.45 | released 2015-09-03 | took 67 ms, 26.77 MiB implode short string: 0.013075113296509 seconds implode med string: 0.012278079986572 seconds implode long string: 0.011571884155273 seconds concat short string: 0.0025660991668701 seconds concat med string: 0.0024619102478027 seconds concat long string: 0.0035378932952881 seconds Output for 5.3.29 | released 2014-08-14 | took 69 ms, 26.77 MiB implode short string: 0.017403125762939 seconds implode med string: 0.015048027038574 seconds implode long string: 0.014576196670532 seconds concat short string: 0.003169059753418 seconds concat med string: 0.0047581195831299 seconds concat long string: 0.005824089050293 seconds Output for 5.2.17 | released 2011-01-06 | took 79 ms, 26.77 MiB implode short string: 0.017266035079956 seconds implode med string: 0.013957023620605 seconds implode long string: 0.016580104827881 seconds concat short string: 0.0035641193389893 seconds concat med string: 0.0036389827728271 seconds concat long string: 0.0048739910125732 seconds ```

If you notice, until fairly recently, it was 3-5x slower to implode, per your benchmark!

But even if we optimize only for the most recent couple of versions of PHP, the variation between versions—or even successive runs—is more than the savings on the best possible runs. Check out that PHP 8.3 at the top. Implode was 0.4ms faster in the best possible case, and exactly the same on the more likely case.

Without real world benchmarks, it's hard to say exactly what performance characteristics would look like, but if we tweak the number of chunks a bit, things get even worse for implode. At 10 string chunks, implode performance is worse across the board in PHP 8.3:

implode short string:  0.00056195259094238 seconds
implode med string:    0.0006868839263916 seconds
implode long string:   0.001615047454834 seconds
concat short string:   0.0005338191986084 seconds
concat med string:     0.00057816505432129 seconds
concat long string:    0.00092005729675293 seconds

But! Even these numbers are close enough that trying to optimize them isn't all that compelling. The best I can say is sometimes one is slightly faster, sometimes the other is, but it's almost always a tie.

My intuition (and experience) is that we'll get a lot more bang for the buck from algorithmic changes than string concatenation optimization 😛

[JohnathanWTF]

Strange, I had very different results. Perhaps it's different across various system architectures.

Any thanks for the thorough reply, I appreciate you looking into it! :)