[10.x] Improve `Arr::dot` performance #49386

bastien-phi · 2023-12-15T08:05:28Z

Re submission of #49380 by @comes

Original description :

This PR improves the speed of Arr::dot() by using the array union operator instead of the slower array_merge

The reason why we can use the union operator here is, that an array always has unique keys.

the + operator will only add the elements of the right side operand, if their key doesn't exist in the leftside operand, while array_merge will override existing keys.

see https://stitcher.io/blog/array-merge-vs+

But this is not a problem here, because, as I already noticed, the keys in an array are unique.

I've attached some benchmarks running the current Arr::dot() implementation agains my new implementation. As you can see, the new implementation solves a significant runtime issue.
Items: 100
old Arr::dot: 0.0003 seconds / 20.00 memory
new Arr::dot: 0.0001 seconds / 20.00 memory


Items: 1000
old Arr::dot: 0.0218 seconds / 22.00 memory
new Arr::dot: 0.0010 seconds / 24.00 memory


Items: 10000
old Arr::dot: 3.5038 seconds / 46.00 memory
new Arr::dot: 0.0129 seconds / 48.50 memory


Items: 15000
old Arr::dot: 10.4789 seconds / 64.00 memory
new Arr::dot: 0.0155 seconds / 68.50 memory
for futher information about the union operator see: https://www.php.net/manual/en/language.operators.array.php

~~I don't add my benchmark results as they are similar to the original ones~~

After some tweak and suggestions (thanks @donnysim and @comes), heres an updated version of the benchmark.

Items: 100
original Arr::dot: 0.0003 seconds / 40.50 memory
new Arr::dot: 0.0002 seconds / 40.50 memory
Items: 1000
original Arr::dot: 0.0213 seconds / 42.50 memory
new Arr::dot: 0.0016 seconds / 42.50 memory
Items: 10000
original Arr::dot: 5.0146 seconds / 68.50 memory
new Arr::dot: 0.0201 seconds / 72.50 memory
Items: 15000
original Arr::dot: 12.8689 seconds / 100.50 memory
new Arr::dot: 0.0272 seconds / 97.50 memory

Note : do not compare with original benchmark, it was not run on the same machine

I also updated the tests with assertSame instead of assertEquals to ensure that the order of the arrays are respected.

jbrooksuk · 2023-12-15T08:09:43Z

I think it'd be useful to prove that this PR doesn't change existing behaviour, with an additional test.

bastien-phi · 2023-12-15T08:16:15Z

@jbrooksuk I guessed that existing tests were enough but I added some based on Arr::undot tests

comes · 2023-12-15T08:20:15Z

@bastien-phi, I appreciate your support here.

I've attached my script to reproduce the results with an unmodified version of laravel.

class ArrDotBench extends Command
{
    protected $signature = 'dot:bench';

    public function handle(): void
    {
        foreach ([100, 1_000, 10_000, 15_000] as $itemCount) {
            $data = $this->data($itemCount);

            $this->framework($data);
            $this->newdot($data);
        }

    }

    protected function data(int $itemCount): array
    {
        $subset = [];
        for ($i=0; $i < $itemCount; $i++) {
            $subset[] = [
                'id' => $i,
                'name' => 'Name ' . $i,
                'email' => 'email' . $i . '@example.com',
                'date' => now()->addDays($i)->format('Y-m-d'),
                'another_sub_array' => [
                    'street' => 'Street ' . $i,
                    'city' => 'City ' . $i,
                    'country' => 'Country ' . $i,
                ],
            ];
        }

        $data = ['items' => $subset];

        $this->info('Items: ' . count($data['items']));

        return $data;
    }

    protected function framework(array $data): array
    {
        $start = $this->start();

        $dottedArr = Arr::dot($data);

        $this->finish('framework dot', $start);

        return $dottedArr;
    }

    protected function newdot(array $data): array
    {
        $start = $this->start();

        $dottedArr = $this->fastdot($data);

        $this->finish('fastdot', $start);

        return $dottedArr;
    }

    protected function start(): float
    {
        memory_reset_peak_usage();

        return microtime(true);
    }

    protected function finish(string $title, float $start): void
    {
        $this->info(sprintf($title . ': %.4f seconds / %.2f memory', microtime(true) - $start, memory_get_peak_usage(true) / 1024 / 1024)).PHP_EOL;
    }

    public static function fastdot($array, $prepend = '')
    {
        $results = [];

        foreach ($array as $key => $value) {
            if (is_array($value) && !empty($value)) {
                $results += static::fastdot($value, $prepend . $key . ".");
            } else {
                $results[$prepend . $key] = $value;
            }
        };

        return $results;
    }
}

donnysim · 2023-12-15T09:05:25Z

You can also do the usual array_merge spread, which is a fraction slower than the union operator, but at a way lower memory cost:

    public function spread($array, $prepend = '')
    {
        $results = [[]];

        foreach ($array as $key => $value) {

            if (is_array($value) && !empty($value)) {
                $results[] = $this->spread($value, $prepend . $key . '.');
            } else {
                $results[0][$prepend . $key] = $value;
            }
        }

        return array_merge(...$results);
    }

out based on @comes bench:

Items: 100
framework dot: 0.0007 seconds / 32.00 memory
fastdot: 0.0003 seconds / 32.00 memory
mergespread: 0.0003 seconds / 32.00 memory
Items: 1000
framework dot: 0.0280 seconds / 34.00 memory
fastdot: 0.0026 seconds / 34.00 memory
mergespread: 0.0031 seconds / 34.00 memory
Items: 10000
framework dot: 4.5470 seconds / 60.00 memory
fastdot: 0.0317 seconds / 66.00 memory
mergespread: 0.0378 seconds / 58.00 memory
Items: 15000
framework dot: 12.1578 seconds / 78.00 memory
fastdot: 0.0468 seconds / 80.00 memory
mergespread: 0.0617 seconds / 72.00 memory

comes · 2023-12-15T09:16:27Z

@donnysim awesome, I prefer your solution. based on a benchmark with up to 1M items it's faster and uses less memory.

Items: 100
fastdot: 0.0001 seconds / 20.00 memory
spread: 0.0001 seconds / 20.00 memory
Items: 1000
fastdot: 0.0009 seconds / 24.00 memory
spread: 0.0009 seconds / 22.00 memory
Items: 10000
fastdot: 0.0129 seconds / 48.50 memory
spread: 0.0127 seconds / 45.00 memory
Items: 15000
fastdot: 0.0204 seconds / 66.50 memory
spread: 0.0168 seconds / 59.00 memory
Items: 50000
fastdot: 0.0952 seconds / 162.00 memory
spread: 0.0705 seconds / 142.00 memory
Items: 100000
fastdot: 0.1972 seconds / 326.02 memory
spread: 0.1685 seconds / 270.03 memory
Items: 500000
fastdot: 1.7555 seconds / 1286.02 memory
spread: 1.3012 seconds / 1169.78 memory
Items: 1000000
fastdot: 3.7078 seconds / 2878.02 memory
spread: 2.7969 seconds / 2429.53 memory

bastien-phi · 2023-12-15T09:17:43Z

Agree with that, this version is also faster on my benchmarks. I update this PR

donnysim · 2023-12-15T09:23:36Z

Windows user casually getting destroyed even with arrays bench. That's me 🥲

comes · 2023-12-15T09:42:12Z

Agree with that, this version is also faster on my benchmarks. I update this PR

Thank you for your support and improvement. Like your solution more than mine.

donnysim · 2023-12-15T09:56:24Z

Oh, i didn't think of ordering, nice catch 👍 it's possible to optimize it a bit more in this case to group attribute batches instead of array per attribute:

    public function spread($array, $prepend = '')
    {
        $results = [];
        $attrs = [];

        foreach ($array as $key => $value) {
            if (is_array($value) && !empty($value)) {
                if ($attrs) {
                    $results[] = $attrs;
                    $attrs = [];
                }

                $results[] = $this->mergespread($value, $prepend . $key . '.');
            } else {
                $attrs[$prepend . $key] = $value;
            }
        }

        if ($attrs) {
            $results[] = $attrs;
        }

        return array_merge(...$results);
    }

haven't tested it fully how much it makes a diff, but it should be little bit better performance and maybe memory wise.

comes · 2023-12-15T10:20:22Z

Oh, i didn't think of ordering, nice catch 👍 it's possible to optimize it a bit more in this case to group attribute batches instead of array per attribute:
    public function spread($array, $prepend = '')
    {
        $results = [];
        $attrs = [];

        foreach ($array as $key => $value) {
            if (is_array($value) && !empty($value)) {
                if ($attrs) {
                    $results[] = $attrs;
                    $attrs = [];
                }

                $results[] = $this->mergespread($value, $prepend . $key . '.');
            } else {
                $attrs[$prepend . $key] = $value;
            }
        }

        if ($attrs) {
            $results[] = $attrs;
        }

        return array_merge(...$results);
    }
haven't tested it fully how much it makes a diff, but it should be little bit better performance and maybe memory wise.

this 'improved' version, did not perform very well:

Items: 100
fastdot: 0.0001 seconds / 20.00 memory
dospread: 0.0001 seconds / 20.00 memory
dospreadImproved: 0.0001 seconds / 20.00 memory
Items: 1000
fastdot: 0.0012 seconds / 24.00 memory
dospread: 0.0013 seconds / 22.00 memory
dospreadImproved: 0.0012 seconds / 24.00 memory
Items: 10000
fastdot: 0.0182 seconds / 48.50 memory
dospread: 0.0149 seconds / 45.00 memory
dospreadImproved: 0.0134 seconds / 50.00 memory
Items: 15000
fastdot: 0.0229 seconds / 66.50 memory
dospread: 0.0183 seconds / 59.00 memory
dospreadImproved: 0.0231 seconds / 64.00 memory
Items: 25000
fastdot: 0.0435 seconds / 99.00 memory
dospread: 0.0375 seconds / 84.00 memory
dospreadImproved: 0.0330 seconds / 94.00 memory
Items: 50000
fastdot: 0.0909 seconds / 172.00 memory
dospread: 0.0792 seconds / 146.00 memory
dospreadImproved: 0.1138 seconds / 162.00 memory
Items: 100000
fastdot: 0.2218 seconds / 326.02 memory
dospread: 0.1973 seconds / 270.03 memory
dospreadImproved: 0.2313 seconds / 306.02 memory

bastien-phi · 2023-12-15T11:23:52Z

AFK, I convert this PR to draft and will try your version when I can

… consistant

Improve Arr::dot performance

816852e

Add some tests for Arr::dot

66aa5fa

Fix cs

62fb709

bastien-phi force-pushed the improve_arr_dot branch from d37ad5f to f49b4e8 Compare December 15, 2023 09:20

Use array_merge spread to increase speed and decrease memory usage

c53eb64

bastien-phi force-pushed the improve_arr_dot branch from f49b4e8 to c53eb64 Compare December 15, 2023 09:29

comes mentioned this pull request Dec 15, 2023

[10.x] The validator is very slow with large datasets when the key contains asterisks #49375

Closed

Fix ordering

d653327

bastien-phi force-pushed the improve_arr_dot branch from 9c963eb to d653327 Compare December 15, 2023 09:44

bastien-phi marked this pull request as draft December 15, 2023 11:25

bastien-phi added 3 commits December 15, 2023 17:10

Change assertEquals to assertSame in order to verify that ordering is…

2b3e588

… consistant

Explicit array creation

b054991

Fix cs

adfdaaa

bastien-phi marked this pull request as ready for review December 15, 2023 16:28

taylorotwell merged commit 03dbd3a into laravel:10.x Dec 15, 2023
23 checks passed

bastien-phi deleted the improve_arr_dot branch December 21, 2023 07:21

kayw-geek mentioned this pull request Dec 28, 2023

[10.x] Fixes the Arr::dot() method to properly handle indexes array #49507

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[10.x] Improve `Arr::dot` performance #49386

[10.x] Improve `Arr::dot` performance #49386

bastien-phi commented Dec 15, 2023 •

edited

Loading

jbrooksuk commented Dec 15, 2023

bastien-phi commented Dec 15, 2023

comes commented Dec 15, 2023

donnysim commented Dec 15, 2023 •

edited

Loading

comes commented Dec 15, 2023

bastien-phi commented Dec 15, 2023

donnysim commented Dec 15, 2023 •

edited

Loading

comes commented Dec 15, 2023

donnysim commented Dec 15, 2023 •

edited

Loading

comes commented Dec 15, 2023 •

edited

Loading

bastien-phi commented Dec 15, 2023

[10.x] Improve Arr::dot performance #49386

[10.x] Improve Arr::dot performance #49386

Conversation

bastien-phi commented Dec 15, 2023 • edited Loading

jbrooksuk commented Dec 15, 2023

bastien-phi commented Dec 15, 2023

comes commented Dec 15, 2023

donnysim commented Dec 15, 2023 • edited Loading

comes commented Dec 15, 2023

bastien-phi commented Dec 15, 2023

donnysim commented Dec 15, 2023 • edited Loading

comes commented Dec 15, 2023

donnysim commented Dec 15, 2023 • edited Loading

comes commented Dec 15, 2023 • edited Loading

bastien-phi commented Dec 15, 2023

[10.x] Improve `Arr::dot` performance #49386

[10.x] Improve `Arr::dot` performance #49386

bastien-phi commented Dec 15, 2023 •

edited

Loading

donnysim commented Dec 15, 2023 •

edited

Loading

donnysim commented Dec 15, 2023 •

edited

Loading

donnysim commented Dec 15, 2023 •

edited

Loading

comes commented Dec 15, 2023 •

edited

Loading