terça-feira, 23 de maio de 2017

Ontem o alphago ganhou mais uma, vitória por meio ponto em cima do Ke Jie, campeão chinês. Antes que alguém ache que ele ganhou raspando, lembro que o algoritmo do alphago é tunado para maximizar a probabilidade de vitória, não para maximizar a diferença de pontos. Então é comum que a diferença seja pequena mesmo.
Na partida contra o Lee Sedol o alphago fez um monte de jogadas loucas e fora do comum. Eu estava esperando ver isso de novo, e aconteceu mesmo. Só que as jogadas doidas vieram do Ke Jie!
Isso faz sentido, e eu cantei essa bola na minha análise dos jogos contra o Sedol ano passado. O alphago tem dois estágios de processamento, uma rede neutral treinada com partidas profissionais, e um monte Carlo tree search. Se você fizer jogadas loucas, você neutraliza a rede neural, e briga só com o mcts. O Ke Jie estava tentando fazer isso (mas não foi o suficiente).
A impressão que eu tive na partida é que eu não sei mais jogar Go. Os dois estavam fazendo jogadas que até ano passado eram consideradas ruins (tipo invadir o sansan no começo do jogo, como assim?). Mas ouvindo os comentaristas parece que é assim que os outros estão jogando hoje em dia, eles aprenderam essas jogadas com o alphago e agora elas são mainstream.
Os comentaristas foram curiosos também, era claro que o ocidental comentando era mais forte que a chinesinha, mas eu entendia melhor os comentários dela (porque está mais próximo do meu nível, o ocidental é avançado demais pra mim). E a chinesinha falando era engraçado porque ela falava em inglês, mas com sotaque chinês, e usando termos técnicos em japonês (sente, dame, etc).
Também achei engraçada a contagem de pontos, a chinesa contou os pontos das brancas de um jeito muito louco, eu não entendi a conta dela haha. Mas o Ke Jie parecia estar entendendo.
A próxima é na quarta, vou assistir mas já não tenho muita esperança de ver o humano ganhando.


sábado, 13 de maio de 2017

Essa semana eu achei um bug em três compiladores diferentes!

Eu estava de boa otimizando o rgzip quando notei ele gerando um assembly bizarro. A função era equivalente a essa:

fn vecsum(v : &[u32]) -> u32 {
return v[0] + v[1] + v[2] + v[3] + v[4] + v[5];
}

O Rust tem como princípio sempre fazer bounds checking para evitar buffer overflow, isso é cool. Mas olha só o assembly que ele gera:

movq %rsi, %rax
testq %rax, %rax
je .LBB0_7
cmpq $1, %rax
je .LBB0_8
cmpq $3, %rax
jb .LBB0_9
je .LBB0_10
cmpq $5, %rax
jb .LBB0_11
je .LBB0_12

Um bound check para cada acesso! Claramente não precisava. Se você fizer só o bound check no v[5], então todos os outros garantidamente passam, porque o vetor é contínuo.

Reportei isso na comunidade de Rust e aí ficou mais bizarro ainda. Primeiro, o bug não aparece se você inverter a função:

return v[5] + v[4] + v[3] + v[2] + v[1] + v[0];

Segundo, não é um bug do Rust, é na camada mais embaixo do LLVM. A gente sabe disso porque um código equivalente em C++ no clang gera o mesmo bug:

struct Vec {
int len;
int* data;
};

inline int get(struct Vec* vec, int i) {
if (i < vec->len) {
return vec->data[i];
} else {
abort();
}
}

int sum5(struct Vec* vec) {
return get(vec, 0) + get(vec, 1) + get(vec, 2) + get(vec, 3) + get(vec, 4) + get(vec, 5);
}

Por fim, o bug não é só no LLVM, ele aparece também no gcc e o no icc! Confiram:


Já foi tudo reportado, agora é só esperar alguém consertar. Idealmente eu mesmo consertaria, mas infelizmente a vida é curta :(



sábado, 29 de abril de 2017

Eu estava com vontade de escrever um descompressor de gzip do zero, também estava com vontade de aprender Rust, aí pensei: por que não os dois ao mesmo tempo? O resultado é o rgzip:
A parte gzip foi relativamente simples, eu só segui os RFCs. Por dentro ele é um LZ codificado com Huffma, não tem muito segredo. Mas tem duas coisas curiosas sobre o formato.
A primeira é que ficou claro para mim que o Phil Katz escreveu a primeira versão em assembly. Tem partes do formato que são difíceis de escrever em linguagens de alto nível, mas são triviais para quem tem rot e shl.
A segunda é que o formato permite emular RLE, usando janelas para o futuro. Por exemplo, se o arquivo começa com AB, você pode colocar uma janela "volta 2 e copia 6", aí o output é ABABABAB.
Sobre a linguagem Rust, achei bem bacana. A idéia foi tentar construir uma linguagem focada em segurança, onde é impossível programar um bug. Ele faz isso colocando restrições bem severas no tipo de código que você consegue escrever, e usando compile-time checks para garantir isso.
Por exemplo, em C++ você pode fazer isso:
int *func () {
int x = 1;
return &x;
}
Esse código vai dar segfault porque x estava no stack, quando a função retorna o x já morreu. Em Rust isso nem compila, ele saca que o lifetime do &x está restrito ao escopo da função e não deixa você retornar o ponteiro.
Outro problema do C++ é assim:
class X {
X(int *p) : p_(p) {}
int *p_;
};
int *p = new int;
X x(p);
E aí, quem vai dar o delete *p, o X() ou quem chamou o X()? O Rust resolve isso com sintaxe própria para dizer quem é o dono do ponteiro. (E como ele sabe quem é o dono, você nem precisa dar o delete. Ele deleta sozinho quando o dono sai do escopo).
Tem mais um monte de manhas, achei bem legal. Outras características são:
- Ele usa o sistema de type inference do Haskell, e tem muitas ferramentas de programação funcional disponíveis.
- O const é invertido em relação ao C++. Por default, todas as variáveis são const, se você quiser alterar o valor de uma variável precisa declarar como mut (inspirado em linguagens funcionais provavelmente).
- A sintaxe lembra bastante o Go, mas ele possui generics, o que é uma grande vantagem! Generics + type inference permite pegar um monte de erros em tempo de compilação.
- Além de generics, ele tem também macros! Mas não são as macros podres do C, ao invés de preprocessar texto, as macros do Rust atuam em cima da syntax tree do Rust. Muito mais legal e ainda permite um tipo de "template metaprogramming".
- Ele não tem o tipo int! Todos os tipo precisam ser explicitamente declarados. Ao invés de int você pode usar u32 ou i16.
- E falando nisso, ele não absolutamente nenhum tipo de cast automático, nem para variáveis inteiras. Você precisa explicitamente fazer um cast para copiar um valor u8 para uma variável u32. Isso vem da filosofia dele de ser o mais explícito possível.
- A stdlib dele é pequena, mas tudo bem porque ele tem um pip-like no pacote default. É só dar um include que ele baixa e instala a lib externa sozinho.
- Em geral, é mais difícil programar em Rust que em Go, C++ ou Python. Mas tem um motivo, é que você é obrigado a escrever um programa sem bugs sempre, senão não compila. Um monte de coisas nas outras linguagens só são fáceis porque você pode ignorar side-effects ou tratamento de erros.
- Inclusive, Rust não tem exceptions. Todo o tratamento de erros é feito com o Option<> e Result<> do Haskell (que colocaram recentemente no java também). Acho isso muito, muito melhor que retornar tuplas como no Go.
- Ele não tem goroutines, mas tem um sistema de threads usando canais para concorrência. Ainda não testei, mas o doc diz que ele pega deadlocks em tempo de compilação. Veremos.
- Ele também não tem garbage collector, mas nem precisa porque o sistema de RAII, lifetime e ownership explicito toma conta da memória sem precisar de gc.
Recomendo dar uma olhada, achei promissor. Já está na versão 1.x então a linguagem está mais ou menos estável. Eu lembro que programei bastante no Go 0.x e os meus programas dessa época nem compilam mais, em Rust stable isso não deve acontecer.