Joel on Software

Joel on Software   Joel sobre Software

 

Outros artigos de "Joel on Software" em Português

Outros artigos de "Joel on Software" em Inglês

Envie email para o autor (apenas em Inglês)

 

Voltando às Raízes


Por Joel Spolsky
Traduzido por Carlos Duarte do Nascimento
Editado por Rodrigo Quaresma
11 de Dezembro de 2001

A gente passa um bocado de tempo neste site falando sobre Grandes Coisas como .NET versus Java, estratégia XML, incompatibilidades de padrões, estratégia competitiva, design de software, arquitetura, e por aí vai. Tudo isso são camadas do bolo, em um certo sentido. Na camada superior, você tem a estratégia de software. Abaixo dela, nós pensamos em arquiteturas como .NET, e abaixo disto, produtos individuais: produtos para  desenvolvimento de software como Java ou plataformas como Windows.

Vamos mais embaixo neste bolo, por favor. DLLs? Objetos? Funções? Não! Mais embaixo! Em algum ponto você está pensando em linhas de código escritas em linguagens de programação.

Ainda não  é baixo o bastante. Hoje eu quero pensar a respeito das CPUs. Um pedaço minúsculo de silício movendo bytes para lá e para cá. Faça de conta que você é um programador iniciante. Jogue fora todo o conhecimento que você construiu sobre programação, software, gerenciamento, e volte para o nível mais baixo. Coisas fundamentais, estilo Von Neumann. Apague  o J2EE da sua mente por um instante. Pense Bytes.

Vancouver BC

Por que estamos fazendo isto? Eu acho que um dos maiores erros que as pessoas cometem, mesmo nos níveis mais altos da arquitetura, vêm de terem um conhecimento fraco ou incorreto de algumas coisas simples nos níveis mais baixos. Você criou uma casa maravilhosa, mas a fundação é um desastre. Assim, o lugar parece agradável, mas de vez em quando a banheira desliza de um lado para outro do chão do banheiro e você não faz a menor idéia do que está acontecendo.

Portanto hoje respire fundo. Venha comigo, por favor, ao longo de um pequeno exercício que será conduzido usando a linguagem de programação C.

Lembre-se de como funcionam as strings em C: elas consistem em uma série de bytes, seguida por um caractere null, que possui o valor 0. Isso tem duas implicações óbvias:

 

  1. Não há como saber onde a string acaba (isto é, o tamanho da string) sem atravessá-la, procurando pelo caractere null que está no final.
  2. Sua string não pode ter nenhum zero no meio. Assim, você não pode jogar um bloco de dados binário, como uma figura JPEG, em uma string C.

Por que as strings C funcionam assim? É porque o microprocessador PDP-7, no qual o UNIX e a linguagem C foram inventados, tinha um tipo de dados ASCIZ. ASCIZ significava "ASCII com um Z (zero) no final."

Esse é o único jeito de armazenar strings? Não, de fato, este é um dos piores jeitos de armazenar strings. Para programas não-triviais, APIs, sistemas operacionais, bibliotecas de classes, deve-se fugir de strings ASCIZ como o diabo da cruz. Por que?

Vamos começar escrevendo uma versão do código para strcat, a função que acrescenta uma string no final de outra.

void strcat( char* destino, char* origem )
{
     while (*destino) destino++;
     while (*destino++ = *origem++);
}

Estude um pouco este código e veja o que estamos fazendo. No início, percorremos toda a primeira string procurando pelo terminador null. Quando o encontramos, percorremos toda a segunda string, copiando um caractere por vez para a primeira string.

Esse tipo de manipulação e concatenação de strings era boa o suficiente para Kernighan e Ritchie, mas tem os seus problemas. Eis um problema. Suponha que você tenha uma série de nomes que você quer concatenar juntos em uma grande string:

char stringGrande[1000];     /* Eu nunca sei quanto alocar... */
stringGrande[0] = '\0';
strcat(stringGrande,"John, ");
strcat(stringGrande,"Paul, ");
strcat(stringGrande,"George, ");
strcat(stringGrande,"Joel ");

Isso funciona, certo? Sim, e parece agradável e limpo.

Quanto à performance, qual é a sua característica? É tão rápido quanto poderia? É adequadamente escalável? Se tivéssemos um milhão de strings para concatenar, isto seria um bom jeito de fazê-lo?

Não. Este código usa o algoritmo Shlemiel, o Pintor. Quem é Shlemiel? É o cara que aparece nesta piada:

Shlemiel arruma um emprego como pintor de rua, no qual ele pinta as linhas tracejadas no meio da estrada. No primeiro dia ele leva uma lata de tinta para a estrada e pinta 300 jardas da estrada. "Muito bom!" diz seu patrão, "você trabalha rápido!" e paga a ele um kopeck.

No dia seguinte Shlemiel só termina 150 jardas. "Bem, não foi tão bom quanto ontem, mas ainda assim você trabalha rápido. 150 jardas é respeitável," e lhe paga um kopeck.

No outro dia, Shlemiel pinta 30 jardas da estrada. "Só 30!" grita seu patrão. "Isso é inaceitável! No primeiro dia você produziu dez vezes mais! O que está acontecendo?"

"Não posso evitar," diz Shlemiel. "A cada dia que passa, eu fico mais e mais longe da lata de tinta!"

kansas(Como bônus extra, quais seriam os números reais?) Essa piada sem-graça ilustra exatamente o que acontece quando se usa strcat do jeito que acabei de fazer. Como a primeira parte de strcat tem que percorrer a string de destino sempre que é chamada, procurando aquele maldito terminador null todas as vezes, esta função é muito mais lenta do que deveria e não escala muito bem. Um bocado do código que você usa todos os dias possui este problema. Muitos sistemas de arquivo são implementados de uma maneira que faz ser uma má idéia colocar muitos arquivos num diretório, porque a performance começa a cair dramaticamente quando você tem milhares de itens no mesmo diretório. Tente abrir uma lixeira do Windows sobrecarregada para ver isto em ação -- ela leva horas para aparecer, o que visivelmente não é linear em relação ao número de arquivos que contém. Deve haver algum Algoritmo Shlemiel, o Pintor lá dentro, em algum lugar. Sempre que alguma coisa parecer que deveria ter performance linear, mas parece ter uma performance elevada a n, procure por Shlemiels escondidos. Eles costumam ser ocultados por suas bibliotecas. Visualizar uma coluna de strcats ou um strcat em um loop não é exatamente algo que grite "elevado a n," mas é o que está acontecendo.

Como consertamos isto ? Alguns programadores C mais espertos implementaram seus próprios meustrcat do seguinte modo:

char* meustrcat( char* destino, char* origem )
{
     while (*destino) destino++;
     while (*destino++ = *origem++);
     return --destino;
}

O que fizemos aqui? Com um custo extra muito pequeno, estamos retornando um ponteiro para o final da string nova e maior. Desta forma, o código que chamar esta função pode concatenar seguidamente sem percorrer novamente a string:

char stringGrande[1000];     /* Eu nunca sei quanto alocar... */
char *p = stringGrande;
stringGrande[0] = '\0';
p = meustrcat(p,"John, ");
p = meustrcat(p,"Paul, ");
p = meustrcat(p,"George, ");
p = meustrcat(p,"Joel ");

Isto é, evidentemente, linear em termos de performance, e não elevado a n, assim não sofre de degradação quando você tem um bocado de coisas para concatenar.

Os designers do Pascal estavam cientes deste problema e o "consertaram" guardando um contador de bytes no primeiro byte da String. Estas strings são chamadas de Strings Pascal. Elas podem conter zeros e não são terminadas em null. Como um byte só pode armazenar números entre 0 e 255, strings Pascal são limitadas a um tamanho de 255 bytes, mas como elas não são terminadas em null ocupam o mesmo espaço de memória que as strings ASCIZ. O legal nas strings Pascal é que você nunca tem que fazer um loop só para saber o tamanho da string. Encontrar o tamanho de uma string em Pascal é uma instrução assembly, ao invés de um loop completo. É monumentalmente mais rápido.

O velho sistema operacional do Macintosh usava strings Pascal em todo canto. Muitos programadores C em outras plataformas usam strings Pascal por causa da velocidade. O Excel usa strings Pscal internamente, motivo pelo qual no Excel as strings são limitadas em 255 bytes em muitos lugares, e também é uma razão pela qual o Excel é estupidamente rápido.

Durante muito tempo, se você quisesse colocar uma string literal Pascal em seu código C, você tinha que escrever:

char* str = "\004Alo!";

Sim, você tinha que contar os bytes manualmente, e inserir manualmente o resultado no primeiro byte da sua string. Programadores preguiçosos faziam isto, obtendo programas lentos:

char* str = "*Alo!";
str[0] = strlen(str) - 1;

Perceba que neste caso você tem uma string que é terminada em nulo (o compilador fazia isto) e também é uma string Pascal. Eu costumava chamar estas de strings fodidas porque é mais fácil do que chamá-las de strings pascal terminadas em null mas isto é um canal permitido para menores então você terá que usar o nome mais comprido.

Eu omiti um assunto importante lá atrás. Lembra-se desta linha de código?

char stringGrande[1000];     /* Eu nunca sei quanto alocar... */

Já que estamos prestando atenção nos bits hoje eu não deveria ter ignorado isto. Eu deveria ter feito do jeito certo: adivinhado quantos bytes eu precisava e alocado a quantidade correta de memória.

Não deveria ?

Porque caso contrário, veja você, um hacker esperto vai ler meu código e perceber que eu só estou alocando 1000 bytes e torcendo para que seja suficiente, e eles vão encontrar alguma maneira de me enganar e me fazer strcattear uma string de 1100 bytes nos meus 1000 bytes de memória, sobrecarregando assim a pilha e mudando o endereço de retorno para que quando a função retorne, ela execute algum código que o hacker mesmo escreveu. É disso que eles estão falando quando dizem que um determinado programa tem uma vulnerabilidade de estouro de buffer (buffer overflow). Isso era a causa número um de hacks e worms nos velhos tempos antes do Microsoft Outlook ter transformado o hacking em algo fácil o suficiente para a molecada.

OK, então todos aqueles programadores são bundões. Eles deviam ter estimado quanta memória deveriam alocar.

Mas realmente, o C não torna isso fácil para você. Vamos voltar ao meu exemplo dos Beatles:

char stringGrande[1000];     /* Eu nunca sei quanto alocar...  */
char *p = stringGrande;
bigString[0] = '\0';
p = meustrcat(p,"John, ");
p = meustrcat(p,"Paul, ");
p = meustrcat(p,"George, ");
p = meustrcat(p,"Joel ");

Quanto nós deveríamos alocar? Vamos tentar fazer isto Do Jeito Certo.

char* stringGrande;
int i = 0;
i = strlen("John, ")
     + strlen("Paul, ")
     + strlen("George, ")
     + strlen("Joel ");
stringGrande = (char*) malloc (i + 1);
/* lembre-se do espaço para o terminador null! */
...

Meus olhos brilharam. Você provavelmente já está a ponto de mudar o canal. Não o culpo, mas fique ao meu lado porque isso fica realmente interessante.

Nós tivemos que percorrer todas as strings uma vez só para saber quão grandes eram, então percorremos elas novamente para concatenar. Pelo menos se você usar strings Pascal a operação strlen é rápida. Talvez pudéssemos escrever uma versão de strcat que realocasse a memória para nós.

Isso abre outra lata de minhocas completamente nova: alocadores de memória. Você sabe como o malloc funciona? A natureza do malloc é que ele tem uma longa lista ligada de blocos disponíveis na memória, denominada cadeia livre (free chain). Quando você chama a função malloc, ela atravessa a lista ligada procurando um bloco de memória grande o bastante para o seu pedido. Então ela quebra o bloco em dois blocos -- um do tamanho que você pediu, e outro com os bytes restantes, e dá a você o bloco que você pediu, e coloca o bloco restante (se houver) de volta na lista ligada. Quando você chama free, ela adiciona o bloco que você liberou na cadeia livre. Eventualmente, a cadeia livre fica fragmentada em pedacinhos pequenos e você pede um bloco grande e não há blocos do tamanho que você quer disponíveis. Então malloc pede um tempo e começa a vasculhar a cadeia livre, organizando as coisas e colando pequenos blocos livres adjacentes em blocos maiores. Isso leva 3 dias e 1/2. O resultado final dessa bagunça é que a característica de performance de malloc é que ela não é nunca muito rápida (ela sempre percorre a cadeia livre), e às vezes, de forma imprevisível, ela se torna assustadoramente lenta enquanto está fazendo a limpeza. (Isso é, não por acaso, a mesma característica de performance de sistemas que trabalham com coleta de lixo, surpresa, então todas as alegações que as pessoas faziam a respeito da coleta de lixo impor uma penalidade de performance não são completamente verdadeiras, já que implementações típicas de malloc tiveram o mesmo tipo de penalidade de performance, ainda que mais leve.)

Programadores espertos minimizam o potencial de interrupção de malloc alocando sempre blocos de memória cujos tamanhos são potências de 2. Sabe como é, 4 bytes, 8 bytes, 16 bytes, 18446744073709551616 bytes, etc. Por motivos que devem ser intuitivos para qualquer um que brinque com Lego, isso minimiza a quantidade de fragmentações bizarras que acontecem na cadeia livre. Apesar disto parecer um desperdício de espaço, também é fácil perceber como isto nunca desperdiça mais de 50% do espaço. Assim seu programa não chega a usar mais que o dobro da memória que precisa, o que não é grande coisa.

Digamos que você tenha escrito uma função strcat que realoca o buffer de destino automaticamente. Ela deveria sempre realocá-lo exatamente para o tamanho necessário? Meu professor e mentor Stan Eisenstat sugere que quando você chamar realloc, você deve sempre duplicar o tamanho de memória que foi alocado anteriormente. Isso quer dizer que você nunca tem que chamar realloc mais que log n vezes, o que tem características de performance decentes mesmo para strings monstruosas, e você nunca desperdiça mais de 50% da sua memória.

De todo jeito, a vida fica mais e mais complicada aqui em baixo no reino dos bytes. Você não fica feliz por não ter mais que escrever em C? Nós temos todas essas linguagens fantásticas como Perl e Java e VB e XSLT que nunca fazem você pensar em nada desse gênero, elas simplesmente resolvem a questão, de alguma maneira. Mas de vez em quando, a infra-estrutura do encanamento brota no meio da sala de estar, e nós temos que pensar se usamos uma classe String ou StringBuilder, ou alguma coisa distinta, porque o compilador ainda não é esperto o bastante para entender tudo a respeito do que estamos tentando realizar e está tentando nos ajudar a não escrever inadvertidamente algoritmos Shlemiel, o Pintor.

[Image]Semana passada eu escrevi que você não pode implementar a declaração SQL SELECT autor FROM livros de forma rápida quando seus dados estão armazenados em XML. Por um acaso ninguém entendeu do que eu estava falando, e agora que passamos o dia todo em torno da CPU, esta afirmação deve fazer mais sentido.

Como um banco de dados relacional implementa SELECT autor FROM livros? Num banco de dados relacional, toda linha em uma tabela (ex.: a tabela livros) é exatamente do mesmo tamanho em bytes, e cada campo está sempre a uma mesma distância (offset) do início da linha. Então, por exemplo, se cada registro na tabela livros tem 100 bytes, e o campo autor está no offset 23, então há autores guardados nos bytes 23, 123, 223, 323, etc. Qual seria o código para avançar para o próximo registro no resultado desta query ? Basicamente é isto:

ponteiro += 100;

Uma instrução da CPU. Ráááááááááááápida.

Agora vamos dar uma olhada na tabela de livros em XML.

<?xml bla bla bla>
<livros>
     <livro>
          <titulo>Design de IU para Programadores</titulo>
          <autor>Joel Spolsky</autor>
     </livro>
     <livro>
          <titulo>O Clube Chop Suey</titulo>
          <autor>Bruce Weber</autor>
     </livro>
</livros>

Pergunta rápida. Qual seria o código para mover para o próximo registro?

Oh...

A essas alturas um bom programador diria, bem, vamos dar um parse (interpretar) a árvore XML, transformando-a numa árvore em memória para que possamos trabalhar nela racionalmente e rapidamente. O volume de trabalho que terá que ser feito aqui pela CPU para dar um SELECT autor FROM books vai matar você de tédio. Como qualquer um que já escreveu um compilador sabe, o processo de parsing e a análise léxica são as partes mais lentas da compilação. Basta dizer que isso envolve um bocado de manipulações de string, o que nós descobrimos que é lento, e um bocado de alocações de memória, o que nós descobrimos que é lento, à medida que nós classificamos, analisamos e montamos a árvore de sintaxe abstrata na memória. Isso partindo do princípio que você tem memória suficiente para carregar a coisa inteira de uma vez só. Em bancos de dados relacionais,a performance para ir de um registro a outro é fixa e é, de fato, uma instrução da CPU. Isso é assim em grande parte devido ao design. E graças ao mapeamento de arquivos na memória você só tem que carregar as páginas do disco que vai realmente usar. Com XML, se você pré-analisar, a performance de ir de um registro a outro é fixa, mas haverá um tempo de inicialização gigantesco, e se você não pré-analisar, a performance de ir de um registro a outro vai variar de acordo como o tamanho do registro anterior e ainda por cima vai tomar centenas de instruções da CPU.

O que isto significa é que você não pode usar XML se precisa de performance e tem muitos dados. Se você tem uma quantidade reduzida de dados, ou se o que você está fazendo não precisa ser rápido, XML é um formato bacana. E se você quiser mesmo o melhor de dois mundos, você tem que arrumar um jeito de armazenar metadados junto com o seu XML, algo como o contador de bytes das strings Pascal, que dê a você dicas a respeito de onde as coisas estão no arquivo para que você não tenha que analisá-lo e procurar por elas. Mas, é claro, se fizer isto você não poderá usar editores de texto para editar o arquivo porque isso bagunçaria os metadados, logo isso não é mais XML.

Quanto aos gentis membros da minha audiência que ainda estão comigo neste ponto, espero que vocês tenham aprendido algo ou repensado algo. Espero que ter ficado pensando sobre coisas tediosas do primeiro ano de ciência da computação como o funcionamento real de malloc e strcat tenha lhes dado novas ferramentas para pensar a respeito das decisões estratégicas e arquiteturais mais recentes e de alto nível que você faz quando lida com tecnologias como XML. Como lição de casa, tente imaginar porque os chips da Transmeta sempre vão parecer lesmas. Ou porque a especificação original do HTML para TABLEs era tão mal desenhada que grandes tabelas em páginas web não podem ser exibidas rapidamente para pessoas com modems. Ou porque COM é rápido pra burro, mas não quando você está cruzando os limites do processo. Ou porque os caras que fizeram o NT colocaram o driver de vídeo no espaço de memória do kernel (kernelspace) ao invés do espaço de memória do usuário (userspace).

Essas coisas todas exigem que você pense em bytes, e como eles afetam as grandes decisões de alto nível que fazemos em todos os tipos de arquiteturas e estratégias.  É por isso que o meu ponto de vista sobre o ensino é que os estudantes de ciência da computação no primeiro ano precisam começar com o básico, usando C e construindo seu caminho a partir da CPU. Eu passo mal só de saber que tantos programas curriculares de ciência da computação acreditam que Java é uma boa linguagem introdutória, porque é "fácil" e você não se confunde com todas aquelas coisas de string/malloc mas pode aprender coisas legais de OOP que vão fazer seus programas grandes tão modulares como jamais foram. Isso é um desastre pedagógico prestes a acontecer. Gerações de graduados estão nos sucedendo e criando algoritmos Shlemiel, o Pintor em todo canto e nem percebem isto, já que eles fundamentalmente não tem qualquer idéia que strings são, num nível mais profundo, difíceis, mesmo que você não veja isto no seu script perl. Se você quiser ensinar alguma coisa a alguém, bem, você tem que começar no nível mais baixo. É como Karate Kid: Lustra Para Esquerda, Lustra Para Direita. Lustra Para Esquerda, Lustra Para Direita. Faça isso por três semanas. Daí Arrebentar A Cabeça Do Outro Garoto fica fácil.

Emacs



Esse artigo apareceu originalmente em Inglês com o título Back to Basics  

Joel Spolsky é o fundador da Fog Creek Software, uma pequena empresa de software na cidade de Nova York. Formou-se na Universidade de Yale, e trabalhou como programador e gerente na Microsoft, na Viacom e no Juno.


O conteúdo dessas páginas reflete exclusivamente a opinião do autor.
Todo o conteúdo Copyright ©1999-2005 Joel Spolsky. Todos os direitos reservados.

FogBUGZ | CityDesk | Fog Creek Software | Joel Spolsky