Como é sabido e notório, implementações normais de C e C++ não fazem verificação de limite de vetor (bounds checking)*. Como também é sabido e notório, essa é uma fonte inexaurível de bugs obscuros e vulnerabilidades de segurança. Dado que esses problemas têm incomodado a humanidade há mais de 30 anos, pergunto: por que diabos compiladores C/C++ não implementam verificação de limites? A resposta normalmente dada é de que isso é feito em nome da performance: verificação de limites é custosa, e se o código for corretamente escrito é desnecessária, logo bounds checking é um desperdício de tempo de execução. Mas será que bounds checking é tão custoso assim?
Testemos, pois. Faremos um benchmark simples comparando a performance de uma função com e sem bounds checking. Para fazermos a verificação de limites, armazenaremos o tamanho dos vetores em uma posição de memória antes do conteúdo "útil" do vetor:
int *make_vector(int length) {
int *vector = malloc(sizeof(int) * (length+1));
vector[0] = length; // Armazena o tamanho no início da região de memória.
vector++; // Aponta 'vector' para o resto da região.
int i;
for (i=0; i<length; i++)
vector[i] = i;
return vector;
}
#define lengthof(v) ((v)[-1])
Nossa função de teste recebe dois vetores e soma cada elemento do segundo ao respectivo elemento do primeiro um determinado número de vezes. (Um compilador suficientemente inteligente poderia substituir o loop de N iterações por uma multiplicação por N, distorcendo os resultados. "Felizmente" esse não é o caso com o GCC (ou provavelmente qualquer compilador C existente).)
void test(int *restrict v1, int *restrict v2, int iterations) {
int length = lengthof(v1);
int i;
while (iterations-- > 0) {
for (i=0; i<length; i++) {
#ifdef BOUNDS_CHECK
if (i<0 || i>=lengthof(v1)) exit(42);
if (i<0 || i>=lengthof(v2)) exit(42); // i<0 redundante
#endif
v1[i] += v2[i];
}
}
}
Note que, como o mesmo índice i é usado duas vezes, temos dois testes i<0. A idéia é simular como um compilador simplista inseriria as verificações de limite; um compilador mais esperto poderia juntar as duas verificações em um if só e eliminar as verificações redundantes. Porém, deixemos o teste extra aí, já que em geral não teremos necessariamente o mesmo índice para todos os acessos de array de um determinado trecho de código. (Estranhamente, o GCC é esperto o suficiente para notar que o corpo dos dois ifs é igual, mas não para notar o teste redundante, mesmo com otimizações ativadas.)
Por fim, nossa main() cria dois vetores e chama a função de teste:
int main() {
test(make_vector(10000), make_vector(10000), 10000);
return 0;
}
Compilemos e testemos:
# gcc -std=c99 -O2 version0.c && time ./a.out real 0m0.385s user 0m0.384s sys 0m0.000s # gcc -DBOUNDS_CHECK -std=c99 -O2 version0.c && time ./a.out real 0m0.704s user 0m0.700s sys 0m0.000s
Quase duas vezes o tempo! (Como curiosidade, sem o i<0 redundante o tempo de execução com bounds checking cai para 0.660s, em "user time".) Mas não tiremos conclusões precipitadas. Quem sabe se usarmos outra representação para o par (tamanho, dados)? Uma struct, por exemplo:
typedef struct vector_t {
int length;
int content[0]; // GCC ftw
} vector_t;
vector_t *make_vector(int length) {
vector_t *vector = malloc(sizeof(vector_t) + sizeof(int)*length);
vector->length = length;
int i;
for (i=0; i<length; i++)
vector->content[i] = i;
return vector;
}
#define lengthof(v) ((v)->length)
void test(vector_t *restrict v1, vector_t *restrict v2, int iterations) {
int length = lengthof(v1);
int i;
while (iterations-- > 0) {
for (i=0; i<length; i++) {
#ifdef BOUNDS_CHECK
if (i<0 || i>=lengthof(v1)) exit(42);
if (i<0 || i>=lengthof(v2)) exit(42);
#endif
v1->content[i] += v2->content[i];
}
}
}
Será que faz diferença?
# gcc -std=c99 -O2 version1.c && time ./a.out real 0m0.386s user 0m0.384s sys 0m0.000s # gcc -DBOUNDS_CHECK -std=c99 -O2 version1.c && time ./a.out real 0m0.505s user 0m0.504s sys 0m0.000s
E não é que faz? Olhando o assembly gerado pelo GCC (gcc -S -fverbose-asm), a principal diferença que eu percebo é que na versão com vetor puro o GCC lê o endereço de lengthof(v2) de uma variável temporária armazenada na pilha, carrega o endereço em %eax e testa i contra %eax, enquanto na versão com struct o valor de lengthof(v2) é lido diretamente como (%esi), já que o tamanho do vetor é o primeiro item da região de memória. Sinceramente não sei por que o GCC não lê lengthof(v2) na versão com vetor como -4(%esi), já que %esi fica com o endereço de v2. Experimentei substituir a carga em %eax e comparação de i contra %eax por um teste direto de i contra -4(%esi); o resultado é o mesmo (verificado com um printf a facão) e o tempo cai dos 0.704s para 0.555s. Go figure.
Mas essa história de registradores nos dá outra idéia. O tamanho dos vetores não muda durante a execução da função. Talvez se copiarmos esses valores para variáveis locais antes de entrar no loop, o compilador os mantenha em registradores, acelerando a checagem:
void test(vector_t *restrict v1, vector_t *restrict v2, int iterations) {
int length1 = lengthof(v1);
int length2 = lengthof(v2);
int i;
while (iterations-- > 0) {
for (i=0; i<length1; i++) {
#ifdef BOUNDS_CHECK
if (i<0 || i>=length1) exit(42);
if (i<0 || i>=length2) exit(42);
#endif
v1->content[i] += v2->content[i];
}
}
}
E agora?
# gcc -std=c99 -O2 version2.c && time ./a.out real 0m0.386s user 0m0.384s sys 0m0.000s root@pts4 bounds2(0)# gcc -DBOUNDS_CHECK -std=c99 -O2 version2.c && time ./a.out real 0m0.387s user 0m0.388s sys 0m0.000s
Conclusão: bounds checking é eficiente se implementado corretamente. Todos os desenvolvedores de compiladores C são tolos e ignorantes. Nós, mentes iluminadas, implementaremos um compilador C com bounds checking e recompilaremos o kernel e todo o universo com bounds checking, tornando todo o software em existência mais seguro, sem perda de performance. Brindemos à nossa glória.
Só tem um problema: nossa verificação assume que, a partir da variável pela qual acessamos o vetor, podemos consultar seu tamanho, que armazenamos em uma posição fixa em relação à área de dados do vetor. O problema é que C permite fazer aritmética de ponteiros: um ponteiro pode apontar para qualquer ponto dentro de um vetor, não necessariamente para o seu começo. Conseqüentemente, a partir de um ponteiro arbitrário não necessariamente sabemos como encontrar o tamanho da região. Em C ainda há o agravante de que vetores e ponteiros não são tipos distintos: não se pode saber se uma função com um argumento do tipo int[] está recebendo um ponteiro para um "vetor completo" ou para uma região arbitrária dentro do vetor. (O próprio conceito de "vetor completo" não faz muito sentido em C.)
Diversas soluções já foram propostas. [Disclaimer: o que se segue são divagações sobre as possíveis soluções. Ênfase na parte "divagações".] Uma das mais simples é representar todos os ponteiros como triplas (ponteiro, limite_inferior, limite_superior), permitindo a verificação de limites para ponteiros arbitrários. O problema é que todos os ponteiros passam a ocupar o triplo do espaço, o que aumenta o tamanho de estruturas de dados com ponteiros (e.g., listas, árvores e outras estruturas recursivas), gera mais empilhamentos na passagem de argumentos para funções e possivelmente consome mais registradores. (Não sei quão válido é o ponto sobre os registradores, já que armazenar (base, length, i) ou (lower, ptr, upper) dá mais ou menos na mesma (exceto no caso em que é necessário armazenar o ponteiro para um vetor e um índice (i.e., (lower, ptr, upper, i)) (mas nada que o compilador não pudesse otimizar, I guess))).
Outro problema com essa solução é que a alteração do formato dos ponteiros implica que código com bounds checking (e ponteiros triplos, também conhecidos como "fat pointers") não pode interagir diretamente com código sem bounds checking (com pointeiros simples). Conseqüentemente, tem-se que recompilar tudo para usar bounds checking, incluindo bibliotecas. (Nossa solução original também tem esse problema, talvez em menor grau: é preciso armazenar o tamanho de cada vetor em seu início. Os ponteiros não mudam de formato, mas o código assume coisas diferentes sobre a região apontada pelos mesmos.)
Segundo estes relatos, o uso de fat pointers desse tipo provoca um aumento de mais de 100% em tempo de execução e quase duplica o tamanho dos dados nos benchmarks utilizados (o que os autores consideram "boa performance"; go figure).
Uma solução intermediária seria armazenar o tamanho de cada região no início da mesma e representar os ponteiros como um par (base, offset), a la Lisp Machine. Não vi ninguém sugerir isso entre os artigos que eu andei lendo, e não sei até que ponto isso seria melhor. Um problema de armazenar o tamanho junto com a região de memória é quando o programador deseja alocar regiões de memória com algum alinhamento, por questões de performance. Por exemplo, o programador pode fazer uma chamada a posix_memalign(&ptr, 4096, 4096), para obter uma região alinhada com uma página de memória; o tamanho da região teria que ser armazenado antes da página. Se duas dessas regiões são alocadas, duas páginas extra são alocadas apenas para conter o tamanho de cada região. (Por outro lado, uma implementação "ingênua" de malloc e posix_memalign já armazena o tamanho da região e outros dados antes da região.)
Soluções que não envolvem alterar o formato dos ponteiros e vetores trabalham armazenando os dados sobre limites em uma tabela ou outra estrutura de dados indexada pelo ponteiro cujos limites se deseja consultar. Uma das soluções mais elaboradas instrumenta todas as ocasiões de alocação e liberação de memória, tanto por malloc quanto na pilha, bem como operações aritméticas sobre ponteiros, com chamadas a funções que fazem o controle de limites. O código resultante é compatível com código sem bounds checking, mas a instrumentação tem um overhead significativo sobre o tempo de execução do programa. É uma solução útil para debugar software, já que permite instrumentar o programa sem recompilar as bibliotecas, mas não serve como um mecanismo permanente de verificação de limites.
A conclusão que eu tiro disso é: pense 44 vezes antes de incluir aritmética de ponteiros (ou ponteiros em geral) em uma linguagem. Além de dificultar bounds checking eficiente, ponteiros atrapalham a vida do compilador na hora de efetuar certas outras otimizações. Talvez o melhor seja acessar vetores sempre através de vetor/índice, e deixar o compilador se encarregar de substituir o par vetor/índice por um ponteiro como uma otimização. Se você incluir ponteiros em uma linguagem, considere mantê-los como um tipo distinto dos tipos de vetor (que carregam consigo o tamanho do vetor). Se performance for importante, me parece uma idéia melhor fazer bounds checking por padrão e fornecer uma declaração de compilação que permita eliminar os testes quando necessário, do que não fazer verificações por padrão e deixar o trabalho sujo nas mãos do programador (que invariavelmente esquece de fazê-lo ou comete um erro uma hora ou outra).
* Tecnicamente não é correto dizer que C não faz bounds checking, mas sim que a linguagem não exige bounds checking e as implementações da linguagem não o fazem. Por sinal, o compilador de C que vinha com o Genera fazia bounds checking (pelo simples fato de que todo acesso a memória na Lisp Machine era checked).
De maneira similar, uma linguagem que "faz bounds checking" apenas garante que todo acesso além do limite de um vetor será detectado. Uma implementação não precisa necessariamente inserir testes em tempo de execução, se ela puder provar de antemão que um acesso fora dos limites nunca ocorrerá. Por exemplo, em um loop do tipo for (i=0; i<lengthof(v); i++) em que i não é alterado no corpo do loop, acessos do tipo v[i] certamente estão dentro dos limites (i.e., i>=0 && i<lengthof(v) é sabidamente verdadeiro em tempo de compilação), e portanto verificações de limite não precisam ser inseridas no código.
Addendum: vide comentário.
1. Pois tem; é só não declarar o tamanho do array. Mas como eu lembrava que existia essa extensão do GCC, nem me ocorreu que existisse um recurso padrão equivalente. :P
2. Eu não acredito em 'register'. :P E podia ser que o compilador achasse coisa melhor pra colocar nos registradores, então fico meio assim de usar...
3. Não tentei; não conheço muito de C++. Em um momento de maior glória (ou tédio) eu experimento (mas se o senhor quiser fazer isso e postar os resultados eu linko para o post :P).
Fiz um teste sem compromisso com o std::vector do C++ comparando [] (isto é, sem bounds checking) e .at() (com bounds checking) e cheguei à seguinte conclusão:
Mais rápido <----------------------------> Mais lento
C sem bounds checking, C++ sem bounds checking, C++ com bounds checking, C com o bounds checking mais "burro" (o primeiro dos teus testes)
Tempos aproximados: 0,090 s; 0,117s ; 0,169 s; 0.194 s
E ainda mais sem compromisso, Java (com bounds checking obrigatório) foi ainda mais rápido que C sem bounds checking: 0,075 s!
Mas como qualquer medida de desempenho com Java, sempre dá uma sensação de trapaça: aposto que todo esse tempo foi usado para carregar a JVM e então o otimizador percebeu que o programa não faz nada útil e finalizou a execução :-p
Todo o meu teste foi completamente não-científico e descuidado, claro.
Sem falar que na primeira execução do Java ele é horrivelmente lento e depois fica até normal...
Que loucura será essa com o Java? Será que ele usa instruções vetoriais malucas (SSE da vida) pra fazer as somas? Ou será que ele nem faz nada mesmo? :P
Haha, a performance mágica do Java se devia a um problema entra a cadeira e o teclado. Deixa pra lá. :-p
Ninguém viu nada. :P
Hahaha, pois é, fazendo o teste certo, o tempo do OpenJDK 6 ficou nos 0,169 s, igual ao C++ com bounds checking, o que já é bastante bom para o Java, hahaha. Mas também, só usa int[] em Java quem está com saudade do C, normalmente se usa ArrayList<Integer>, o que equivaleria a um int*[] em C e aí o tempo vai para a casa de 1 segundo...
Voltando ao C e C++, no meu GCC (4.6.3) encontrei uma bizarrice onde a otimização com -O3 deixava o programa mais lento que com -O2. Só espero não haver outro problema entre a cadeira e o teclado...
Vish, meu nome saiu incompleto no comentário anterior.
Já vi disso com o gcc antes (de o -O3 ser mais lento que o -O2)...
Depois eu me dei conta de que de certa forma tem um problema entre o teclado e a cadeira deste lado: na minha última versão com bounds checking, o gcc aparentemente está matando o teste de "i>=length1"; aparentemente ele foi esperto o suficiente para determinar que se isso pudesse verdade ele não estaria dentro do loop. Usando uma variável diferente para controlar o loop (length ao invés de length1, e enganado o gcc para ele não ver que as duas têm o mesmo valor), o tempo sobe um pouco, para 0.478s (vs. 0.382s sem bounds checking (adoro meu Atom :P))... um compilador suficiente inteligente que fizesse bounds checking faria isso de qualquer forma, então não chega a ser muito "irrealista" o resultado menor, mas a coisa não é tão bonita quanto eu tinha imaginado...
Eu to até agora tentando entender daonde tu tirou esse link do "compilador suficientemente inteligente". Aquela wiki é ótima, mas é meio "Wtf?". Eu não entendo o que é comentário e o que não é lá.
Parece ser muito cheia de coisas de programação, mas ao mesmo tempo eu nunca consigo dizer o que é só opinião e o que é realmente algo "decidido" (algo que todos concordam, sei lá).
Já entrei lá umas 3x desde que li esse artigo pra ler qualquer coisa random... HUEAHUEHAUHEAUH...
(no mais, lendo os comentários aqui: esses dias eu tive um problema estranho. Quando eu colocava pra otimiar -O3, o código entrava em loop. Se eu tirava o -O3, o código dava Segfault -- e na real a otimização tava só mesmo me trollando de achar o erro, que era um ponteiro NULL)
Bom... voltar ao trabalho... u.u
Cara, não sei mais como eu encontrei a c2wiki pela primeira vez, mas eu fiquei igualmente perdido na ocasião. Ela parece ser um "living fossil" de 1995 que não mudou nada desde que surgiu... :P
Se tu ainda tiver esse código à mão, queira compartilhar. Esses dias mesmo eu li uma história muito interessante sobre uma otimização envolvendo NULL:
https://isc.sans.edu/diary/A+new+fascinating+Linux+kernel+vulnerability/6820
Bá, essa coisa foi a primeira wiki do mundo, e ainda tá funcionando...
http://en.wikipedia.org/wiki/WikiWikiWeb
Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.
Powered by Blognir.
Marcus Aurelius, 2012-12-07 21:16:50 -0200 #
Curiosidades:
1 - Não tem um recurso padrão do C99 equivalente à gambiarra
int content[0]; // GCC ftw
?
2 - Quando tu resolveu colocar o tamanho em variáveis locais, eu jurava que tu ia usar a palavra "register" e ainda por cima ia fazer diferença (ao contrário do senso comum atual que diz que essa palavra chave é obsoleta pois o compilador pode fazer isso sozinho).
3 - Já tentou em C++, com vector::operator[] comparado com vector::at()?
Bounds checking ativáveis/desativáveis ao compilar? Acho que tinha isso em Delphi (e talvez outros Pascais)... Não que eu goste das linguagens do tio Wirth (na verdade acho que ele era meio pirado)