C não é um idioma de baixo nível

Seu computador não é uma versão rápida do PDP-11

Olá Habr!

Meu nome é Anton Dovgal, sou desenvolvedor C (e não apenas) no Badoo.

Me deparei com um artigo de David Chiznell, pesquisador da Universidade de Cambridge, no qual ele contesta a opinião geralmente aceita de que C é uma linguagem de baixo nível, e seus argumentos pareciam interessantes o suficiente para mim.

À luz das vulnerabilidades descobertas recentemente, Meltdown e Spectre devem reservar um tempo para descobrir os motivos de sua ocorrência. Essas duas vulnerabilidades exploraram a execução especulativa de instruções pelos processadores e permitiram que um invasor recebesse resultados por meio de canais de terceiros. Foram adicionadas vulnerabilidades nos recursos do processador, juntamente com alguns outros, para que os programadores de C continuassem acreditando que programavam em uma linguagem de baixo nível, embora isso não ocorra há décadas.

Os fabricantes de processadores não estão sozinhos nisso. Os desenvolvedores do compilador C / C ++ também contribuíram.

O que é um idioma de baixo nível?

O cientista da computação americano e o primeiro vencedor do Prêmio Turing Alan Perlis deram a seguinte definição:

"Uma linguagem de programação é de baixo nível se os programas escritos nela exigirem atenção ao não essencial".

Embora essa definição se refira a C, ela não fornece uma compreensão do que as pessoas querem ver em um idioma de baixo nível. Várias propriedades fazem as pessoas considerarem o idioma baixo. Imagine uma escala de linguagens de programação com assembler em uma extremidade e uma interface para um computador Enterprise na outra. Os idiomas de baixo nível estão mais próximos do ferro, enquanto os idiomas de nível superior estão mais próximos de como as pessoas pensam.

Para estar “mais próximo do hardware”, o idioma deve fornecer abstrações que correspondam às abstrações da plataforma de destino. É fácil provar que C era uma linguagem de baixo nível no PDP-11. A execução seqüencial de programas, um espaço de endereço plano, até mesmo operadores de pré e pós-incremento, caiu perfeitamente nos modos de endereçamento do PDP-11.

Emuladores rápidos PDP-11

O principal motivo para as vulnerabilidades Spectre e Meltdown é que os criadores dos processadores não fizeram apenas processadores rápidos, eles fizeram processadores rápidos com a interface PDP-11. Isso é importante porque permite que os programadores de C continuem acreditando que sua linguagem está próxima do hardware.

O código C fornece um autômato abstrato principalmente seqüencial (até C11, é completamente seqüencial, se extensões não padronizadas forem excluídas). Criar um novo encadeamento é uma chamada para uma função de biblioteca, uma operação bastante cara. Portanto, os processadores, desejando continuar executando o código C, contam com o paralelismo em nível de instrução (ILP). Eles analisam operações vizinhas e executam operações independentes em paralelo. Isso complica muito os processadores e leva ao aumento do consumo de energia, mas permite que os programadores escrevam principalmente códigos sequenciais. Por outro lado, os processadores gráficos (GPUs) alcançam alto desempenho de outra maneira: eles exigem a gravação de programas paralelos.

Alta simultaneidade no nível do comando é a causa direta do Spectre e do Meltdown. O processador Intel moderno executa até 180 instruções simultaneamente (ao contrário da máquina abstrata C seqüencial, que espera que a instrução anterior seja executada antes do início da próxima). Uma heurística típica do código C mostra que há uma ramificação em média para cada sete instruções. Se você quiser manter o pipeline de instruções completo, precisará adivinhar as próximas 25 ramificações. Isso, por sua vez, aumenta a complexidade - o processador primeiro calcula a ramificação adivinhada incorretamente e depois lança os resultados dos cálculos, que afetam negativamente o consumo de energia. Esses dados lançados têm resultados indiretos visíveis, que foram usados ​​nos ataques Spectre e Meltdown.

Renomear registros consome muita energia e área de chip nos processadores modernos. Ele não pode ser desligado ou seu consumo de energia reduzido, o que a torna inconveniente na era do silício escuro , quando os transistores são baixos, mas os transistores envolvidos são um recurso valioso. Este dispositivo está ausente na GPU, onde a simultaneidade é alcançada usando threads em vez de tentar executar paralelamente o código seqüencial inicialmente. Se as instruções não tiverem dependências que precisam ser reconstruídas, também não será necessário renomear os registros.

Considere outra parte fundamental do design de C: memória plana. Não existe há algumas décadas. Um processador moderno geralmente possui três níveis de cache entre os registradores e a memória principal, reduzindo assim o tempo necessário para acessar o último.

O cache está oculto do programador e, portanto, inacessível a C. O uso efetivo do cache é uma das maneiras de acelerar a execução de código em um processador moderno, no entanto, está completamente oculto da máquina abstrata e os programadores são forçados a confiar no conhecimento dos detalhes da implementação do cache (por exemplo, que dois alinhados de 64 bits valores podem aparecer em uma linha do cache) para escrever código eficiente.

Otimização C

Uma das características comuns atribuídas a idiomas de baixo nível é a velocidade. Em particular, eles devem ser fáceis de traduzir em código rápido sem um compilador complicado. O argumento de que um compilador inteligente o suficiente pode acelerar um idioma é frequentemente ignorado pelos proponentes do C quando falam sobre outros idiomas.

Infelizmente, usando uma tradução simples, você não pode obter código rápido de C.
Os arquitetos de processadores fazem esforços heróicos para criar chips que podem executar o código C rapidamente. Mas os níveis de desempenho que os programadores esperam ver são alcançados apenas com a ajuda de otimizações incrivelmente complexas executadas pelo compilador.
O compilador Clang (incluindo as partes correspondentes do LLVM) possui cerca de 2 milhões de linhas de código. Para a análise e transformação do código, necessárias para acelerar o C, são necessárias cerca de 200.000 linhas de código (excluindo comentários e linhas em branco).

Por exemplo, para processar uma grande quantidade de dados em C, você precisa escrever um loop que processa cada elemento sequencialmente. Para a execução ideal desse ciclo em um processador moderno, o compilador deve determinar que as iterações do ciclo são independentes uma da outra. A palavra-chave restringir pode ajudar nesse caso - garante que as gravações em um ponteiro não interfiram na leitura de outro ponteiro. Essas informações em C são muito mais limitadas do que em um idioma como o Fortran, que é o principal motivo pelo qual o C não conseguiu tirá-las da computação de alto desempenho.

Depois que o compilador determinar que as iterações são independentes uma da outra, a próxima etapa é uma tentativa de vetorizar o resultado, porque a taxa de transferência dos processadores modernos é quatro a oito vezes maior no código vetorizado do que no código escalar. Uma linguagem de baixo nível para esses processadores teria seus próprios tipos de vetores de comprimento arbitrário. Esses tipos estão presentes na representação intermediária do LLVM, porque é sempre mais fácil dividir operações grandes com vetores em várias pequenas do que construir operações vetoriais maiores.

Nesse ponto, os otimizadores precisam lidar com as regras de memória C. O C assegura que estruturas com o mesmo prefixo possam ser usadas de forma intercambiável e fornece acesso a campos de estruturas de deslocamento no idioma. Isso significa que o compilador não pode alterar a ordem dos campos na estrutura ou adicionar alinhamento para melhorar a vetorização (por exemplo, transformar uma estrutura de matrizes em uma matriz de estruturas ou vice-versa). Isso geralmente não é um problema em linguagens de baixo nível, onde é possível controlar a localização dos campos na estrutura, mas dificulta a tarefa de acelerar o C.

C também requer alinhamento no final da estrutura, pois garante que o alinhamento não esteja nas matrizes. O alinhamento é uma parte bastante complexa da especificação C, que interage mal com outras partes da linguagem. Por exemplo, você deve poder comparar duas estruturas usando o método de comparação sem tipo (ou seja, a função memcmp ()), para que a cópia da estrutura também seja alinhada. Em alguns casos, copiar o alinhamento leva um tempo considerável.

Considere as duas otimizações básicas que o compilador C produz: SROA (substituição escalar de agregados, substituição escalar de agregados) e abertura de loop .

O SROA está tentando substituir estruturas e matrizes de tamanho fixo por variáveis ​​separadas. Isso permite que o compilador processe o acesso a eles independentemente um do outro e ignore a operação, se for óbvio que seu resultado não é usado. Em alguns casos, o efeito indireto dessa otimização é remover o alinhamento.

A segunda otimização, abrindo o loop, converte o loop com a condição em uma condição com diferentes loops nos dois ramos. Isso altera a ordem de execução, em oposição à afirmação de que o programador sabe o que será executado em uma linguagem de baixo nível. E isso também cria sérios problemas com a forma como C lida com variáveis ​​indefinidas e comportamento indefinido.

Em C, uma variável não inicializada possui um valor indefinido, que pode ser diferente a cada chamada. Isso é importante porque permite implementar uma reciclagem lenta de páginas de memória. Por exemplo, no FreeBSD, a implementação malloc () informa ao sistema que as páginas não estão mais em uso, e o sistema usa a primeira entrada na página como prova de que esse não é o caso. O apelo à memória recém-alocada pode obter o valor antigo, o sistema operacional pode reutilizar a página de memória e substituí-la por uma página com zero preenchimento na próxima vez que você gravar em outro local da página. A segunda chamada para o mesmo local na página terá um valor zero.

Se a condição usar um valor indefinido, o resultado também não será definido - tudo pode acontecer. Imagine uma otimização de loop aberto, onde um loop é executado zero vezes. No original, todo o loop é um código morto. Na versão aberta, agora existe uma condição com uma variável que pode não ser inicializada.
Como resultado, o código morto pode ser convertido em comportamento indefinido. Essa é apenas uma das muitas otimizações que, ao explorar mais detalhadamente a semântica de C, acabam não sendo confiáveis.

No final, você pode fazer o código C rodar rapidamente, mas somente depois de gastar milhares de homens-ano criando um compilador inteligente o suficiente. Mas isso só é possível se certas regras do idioma forem violadas. Os criadores de compiladores permitem que programadores C imaginem que escrevem código "próximo ao hardware", mas precisam gerar código de máquina que se comporte de maneira diferente, para que os programadores continuem acreditando que escrevem em uma linguagem rápida.

Entendendo C

Um dos atributos básicos de uma linguagem de baixo nível é que os programadores podem entender facilmente como uma máquina de linguagem abstrata é transferida para uma máquina física. Esse foi definitivamente o caso do PDP-11, onde as expressões C foram traduzidas em uma ou duas instruções. Da mesma forma, o compilador colocou variáveis ​​nos slots da pilha e converteu tipos simples em compreensíveis para o PDP-11.

Desde então, as implementações de C tornaram-se muito mais complicadas - para manter a ilusão de que C é facilmente transportado para uma plataforma de hardware e roda rapidamente. Em 2015, uma pesquisa entre programadores C, autores de compiladores e membros do comitê de padronização mostrou que havia problemas para entender C. Por exemplo, esse idioma permite que uma implementação adicione alinhamento às estruturas (mas não às matrizes) para garantir que todos os campos estejam alinhados corretamente para a plataforma de destino. Se você preencher essa estrutura com zeros e especificar um valor para alguns campos, haverá zeros nos bits de alinhamento? Segundo a pesquisa, 36% tinham certeza de que sim e 29% não sabiam a resposta. Dependendo do compilador e do nível de otimização, isso pode ser verdade (ou não).

Este é um exemplo bastante trivial, mas muitos programadores dão a resposta errada ou não conseguem responder.

Se você adicionar ponteiros, a semântica de C se tornará ainda mais confusa. O modelo BCPL era bastante simples: todos os significados são palavras. Cada palavra é um dado ou um endereço na memória. A memória é uma matriz plana de células indexadas por endereço.

O Modelo C permite a implementação de diferentes plataformas, incluindo arquiteturas segmentadas, nas quais o ponteiro pode consistir em IDs e compensações de segmentos, além de máquinas virtuais com um coletor de lixo. A especificação C restringe as operações permitidas do ponteiro para evitar problemas com esses sistemas. A resposta ao Relatório de Defeitos 260 menciona a origem do ponteiro:

“As implementações podem seguir a origem de um conjunto de bits e lidar com aqueles que contêm um valor indefinido de forma diferente daqueles que contêm um valor específico. "Eles podem lidar com ponteiros de maneira diferente, dependendo de sua origem, mesmo que sejam os mesmos em termos de valor de bits".

Infelizmente, a palavra "origem" está ausente na especificação C11, então os compiladores decidem por si mesmos o que isso significa. O GCC e o Clang, por exemplo, diferem se o ponteiro que foi convertido no número inteiro e vice-versa mantém sua origem. Os compiladores podem decidir que dois ponteiros para os resultados de malloc () sempre dão um resultado negativo ao comparar, mesmo que apontem para o mesmo endereço.

Esses mal-entendidos não são puramente acadêmicos. Por exemplo, já foram observadas vulnerabilidades, que foram o resultado do transbordamento de um número inteiro assinado (comportamento indefinido em C) ou da desreferenciação de um ponteiro antes de procurar NULL , apesar do fato de o compilador ter sido informado de que o ponteiro não podia ser NULL.

Se houver tais problemas, é difícil esperar que um programador entenda completamente como um programa C se traduz na arquitetura apropriada.

Introduzindo um processador não para C

Os patches propostos para proteção contra Spectre e Meltdown causam severa degradação do desempenho, anulando todas as conquistas da microarquitetura na última década. Talvez seja hora de parar de pensar em como tornar o código C mais rápido e, em vez disso, pensar em novos modelos de programação em processadores projetados para aumentar a velocidade.

Existem muitos exemplos de arquiteturas que não se concentraram no código C tradicional e para inspirar. Por exemplo, processadores orientados a multithreading, como o Sun / Oracle UltraSPARC Tx, não exigem muito cache para manter seus atuadores ocupados. Os processadores de pesquisa expandiram esse conceito para um número muito grande de threads planejados por hardware. A ideia principal é que, com threads suficientes, o processador possa pausar os threads que estão aguardando dados e preencher os atuadores com instruções de outros threads. O problema é que os programas C geralmente têm muito poucos threads.

O SVE da ARM (Extensões de vetores escalares, extensões de vetores escalares) é outro trabalho semelhante de Berkeley, que oferece uma olhada na interface aprimorada entre o programa e o hardware. Blocos de vetorização regulares implementam operações com vetores de tamanho fixo e esperam que o compilador adapte o algoritmo ao tamanho especificado. Por outro lado, a interface do SVE solicita ao programador que descreva independentemente o nível de paralelismo e espera que o hardware o adapte aos atuadores disponíveis. Usar isso em C é difícil porque o auto-vetorizador precisa calcular o paralelismo com base nos loops do código.

Os caches são grandes, mas esse não é o único motivo de sua complexidade. O protocolo de suporte à coerência de cache é um dos componentes mais complexos de um processador moderno. A maior parte da dificuldade vem de ter que manter um idioma no qual os dados possam ser compartilhados e mutáveis. Como exemplo oposto, podemos usar uma máquina abstrata do estilo Erlang, onde cada objeto é local ou imutável. O protocolo de coerência de cache para esse sistema teria apenas dois casos: dados mutáveis ​​e dados compartilhados. O cache do fluxo do programa que foi transferido para outro processador deve ser explicitamente desativado, mas essa é uma operação relativamente rara.

Objetos imutáveis ​​podem simplificar ainda mais os caches e também tornar algumas operações mais baratas. Em um projeto Maxwell do Sun Labs, observou-se que os objetos no cache e nos objetos criados recentemente são quase sempre os mesmos. Se os objetos morrerem antes de serem excluídos do cache, você não poderá gravá-los na memória principal e assim economizar o consumo de energia. O projeto Maxwell propôs um coletor de lixo que funcionava no cache e permitia reciclar rapidamente a memória. Com objetos imutáveis ​​na pilha e pilha mutável, o coletor de lixo se torna uma máquina de estado muito simples, que é facilmente implementada no hardware e permite que você use eficientemente um cache relativamente pequeno.

Um processador projetado exclusivamente para velocidade, e não para a troca entre velocidade e suporte C, provavelmente deve suportar um grande número de encadeamentos, ter grandes blocos de vetorização e um modelo de memória mais simples. Será difícil executar o código C nesse processador; portanto, dado o volume do código C antigo no mundo, é improvável que tenha sucesso comercial.

No campo do desenvolvimento de software, existe um mito de que a programação paralela é difícil. Alan Kay ficaria muito surpreso ao ouvir isso: ele ensinou as crianças a usar o modelo de ator, com o qual eles escreveram programas em mais de 200 transmissões. Isso também é desconhecido para os programadores Erlang, que costumam escrever programas com milhares de componentes paralelos. É mais correto dizer que a programação paralela é difícil em uma linguagem com uma máquina abstrata como C. E se você prestar atenção à predominância de hardware paralelo (de processadores com vários núcleos a GPUs com vários núcleos), essa é apenas outra maneira de dizer que C não é adequado para hardware moderno fornecendo.