Instantly share code, notes, and snippets.

Embed
What would you like to do?
PHP Matrix multiplication benchmark
<?php
declare(strict_types=1);
/**
* Requires the DS extension (see https://github.com/php-ds/extension).
* This script is a benchmark for many possible combinations to perform matrix multiplications:
* - Ds\Vector vs PHP array
* - Single array vs Nested arrays
* - iterations order: I,J,K vs I,K,J
*/
/**
* RESULTS (the times are not divided by the number of iterations, only numbers in the same row can be compared):
*
* ijk cont. array ijk nest. array ijk cont. vector ijk nest. vector ikj cont. array ikj nest. array ikj cont. vector ikj nest. vector
* 4 -> 0.00042104721069336 0.0004429817199707 0.00049710273742676 0.00060391426086426 0.00030279159545898 0.00032591819763184 0.00038003921508789 0.00046491622924805
* 8 -> 0.002924919128418 0.003281831741333 0.0034310817718506 0.0043010711669922 0.0017859935760498 0.0020260810852051 0.0023138523101807 0.0028958320617676
* 16 -> 0.019437074661255 0.020691156387329 0.020630836486816 0.025195837020874 0.0088889598846436 0.010462045669556 0.011255979537964 0.014892101287842
* 32 -> 0.094998121261597 0.1055748462677 0.11357617378235 0.15099906921387 0.052932024002075 0.064934968948364 0.0711350440979 0.10097599029541
* 64 -> 0.72782516479492 0.83726596832275 0.9531569480896 1.1677219867706 0.39643001556396 0.49447298049927 0.53884315490723 0.7768931388855
* 128 -> 2.8404879570007 3.2943258285522 3.5353372097015 4.66787981987 1.5506911277771 1.9599390029907 2.1567468643188 3.1205151081085
* 256 -> 22.941949129105 26.903174877167 28.000234127045 38.06840801239 12.362766981125 15.758536100388 17.036547899246 24.780100107193
* 512 -> 281.45276784897 298.90023684502 236.78369307518 324.35555291176 99.469950199127 126.31004500389 135.40308403969 198.58974289894
*
*/
require __DIR__ . '/../vendor/autoload.php';
use Ds\Vector;
$matSizes = [4, 8, 16, 32, 64, 128, 256, 512];
if (\extension_loaded('ds')) {
echo "\n\nLOADED DS\n\n";
} else {
echo "\n\nNO EXTENSION\n\n";
}
foreach ($matSizes as $matSize) {
list($ca1, $na1, $cv1, $nv1) = getMatrixInstances($matSize);
list($ca2, $na2, $cv2, $nv2) = getMatrixInstances($matSize);
list($caR, $naR, $cvR, $nvR) = getMatrixInstances($matSize, true);
$limit = $matSize < 128 ? 40 : 20;
$tIJK_ca_1 = \microtime(true);
for ($x = 0; $x < $limit; $x++) {
for ($i = 0, $im = 0; $i < $matSize; $i++, $im += $matSize) {
for ($j = 0; $j < $matSize; $j++) {
for ($k = 0, $km = 0; $k < $matSize; $k++, $km += $matSize) {
$caR[$im + $j] += $ca1[$im + $k] * $ca2[$km + $j];
}
}
}
}
$tIJK_ca_2 = \microtime(true);
$tIJK_na_1 = \microtime(true);
for ($x = 0; $x < $limit; $x++) {
for ($i = 0; $i < $matSize; $i++) {
for ($j = 0; $j < $matSize; $j++) {
for ($k = 0; $k < $matSize; $k++) {
$naR[$i][$j] += $na1[$i][$k] * $na2[$k][$j];
}
}
}
}
$tIJK_na_2 = \microtime(true);
$tIJK_cv_1 = \microtime(true);
for ($x = 0; $x < $limit; $x++) {
for ($i = 0, $im = 0; $i < $matSize; $i++, $im += $matSize) {
for ($j = 0; $j < $matSize; $j++) {
for ($k = 0, $km = 0; $k < $matSize; $k++, $km += $matSize) {
$cvR[$im + $j] += $cv1[$im + $k] * $cv2[$km + $j];
}
}
}
}
$tIJK_cv_2 = \microtime(true);
$tIJK_nv_1 = \microtime(true);
for ($x = 0; $x < $limit; $x++) {
for ($i = 0; $i < $matSize; $i++) {
for ($j = 0; $j < $matSize; $j++) {
for ($k = 0; $k < $matSize; $k++) {
$nvR[$i][$j] += $nv1[$i][$k] * $nv2[$k][$j];
}
}
}
}
$tIJK_nv_2 = \microtime(true);
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
list($caR, $naR, $cvR, $nvR) = getMatrixInstances($matSize, true);
$tIKJ_ca_1 = \microtime(true);
for ($x = 0; $x < $limit; $x++) {
for ($i = 0, $im = 0; $i < $matSize; $i++, $im += $matSize) {
for ($k = 0, $km = 0; $k < $matSize; $k++, $km += $matSize) {
$t = $ca1[$im + $k];
for ($j = 0; $j < $matSize; $j++) {
$caR[$im + $j] += $t * $ca2[$km + $j];
}
}
}
}
$tIKJ_ca_2 = \microtime(true);
$tIKJ_na_1 = \microtime(true);
for ($x = 0; $x < $limit; $x++) {
for ($i = 0; $i < $matSize; $i++) {
for ($k = 0; $k < $matSize; $k++) {
$t = $na1[$i][$k];
for ($j = 0; $j < $matSize; $j++) {
$naR[$i][$j] += $t * $naR[$k][$j];
}
}
}
}
$tIKJ_na_2 = \microtime(true);
$tIKJ_cv_1 = \microtime(true);
for ($x = 0; $x < $limit; $x++) {
for ($i = 0, $im = 0; $i < $matSize; $i++, $im += $matSize) {
for ($k = 0, $km = 0; $k < $matSize; $k++, $km += $matSize) {
$t = $cv1[$im + $k];
for ($j = 0; $j < $matSize; $j++) {
$cvR[$im + $j] += $t * $cv2[$km + $j];
}
}
}
}
$tIKJ_cv_2 = \microtime(true);
$tIKJ_nv_1 = \microtime(true);
for ($x = 0; $x < $limit; $x++) {
for ($i = 0; $i < $matSize; $i++) {
for ($k = 0; $k < $matSize; $k++) {
$t = $nv1[$i][$k];
for ($j = 0; $j < $matSize; $j++) {
$nvR[$i][$j] += $t * $nvR[$k][$j];
}
}
}
}
$tIKJ_nv_2 = \microtime(true);
$result = [
$matSize => [
'ca_ijk' => $tIJK_ca_2 - $tIJK_ca_1,
'na_ijk' => $tIJK_na_2 - $tIJK_na_1,
'cv_ijk' => $tIJK_cv_2 - $tIJK_cv_1,
'nv_ijk' => $tIJK_nv_2 - $tIJK_nv_1,
'ca_ikj' => $tIKJ_ca_2 - $tIKJ_ca_1,
'na_ikj' => $tIKJ_na_2 - $tIKJ_na_1,
'cv_ikj' => $tIKJ_cv_2 - $tIKJ_cv_1,
'nv_ikj' => $tIKJ_nv_2 - $tIKJ_nv_1,
]
];
echo \json_encode($result) . "\n";
}
/**
* @param int $matSize
* @param bool $zeros
* @return array [$singleArray, $nestedArray, $singleVector, $nestedVector]
*/
function getMatrixInstances(int $matSize, bool $zeros = false) : array
{
$totalSize = $matSize * $matSize;
$singleArray = \array_fill(0, $totalSize, 0.0); // ARRAY - contiguous memory
$rowTemplate = \array_fill(0, $matSize, 0);
$rowTmplVect = new Vector($rowTemplate);
$nestedArray = \array_fill(0, $matSize, $rowTemplate); // ARRAY - nested rows
$nestedVector = new Vector(); // VECTOR - nested rows
$nestedVector->allocate($matSize);
for ($i = 0, $im = 0; $i < $matSize; $i++, $im += $matSize) {
$nestedVector->push(clone $rowTmplVect);
if (!$zeros) {
for ($j = 0; $j < $matSize; $j++) {
$v = \random_int(-5000, 5000);
$singleArray[$im + $j] = $v;
$nestedArray[$i][$j] = $v;
$nestedVector[$i][$j] = $v;
}
}
}
$singleVector = new Vector($singleArray); // VECTOR - contiguous memory
return [$singleArray, $nestedArray, $singleVector, $nestedVector];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment