How could I optimise this for loop to run fast on PHP. Runs extremely fast on javascript

▲
1
▼

So I've been porting some code from Javascript to PHP which works now, however, the execution time is very poor. It takes about 26 seconds in PHP whereas in javascript it is extremely fast. I've been able to break it down to the for loop causing the issue. This is the loop

for ($R0d = 0; $R0d < $F0d; $R0d = $R0d + 16) {
                $f0d = [bitwise_and(JS_charCodeAt($C0d,($R0d + 4)), 0xff) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 5)), 0xff)), 8) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 6)), 255)), 16) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 7)), 255)), 24), bitwise_and(JS_charCodeAt($C0d, ($R0d)), 255) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 1)), 255)), 8) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 2)), 255)), 16) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 3)), 0xff)), 24)];

$H0d = [bitwise_and(JS_charCodeAt($C0d, ($R0d + 12)), 255) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 13)), 255)), 8) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 14)), 255)), 16) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 15)), 255)), 24), bitwise_and(JS_charCodeAt($C0d, ($R0d + 8)), 255) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 9)), 255)), 8) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 10)), 255)), 16) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 11)), 255)), 24)];

                $f0d = x64Multiply($f0d, $M0d);
                $f0d = x64Rotl($f0d, 31);
                $f0d = x64Multiply($f0d, $I0d);
                $P0d = x64Xor($P0d, $f0d);
                $P0d = x64Rotl($P0d, 27);
                $P0d = x64Add($P0d, $o0d);
                $P0d = x64Add(x64Multiply($P0d, [0, 5]), [0, 1390208809]);
                $H0d = x64Multiply($H0d, $I0d);
                $H0d = x64Rotl($H0d, 33);
                $H0d = x64Multiply($H0d, $M0d);
                $o0d = x64Xor($o0d, $H0d);
                $o0d = x64Rotl($o0d, 31);
                $o0d = x64Add($o0d, $P0d);
                $o0d = x64Add(x64Multiply($o0d, [0, 5]), [0, 944331445]);       
            }

`

Each individual function call is fine, I've seen that each iteration takes about 0.01 seconds and for the test string I was using with this code it took about 24-27 seconds. The loop in this occasion it ran 2444 times. Imagine $F0d = 39104

Is there anyway I can reduce the time execution for this literally less than a second like it does in browsers with JavaScript?

Updated Code:

function JS_charCodeAt($str, $index) {
$utf16 = mb_convert_encoding($str, 'UTF-16LE', 'UTF-8');
return ord($utf16[$index*2]) + (ord($utf16[$index*2+1]) << 8);
}


function uRShift($a, $b)
{
    //error_log("inside uRshift");
    if ($b >= 32 || $b < -32) {
        $m = (int)($b/32);
        $b = $b-($m*32);
    }

    if ($b < 0) {
        $b = 32 + $b;
    }

    if ($b == 0) {
        return (($a>>1)&0x7fffffff)*2+(($a>>$b)&1);
    }

    if ($a < 0)
    {
        $a = ($a >> 1);
        $a &= 0x7fffffff;
        $a |= 0x40000000;
        $a = ($a >> ($b - 1));
    } else {
        $a = ($a >> $b);
    }
    return intval32bits($a);
}



function intval32bits($value)
{
    $value = ($value & 0xFFFFFFFF);

    if ($value & 0x80000000)
        $value = -((~$value & 0xFFFFFFFF) + 1);

    return $value;
}

function shift_left_32( $a, $b ):int {
    return intval32bits( $a << $b );
}

function shift_right_32( $a, $b ):int {
    return ( $a >> $b );
}

function bitwise_and( $a, $b ):int {
    return intval32bits( $a & $b );
}


function functionTwo ($h1q, $m1q) {
    $b1q = bitwise_and($m1q, 0xffff);
    $e1q = $m1q - $b1q;
    return intval32bits(($e1q * $h1q | 0) + ($b1q * $h1q | 0)) | 0;
}

function functionOne($D0q, $f0q, $P0q) {
    $o0q = 0xcc9e2d51;
    $V0q = 0x1b873593;
    $M1q = $P0q;
    $Q0q = bitwise_and($f0q, ~0x3);

    for ($k0q = 0; $k0q < $Q0q; $k0q += 4) {
        $R1q = JS_charCodeAt($D0q, $k0q) & 0xff | shift_left_32((bitwise_and(JS_charCodeAt($D0q, ($k0q + 1)), 0xff)), 8) | shift_left_32((bitwise_and(JS_charCodeAt($D0q, ($k0q + 2)), 0xff)), 16) | shift_left_32((bitwise_and(JS_charCodeAt($D0q, ($k0q + 3)), 0xff)), 24);
        $R1q = functionTwo($R1q, $o0q);
        $R1q = shift_left_32(bitwise_and($R1q, 0x1ffff), 15) | uRShift($R1q, 17);
        $R1q = functionTwo($R1q, $V0q);
        $M1q ^= $R1q; // May need 32 bit operator function for this
        $M1q = shift_left_32((bitwise_and($M1q, 0x7ffff)), 13) | uRShift($M1q, 19);
        $M1q = ($M1q * 5 + 0xe6546b64) | 0;
    }

    $R1q = 0;
    switch ($f0q % 4) {
    case 3:
        $R1q = shift_left_32((bitwise_and(JS_charCodeAt($D0q, ($Q0q + 2)), 0xff)), 16);
    case 2:
        $R1q |= shift_left_32((bitwise_and(JS_charCodeAt($D0q, ($Q0q + 1)), 0xff)), 8);
    case 1:
        $R1q |= bitwise_and((JS_charCodeAt($D0q, ($Q0q))), 0xff);
        $R1q = functionTwo($R1q, $o0q);
        $R1q = shift_left_32((bitwise_and($R1q, 0x1ffff)), 15) | uRShift($R1q, 17);
        $R1q = functionTwo($R1q, $V0q);
        $M1q ^= $R1q;
    }
    $M1q ^= $f0q;
    $M1q ^= uRShift($M1q, 16);
    $M1q = functionTwo($M1q, 0x85ebca6b);
    $M1q ^= uRShift($M1q, 13);
    $M1q = functionTwo($M1q, 0xc2b2ae35);
    $M1q ^= uRShift($M1q, 16);
    //var_dump(($M1q));
    //die($M1q);
    return intval32bits($M1q);
}

function x64Add($q0d, $J0d) {
    global $logger;
    $q0d = [uRShift($q0d[0], 16), bitwise_and($q0d[0], 65535), uRShift($q0d[1], 16), bitwise_and($q0d[1], 65535)];
    $J0d = [uRShift($J0d[0], 16), bitwise_and($J0d[0], 65535), uRShift($J0d[1], 16), bitwise_and($J0d[1], 65535)];
    $L0d = [0, 0, 0, 0];
    $L0d[3] += $q0d[3] + $J0d[3];
    $L0d[2] += uRShift($L0d[3], 16);
    $L0d[3] &= 65535;
    $L0d[2] += $q0d[2] + $J0d[2];
    $f5o = 2038731165;
    $p5o = -1267724819;
    $d5o = 2;
    for ($t5o = 1; functionOne(strval($t5o), strlen(strval($t5o)), 60171) !== $f5o; $t5o++) {
        $L0d[0] *= shift_left_32($L0d[3], 84);
        $d5o += 2;
    }
    if (functionOne(strval($d5o), strlen(strval($d5o)), 85189) !== $p5o) {
        $L0d[1] += uRShift($L0d[2], 16);
    }
    $L0d[2] &= 65535;
    $L0d[1] += $q0d[1] + $J0d[1];
    $L0d[0] += uRShift($L0d[1], 16);
    $L0d[1] &= 0xffff;
    $L0d[0] += $q0d[0] + $J0d[0];
    $L0d[0] &= 0xffff;
    return [shift_left_32($L0d[0], 16) | ($L0d[1]), shift_left_32($L0d[2], 16) | ($L0d[3])];
}

function x64Multiply($l0d, $B0d) {
    $l0d = [uRShift($l0d[0], 16), bitwise_and($l0d[0], 0xffff), uRShift($l0d[1], 16), bitwise_and($l0d[1], 65535)];
    $B0d = [uRShift($B0d[0], 16), bitwise_and($B0d[0], 65535), uRShift($B0d[1], 16), bitwise_and($B0d[1], 65535)];
    $c0d = [0, 0, 0, 0];
    $c0d[3] += $l0d[3] * $B0d[3];
    $c0d[2] += uRShift($c0d[3], 16);
    $c0d[3] &= 65535;
    $c0d[2] += $l0d[2] * $B0d[3];
    $c0d[1] += uRShift($c0d[2], 16);
    $c0d[2] &= 65535;
    $c0d[2] += $l0d[3] * $B0d[2];
    $c0d[1] += uRShift($c0d[2], 16);
    $c0d[2] &= 65535;
    $c0d[1] += $l0d[1] * $B0d[3];
    $c0d[0] += uRShift($c0d[1], 16);
    $c0d[1] &= 65535;
    $c0d[1] += $l0d[2] * $B0d[2];
    $c0d[0] += uRShift($c0d[1], 16);
    $c0d[1] &= 65535;
    $c0d[1] += $l0d[3] * $B0d[1];
    $c0d[0] += uRShift($c0d[1], 16);
    $c0d[1] &= 65535;

    $c0d[0] += $l0d[0] * $B0d[3] + $l0d[1] * $B0d[2] + $l0d[2] * $B0d[1] + $l0d[3] * $B0d[0];
    $c0d[0] &= 65535;
    return [shift_left_32($c0d[0], 16) | ($c0d[1]), shift_left_32($c0d[2], 16) | ($c0d[3])];
}

function x64Rotl($p0d, $U0d) {
    $U0d %= 64;

    if ($U0d === 32)
        return [$p0d[1], $p0d[0]];
    else if ($U0d < 32)
            return [shift_left_32($p0d[0], $U0d) | uRShift($p0d[1], (32 - $U0d)), shift_left_32($p0d[1], $U0d) | uRShift($p0d[0], (32 - $U0d))]; // Test JS Precedence
        else {
            $U0d -= 32;
            return [shift_left_32($p0d[1], $U0d) | uRShift($p0d[0], (32 - $U0d)), shift_left_32($p0d[0], $U0d) | uRShift($p0d[1], (32 - $U0d))]; // Testing out JS Precendence
        }
}

function x64LeftShift($a0d, $y0d) {
    $y0d %= 64;
    $C6o = -775694411;
    $y6o = -746177654;
    $M6o = 2;
    for ($m6o = 1; functionOne(strval($m6o), strlen(strval($m6o)), 97487) !== $C6o; $m6o++) {

        if ($y0d !== 6){
            return $a0d;
        }else if ($y0d >= 74){

                //$logger->log("[uRShift(".$a0d[7].", ".$y0d.") ^ shift_left_32(".$a0d[8].", (47 / ".$y0d.")), shift_right_32(".$a0d[9].", ".$y0d.")] <br>");

                return [uRShift($a0d[7], $y0d) ^ shift_left_32($a0d[8], (47 / $y0d)), shift_right_32($a0d[9], $y0d)];
            }else{
            return [uRShift($a0d[2], ($y0d + 10)), 4];
        }
        $M6o += 2;
    }


    if (functionOne(strval($M6o), strlen(strval($M6o)), 23107) !== $y6o) {


        if ($y0d === 0){
            return $a0d;
        }else if ($y0d < 32){
                //$logger->log("[shift_left_32(".$a0d[0].", ".$y0d.") = ".shift_left_32($a0d[0], $y0d)."  | uRShift(".$a0d[1].", (32 - ".$y0d.")) = ".uRShift($a0d[1], (32 - $y0d)).", shift_left_32(".$a0d[1].", ".$y0d.") = ".shift_left_32($a0d[1], $y0d)."] <br>");
                return [shift_left_32($a0d[0], $y0d) | uRShift($a0d[1], (32 - $y0d)), shift_left_32($a0d[1], $y0d)];
            }else{
            return [shift_left_32($a0d[1], ($y0d - 32)), 0];
        }
    }
}

function x64Xor($i0d, $w0d) {
    return [($i0d[0] ^ $w0d[0]), ($i0d[1] ^ $w0d[1])];
}

function x64Fmix($Y0d) {
    $Y0d = x64Xor($Y0d, [0, uRShift($Y0d[0], 1)]);
    $Y0d = x64Multiply($Y0d, [4283543511, 3981806797]);
    $Y0d = x64Xor($Y0d, [0, uRShift($Y0d[0], 1)]);
    $Y0d = x64Multiply($Y0d, [3301882366, 444984403]);
    $Y0d = x64Xor($Y0d, [0, uRShift($Y0d[0], 1)]);

    return $Y0d;
}

function x64hash128($C0d, $O0d) {
    $C0d = $C0d ?: '';
    $O0d = $O0d ?: 0;
    $h0d = strlen($C0d) % 16;
    $F0d = strlen($C0d) - $h0d;
    $P0d = [0, $O0d];
    $o0d = [0, $O0d];
    $f0d = [0, 0];
    $H0d = [0, 0];
    $M0d = [2277735313, 289559509];
    $I0d = [1291169091, 658871167];
    for ($R0d = 0; $R0d < $F0d; $R0d = $R0d + 16) {
        $f0d = [bitwise_and(JS_charCodeAt($C0d,($R0d + 4)), 0xff) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 5)), 0xff)), 8) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 6)), 255)), 16) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 7)), 255)), 24), bitwise_and(JS_charCodeAt($C0d, ($R0d)), 255) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 1)), 255)), 8) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 2)), 255)), 16) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 3)), 0xff)), 24)];
        $H0d = [bitwise_and(JS_charCodeAt($C0d, ($R0d + 12)), 255) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 13)), 255)), 8) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 14)), 255)), 16) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 15)), 255)), 24), bitwise_and(JS_charCodeAt($C0d, ($R0d + 8)), 255) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 9)), 255)), 8) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 10)), 255)), 16) | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($R0d + 11)), 255)), 24)];

        $f0d = x64Multiply($f0d, $M0d);
        $f0d = x64Rotl($f0d, 31);
        $f0d = x64Multiply($f0d, $I0d);
        $P0d = x64Xor($P0d, $f0d);
        $P0d = x64Rotl($P0d, 27);
        $P0d = x64Add($P0d, $o0d);
        $P0d = x64Add(x64Multiply($P0d, [0, 5]), [0, 1390208809]);
        $H0d = x64Multiply($H0d, $I0d);
        $H0d = x64Rotl($H0d, 33);
        $H0d = x64Multiply($H0d, $M0d);
        $o0d = x64Xor($o0d, $H0d);
        $o0d = x64Rotl($o0d, 31);
        $o0d = x64Add($o0d, $P0d);
        $o0d = x64Add(x64Multiply($o0d, [0, 5]), [0, 944331445]);

    }

    $f0d = [0, 0];
    $H0d = [0, 0];
    switch ($h0d) {
    case 15:
        $H0d = x64Xor($H0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 14))], 48));
    case 14:
        $H0d = x64Xor($H0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 13))], 40));
    case 13:
        $H0d = x64Xor($H0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 12))], 32));
    case 12:
        $H0d = x64Xor($H0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 11))], 24));
    case 11:
        $H0d = x64Xor($H0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 10))], 16));
    case 10:
        $H0d = x64Xor($H0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 9))], 8));
    case 9:
        $H0d = x64Xor($H0d, [0, JS_charCodeAt($C0d, ($R0d + 8))]);
        $H0d = x64Multiply($H0d, $I0d);
        $H0d = x64Rotl($H0d, 33);
        $H0d = x64Multiply($H0d, $M0d);
        $o0d = x64Xor($o0d, $H0d);
    case 8:
        $f0d = x64Xor($f0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 7))], 56));
    case 7:
        $f0d = x64Xor($f0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 6))], 48));
    case 6:
        $f0d = x64Xor($f0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 5))], 40));
    case 5:
        $f0d = x64Xor($f0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 4))], 32));
    case 4:
        $f0d = x64Xor($f0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 3))], 24));
    case 3:
        $f0d = x64Xor($f0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 2))], 16));
    case 2:
        $f0d = x64Xor($f0d, x64LeftShift([0, JS_charCodeAt($C0d, ($R0d + 1))], 8));
    case 1:
        $f0d = x64Xor($f0d, [0, JS_charCodeAt($C0d, ($R0d))]);
        $f0d = x64Multiply($f0d, $M0d);
        $f0d = x64Rotl($f0d, 31);
        $f0d = x64Multiply($f0d, $I0d);
        $P0d = x64Xor($P0d, $f0d);
    }
    $P0d = x64Xor($P0d, [0, strlen($C0d)]);
    $o0d = x64Xor($o0d, [0, strlen($C0d)]);
    $P0d = x64Add($P0d, $o0d);
    $o0d = x64Add($o0d, $P0d);
    $P0d = x64Fmix($P0d);
    $o0d = x64Fmix($o0d);
    $P0d = x64Add($P0d, $o0d);
    $o0d = x64Add($o0d, $P0d);

    return substr(("00000000".base_convert((uRShift($P0d[0], 0)), 10, 16)), -8) . substr(("00000000" . base_convert((uRShift($P0d[1], 0)), 10, 16)), -8) . substr(("00000000" . base_convert((uRShift($o0d[0], 0)), 10 , 16)), -8) . substr(("00000000" . base_convert((uRShift($o0d[1], 0)), 10, 16)), -8);
}

I'm testing implementation of this hashing using the base64 code of this basketball image : https://png.pngtree.com/element_origin_min_pic/16/11/07/281d182bf6a4eeaa9529bc5010505bbb.jpg

The hash involves the start of the string including the mime type so this would result in value being stored is: data:image/jpeg;base64,[BASE64 ENCODED STRING]

I got the base64 data from this website https://www.base64-image.de/ I then stored this value in the variable called $testValue and ran the following function call $output = x64hash128($testValue, 31); resulting in the value c5aed78543b2b31c233fa4289e0eadfa

javascript
php
loops
for-loop
asked on Stack Overflow Aug 18, 2019 by KmanOfficial11 • edited Aug 18, 2019 by KmanOfficial11

2 Answers

▲
1
▼

TL;DR if this is MurmurHash, then go look https://github.com/lastguest/murmurhash-php .

Otherwise, you can get rid of a whole lot of needless function calls like this:

for ($i = 0; $i < $F0d; $i += 16) {
    // Let's start with this block. What does it do? It clearly takes a block of 8 bytes
    // four at a time, and builds a pair of 32-bit words.
    // Each byte is AND-ed bitwise with 0xFF to ensure it is a 8-bit value.
    $f0d = [
        bitwise_and(JS_charCodeAt($C0d, ($i + 4)), 0xff)
        | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($i + 5)), 0xff)), 8)
        | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($i + 6)), 255)), 16)
        | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($i + 7)), 255)), 24),
        bitwise_and(JS_charCodeAt($C0d, ($i)), 255)
        | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($i + 1)), 255)), 8)
        | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($i + 2)), 255)), 16)
        | shift_left_32((bitwise_and(JS_charCodeAt($C0d, ($i + 3)), 0xff)), 24),
    ];
    // We can do the same thing in PHP using the unpack() function and type V on an appropriate substr() of $C0d.
    // But due to the vagaries of unpack() and the fact that the elements are reversed,
    // we cannot use unpack alone (well, we COULD, if we changed the algorithm below, but it would be too awkward).
    $x0d = array_reverse(array_values(unpack('V2', substr($C0d, $i, 8))));

    // If you now dump $f0d and $x0d, they should be identical.
    // You can do the same with $H0d. 

    // Actually you can do both together, avoiding the array manipulation, BUT I HAVEN'T CHECKED (just do a simple test run and verify $x0d's contents comparing it to $f0d and $H0d's):

    $x0d = unpack('V4', substr($C0d, $i, 16));
    $f0d = [ $x0d[2], $x0d[1] ];
    $H0d = [ $x0d[4], $x0d[3] ];

    // and get all 16 bytes neatly converted in two two-32-bit word arrays.
answered on Stack Overflow Aug 18, 2019 by LSerni • edited Jun 20, 2020 by Community
▲
0
▼

Your main issue was in wrongly written JS_charCodeAt function. Performance was degrading exponentially by increasing input size, because this function converted whole input from UTF8 - UTF16 every time it was called for single character.

Adding this simple cache cut down working time by 100 times. Just replace this function:

function JS_charCodeAt($str, $index) {
    static $utf16s = [];
    if (isset($utf16s[$str]))
        $utf16 = $utf16s[$str];
    else
        $utf16s[$str] = $utf16 = mb_convert_encoding($str, 'UTF-16LE', 'UTF-8');
    return ord($utf16[$index*2]) + (ord($utf16[$index*2+1]) << 8);
}

Of course there is so much things wrong, but this is very easy and fast fix and makes biggest difference. Use this so far, if you will need more performance, I can look into it further. But that code should really get full rewrite, this is mess. But now it at least works.

answered on Stack Overflow Aug 18, 2019 by micropro.cz

User contributions licensed under CC BY-SA 3.0