Categorias
PHP

High-performance Fibonacci numbers generator in PHP

Based on the article High-performance Fibonacci numbers generator in Go I wrote my version using PHP. Despite the differences between PHP and Go architectures reflected in response times, we can face a huge performance difference when using an optimized function. We may notice that we can have the same results, but the quality of the written code can change lots of things.

Recursive approach

function fibonacci(int $n):int {
  if ($n <= 1) {
    return $n;
  }

  return fibonacci($n-1) + fibonacci($n-2);
}

Benchmark and test

function test_fibonacci() {
  $data = [
    [0,0], [1,1], [2,1], [3,2], [4,3], [5,5], [6,8], [10,55], [42,267914296]
  ];

  foreach($data as $test) {
    $result = fibonacci($test[0]);
    if ($result !== $test[1]) {
      throw new \UnexpectedValueException("Error Processing Request. N: {$test[0]}, got: {$result}, expected: {$test[1]}", 1);
    }
  }

  echo "Tests - Success.".PHP_EOL;
}

/**
  * From https://gist.github.com/blongden/2352583
  */
function benchmark($x)
{
    $start = $t = microtime(true);
    $total = $c = $loop = 0;
    while (true) {
        $x();
        $c++;
        $now = microtime(true);
        if ($now - $t > 1) {
            $loop++;
            $total += $c;
            list($t, $c) = array(microtime(true), 0);
        }
        if ($now - $start > 2) {
            return round($total / $loop);
        }
    }
}
Benchmark 10 run: 163,754/sec or 0.0061067210571955ms/op
Benchmark 20 run: 1,351/sec or 0.74019245003701ms/op

As we can see, calculations of 20 Fibonacci numbers takes 123 times longer than 10 Fibonacci numbers. Not well performed at all! The explanation can be found in the linked article.

Sequential approach

function fibonacci_tuned(int $n):float {
  if ($n <= 1) {
    return $n;
  }

  $n2 = 0;
  $n1 = 1;

  for ($i = 2; $i < $n; $i++) {
    $n2_ = $n2;
    $n2 = $n1;
    $n1 = ($n1 + $n2_);
  }

  return $n2 + $n1;
}

function test_fibonacci_tuned() {
  $data = [
    [0,0], [1,1], [2,1], [3,2], [4,3], [5,5], [6,8], [10,55], [42,267914296]
  ];

  foreach($data as $test) {
    $result = fibonacci_tuned($test[0]);
    $float_test_value = (float) $test[1];
    if ($result !== $float_test_value) {
      throw new \UnexpectedValueException("Error Processing Request. N: {$test[0]}, got: {$result}, expected: {$float_test_value}", 1);
    }
  }

  echo "Tests - Success.".PHP_EOL;
}

Results:

Benchmark 10 tuned run: 3,345,999/sec or 0.00029886440492062ms/op
Benchmark 20 tuned run: 2,069,100/sec or 0.00048330191870862ms/op

As a much better scenario, calculate 20 numbers takes almost 2 times longer than 10 numbers. Makes sense. And performs well!

Considering the two approaches, the recursive approach runs 10 Fibonacci numbers operations 20 times longer than sequential one and 1,824 times longer for 20 Fibonacci numbers.

Fibonacci implementation in PHP can be found at https://github.com/rafaelbernard/php-fibonacci.

Categorias
PHP

Codility – MissingInteger

I scored 100% in #php on @Codility!
https://codility.com/demo/take-sample-test/missing_integer/

Training ticket

Session
ID: training5FZX3Y-S7H
Time limit: 120 min.

Status: closed
Created on: 2016-01-17 05:31 UTC
Started on: 2016-01-17 05:31 UTC
Finished on: 2016-01-17 05:35 UTC

Categorias
PHP

Codility – TapeEquilibrium

I scored 100% in #php on @Codility!
https://codility.com/demo/take-sample-test/tape_equilibrium/

Training ticket (real time - 1 hour)

Session
ID: trainingK8ND7B-7TN
Time limit: 120 min.

Status: closed
Created on: 2016-01-17 05:21 UTC
Started on: 2016-01-17 05:21 UTC
Finished on: 2016-01-17 05:22 UTC

Categorias
PHP

Codility – PermMissingElem

I scored 100% in #php on @Codility!
https://codility.com/demo/take-sample-test/perm_missing_elem/

Training ticket

Session
ID: trainingWEF9F8-YEU
Time limit: 120 min.

Status: closed
Created on: 2016-01-17 03:25 UTC
Started on: 2016-01-17 03:25 UTC
Finished on: 2016-01-17 03:40 UTC

Training ticket (real finishing time)

Session
ID: trainingCSVQV7-4KF
Time limit: 120 min.

Status: closed
Created on: 2016-01-17 04:29 UTC
Started on: 2016-01-17 04:29 UTC
Finished on: 2016-01-17 04:30 UTC

Categorias
PHP

Codility – OddOccurrencesInArray

I scored 66% in #php on @Codility!
https://codility.com/demo/take-sample-test/odd_occurrences_in_array/

I don't know how to do better yet.

Training ticket

Session
ID: training8BGA3Q-8PA
Time limit: 120 min.

Status: closed
Created on: 2016-01-17 03:06 UTC
Started on: 2016-01-17 03:06 UTC
Finished on: 2016-01-17 03:07 UTC

Categorias
PHP

Codility – FrogJmp

I scored 100% in #php on @Codility!
https://codility.com/demo/take-sample-test/frog_jmp/

Training ticket

Session
ID: trainingXKJK2U-3C6
Time limit: 120 min.

Status: closed
Created on: 2016-01-17 02:47 UTC
Started on: 2016-01-17 02:47 UTC
Finished on: 2016-01-17 02:56 UTC

Categorias
PHP

Codility – BinaryGap

I scored 100% in #php on @Codility!
https://codility.com/demo/take-sample-test/binary_gap/

Categorias
PHP

Codility – CyclicRotation

I scored 100% in #php on @Codility!
https://codility.com/demo/take-sample-test/cyclic_rotation/

100% de aproveitamento!

Categorias
PHP

Force errors to raise an exception in PHP

<?php

function exception_error_handler($severity, $message, $filename, $lineno) {
    if (error_reporting() == 0) {
        return;
    }
    if (error_reporting() & $severity) {
        throw new ErrorException($message, 0, $severity, $filename, $lineno);
    }
}

set_error_handler("exception_error_handler");
Categorias
PHP

Segurança no PHP II

Requisito 4: Sem erros para o usuário

Falaremos aqui de outro ponto importantíssimo na questão de segurança que é freqüentemente ignorado pelos desenvolvedores: as mensagens de erro.

As mensagens de erro foram feitas para que o desenvolvedor possa trabalhar de forma mais prática e descobrir o que ele está fazendo de errado. Observem, entretando, que, quando uma aplicação atinge maturidade suficiente para "entrar em produção", torna-se imperativo que o usuário não visualize mensagens de erro.

A razão disso é muito simples: as mensagens de erro freqüentemente trazem informações sensíveis. Observe como exemplo uma típica mensagem de falha de conexão com a base de dados:

Warning: mysql_connect() [function.mysql-connect]:
Access denied for user 'foo'@'localhost' (using password: YES)
in /usr/local/apache/htdocs/script.php on line 2

Note, através das partes destacadas, que esta mensagem me informa:

  1. O tipo de RDBMS: mysql
  2. O usuário de conexão com a base: foo
  3. Que este usuário está tentando uma conexão de dentro do servidor: localhost
  4. O caminho absoluto da raiz web: /usr/local/apache/htdocs
  5. O nome do script: script.php

É por isso que, quando colocamos uma aplicação em produção, ocultamos as mensagens de erro e as gravamos diretamente em um arquivo de log. Isto é muito simples de implementar:

Exemplo:

display_errors = Off
log_errors = On
error_log = /log/php_errors.log

Requisito #5: Esconda do servidor web o que ele não precisa acessar

Quantos de nós não usamos em nossas aplicações um arquivo, tipicamente chamado de config.php ou setup.php, onde guardamos, por exemplo, usuário e senha da base de dados?

Não há nada de errado nisso, mas cuidado: se este arquivo não gera saída de informação em HTML, por que deixá-lo acessível via web?

Para esclarecermos o problema, vamos definir 3 coisas:

  1. minha raiz web é: /usr/local/apache/htdocs
  2. meu arquivo de configuração fica localizado em /usr/local/htdocs/config/config.php
  3. este é um código típico que usa este arquivo:

require_once("/urs/local/htdocs/config/config.php");
/ bla bla bla /

Observe que o erro neste caso é confundir interpretador PHP e servidor web. O Apache (ou IIS, Xitami etc) não precisa saber onde está este arquivo. Isto é responsabilidade do interpretador.

Outro problema é que se arquivo fica desnecessariamente exposto, afinal de contas basta eu abrir um navegador e digitar:

http://www.meusite.com.br/config/config.php

Não faz sentido. Por mais que você possa argumentar que não há forma de ler o código-fonte deste arquivo, ainda assim, isto não muda o fato de que ele está desnecessariamente exposto.

A solução é simples: movemos o arquivo para fora da raiz web:

/usr/local/config/config.php

E depois apenas acertamos as permissões e corrigimos nosso código:

require_once("/urs/local/config/config.php");
/ bla bla bla /

A partir de agora nosso arquivo de configuração só pode ser lido por quem precisa dele: o interpretador PHP.

Requisito #6: Use criptografia

Dados sigilosos são chamados assim por um motivo. Quando tratamos especificamente de senhas é impressionante a quantidade de aplicações web que gravam senhas em texto puro na base de dados.

Ora, se a senha possui a importância que tem e quem a escolhe é o usuário, por que alguém mais precisa ler essa senha?

Se a senha possui este peso em nossa aplicação, não podemos nos dar o luxo de fazer com que ela trafegue pela aplicação totalmente exposta.

PHP implementa criptografia de várias formas, mas eu sugiro - para quem puder usar, pois exige instalação e configuração extra - a utilização da função mcrypt.

Os hashes MD5 e SHA-1 são opções válidas, mas o problema é a sua fragilidade: para o MD5 existe até dicionário de dados, enquanto o SHA-1 foi recentemente "quebrado" por um pesquisador chinês.

Conclusão

A implementação de regras básicas de segurança depende apena da boa vontade do desenvolvedor. Você deve ter percebido como a maior parte das soluções aqui apresentadas significam simples mudanças de hábito.

É mais do que tempo de nós, desenvolvedores PHP, deixarmos de lado nossos antigos vícios e começarmos a implementar boas práticas de programação.

Ganha o profissional, ganha a sua aplicação, ganha o seu cliente, ganha o mercado. Só quem perde nessa situação é quem tenta se aproveitar de nossa aplicação.

Referências e links sugeridos

[PHP Security Consortium] - http://phpsec.org/

Er Galvão Abbott trabalha há mais de dez anos com programação de websites e sistemas corporativos com interface web. Autodidata, teve seu primeiro contato com a linguagem HTML em 1995, quando a internet estreava no Brasil. Atualmente, além de lecionar em diversos cursos, tem se dedicado ao desenvolvimento de sistemas baseados na web, tendo nas linguagens PHP, Perl e JavaScript suas principais paixões.

Parte I