Florian Engelhardt

Husband and dad

1brc?

The input

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
Hamburg;34.2
St. John's;15.2
Cracow;12.6
...

The output

{
    Abha=-23.0/18.0/59.2,
    Abidjan=-16.2/26.0/67.3,
    Abéché=-10.0/29.4/69.0,
    Accra=-10.1/26.4/66.4,
    Addis Ababa=-23.7/16.0/67.0,
    Adelaide=-27.8/17.3/58.5
    ...
}

The rules

no external library dependencies
single source file
computation at runtime

Let’s give it a try, shall we?

 $stations = [];
$fp = fopen('measurements.txt', 'r');
 
while ($data = fgetcsv($fp, null, ';')) {
    if (!isset($stations[$data[0]])) {
        $stations[$data[0]] = [
            $data[1],
            $data[1],
            $data[1],
            1
        ];
    } else {
        $stations[$data[0]][3] ++;
        $stations[$data[0]][2] += $data[1];
        if ($data[1] < $stations[$data[0]][0]) {
            $stations[$data[0]][0] = $data[1];
        }
        if ($data[1] > $stations[$data[0]][1]) {
            $stations[$data[0]][1] = $data[1];
        }
    }
}
 
ksort($stations);
 
echo '{';
foreach($stations as $k=>&$station) {
    $station[2] = $station[2]/$station[3];
    echo $k, '=', $station[0], '/', $station[2], '/', $station[1], ', ';
}
echo '}'; $stations = [];
$fp = fopen('measurements.txt', 'r');
 
while ($data = fgetcsv($fp, null, ';')) {
    if (!isset($stations[$data[0]])) {
        $stations[$data[0]] = [
            $data[1],
            $data[1],
            $data[1],
            1
        ];
    } else {
        $stations[$data[0]][3] ++;
        $stations[$data[0]][2] += $data[1];
        if ($data[1] < $stations[$data[0]][0]) {
            $stations[$data[0]][0] = $data[1];
        }
        if ($data[1] > $stations[$data[0]][1]) {
            $stations[$data[0]][1] = $data[1];
        }
    }
}
 
ksort($stations);
 
echo '{';
foreach($stations as $k=>&$station) {
    $station[2] = $station[2]/$station[3];
    echo $k, '=', $station[0], '/', $station[2], '/', $station[1], ', ';
}
echo '}'; $stations = [];
$fp = fopen('measurements.txt', 'r');
 
while ($data = fgetcsv($fp, null, ';')) {
    if (!isset($stations[$data[0]])) {
        $stations[$data[0]] = [
            $data[1],
            $data[1],
            $data[1],
            1
        ];
    } else {
        $stations[$data[0]][3] ++;
        $stations[$data[0]][2] += $data[1];
        if ($data[1] < $stations[$data[0]][0]) {
            $stations[$data[0]][0] = $data[1];
        }
        if ($data[1] > $stations[$data[0]][1]) {
            $stations[$data[0]][1] = $data[1];
        }
    }
}
 
ksort($stations);
 
echo '{';
foreach($stations as $k=>&$station) {
    $station[2] = $station[2]/$station[3];
    echo $k, '=', $station[0], '/', $station[2], '/', $station[1], ', ';
}
echo '}'; $stations = [];
$fp = fopen('measurements.txt', 'r');
 
while ($data = fgetcsv($fp, null, ';')) {
    if (!isset($stations[$data[0]])) {
        $stations[$data[0]] = [
            $data[1],
            $data[1],
            $data[1],
            1
        ];
    } else {
        $stations[$data[0]][3] ++;
        $stations[$data[0]][2] += $data[1];
        if ($data[1] < $stations[$data[0]][0]) {
            $stations[$data[0]][0] = $data[1];
        }
        if ($data[1] > $stations[$data[0]][1]) {
            $stations[$data[0]][1] = $data[1];
        }
    }
}
 
ksort($stations);
 
echo '{';
foreach($stations as $k=>&$station) {
    $station[2] = $station[2]/$station[3];
    echo $k, '=', $station[0], '/', $station[2], '/', $station[1], ', ';
}
echo '}'; $stations = [];
$fp = fopen('measurements.txt', 'r');
 
while ($data = fgetcsv($fp, null, ';')) {
    if (!isset($stations[$data[0]])) {
        $stations[$data[0]] = [
            $data[1],
            $data[1],
            $data[1],
            1
        ];
    } else {
        $stations[$data[0]][3] ++;
        $stations[$data[0]][2] += $data[1];
        if ($data[1] < $stations[$data[0]][0]) {
            $stations[$data[0]][0] = $data[1];
        }
        if ($data[1] > $stations[$data[0]][1]) {
            $stations[$data[0]][1] = $data[1];
        }
    }
}
 
ksort($stations);
 
echo '{';
foreach($stations as $k=>&$station) {
    $station[2] = $station[2]/$station[3];
    echo $k, '=', $station[0], '/', $station[2], '/', $station[1], ', ';
}
echo '}'; $stations = [];
$fp = fopen('measurements.txt', 'r');
 
while ($data = fgetcsv($fp, null, ';')) {
    if (!isset($stations[$data[0]])) {
        $stations[$data[0]] = [
            $data[1],
            $data[1],
            $data[1],
            1
        ];
    } else {
        $stations[$data[0]][3] ++;
        $stations[$data[0]][2] += $data[1];
        if ($data[1] < $stations[$data[0]][0]) {
            $stations[$data[0]][0] = $data[1];
        }
        if ($data[1] > $stations[$data[0]][1]) {
            $stations[$data[0]][1] = $data[1];
        }
    }
}
 
ksort($stations);
 
echo '{';
foreach($stations as $k=>&$station) {
    $station[2] = $station[2]/$station[3];
    echo $k, '=', $station[0], '/', $station[2], '/', $station[1], ', ';
}
echo '}'; $stations = [];
$fp = fopen('measurements.txt', 'r');
 
while ($data = fgetcsv($fp, null, ';')) {
    if (!isset($stations[$data[0]])) {
        $stations[$data[0]] = [
            $data[1],
            $data[1],
            $data[1],
            1
        ];
    } else {
        $stations[$data[0]][3] ++;
        $stations[$data[0]][2] += $data[1];
        if ($data[1] < $stations[$data[0]][0]) {
            $stations[$data[0]][0] = $data[1];
        }
        if ($data[1] > $stations[$data[0]][1]) {
            $stations[$data[0]][1] = $data[1];
        }
    }
}
 
ksort($stations);
 
echo '{';
foreach($stations as $k=>&$station) {
    $station[2] = $station[2]/$station[3];
    echo $k, '=', $station[0], '/', $station[2], '/', $station[1], ', ';
}
echo '}';

Runtime?

25 minutes

Whats going on?

What is happening in `fgetcsv()`?

Switch to `fgets()`
and `substr()`!

 while ($data = fgets($fp, 108)) {
    $pos = strpos($data, ';');
    $city = substr($data, 0, $pos);
    $temp = substr($data, $pos+1, -1);
// ...

Runtime:
19m 49s

Whats going on?

 while ($data = fgets($fp, 108)) {
    $pos = strpos($data, ';');
    $city = substr($data, 0, $pos);
    $temp = substr($data, $pos+1, -1);
 
    if (!isset($stations[$city])) {
        $stations[$city] = [
            $temp,
            $temp,
            $temp,
            1
        ];
    } else {
        $stations[$city][3] ++;
        $stations[$city][2] += $temp;
        if ($temp < $stations[$city][0]) {
            $stations[$city][0] = $temp;
        }
        if ($temp > $stations[$city][1]) {
            $stations[$city][1] = $temp;
        }
    }
}

References FTW

 while ($data = fgets($fp, 108)) {
    $pos = strpos($data, ';');
    $city = substr($data, 0, $pos);
    $temp = substr($data, $pos+1, -1);
 
    if (!isset($stations[$city])) {
        $stations[$city] = [
            $temp,
            $temp,
            $temp,
            1
        ];
    } else {
        $station = &$stations[$city];
        $station[3] ++;
        $station[2] += $temp;
        if ($temp < $station[0]) {
            $station[0] = $temp;
        }
        if ($temp > $station[1]) {
            $station[1] = $temp;
        }
    }
}

Runtime:
17m 48s

Less compares

 if ($temp < $station[0]) {
    $station[0] = $temp;
}
if ($temp > $station[1]) {
    $station[1] = $temp;
}

 if ($temp < $station[0]) {
    $station[0] = $temp;
} elseif ($temp > $station[1]) {
    $station[1] = $temp;
}

Runtime:
17m 30s

Bad bad type juggling!

 $a = "100";
$b = "25.5";
if ($a > $b) {
    echo "100 > 25.5";
} else {
    echo "25.5 > 100";
}

If both operands are numeric strings, or one operand is a number and the other one is a numeric string, then the comparison is done numerically.

No juggling!

 while ($data = fgets($fp, 108)) {
    $pos = strpos($data, ';');
    $city = substr($data, 0, $pos);
    $temp = (float)substr($data, $pos+1, -1);
 
    if (!isset($stations[$city])) {
        $stations[$city] = [
            $temp,
            $temp,
            $temp,
            1
        ];
    } else {
        $station = &$stations[$city];
        $station[3] ++;
        $station[2] += $temp;
        if ($temp < $station[0]) {
            $station[0] = $temp;
        } elseif ($temp > $station[1]) {
            $station[1] = $temp;
        }
    }
} while ($data = fgets($fp, 108)) {
    $pos = strpos($data, ';');
    $city = substr($data, 0, $pos);
    $temp = (float)substr($data, $pos+1, -1);
 
    if (!isset($stations[$city])) {
        $stations[$city] = [
            $temp,
            $temp,
            $temp,
            1
        ];
    } else {
        $station = &$stations[$city];
        $station[3] ++;
        $station[2] += $temp;
        if ($temp < $station[0]) {
            $station[0] = $temp;
        } elseif ($temp > $station[1]) {
            $station[1] = $temp;
        }
    }
} while ($data = fgets($fp, 108)) {
    $pos = strpos($data, ';');
    $city = substr($data, 0, $pos);
    $temp = (float)substr($data, $pos+1, -1);
 
    if (!isset($stations[$city])) {
        $stations[$city] = [
            $temp,
            $temp,
            $temp,
            1
        ];
    } else {
        $station = &$stations[$city];
        $station[3] ++;
        $station[2] += $temp;
        if ($temp < $station[0]) {
            $station[0] = $temp;
        } elseif ($temp > $station[1]) {
            $station[1] = $temp;
        }
    }
}

Runtime:
13m 32s

Whats going on?

Something important about PHP on CLI

No OPcache …

… and with no OPcache comes …

… no JIT!

opcache.enable_cli = 1; default: 0
opcache.jit-buffer-size = 10M; default: 0

Runtime:
7m 19s

Is there more?

Divide et impera

Demo time!

Runtime:
1m 35s

CFLAGS="-g -O0 ..."

CFLAGS="-Os ..."

Demo time (again)!

Runtime:
27.7 seconds

Bonus!

 if (!isset($stations[$city])) {
    // ..
} else {
    $station = &$stations[$city];
    // ..
}

 $station = &$stations[$city];
if ($station === NULL) {
    // ..
} else {
    // ..
}

Bonus!!

 while ($data = fgets($fp)) {
    $chunk_start += strlen($data);
    if ($chunk_start > $chunk_end) {
        break;
    }
// ..

 while ($chunk_start < $chunk_end) {
    $data = fgets($fp);
    $chunk_start += strlen($data);
// ..

Bonus!!!

 $data = fgets($fp);
$chunk_start += strlen($data);
$pos = strpos($data, ';');
$city = substr($data, 0, $pos);
$temp = (float)substr($data, $pos+1, -1);

 $city = stream_get_line($fp, 99, ';');
$temp = stream_get_line($fp, 99, "\n");
$chunk_start += strlen($city) + strlen($temp) + 2;
$temp = (float)$temp;

	$stations = [];
	$fp = fopen('measurements.txt', 'r');

	while ($data = fgetcsv($fp, null, ';')) {
	if (!isset($stations[$data[0]])) {
	$stations[$data[0]] = [
	$data[1],
	$data[1],
	$data[1],
	1
	];
	} else {
	$stations[$data[0]][3] ++;
	$stations[$data[0]][2] += $data[1];
	if ($data[1] < $stations[$data[0]][0]) {
	$stations[$data[0]][0] = $data[1];
	}
	if ($data[1] > $stations[$data[0]][1]) {
	$stations[$data[0]][1] = $data[1];
	}
	}
	}

	ksort($stations);

	echo '{';
	foreach($stations as $k=>&$station) {
	$station[2] = $station[2]/$station[3];
	echo $k, '=', $station[0], '/', $station[2], '/', $station[1], ', ';
	}
	echo '}';

	while ($data = fgets($fp, 108)) {
	$pos = strpos($data, ';');
	$city = substr($data, 0, $pos);
	$temp = substr($data, $pos+1, -1);
	// ...

	if ($temp < $station[0]) {
	$station[0] = $temp;
	}
	if ($temp > $station[1]) {
	$station[1] = $temp;
	}

	if ($temp < $station[0]) {
	$station[0] = $temp;
	} elseif ($temp > $station[1]) {
	$station[1] = $temp;
	}

	$a = "100";
	$b = "25.5";
	if ($a > $b) {
	echo "100 > 25.5";
	} else {
	echo "25.5 > 100";
	}

	if (!isset($stations[$city])) {
	// ..
	} else {
	$station = &$stations[$city];
	// ..
	}

	$station = &$stations[$city];
	if ($station === NULL) {
	// ..
	} else {
	// ..
	}

	while ($data = fgets($fp)) {
	$chunk_start += strlen($data);
	if ($chunk_start > $chunk_end) {
	break;
	}
	// ..

	while ($chunk_start < $chunk_end) {
	$data = fgets($fp);
	$chunk_start += strlen($data);
	// ..

	$city = stream_get_line($fp, 99, ';');
	$temp = stream_get_line($fp, 99, "\n");
	$chunk_start += strlen($city) + strlen($temp) + 2;
	$temp = (float)$temp;

Processing One Billion Rows … with PHP

Processing One Billion Rows
… with PHP