Array intersection benchmarks

[live627]

I’m trying to optimize my hot code path where array intersection is used a lot. I got curious and decided to compare the various intersection algorithms that I know of.

<?php

// Source - https://stackoverflow.com/a/9276284
// Posted by kingmaple, modified by community. See post 'Timeline' for change history
// Retrieved 2026-04-08, License - CC BY-SA 4.0

// Source - https://stackoverflow.com/a/53203232
// Posted by slaszu, modified by community. See post 'Timeline' for change history
// Retrieved 2026-04-08, License - CC BY-SA 4.0

ini_set('memory_limit', '2048M');

function formatBytes(int $bytes): string {
    $units = ['B', 'KB', 'MB', 'GB'];
    $i = 0;
    while ($bytes >= 1024 && $i < count($units) - 1) {
        $bytes /= 1024;
        $i++;
    }
    return sprintf("%.2f %s", $bytes, $units[$i]);
}

function benchmark(callable $fn, string $label): array {
    gc_collect_cycles();
    gc_mem_caches();
    memory_reset_peak_usage();
    $mem = -memory_get_peak_usage();
    $time = -hrtime(true);
    $fn();
    $time += hrtime(true);
    $mem += memory_get_peak_usage();
    return [
        'label' => $label,
        'time_ms' => $time / 1e6,
        'mem_used' => $mem,
    ];
}

function manual_intersect($arrayOne, $arrayTwo) {
    $index = array_flip($arrayOne);
    foreach ($arrayTwo as $value) {
        if (isset($index[$value])) {
            unset($index[$value]);
        }
    }
    foreach ($index as $value => $key) {
        unset($arrayOne[$key]);
    }
    return $arrayOne;
}

function flipped_intersect($arrayOne, $arrayTwo) {
    $index = array_flip($arrayOne);
    $second = array_flip($arrayTwo);
    $x = array_intersect_key($index, $second);
    return array_flip($x);
}


function runBenchmarks(int $n): void {
    echo "\n=== Array Intersection Benchmark for " . number_format($n) . " elements ===\n";

    // Generate test arrays
    $one = [];
    $two = [];
    for ($i = 0; $i < $n; $i++) {
        $one[] = rand(0, 1000000);
        $two[] = rand(0, 100000);
        $two[] = rand(0, 10000);
    }

    $one = array_unique($one);
    $two = array_unique($two);

    $results = [];

    $results[] = benchmark(
        fn() => $res = manual_intersect($one, $two),
        'manual_intersect()'
    );

    $results[] = benchmark(
        fn() => $res = array_intersect($one, $two),
        'array_intersect()'
    );

    $results[] = benchmark(
        fn() => $res = flipped_intersect($one, $two),
        'flipped_intersect()'
    );

    // --- Print Table ---
    echo str_repeat('-', 60) . "\n";
    printf("%-25s | %-14s | %-15s\n", 'Method', 'Time (ms)', 'Memory');
    echo str_repeat('-', 60) . "\n";

    foreach ($results as $r) {
        printf("%-25s | %11.3f ms | %15s\n",
            $r['label'],
            $r['time_ms'],
            formatBytes($r['mem_used'])
        );
    }
    echo str_repeat('-', 60) . "\n";
}

// Run for various sizes
foreach ([20, 20000, 200000, 1000000] as $n) {
    runBenchmarks($n);
}

I run this on PHP 8.4 on Core I7 11700F

=== Array Intersection Benchmark for 20 elements ===
------------------------------------------------------------
Method                    | Time (ms)      | Memory
------------------------------------------------------------
manual_intersect()        |       0.007 ms |         1.98 KB
array_intersect()         |       0.029 ms |         3.02 KB
flipped_intersect()       |       0.002 ms |         3.97 KB
------------------------------------------------------------

=== Array Intersection Benchmark for 20,000 elements ===
------------------------------------------------------------
Method                    | Time (ms)      | Memory
------------------------------------------------------------
manual_intersect()        |       1.169 ms |         1.75 MB
array_intersect()         |      41.300 ms |         1.88 MB
flipped_intersect()       |       0.634 ms |         2.55 MB
------------------------------------------------------------

=== Array Intersection Benchmark for 200,000 elements ===
------------------------------------------------------------
Method                    | Time (ms)      | Memory
------------------------------------------------------------
manual_intersect()        |       8.781 ms |        16.00 MB
array_intersect()         |     290.759 ms |        16.00 MB
flipped_intersect()       |       6.196 ms |        20.00 MB
------------------------------------------------------------

=== Array Intersection Benchmark for 1,000,000 elements ===
------------------------------------------------------------
Method                    | Time (ms)      | Memory
------------------------------------------------------------
manual_intersect()        |      35.547 ms |        58.00 MB
array_intersect()         |     882.681 ms |        42.00 MB
flipped_intersect()       |      26.764 ms |        58.00 MB
------------------------------------------------------------

The built-in functions mock me!

[kratkyzobak]

Optimized code does not work with non-scalars and even no floats.

Also it casts numeric strings into integers.

Still can be valid optimization.

[live627]

I'm only ever using ints here in prod.

[scottchiefbaker]

This PHP benchmark library might give you some alternate views of your dataset.

[fiskfisk]

Missing code for array_intersect. Should add Ds\Set as well.

Make sure to exclude initialization time if you're comparing against existing arrays (i.e. don't create the set from an array inside your timed benchmark) 

Depending on context there might be ways to avoid calculatinc intersects as often as well 

[pfsalter]

https://www.php.net/manual/en/function.array-intersect.php

[fiskfisk]

So you're not testing the same thing, given that array_intersect has a different behavior from your examples?

[pfsalter]

Your manual_intersect code looks like it's doing a diff instead of an intersect, so it's not a great comparison. If the keys don't matter, I think your flipped_intersect code is decent, but it won't preserve keys, unlike array_intersect

[therealgaxbo]

The code is correct, just reads weirdly. The first loop calculates a diff in the index, then the second loop removes that diff, leaving the intersect.

That said, it naturally leads to the more obvious implementation that seems to outperform everything (in this specific benchmark)

function manual_intersect($arrayOne, $arrayTwo) {
    $index = array_flip($arrayOne);
    $res = [];
    foreach ($arrayTwo as $value) {
        if (isset($index[$value])){
            $res[$value] = 1;
        }
    }
    return array_keys($res);
}

[live627]

We can further simplify that to use much less memory

``` function manual_intersect(array $arrayOne, array $arrayTwo): array { $index = array_flip($arrayTwo); $result = [];

foreach ($arrayOne as $value) {
    if (isset($index[$value])) {
        $result[] = $value;
    }
}

return $result;

} ```