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.

Um convincente e-mail fraudulento do Bitcoin extorquindo você

Esta publicação foi originalmente publicada em The convincing Bitcoin scam e-mail extorting you, por Mattias Geniar, em inglês. Mas o alerta vale ser traduzido para o português, tendo você assistido ou não do que a acusação se trata.

Mais uma vez vemos a criatividade de aplicadores de golpe. Fique atento. Fique alerta. A internet é uma terra tão selvagem quando as ruas em que andamos.

Há alguns meses recebi um e-mail que me deixou preocupado por alguns segundos. Parecia assim, e é bem provável que você tenha visto também.

From: Kalie Paci 
Subject: mattias - UqtX7m

It seems that, UqtX7m, is your pass word. You do not know me and you are probably thinking
why you are getting this mail, correct?

Well, I actually placed a malware on the adult video clips (porn) web-site and guess what,
you visited this site to have fun (you know what I mean). While you were watching videos,
your browser started operating as a RDP (Remote control Desktop) that has a keylogger which
gave me access to your display and also web camera. Immediately after that, my software
program collected your entire contacts from your Messenger, FB, and email.

What exactly did I do?

I created a double-screen video. First part displays the video you were viewing (you have
a nice taste lol), and second part displays the recording of your web camera.

What should you do?

Well, in my opinion, $1900 is a fair price for our little secret. You’ll make the payment
through Bitcoin (if you do not know this, search “how to buy bitcoin” in Google).

BTC Address: 1MQNUSnquwPM9eQgs7KtjDcQZBfaW7iVge
(It is cAsE sensitive, so copy and paste it)

Important:
You now have one day to make the payment. (I’ve a unique pixel in this message, and right
now I know that you have read this email message). If I don’t get the BitCoins, I will
send your video recording to all of your contacts including members of your family,
colleagues, and many others. Having said that, if I do get paid, I will destroy the video
immidiately. If you need evidence, reply with “Yes!” and I definitely will send your video
recording to your 11 friends. This is a non-negotiable offer, and so please don’t waste
my personal time and yours by responding to this mail.

Se você lê, parece spam – não é?

Bem, o que me preocupou por alguns segundos foi que a linha de assunto e o corpo continham uma senha real que eu usei um tempo atrás: UqtX7m.

Para receber um email com um – o que parece ser – segredo pessoal no assunto, chama a atenção. É inteligente no sentido de que você se sente violado e envergonhado pelas consequências. Parece legítimo.

Deixe-me dizer claramente: é uma farsa e você não precisa pagar ninguém.

Mencionei pela primeira vez no meu Twitter descrevendo o que parece ser a parte brilhante desse golpe:

  • E-mail + senhas, fáceis de obter (muitos vazamentos on-line)
  • Todo mundo assiste pornô
  • Ninguém quer que esta informação vaze
  • O mesmo e-mail genérico pode ser usado para todas as vítimas

Quem quer que esteja executando esse esquema pensou sobre a psicologia do golpe e encontrou o ponto ideal: ele chama sua atenção e deixa você preocupado.

Bem jogado. Mas não se apegue a isso e, mais importante: não pague nada.

Quanto à Combate à pornografia conheça Just1ClickAway. Busque se livrar deste mal.

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

Precisamos de apoio das ferramentas para a paginação por conjunto de chaves

(Traduzido de We need tool support for keyset pagination)

Você sabia que a paginação via offset é muito problemática, mas fácil de evitar?

offset instrui os bancos de dados a pular os primeiros N resultados N de uma consulta. No entanto, o banco de dados ainda deve buscar essas linhas a partir do disco e trazê-los em ordem antes de ele pode enviar os seguintes.

Isto não é um problema de implementação, é a maneira na qual offset foi desenhado:

… As linhas são primeiro classificadas de acordo com a <cláusula order by> e, em seguida, limitada retirando-se o número de linhas especificadas na <cláusula offset> desde o início …

— SQL:2011, Part 2, §4.15.3 Derived tables

Em outras palavras, grandes offsets impõe um grande trabalho para o banco de dados, não importa se SQL ou NoSQL.

Mas o problema com offset não pára aqui: já pensou sobre o que acontece se uma nova linha é inserida entre duas páginas buscadas?

offset-drifting

Quando offset➌ é usado para ignorar as entradas❶ anteriores, você terá duplicações no caso de existirem novas linhas inseridas entre as duas páginas➋. Há outras anomalias possíveis também, este é apenas o caso mais comum.

Este nem é um problema de banco de dados, é a maneira como os frameworks implementam paginação: eles apenas dizem qual é o número da página a ser recuperada ou quantas linhas devem ser ignoradas. Com estas informações apenas, nenhum banco de dados pode fazer melhor.

Vida sem OFFSET

Agora imagine um mundo sem estes problemas. Como se constata, viver sem offset é bem simples: apenas utilize uma cláusula where que selecione apenas os dados que você ainda não viu.

Para isso, exploraremos o fato de que trabalhamos com um conjunto ordenado – você tem uma cláusula order by, não é? Uma vez que há uma ordenação definida, podemos usar um filtro simples para somente selecionar o que é posterior a entrada que vimos anteriormente.

SELECT ...
FROM ...
WHERE ...
AND id < ?last_seen_id
ORDER BY id DESC
FETCH FIRST 10 ROWS ONLY

Esta é a receita básica. Ele fica mais interessante quando a classificação é por várias colunas, mas a idéia é a mesma. Esta receita também é aplicável a muitos sistemas NoSQL.

Esta abordagem – chamada seek method ou keyset pagination – resolve o problema de derivação de resultados como ilustrado acima e é ainda mais rápido do que offset. Se você quer saber o que acontece dentro do banco de dados ao usar offset ou keyset pagination, dê uma olhada nestes slides (benchmarks, benchmarks!):

No slide 43 você também pode ver que keyset pagination tem algumas limitações: mais notavelmente que você não pode navegar diretamente para páginas arbitrariamente. No entanto, isto não é um problema quando se utiliza rolagem infinita. Mostrar o número de páginas para serem clicadas é uma interface de navegação pobre, na minha humilde opinião.

Se você quiser ler mais sobre como implementar corretamente keyset pagination em SQL, por favor fetch-next-page. Mesmo que você não esteja envolvido com o SQL, vale a pena ler fetch-next-page antes de começar a implementar qualquer coisa.

No entando, os frameworks

A principal razão para preferir offset a paginação por conjunto de chaves (keyset pagination) é a falta de suporte. A maioria das ferramentas de paginação são baseadas em offset, mas não oferecem nenhuma maneira conveniente para a utilização de paginação por conjunto de chaves.

Por favor, note que a paginação por conjunto de chaves afeta toda a tecnologia envolvida na execução de JavaScript do navegador que esteja fazendo a requisição AJAX para rolagem infinita: ao invés de simplesmente passar um número de página para o servidor, você deve passar o conjunto de chaves completo (geralmente múltiplas colunas) para o servidor.

O hall da fama de frameworks que suportam paginação por conjunto de chaves é ainda pequeno:

É por isto que preciso da sua ajuda. Se você estiver mantendo um framework que tem algum envolvimento com paginação, eu peço, eu imploro, que você construa um suporte nativo para navegação por conjunto de chaves também. Se você tiver quaisquer perguntas sobre detalhes, ficarei feliz em ajudar (forum, contact form, Twitter)!

Mesmo que você esteja apenas utilizando um software que deveria suportar paginação por conjunto de chaves, como um gerenciador de conteúdos ou uma loja virtual, faça os mantenedores saberem sobre isso. Você poderia fazer uma requisitação da funcionalidade (link a esta página) ou, se possível, desenvolva um patch. Novamente, ficarei feliz em ajudar a ter todos os devidos detalhes.

Tome WordPress como um exemplo.

Espalhe a palavra

O problema com a paginação de conjunto de chaves não é técnico. O problema é que é pouquíssimo conhecido no meio e não há suporte das ferramentas. Se você gosta da idéia de evitar o uso de paginação por offset, por favor, ajude a espalhar a palavra. Use o Twitter, compartilhe, envie por e-mail, você pode até reproduzir este post (CC-BY-NC-ND). Traduções são também bem-vindas, apenas faça um contato prévio – eu também incluirei o link da tradução a esta página.

Ah, e se você estiver em um blog, você também pode acrescentar um banner para que seus leitores fiquem alertas a isto. Eu preparei uma a galeria de banner NoOffset com alguns formatos comuns. Escolha o que ficar melhor.