Demonstrando a lentidão da STL

C++ tem alguns recursos interessantes. Um deles é a biblioteca de templates conhecida como STL (Standard Template Library), criada por Alexander Stepanov e implementada em C++ em 1994. Dentre outras coisas a biblioteca implementa uma série de containers, como vetores, listas, mapas… A biblioteca de templates tem alguns problemas:

  • A performance, embora muito boa, não se compara ao uso de estruturas simples e funções especializadas;
  • As classes da STL não são feitas para serem herdadas;
  • O código gerado pelo compilador é complicado de entender;
  • A STL é sempre compilada inline. Não existe um shared object ou uma static lib para a STL (existe sim, chamada STLport, mas eu nunca consegui fazer esse treco funcionar direito!);

Dentre outras complicações que não vou falar por aqui. Só quero fazer uma comparação entre o template vector e uma rotina similar, escrita em C, para manipular arrays (vetores) de inteiros. Essa análise terá foco somente relacionada à performance. Os containers STL possuem muitas características funcionais que são extremamente úteis… Não é da utilidade da STL que estou falando!

Em C++ poderíamos fazer algo assim:

int i, sum;

/* Criando o vetor */
vector<int> array;

/* Colocando 10000 inteiros no vetor */
for (i = 0; i < 10000; i++)
  array.push_back(i);

/* Percorrendo o vetor e somando seus items... */
sum = 0;
for (vector::iterator i = array.begin; i != array.end(); i++)
  sum += *i;

Para ser “justo” com a STL, preciso criar rotinas para alocar, inserir e ler dados do vetor, em C, mais ou menos da forma como a STL o faz (a STL, por exemplo, cria um espaço pré-alocado e só o realoca se precisar – farei o mesmo aqui):

/* Aloca/realoca 1000 inteiros de cada vez */
#define CHUNK_SIZE 1000

struct vector {
  int numItems;
  int chunkSize;
  int *data;
};

struct vector *CreateVector(void)
{
  struct vector *p;

  p = (struct vector *)malloc(sizeof(struct vector));
  p->chunkSize = CHUNK_SIZE;
  p->data = (int *)malloc(CHUNK_SIZE * sizeof(int));
  p->numItems = 0;
  return p;
}

void VectorPushBack(struct vector *p, int data)
{
  int n = p->numItems;

  /* Só realoca se precisar! */
  if (n >= p->chunkSize)
  {
    p->chunkSize += CHUNK_SIZE;
    p->data = (int *)realloc(p->chunkSize * sizeof(int));
  }

  p->data[n] = data;
  p->numItems++;
}

void DestroyVector(struct vector **pp)
{
  struct vector *p = *pp;

  free(p->data);

  /* Essa linha aqui não é realmente necessária! */
  p->numItems = p->chunkSize = 0;

  free(p);
  *pp = NULL;
}

Agora, nosso código em C ficaria mais ou menos assim:

struct vector *array;
int i, sum;

/* equivalente a vector array; */
array = CreateVector();

for (i = 0; i < 10000; i++)
  VectorPushBack(array, i);

/* O nosso "iterator" será o índice do array */
sum = 0;
for (i = 0; i < array->numItems; i++)
  sum += array->data[i];

/* Embora não esteja visível no código em C++,
   o vetor 'array' é destruído quando a variável
   sai do escopo. Simulo isso aqui com essa chamada. */
VectorDestroy(&array);

Este código é bem parecido ao equivalente em C++ (mas, de novo, não faz justiça ao container vector!). Medindo a performance de ambas as rotinas o que encontramos? A rotina em C é cerca de 2 vezes mais rápida do que a em C++, que usa o container, e cerca de 50% menor (deixo os detalhes da medição dos ciclos para vocês, é bem simples fazê-lo).

Se você não se preocupa muito com performance (ou sua aplicação não exige), então use a STL. Ela é bem útil! No meu projeto VirtualWorld eu não usarei (sou um performance junkie!).

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s