Cifrado César (PHP vs Python)

Vuelvo con un pequeño problema al que le he estado dando vueltas, el del cifrado césar. No sé vosotros pero almenos a mi en seguridad informática fue el primer problema que nos hicieron desarrollar, por lo que a mi ya me resultaba bastante familiar. Visto que es el problema del mes en 12meses12katas vamos a intentar hacer un benchmark para ver cual es el rendimiento en este problema resuelto en Python y en PHP.

Pensé en como desarrollarlo, y se me ocurrió hacerlo con un histórico en plan git, realizando diferentes pequeñas mejoras y haciendo medidas de rendimiento sobre la solución, viendo como diferentes cambios podían afectar al rendimiento tanto en Python como en PHP. Este histórico de mejoras puede consultarse en el repositorio caesar en el que publiqué la solución en mi cuenta de github.

Bueno, vayamos al pequeño resumen que quería poner aquí del desarrollo. Al principio, pensé en realizar una solución directa, tanto en Python como en PHP. En ella, no se ha hecho uso de funciones ni otros mecanismos de abstracción. Está claro que eso hace que el código no sea tan fácil de seguir, pero para el fin con el que yo quería realizar este ejercicio me resultaba más interesante no meter estos mecanismos de por medio para la medición de rendimiento. Por otro lado, aprovechando que las implementaciones funcionan por entrada y salida estándar, las pruebas se pueden hacer para ambas implementaciones, utilizando un shell script que se puede encontrar en el repositorio de la solución.

Versión PHP

<?php
function error_die($message) {
    $STDERR = fopen('php://stderr', 'w');
    fwrite($STDERR, $message);
    fwrite($STDERR, PHP_EOL);
    fclose($STDERR);
    die();
}

if (count($argv) < 2) {
    error_die('Usage: ./caesar.php N');
}

$N = $argv[1];

if (!is_numeric($N)) {
    error_die("$N should be numeric");
}

define('CHUNK_SIZE', 1024);
$N = intval($N);
$low_bounds = array('a', 'z');
$up_bounds = array('A', 'Z');
$diff = ord('Z') - ord('A') + 1;
$ord_low_bounds = array(ord('a'), ord('z'));
$ord_up_bounds = array(ord('A'), ord('Z'));
$fp = fopen('php://stdin', 'r');

while ( $input = fread($fp, CHUNK_SIZE) ) {
    $buffer = array();
    foreach(str_split($input) as $c) {
        $ord_c = ord($c);
        if ($ord_c >= $ord_low_bounds[0] &&
            $ord_c <= $ord_low_bounds[1]) {
            $x = $ord_c + $N;
            if ($x > $ord_low_bounds[1]) {
                $x -= $diff;
            }

            if ($x < $ord_low_bounds[0]) {
                $x += $diff;
            }
            $c = chr($x);

        }

        if ($ord_c >= $ord_up_bounds[0] &&
            $ord_c <= $ord_up_bounds[1]) {

            $x = $ord_c + $N;
            if ($x > $ord_up_bounds[1]) {
                $x -= $diff;
            }

            if ($x < $ord_up_bounds[0]) {
                $x += $diff;
            }

            $c = chr($x);
        }

        $buffer[] = $c;
    }

    echo implode('', $buffer);
    }

fclose($fp);

Por otro lado, tenemos la solución en python.

Versión Python

import sys

def error_die(message):
    sys.stderr.write(message)
    sys.stderr.write("\n")
    sys.exit(-1)


if len(sys.argv) < 2:
    error_die('Usage: ./caesar.php N')

N = sys.argv[1];

if not N.isdigit() and (N[0:1] != '-' or not N[1:].isdigit()) :
    error_die("{} should be numeric".format(N))

CHUNK_SIZE = 1024
N = int(N)

low_bounds = ['a', 'z']
up_bounds = ['A', 'Z']
diff = ord('Z') - ord('A') + 1
ord_low_bounds = [ord('a'), ord('z')]
ord_up_bounds = [ord('A'), ord('Z')]

while True:
    input = sys.stdin.read(CHUNK_SIZE)
    if len(input) == 0:
        break
    buffer = []
    for c in input:
        if c >= low_bounds[0] and c <= low_bounds[1]:
            c = ord(c) + N
            if c > ord_low_bounds[1]:
                c -= diff
            if c < ord_low_bounds[0]:
                c += diff
            c = chr(c)

        if c >= up_bounds[0] and c <= up_bounds[1]:
            c = ord(c) + N
            if c > ord_up_bounds[1]:
                c -= diff
            if c < ord_up_bounds[0]:
                c += diff

            c = chr(c)

        buffer.append(c)
    sys.stdout.write("".join(buffer))

Como podeis ver, las diferencias son mínimas. La diferencia más curiosa es la que en PHP se está comparando a los caracteres fronteras como enteros y en Python como strings. Aún sigo preguntándome el porqué, pero demostrado por las pruebas de rendimiento, que en Python la solución es más rápida comparando caracteres como strings que como su equivalente numérico y en PHP lo hace más rápido con comparaciones numéricas.

Bueno, en cuanto a resultados, PHP como siempre me decepciona demasiado. Dejando claro las versiones de Python y PHP que estamos usando (Python 2.7.3 y PHP 5.4.9), podemos ver una tabla de tiempos tomada con time ante una entrada que ronda los 10MB.

Evidentemente, los tiempos varían dependiendo de la ejecución. No tomé medias ni medianas, pero la verdad es que pensé que no valía la pena, dada que la diferencia es de 3 órdenes de magnitud y que estos benchmarks tampoco es que sean una verdad absoluta, por lo que perder precisión tampoco me resulta demasiado desconcertante.

En mi opinión, PHP muy mal. Como prácticamente en cualquier comparación que se haga de un problema, la solución en Python siempre suele ser más eficiente. No sé si el motivo viene relacionado con las estructuras de datos, o bien con que simplemente el intérprete es más eficiente.

Bueno, volviendo al problema, es evidente que estamos haciendo más cálculos de los necesarios. Podemos cachear estos resultados con un diccionario/hash/array o como queramos llamarle dependiendo de nuestro lenguaje (hash me parece la nomenclatura más acertada). Esto acelerará en mucho el problema, ya que tomar el dato del diccionario será más rápido que calcularlo de nuevo.

Versión PHP

<?php
function error_die($message) {
    $STDERR = fopen('php://stderr', 'w');
    fwrite($STDERR, $message);
    fwrite($STDERR, PHP_EOL);
    fclose($STDERR);
    die();
}


if (count($argv) < 2) {
    error_die('Usage: ./caesar.php N');
}

$N = $argv[1];

if (!is_numeric($N)) {
    error_die("$N should be numeric");
}

define('CHUNK_SIZE', 1024);

$N = intval($N);

$low_bounds = array('a', 'z');
$up_bounds = array('A', 'Z');
$diff = ord('Z') - ord('A') + 1;
$ord_low_bounds = array(ord('a'), ord('z'));
$ord_up_bounds = array(ord('A'), ord('Z'));

$cache = array();
$fp = fopen('php://stdin', 'r');
while ( $input = fread($fp, CHUNK_SIZE) ) {
    $buffer = array();
    foreach(str_split($input) as $c) {
        $r = @$cache[$c];
        if (!$r) {
            $r = $c;
            $ord_c = ord($c);
            if ($ord_c >= $ord_low_bounds[0]
                && $ord_c <= $ord_low_bounds[1])
            {
                $x = $ord_c + $N;
                if ($x > $ord_low_bounds[1]) {
                    $x -= $diff;
                }
                if ($x < $ord_low_bounds[0]) {
                    $x += $diff;
                }
                $r = chr($x);
            }

            if ($ord_c >= $ord_up_bounds[0]
                && $ord_c <= $ord_up_bounds[1]) {
                $x = $ord_c + $N;
                if ($x > $ord_up_bounds[1]) {
                    $x -= $diff;
                }
                if ($x < $ord_up_bounds[0]) {
                    $x += $diff;
                }

                $r = chr($x);
            }
            $cache[$c] = $r;
        }
        $buffer[] = $r;
    }
    echo implode('', $buffer);
}

fclose($fp);

Antes de pasar a la versión Python, me gustaría comentar el "uso" del operador @ para evitar el error_reporting del notice debido al no estar comprobando la existencia en el array de la clave con la que accedemos al array $cache. Si no estoy mal informado, esto es más eficiente que el tener q comprobar la existencia, por lo que ya que estamos intentando ser lo más rápidos posible, seamos lo suficientemente sucios :)

Versión Python

import sys

def error_die(message):
    sys.stderr.write(message)
    sys.stderr.write("\n")
    sys.exit(-1)


if len(sys.argv) < 2:
    error_die('Usage: ./caesar.php N')

N = sys.argv[1];

if not N.isdigit() and (N[0:1] != '-' or not N[1:].isdigit()) :
    error_die("{} should be numeric".format(N))

CHUNK_SIZE = 1024
N = int(N)

cache = {}
low_bounds = ['a', 'z']
up_bounds = ['A', 'Z']
diff = ord('Z') - ord('A') + 1;
ord_low_bounds = [ord('a'), ord('z')]
ord_up_bounds = [ord('A'), ord('Z')]

while True:
    input = sys.stdin.read(CHUNK_SIZE)
    if len(input) == 0:
        break
    buffer = []
    for c in input:
        r = cache.get(c)
        if r == None:
            r = c
            if c >= low_bounds[0] and c <= low_bounds[1]:
                x = ord(c) + N
                if x > ord_low_bounds[1]:
                    x -= diff
                if x < ord_low_bounds[0]:
                    x += diff
                r = chr(x)

            if c >= up_bounds[0] and c <= up_bounds[1]:
                x = ord(c) + N
                if x > ord_up_bounds[1]:
                    x -= diff
                if x < ord_up_bounds[0]:
                    x += diff

                r = chr(x)
            cache[c] = r

        buffer.append(r)
    sys.stdout.write("".join(buffer))

Y esta sería la tabla con los tiempos.

Volvemos a ver una gran diferencia entre intérpretes. Aunque PHP ha mejorado 4 veces su tiempo, Python sigue siendo más rápido que PHP, aunque ahora del orden de 2 veces y no de 3, por lo que con una solución mejor pensada la diferencia no se hace tan notable.

Conclusiones

Mi opinión es que en el intérprete de PHP hay trabajo por hacer. Cada vez se lo ponen más difícil sus competidores Python y Ruby, lenguajes mucho más expresivos y mucho más elegantes sintácticamente. PHP no tiene ventaja alguna si almenos no muestra mejores prestaciones. Hay opiniones que comentan que el desarrollo en PHP es más rápido, que rindes más. En mi opinión nada más lejos de la realidad. Tienes que hacer más "keystrokes" por culpa de su sintaxis enrevesada, sus comportamientos suelen ser muy inconsitentes y, si no es más rápido que el resto, ¿qué motivo hay para usarlo?

También es cierto, que al estar usando PHP desde CLI, no estoy del todo seguro si se puede sacar alguna mejora de APC. Creo que este módulo es específico de apache para mantener el opcode de los ficheros PHP para no tener que reinterpretarlos en cada petición. En CLI no tiene demasiado sentido, ambos lenguajes compiten igual interpretando su código. Pero es cierto, que en un entorno Web puede que PHP funcionara mejor. Mi desconocimiento en herramientas para otros lenguajes como APC me hace darle aún esa posibilidad a PHP, pero si existen alternativas similares para Python, a PHP la única posibilidad que le queda es desaparecer del mapa.

Implementación en C

Dándole otra vuelta de tuerca, también he desarrollado una versión del algoritmo de cifrado en C. Esta versión se encuentra en el repositorio y, para mí, no tiene perdida. Hacía mucho tiempo que no tocaba C, así que si tiene algún fallo gordo, no dudéis en comentarlo. Acabo con la tabla de tiempos de la versión con cache de resultados en los tres lenguajes para observar la gran diferencia de rendimiento que ofrece bajar al nivel de C.

C se muestra del orden de 60 veces más rápido que Python y del orden de casi 120 veces más rápido que PHP. Y eso compilando sin usar opción alguna de optimización. Asombroso.