BenchmarkTest::testHopeAddingTargetDoesNotChangeMuchWithCrc32Hasher() - Code Metrics - Inspection of "feat: add Fnv1-a hasher" - ericsizemore/consistent-hash - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — main ( ddf3a0...f0c061 )

by Eric

created 2024-12-06 05:58 UTC

testHopeAddingTargetDoesNotChangeMuchWithCrc32Hasher() B

↳ Parent: BenchmarkTest

Complexity

Conditions	6
Paths	24

Size

Total Lines	35
Code Lines	21

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	6
eloc	21
nc	24
nop	0
dl	0
loc	35
rs	8.9617
c	0
b	0
f	0

<?php

declare(strict_types=1);

/**
 * This file is part of Esi\ConsistentHash.
 *
 * (c) Eric Sizemore <[email protected]>
 * (c) Paul Annesley <[email protected]>
 *
 * This source file is subject to the MIT license. For the full copyright and
 * license information, please view the LICENSE file that was distributed with
 * this source code.
 */

namespace Esi\ConsistentHash\Tests;

use Esi\ConsistentHash\ConsistentHash;
use Esi\ConsistentHash\Hasher\Crc32Hasher;
use Esi\ConsistentHash\Hasher\Fnv1AHasher;
use Esi\ConsistentHash\Hasher\Md5Hasher;
use Esi\ConsistentHash\Hasher\Murmur3Hasher;
use Esi\ConsistentHash\Hasher\Xxh32Hasher;
use PHPUnit\Framework\Attributes\CoversClass;
use PHPUnit\Framework\Attributes\DoesNotPerformAssertions;
use PHPUnit\Framework\Attributes\Group;
use PHPUnit\Framework\TestCase;

/**
 * Benchmarks, not really tests.
 *
 * @internal
 */
#[CoversClass(ConsistentHash::class)]
#[CoversClass(Crc32Hasher::class)]
#[CoversClass(Fnv1AHasher::class)]
#[CoversClass(Md5Hasher::class)]
#[CoversClass(Murmur3Hasher::class)]
#[CoversClass(Xxh32Hasher::class)]
#[Group('benchmark')]
#[DoesNotPerformAssertions]
class BenchmarkTest extends TestCase
{
    private int $lookups = 1000;
    private int $targets = 10;

    public function dump(string $message): void
    {
        echo \sprintf("%s\n\n", $message);
    }

    public function testAddTargetWithNonConsistentHash(): void
    {
        $results1 = [];
        foreach (range(1, $this->lookups) as $i) {
            $results1[$i] = $this->basicHash("t$i", 10);
        }

        $results2 = [];
        foreach (range(1, $this->lookups) as $i) {
            $results2[$i] = $this->basicHash("t$i", 11);
        }

        $differences = 0;
        foreach (range(1, $this->lookups) as $i) {
            if ($results1[$i] !== $results2[$i]) {
                ++$differences;
            }
        }

        $percent = round($differences / $this->lookups * 100);

        $this->dump(\sprintf(
            'NonConsistentHash: %d%% of lookups changed after adding a target to the existing %d',
            $percent,
            $this->targets
        ));
    }

    public function testHashDistributionWithCrc32Hasher(): void
    {
        $hashSpace = new ConsistentHash(
            new Crc32Hasher()
        );

        foreach (range(1, $this->targets) as $i) {
            $hashSpace->addTarget("target$i");
        }

        $results = [];
        foreach (range(1, $this->lookups) as $i) {
            $results[$i] = $hashSpace->lookup("t$i");
        }

        $distribution = [];
        foreach ($hashSpace->getAllTargets() as $target) {
            /**
             * @psalm-var non-empty-array<array-key, int> $distribution
             */
            $distribution[$target] = \count(array_keys($results, $target, true));
        }

        $this->dump(\sprintf(
            'Distribution of %d lookups per target (min/max/median/avg): %d/%d/%d/%d',
            $this->lookups / $this->targets,
            min($distribution),
            max($distribution),
            round($this->median($distribution)),
            round(array_sum($distribution) / \count($distribution))
        ));
    }

    public function testHasherSpeed(): void
    {
        $hashCount = 100000;

        $md5Hasher     = new Md5Hasher();
        $crc32Hasher   = new Crc32Hasher();
        $fnv1Hasher    = new Fnv1AHasher();
        $murmur3Hasher = new Murmur3Hasher();
        $xxh32Hasher   = new Xxh32Hasher();

        $start = microtime(true);
        for ($i = 0; $i < $hashCount; ++$i) {
            $md5Hasher->hash("test$i");
        }
        $timeMd5 = microtime(true) - $start;

        $start = microtime(true);
        for ($i = 0; $i < $hashCount; ++$i) {
            $crc32Hasher->hash("test$i");
        }
        $timeCrc32 = microtime(true) - $start;

        $start = microtime(true);
        for ($i = 0; $i < $hashCount; ++$i) {
            $fnv1Hasher->hash("test$i");
        }
        $timeFnv1 = microtime(true) - $start;

        $start = microtime(true);
        for ($i = 0; $i < $hashCount; ++$i) {
            $murmur3Hasher->hash("test$i");
        }
        $timeMurmur3 = microtime(true) - $start;

        $start = microtime(true);
        for ($i = 0; $i < $hashCount; ++$i) {
            $xxh32Hasher->hash("test$i");
        }
        $timeXxh32 = microtime(true) - $start;

        $this->dump(\sprintf(
            "Hashers timed over %d hashes (MD5 / CRC32 / FNV1-A / MURMUR3 / XXH32):\n %f / %f / %f / %f / %f",
            $hashCount,
            $timeMd5,
            $timeCrc32,
            $timeFnv1,
            $timeMurmur3,
            $timeXxh32
        ));
    }

    public function testHopeAddingTargetDoesNotChangeMuchWithCrc32Hasher(): void
    {
        $hashSpace = new ConsistentHash(
            new Crc32Hasher()
        );
        foreach (range(1, $this->targets) as $i) {
            $hashSpace->addTarget("target$i");
        }

        $results1 = [];
        foreach (range(1, $this->lookups) as $i) {
            $results1[$i] = $hashSpace->lookup("t$i");
        }

        $hashSpace->addTarget('target-new');

        $results2 = [];
        foreach (range(1, $this->lookups) as $i) {
            $results2[$i] = $hashSpace->lookup("t$i");
        }

        $differences = 0;
        foreach (range(1, $this->lookups) as $i) {
            if ($results1[$i] !== $results2[$i]) {
                ++$differences;
            }
        }

        $percent = round($differences / $this->lookups * 100);

        $this->dump(
            \sprintf(
                'ConsistentHash: %d%% of lookups changed after adding a target to the existing %d',
                $percent,
                $this->targets
            )
        );
    }

    public function testHopeRemovingTargetDoesNotChangeMuchWithCrc32Hasher(): void
    {
        $hashSpace = new ConsistentHash(
            new Crc32Hasher()
        );
        foreach (range(1, $this->targets) as $i) {
            $hashSpace->addTarget("target$i");
        }

        $results1 = [];
        foreach (range(1, $this->lookups) as $i) {
            $results1[$i] = $hashSpace->lookup("t$i");
        }

        $hashSpace->removeTarget('target1');

        $results2 = [];
        foreach (range(1, $this->lookups) as $i) {
            $results2[$i] = $hashSpace->lookup("t$i");
        }

        $differences = 0;
        foreach (range(1, $this->lookups) as $i) {
            if ($results1[$i] !== $results2[$i]) {
                ++$differences;
            }
        }

        $percent = round($differences / $this->lookups * 100);

        $this->dump(
            \sprintf(
                'ConsistentHash: %d%% of lookups changed  after removing 1 of %d targets',
                $percent,
                $this->targets
            )
        );
    }

    public function testRemoveTargetWithNonConsistentHash(): void
    {
        $results1 = [];
        foreach (range(1, $this->lookups) as $i) {
            $results1[$i] = $this->basicHash("t$i", 10);
        }

        $results2 = [];
        foreach (range(1, $this->lookups) as $i) {
            $results2[$i] = $this->basicHash("t$i", 9);
        }

        $differences = 0;
        foreach (range(1, $this->lookups) as $i) {
            if ($results1[$i] !== $results2[$i]) {
                ++$differences;
            }
        }

        $percent = round($differences / $this->lookups * 100);

        $this->dump(
            \sprintf(
                'NonConsistentHash: %d%% of lookups changed after removing 1 of %d targets',
                $percent,
                $this->targets
            )
        );
    }

    // ----------------------------------------

    private function basicHash(string $value, int $targets): int
    {
        return abs(crc32($value) % $targets);

    }

    /**
     * @param array<int> $values list of numeric values
     */
    private function median(array $values): float|int
    {
        $values = array_values($values);
        sort($values);

        $count       = \count($values);
        $middleFloor = floor($count / 2);

        if ($count % 2 === 1) {
            return $values[$middleFloor];
        }

        return ($values[$middleFloor] + $values[$middleFloor + 1]) / 2;
    }
}


1			<?php
2
3			declare(strict_types=1);
4
5			/**
6			* This file is part of Esi\ConsistentHash.
7			*
8			* (c) Eric Sizemore <[email protected]>
9			* (c) Paul Annesley <[email protected]>
10			*
11			* This source file is subject to the MIT license. For the full copyright and
12			* license information, please view the LICENSE file that was distributed with
13			* this source code.
14			*/
15
16			namespace Esi\ConsistentHash\Tests;
17
18			use Esi\ConsistentHash\ConsistentHash;
19			use Esi\ConsistentHash\Hasher\Crc32Hasher;
20			use Esi\ConsistentHash\Hasher\Fnv1AHasher;
21			use Esi\ConsistentHash\Hasher\Md5Hasher;
22			use Esi\ConsistentHash\Hasher\Murmur3Hasher;
23			use Esi\ConsistentHash\Hasher\Xxh32Hasher;
24			use PHPUnit\Framework\Attributes\CoversClass;
25			use PHPUnit\Framework\Attributes\DoesNotPerformAssertions;
26			use PHPUnit\Framework\Attributes\Group;
27			use PHPUnit\Framework\TestCase;
28
29			/**
30			* Benchmarks, not really tests.
31			*
32			* @internal
33			*/
34			#[CoversClass(ConsistentHash::class)]
35			#[CoversClass(Crc32Hasher::class)]
36			#[CoversClass(Fnv1AHasher::class)]
37			#[CoversClass(Md5Hasher::class)]
38			#[CoversClass(Murmur3Hasher::class)]
39			#[CoversClass(Xxh32Hasher::class)]
40			#[Group('benchmark')]
41			#[DoesNotPerformAssertions]
42			class BenchmarkTest extends TestCase
43			{
44			private int $lookups = 1000;
45			private int $targets = 10;
46
47			public function dump(string $message): void
48			{
49			echo \sprintf("%s\n\n", $message);
50			}
51
52			public function testAddTargetWithNonConsistentHash(): void
53			{
54			$results1 = [];
55			foreach (range(1, $this->lookups) as $i) {
56			$results1[$i] = $this->basicHash("t$i", 10);
57			}
58
59			$results2 = [];
60			foreach (range(1, $this->lookups) as $i) {
61			$results2[$i] = $this->basicHash("t$i", 11);
62			}
63
64			$differences = 0;
65			foreach (range(1, $this->lookups) as $i) {
66			if ($results1[$i] !== $results2[$i]) {
67			++$differences;
68			}
69			}
70
71			$percent = round($differences / $this->lookups * 100);
72
73			$this->dump(\sprintf(
74			'NonConsistentHash: %d%% of lookups changed after adding a target to the existing %d',
75			$percent,
76			$this->targets
77			));
78			}
79
80			public function testHashDistributionWithCrc32Hasher(): void
81			{
82			$hashSpace = new ConsistentHash(
83			new Crc32Hasher()
84			);
85
86			foreach (range(1, $this->targets) as $i) {
87			$hashSpace->addTarget("target$i");
88			}
89
90			$results = [];
91			foreach (range(1, $this->lookups) as $i) {
92			$results[$i] = $hashSpace->lookup("t$i");
93			}
94
95			$distribution = [];
96			foreach ($hashSpace->getAllTargets() as $target) {
97			/**
98			* @psalm-var non-empty-array<array-key, int> $distribution
99			*/
100			$distribution[$target] = \count(array_keys($results, $target, true));
101			}
102
103			$this->dump(\sprintf(
104			'Distribution of %d lookups per target (min/max/median/avg): %d/%d/%d/%d',
105			$this->lookups / $this->targets,
106			min($distribution),
107			max($distribution),
108			round($this->median($distribution)),
109			round(array_sum($distribution) / \count($distribution))
110			));
111			}
112
113			public function testHasherSpeed(): void
114			{
115			$hashCount = 100000;
116
117			$md5Hasher = new Md5Hasher();
118			$crc32Hasher = new Crc32Hasher();
119			$fnv1Hasher = new Fnv1AHasher();
120			$murmur3Hasher = new Murmur3Hasher();
121			$xxh32Hasher = new Xxh32Hasher();
122
123			$start = microtime(true);
124			for ($i = 0; $i < $hashCount; ++$i) {
125			$md5Hasher->hash("test$i");
126			}
127			$timeMd5 = microtime(true) - $start;
128
129			$start = microtime(true);
130			for ($i = 0; $i < $hashCount; ++$i) {
131			$crc32Hasher->hash("test$i");
132			}
133			$timeCrc32 = microtime(true) - $start;
134
135			$start = microtime(true);
136			for ($i = 0; $i < $hashCount; ++$i) {
137			$fnv1Hasher->hash("test$i");
138			}
139			$timeFnv1 = microtime(true) - $start;
140
141			$start = microtime(true);
142			for ($i = 0; $i < $hashCount; ++$i) {
143			$murmur3Hasher->hash("test$i");
144			}
145			$timeMurmur3 = microtime(true) - $start;
146
147			$start = microtime(true);
148			for ($i = 0; $i < $hashCount; ++$i) {
149			$xxh32Hasher->hash("test$i");
150			}
151			$timeXxh32 = microtime(true) - $start;
152
153			$this->dump(\sprintf(
154			"Hashers timed over %d hashes (MD5 / CRC32 / FNV1-A / MURMUR3 / XXH32):\n %f / %f / %f / %f / %f",
155			$hashCount,
156			$timeMd5,
157			$timeCrc32,
158			$timeFnv1,
159			$timeMurmur3,
160			$timeXxh32
161			));
162			}
163
164			public function testHopeAddingTargetDoesNotChangeMuchWithCrc32Hasher(): void
165			{
166			$hashSpace = new ConsistentHash(
167			new Crc32Hasher()
168			);
169			foreach (range(1, $this->targets) as $i) {
170			$hashSpace->addTarget("target$i");
171			}
172
173			$results1 = [];
174			foreach (range(1, $this->lookups) as $i) {
175			$results1[$i] = $hashSpace->lookup("t$i");
176			}
177
178			$hashSpace->addTarget('target-new');
179
180			$results2 = [];
181			foreach (range(1, $this->lookups) as $i) {
182			$results2[$i] = $hashSpace->lookup("t$i");
183			}
184
185			$differences = 0;
186			foreach (range(1, $this->lookups) as $i) {
187			if ($results1[$i] !== $results2[$i]) {
188			++$differences;
189			}
190			}
191
192			$percent = round($differences / $this->lookups * 100);
193
194			$this->dump(
195			\sprintf(
196			'ConsistentHash: %d%% of lookups changed after adding a target to the existing %d',
197			$percent,
198			$this->targets
199			)
200			);
201			}
202
203			public function testHopeRemovingTargetDoesNotChangeMuchWithCrc32Hasher(): void
204			{
205			$hashSpace = new ConsistentHash(
206			new Crc32Hasher()
207			);
208			foreach (range(1, $this->targets) as $i) {
209			$hashSpace->addTarget("target$i");
210			}
211
212			$results1 = [];
213			foreach (range(1, $this->lookups) as $i) {
214			$results1[$i] = $hashSpace->lookup("t$i");
215			}
216
217			$hashSpace->removeTarget('target1');
218
219			$results2 = [];
220			foreach (range(1, $this->lookups) as $i) {
221			$results2[$i] = $hashSpace->lookup("t$i");
222			}
223
224			$differences = 0;
225			foreach (range(1, $this->lookups) as $i) {
226			if ($results1[$i] !== $results2[$i]) {
227			++$differences;
228			}
229			}
230
231			$percent = round($differences / $this->lookups * 100);
232
233			$this->dump(
234			\sprintf(
235			'ConsistentHash: %d%% of lookups changed after removing 1 of %d targets',
236			$percent,
237			$this->targets
238			)
239			);
240			}
241
242			public function testRemoveTargetWithNonConsistentHash(): void
243			{
244			$results1 = [];
245			foreach (range(1, $this->lookups) as $i) {
246			$results1[$i] = $this->basicHash("t$i", 10);
247			}
248
249			$results2 = [];
250			foreach (range(1, $this->lookups) as $i) {
251			$results2[$i] = $this->basicHash("t$i", 9);
252			}
253
254			$differences = 0;
255			foreach (range(1, $this->lookups) as $i) {
256			if ($results1[$i] !== $results2[$i]) {
257			++$differences;
258			}
259			}
260
261			$percent = round($differences / $this->lookups * 100);
262
263			$this->dump(
264			\sprintf(
265			'NonConsistentHash: %d%% of lookups changed after removing 1 of %d targets',
266			$percent,
267			$this->targets
268			)
269			);
270			}
271
272			// ----------------------------------------
273
274			private function basicHash(string $value, int $targets): int
275			{
276			return abs(crc32($value) % $targets);
			1 ignored issue – show Bug Best Practice introduced 2024-12-06 06:06 UTC by Report Bug Copy Issue Report The expression `return abs(crc32($value) % $targets)` could return the type `double` which is incompatible with the type-hinted return `integer`. Consider adding an additional type-check to rule them out. Loading history...
277			}
278
279			/**
280			* @param array<int> $values list of numeric values
281			*/
282			private function median(array $values): float\|int
283			{
284			$values = array_values($values);
285			sort($values);
286
287			$count = \count($values);
288			$middleFloor = floor($count / 2);
289
290			if ($count % 2 === 1) {
291			return $values[$middleFloor];
292			}
293
294			return ($values[$middleFloor] + $values[$middleFloor + 1]) / 2;
295			}
296			}
297

ericsizemore / consistent-hash

Push — main ( ddf3a0...f0c061 )

testHopeAddingTargetDoesNotChangeMuchWithCrc32Hasher() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like