Atualização sobre geração de valores aleatórios

Em posts anteriores eu disse que a instrução RDRAND era lenta em relação à chamada da função rand(), da libc. Bem… A informação está errada! Ela foi baseada no fato de que os processadores mais modernos incorporam um DRNG (Digital Random Number Generator) ou, se preferirem, um quase TRNG (True Random Number Generator). Não é bem um TRNG porque o gerador usado pela Intel sofre algum condicionamento para adequar-se à padrões criptográficos impostos pelo NIST. Mas, ele é, de fato, um TRNG porque a entropia é obtida por um meio físico caótico (um fenômeno quântico!), no caso, o ruído eletrônico causado pela temperatura do processador…

Dito tudo isso, a Intel nos diz que o circuito do DRNG tem um clock isolado de 800 MHz e o valor condicionado pode ser obtido, em teoria, a cada 10 ciclos, mas que é mais provável que um valor possa ser colhido a cada 10 μs.

Dez microssegundos é uma eternidade em relação aos ciclos de clock “principais” do processador e, por isso, eu disse antes: É lerdo!!! E nisso eu estava errado. O programinha abaixo usa 3 métodos para obter um valor aleatório e mede o tempo gasto com meu “medidor de ciclos do homem pobre”:

// test.c
// Compile com:
//
//    $ cc -O2 -o test test.c
//

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <sys/time.h>
#include "cycle_counting.h"

static unsigned int rand_rdrand(void);
static unsigned int rand_urandom(void);

int main(void)
{
  unsigned int r1, r2, r3;
  unsigned long c1, c2, c3;
  struct timeval tv;

  // Informa 'semente' para o LCG, a mais 'única' possível,
  // de forma rápida.
  gettimeofday(&tv, NULL);
  srand(tv.tv_sec * 1000000 + tv.tv_usec);  // overflow?

  BEGIN_TSC;
  r1 = rand();
  END_TSC(c1);

  BEGIN_TSC;
  r2 = rand_rdrand();
  END_TSC(c2);
  
  BEGIN_TSC;
  r3 = rand_urandom();
  END_TSC(c3);

  printf("rand():       %10u (%lu cycles)\n"
         "rdrand:       %10u (%lu cycles)\n"
         "/dev/urandom: %10u (%lu cycles)\n",
         r1, c1,
         r2, c2,
         r3, c3);

  return 0;
}

// Usando a instrução RDRAND...
static unsigned int rand_rdrand(void)
{
  unsigned int r;

  __asm__ __volatile__ ("1: rdrand %0\n"
                        "   jnc 1b"
                        : "=a" (r));

  return r;
}

// Usando o dispositivo /dev/urandom
static unsigned int rand_urandom(void)
{
  int fd;
  unsigned int r = 0;

  if ((fd = open("/dev/urandom", O_RDONLY)) != -1)
  {
    if (read(fd, &r, sizeof r) == -1)
      r = 0;

    close(fd);
  }

  // retorna 0 em caso de erro!
  return r;
}

Em teoria a instrução rand() deveria ser mais rápida das 3, já que efetua apenas uma multiplicação, uma adição e uma divisão. No entanto, isso não é o que se observa:

$ ./rdrand
rand():       2006714670 (2380 cycles)
rdrand:       4079123206 (560 cycles)
/dev/urandom:  438031533 (50464 cycles)

Ou seja, rdrand() é 4 vezes mais rápida que rand(). Ler /dev/urandom é 21 vezes mais lento que rand() e 90 vezes mais lento que rdrand!

Claro, você precisa verificar se RDRAND é implementada por seu processador:

int check_rdrand(void)
{
  int r;

  __asm__ __volatile__ ("cpuid" : "=c" (r) : "a" (1) :
#ifdef __x86-64
                                  "rbx", "rdx");
#elif  __i386
                                  "ebx", "edx");
#else
  #error i386 or x86-64 only!
#endif

  return r & (1U << 30);
}

Ahhh… e existe outra vantagem de usar RDRAND ao invés de rand(). A última limita o valor retornado à constante MAX_RAND que, normalmente, tem 31 bits de tamanho (sim! 31, não 32!). RDRAND, por outro lado, pode retornar 16, 32 ou 64 bits em uma única instrução (ou duas, se considerar o salto condicional para o caso de erros).

Anúncios