Brincando com Numba pra poder usar Python no Google Code Jam 2014

TL;DR; Fiz uns testes simples simplórios com o numba, com uma abordagem não-científica, na solução de um problema para o code jam’14. Obtive um speed-up de 50x e fiquei faceiro por poder continuar usando Python nos próximos rounds (hahaha, como se eu fosse passar). A proposta não é explicar como o numba funciona, mas apenas como ele me ajudou e, quem sabe, pode te ajudar.

The long story

Semana passada ocorreu o qualification round do code jam 2014 e eu, que gosto muito desse tipo de competição desde a faculdade, despretensiosamente tentei resolver os dois probleminhas mais fáceis e acabei passando de fase.

No qualification round eu usei  Python, mas conforme os rounds vão avançado os problemas vão se complicando e as estatísticas mostram que a proporção de competidores que usam C/C++ e Java vai crescendo, enquanto as outras linguagens vão ficando pra trás, principalmente por performance.

Como eu já estava interessado em dar uma olhada nas alternativas mais modernas (fáceis, 80/20, you know?) de otimizar minhas soluções em Python, e não estou afim de usar Java (awesome language, btw) ou C++ nas minhas horas de lazer, aproveitei o feriadão pra brincar um pouco, nada rigoroso.

O que “pega” é que temos muitas alternativas hoje(!): numpy, cython, pypy, jython, numba, blaze, numexpr, entre outros, sem falar na joblib, sobre a qual eu pretendo escrever um (ou mais) post mais pra frente. A boa notícia é que a maioria dessas alternativas pode se complementar e podemos ter small-wins fáceis só estudando um pouco.

Enfim, comecei a ler artigos aleatórios e acabei concluindo que o numba seria uma boa primeira tentativa, principalmente porque ia doer menos, como vamos ver agora.

Instalando

Very easy, se você não se importa de usar o conda (no OSX não sei se tem pra onde fugir):

$ conda install numba

Otimizando

Como o meu objetivo de curtíssimo prazo era ver se o numba seria uma boa opção pra usar no próximo round, nada melhor do que testá-lo nos problemas do round anterior.

Você não precisa se preocupar muito em entender 100% do código (e eu não me preocupei em deixá-lo 100% legível :D), porque eu vou destacar as partes mais importantes a cada etapa de otimização, mas o código original que eu submeti durante a competição para o problema Cookie Clicker foi o seguinte:

#!/usr/bin/env python
# coding=utf-8

import fileinput

data = (l for l in fileinput.input())
T = int(data.next())

def worth_build_another_farm(rate, C, F, X):
    time_to_reach_X = X / rate
    time_to_build_another_farm = C / rate
    time_to_reach_X_in_the_new_rate = X / (rate + F) 

    return time_to_reach_X > time_to_build_another_farm + time_to_reach_X_in_the_new_rate

for i in xrange(1, T+1):
    C, F, X = [float(f) for f in data.next().split()]

    rate = 2.0 # cookies/sec
    elapsed_time = 0.0

    while worth_build_another_farm(rate, C, F, X):
        elapsed_time += C / rate # time to build another farm
        rate += F 

    # by now I've burned all cookies building new farms
    elapsed_time += X / rate 

    answer = elapsed_time
    print('Case #%d: %.7f' % (i, answer))

Em alto nível, são apenas dois loops: o primeiro for que lê a entrada e o while que chama a função #worth_build_another_farm enquanto fizer sentido para cada entrada, nada de complicado.

Esse código estava resolvendo o Large Input em 0.3s.

Não tem mágica

O jeito mais simples de usar o numba é através do decorator @numba.jit, usado para indicar que a função deve ser compilada just-in-time. Assim, a minha primeira tentativa de otimização foi, logo de cara, colocar um @numba.jit na função #worth_build_another_farm, que resultou em um tempo de execução de 0.4s… Wat?

O que eu posso imaginar é que o tempo de execução do script não era lá dos maiores e, logo, o tempo que o numba levou pra compilar a função (JIT, lembram?) não se pagou.

A primeira vitória

Com isso eu pensei: “será que se eu jogar TODA a lógica do script (fora a leitura do input) para o numba otimizar vai resultar em ganho?”. O primeiro passo foi refatorar o código e colocar toda a lógica em apenas uma função, a #elapsed_time abaixo:

@numba.jit
def elapsed_time(rate, C, F, X):
    def worth_build_another_farm(rate, C, F, X):
        time_to_reach_X = X / rate
        time_to_build_another_farm = C / rate
        time_to_reach_X_in_the_new_rate = X / (rate + F)

        return time_to_reach_X > time_to_build_another_farm + time_to_reach_X_in_the_new_rate

    elapsed_time = 0.0

    while worth_build_another_farm(rate, C, F, X):
        elapsed_time += C / rate # time to build another farm
        rate += F

    # by now I've burned all cookies building new farms
    return elapsed_time + X/rate

start = time.time()

for i in xrange(1, T+1):
    C, F, X = [float(f) for f in data.next().split()]

    rate = 2.0 # cookies/sec

    answer = elapsed_time(rate, C, F, X)

É interessante notar aqui que, apenas com essa modificação (sem usar o numba) o tempo de execução com Python puro já caiu pra 0.23s. Isso ocorre muito provavelmente pela redução do escopo da #worth_build_another_farm, que agora é uma nested function e buscar por ela tornou-se mais rápido do que buscar no escopo global.

Contudo, ao tentar usar o numba dessa vez, obtive um erro:

NotImplementedError: offset=3 opcode=84 opname=MAKE_FUNCTION

E com isso chegamos à nossa 2ª lição: o numba não otimiza nested functions (linha 2).

A segunda vitória

Refatorando o código para remover a nested function e, finalmente, podendo usar a @numba.jit:

@numba.jit
def elapsed_time(rate, C, F, X):
    elapsed_time = 0.0

    worth = True
    while worth:
        time_to_reach_X = X / rate
        time_to_build_another_farm = C / rate
        time_to_reach_X_in_the_new_rate = X / (rate + F)
        worth = time_to_reach_X > time_to_build_another_farm + time_to_reach_X_in_the_new_rate

        if worth:
            elapsed_time += C / rate # time to build another farm
            rate += F

    # by now I've burned all cookies building new farms
    return elapsed_time + (X / rate)

start = time.time()

data = (l for l in fileinput.input())
T = int(data.next())

for i in xrange(1, T+1):
    C, F, X = [float(f) for f in data.next().split()]

    rate = 2.0 # cookies/sec
    answer = elapsed_time(rate, C, F, X)
    #print('Case #%d: %.7f' % (i, answer))

print "Finished in ", time.time()-start, " secs."

Conseguimos uma nova vitória com o novo tempo de execução de 0.06s.

A terceira vitória

Nesse momento eu já tinha um speed-up razoável, de 5x, apenas refatorando o código e adicionando um decorator. Contudo, a @numba.jit ainda estava sendo usada na sua forma mais simples, em que o numba é forçado a fazer inferência dos parâmetros e do retorno da função.

Por sorte, podemos ajudar o numba a nos ajudar. Nós podemos dizer ao numba quais são os tipos dos nosso parâmetros e o tipo do retorno da função. Para esse problema, eu sabia que os parâmetros seriam sempre floats e um int e que o retorno seria sempre um float. Será que definindo a assinatura da função seria possível obter um tempo melhor? Alterando a linha 1 do código anterior para:

@numba.jit('f8(f8,i4,f8,f8)')

obtive a terceira vitória com um novo tempo de execução: 0.006s.

Great, agora temos um speed-up apresentável, de 50x. Por hoje, estou satisfeito :D

Conclusões

É possível obter algumas melhoras rápidas no desempenho do código com o numba. Se a #elapsed_time fosse o principal gargalo no processamento de 1M de linhas de um banco de dados, por exemplo, ao invés de esperar 83.3 horas com a solução inicial, esperaríamos apenas 1.6 horas, tudo por causa de um refactoring e um decorator do numba.

Not bad

Por fim, usar o numba tem suas implicações e, como vimos na primeira tentativa de otimização, ele não pode ser utilizado indiscriminadamente. Caso você decida utilizá-lo, vale a pena começar pelos seguintes textos para que você tenha uma visão melhor dos trade-offs  a que estará sujeito e dos ganhos que pode esperar obter:

Ah, você pode encontrar as versões intermediárias do cookieclicker no meu github.

Book Review: The Phoenix Project

The Phoenix Project

No mês passado eu li o The Phoenix Project, livro que estava na primeira posição do Top 100 Agile Books do Jurgen Appelo, primeiro motivo pelo qual eu achei legal dar uma olhada. O segundo foi porque ele é A Novel About IT, DevOps… e eu ainda não tinha parado pra criar uma imagem bem definida sobre o que é esse tal de DevOps que o povo tanto fala por aí.

Como o próprio subtítulo já diz, se trata de A Novel, ou seja, uma historinha, um romance. Então, não espere um livro técnico cheio de do’s and don’ts.

Pra ser bem sincero, o começo da história é um pouco entediante e eu quase desisti de lê-lo quando estava lá pela centésima página (de um livro de 340 páginas!). Contudo, após o primeiro terço não tão legal, a coisa começa a esquentar. Como não é um livro técnico, não vou entrar em muitos detalhes da trama para não estragar a sua leitura. Contudo, fica a dica para perseverar.

O livro conta a história do Bill, que era chefe de uma pequena divisão e acaba sendo promovido a VP of IT Operations de uma empresa de peças para carros, na qual se tinha a visão de que TI era apenas uma atividade meio. Ao assumir o cargo ele se depara com várias bizarrices no modo como as coisas eram feitas na empresa, que era totalmente disfuncional. Essa empresa tinha o tal do Projeto Phoenix que deveria ser a salvação da lavoura, pois a tiraria de um atraso de anos (porque o Phoenix estava atrasado há anos) em relação aos competidores. O problema é que havia vários problemas que forçavam as equipes a passar a maior parte do tempo apagando incêndios.

O restante do livro conta o processo pelo qual o Bill, auxiliado pelo seu mentor Erik, passa a entender o que é realmente importante para a entrega de software e começa a desfazer os erros do passado utilizando abordagens que integram mais todas as partes envolvidas na produção e entrega de um software (ah, o tal do DevOps).

Bem, em alto nível é isso, não quero estragar a sua leitura. Mas gostei do formato pouco comum para apresentar de forma suave tópicos que são difíceis para algumas pessoas de serem compreendidos quando são apresentados através de regras em um livro mais técnico. É legal que a gente se sente na pele do cara responsável por resolver pepinos que muita gente deve encontrar nas próprias empresas onde trabalham. Principalmente para aqueles que ainda trabalham em empresas  em que devs, testers, OPs e afins trabalham isoladamente, recomendo a leitura do livro. Quem sabe ele sirva de inspiração para futuras mudanças positivas no seu dia-a-dia. Ou então passa pro teu chefe, quem sabe assim ele abre o olho :D

Para o pessoal que já tem acompanhado e tentado aplicar técnicas mais Lean/Ágeis nas suas empresas, acho que o livro não vai agregar tanto, mas ainda vale como uma leitura mais leve, de lazer.

Uma lista de listas de livros que todo programador deveria ler

Cansado de ficar no facebook? A sua timeline do twitter não tem novidades? Seus problemas acabaram.

Uma vez algum sábio me disse: encontre um guru e descubra quem são os gurus desse guru. É assim que você vai encontrando fontes de informação/inspiração/luz, cria a sua árvore genealógica de sabedoria e consegue melhorar em seja-lá-o-que-for-que-você-quer-fazer. Acho que um jeito simples de começar essa jornada é encontrar as listas de livros que os gurus apontam como leituras obrigatórias. Aí você lê alguns desses livros, que vão ter referências a outros livros e outros e então você começa a encontrar alguns que são mais referenciados e mais fundamentais e por aí vai, ad infinitum.

Acho isso importante também porque dessa maneira você acaba chegando na origem das informações. Você não lê a releitura da cópia do plágio que alguém entendeu errado. Você bebe direto da fonte. É um caminho mais longo e dá mais trabalho, mas é também o caminho que leva à formação mais sólida que se pode conseguir (juntando com a prática).

Eu consultei os meus gurus e encontrei várias listas de livros que você, como bom (aspirante a?) programador, poderia gostar de ler. No final eu separei os livros mais recomendados, pra facilitar a sua vida.

É importante notar que algumas dessas listas são interessantes não somente pelas indicações em si, mas também pelas justificativas dadas para as indicações. É uma das maneiras de entender melhor como esses caras pensam e enxergam a área.

Essa lista é especialmente relevante porque o nosso tempo é limitado. Então prefiro ler um livro recomendado por pessoas mais experientes e inteligentes que eu a ler um livro qualquer ou com uma recomendação mais fraca.

As listas

Peneirando

Na minha peneirada informal, alguns que eu encontrei várias vezes (e podem ser o seu começo) foram:

  • The Mythical Man Month
  • Peopleware
  • Code Complete
  • Refactoring

No final das contas, pelo o que eu tenho visto, esses livros da peneirada realmente são clássicos que são pesadamente referenciados e você não vai perder o seu tempo lendo.

Tentei, mas não consegui encontrar a lista do Knuth. Ele até criou uma lista, mas é de romances.

Artigos?

E tem também a reading list do Michael Feathers, mas não é de livros, mas de artigos que, segundo ele, todo programador deveria ler ao menos duas vezes.

O Fogus também fez uma lista de 10 artigos. Esse é um cara que lê 200 livros por ano, então acho que ele serve como um bom filtro de ruído.

Enfim, acredito que esses são bons pontos de partida pra quem estiver atrás de mais fundamentos.

Até o próximo post,

Ps: Comenta aí se esqueci de alguma que você considera importante :)

Sobre os dois tipos de livros de programação

“Vivemos em uma época em que o fio da história se perde em meio ao imediatismo”

~ Rosiska Darcy de Oliveira

Há algum tempo estou com esse post na cabeça e só agora tive motivação para colocá-lo no papel. São apenas algumas coisas que aprendi e que acho que, especialmente se você estiver começando, podem ajudá-lo a tomar decisões um pouco melhores na hora de escolher um livro visando a se tornar um programador melhor (1). Atente-se ao que eu disse: programador melhor, e não “arranjar um emprego” ou “receber um aumento” (2), que são importantes, mas junto com outras coisas como “orgulho do que se faz” e peace of mind (estranhamente pouco valorizada no nosso meio e ainda procuro o porquê disso).

Ao que interessa. No clássico meta-livro How to Read a Book(3) os autores fazem uma divisão interessante dos livros práticos em duas categorias: os que fornecem predominantemente regras explícitas e os livros de fundamentos.

Livros que fornecem regras explícitas

Estes são os cookbooks e manuais em geral. É mais difícil encontrar livros de qualidade, do tipo que vão te engrandecer de alguma forma, nesta categoria. Não podem ser descartados, porque no final das contas algum código terá que ser escrito.

Infelizmente, vejo muitas pessoas no mercado que se interessam (quando se interessam) apenas por livros desse tipo. Tenho uma leve impressão de que são as mesmas pessoas que acham que desenvolvimento de software é um sofrimento. Que deployments são uma roleta russa. Que acham que o cliente é um sacana porque muda os requisitos, sendo que software que eles escreveram é difícil de mudar que dói. Assim como os livros que os formaram, o software escrito por essas pessoas também é efêmero.

Esse é o tipo de livro que vale a pena você economizar um dinheiro e comprar o e-book mesmo, até porque em poucos meses ele se tornará um peso morto na sua casa, nem o sebo vai querer. Ah! Hoje em dia algumas editoras legais como a PragProg atualizam os seus e-books quando novas versões do software são lançadas, aumentando um pouco a vida útil desse tipo de livro. Contudo, geralmente a gente não revisita esses livros. A gente olha, aplica e pronto. Não há nada mais a ser explorado. Você não vai querer matar árvores por uma rapidinha, vai?

Não é interessante restringir a sua formação apenas a esse tipo de livro, pois o seu conhecimento será sempre superficial.

Livros de fundamentos

Os autores de livros dessa categoria estão mais preocupados em fazer você entender os porquês, ao invés dos comos, apesar dos últimos virem de brinde muitas das vezes. A maioria dos bons livros está nessa categoria.

São estes livros que vão mudar (ao menos um pouco) o seu jeito de pensar. Vão mudar o seu processo de construção de um programa. Em outras palavras, vão provavelmente te tornar um melhor designer, que sofre menos pra construir e manter o seu código. Nesses vale a pena você gastar um pouco mais e ter a cópia física, principalmente porque eles demoram muito mais pra envelhecer e você vai querer revisitá-los. O mais legal desses livros é que você aprende coisas novas quando os lê novamente (com limites, obviamente).

Cuidado! Algumas pessoas, às vezes, rejeitam ou acreditam que um livro de fundamentos é um livro de receitas só porque possui o nome de uma linguagem no título ou porque ficam sabendo que os exemplos são todos em uma linguagem. Exemplos de ótimos livros de fundamentos que eu li, recomendo e que se encaixam nessa categoria:

  • GOOS: “mas todos os exemplos são em Java”, e daí? Você sabe “cultivar software guiando-se por testes”?. Quem não tem sequer a curiosidade de saber sobre o que um livro com esse título fala, provavelmente não deveria estar na indústria de software.
  • POODR: “tem ruby e prático no título e os exemplos são em ruby”, e daí? É um livro bastante pragmático sobre orientação a objetos e a Sandi Metz tenta ao máximo não fornecer regras simples e rápidas (apesar de o fazer em alguns momentos, mas nada que comprometa).

Por fim, nem sempre é possível saber se um livro é um livro de fundamentos ou se é um cookbook apenas olhando o título. Felizmente hoje em dia a gente consegue dar uma olhada em alguns capítulos de graça na internet. Ainda assim, sempre vai sobrar espaço para subjetividade. O ideal é não dar tiros no escuro e sempre pender para livros, predominantemente, sobre fundamentos. Essa é também a hora que os gurus entram em cena. Se você ainda não tem os seus gurus, está na hora de encontrá-los.

Em breve eu publico um post sobre algumas dicas de livros e gurus, se você estiver mais perdido do que eu :D

(1) Na verdade o que eu falei aqui se aplica a livros práticos em qualquer área, eu só contextualizei pra programação.
(2) Sim, em um mundo ideal faria sentido que os fundamentos fossem mais valorizados. Mas, além do imediatismo, acho que avaliar o domínio sobre os fundamentos de uma pessoa é um pouco subjetivo e requer tempo e bons conhecimentos também por parte de quem avalia. Um arranjo de estrelas difícil de se encontrar em alguns departamentos de RH, até onde eu sei. Mas existem empresas que conseguem avaliar e valorizam isso, não perca as esperanças!
(3) Aproveitando, recomendo fortemente. Só para se ter uma ideia. Os autores classificam os leitores em quatro níveis e, para eles, quem apenas lê um livro de ponta a ponta de forma passiva (eu fiz isso por muito tempo) ainda está no nível 1.

5 regras rápidas para fazer um bom commit

Vou assumir que você usa Git, então:

  1. Faça apenas uma alteração por commit. Mas o que é uma alteração? Se você consegue descrever o commit sem usar E, provavelmente está fazendo apenas uma alteração
    1. “Mas e se no meio da alteração eu vir alguma coisa errada?” Anote e faça depois, em outro commit.
    2. “Mas não tem jeito, eu preciso fazer isso antes”. Blz, git stash.
  2. Faça a alteração inteira em um commit. Se for muito grande, você pode fazer pequenos commits e depois usar squash para transformá-los em apenas um.
  3. Documente o que você mudou. Um formato legal, que você pode usar como partida:
    1. Alguma classe: usei bleh ao invés de xyz no #metodoQualquer (isso resolve FOO-123)
  4. Documente o porquê da alteração.
    1. Isso também vale para os comentários no código. Isso é importantíssimo para que alterações sejam feitas com confiança no futuro. Ninguém vai deixar de alterar porque “está assim por algum bom motivo” e nem vai alterar de um jeito que tenha efeitos colaterais não óbvios (o que não deveria acontecer, mas…)
  5. Não faça commit de código comentado. Acho que essa é a regra que tem mais resistência por aí. Mas eu nunca vi código comentado ressucitar.

Acho que é uma boa checklist pra se verificar antes de fazer um commit. Você retiraria ou adicionaria alguma coisa? Enlighten me.

Mais detalhes em What's in a good commit.

Generating word clouds based on the frequencies of change in a git project

Hi, for quite some time I’ve been wanting to visualize the files that were most changed in my projects.

I’ve even considered building my own heatmap generator. It turns out that this task can be quite easily accomplished with bash and a simple project called defect-density-heatmap by @bcarlso. It will let us build a word cloud like this:

Word Cloud

Extracting the frequency data

The first step is to extract the frequencies from our repository. This can be done using the following bash script, which I will call freqs.sh:


#!/bin/bash

git rev-list --objects --all | awk '"" != $2' | sort -k2 | uniq -cf1 | sort -rn |
while read frequency sample path
 do
 [ "blob" == "$(git cat-file -t $sample)" ] && echo -e "$frequency,0,$path";
 done |
grep -v '^1,'

The above script discards files that were touched only once, which is useful if your project has too many files. If you want to visualize all files, just remove line 8 and the pipe in the end of line 7.

Generating the word cloud

Generating the word cloud is easy. After cloning the defect-density-heatmap project, all you have to do is run the bin/heatmap script using the output of freqs.sh as its input. Something like


freqs.sh | ...defect-density-heatmap/bin/heatmap > wordcould.html

Bonus

If you read the README of the defect-density-heatmap carefully, you will notice that the author also intended to use it to better visualize the cause for changing the files. The idea is quite interesting  and is based on a convention on the commit messages. Simple and effective.

Sources

Find out which files have had the most commits

Uma lista de listas para aprender Data Science e Machine Learning

Parece-me que data science e machine learning são tópicos quentes hoje em dia, certo?

Eu quero que você se sinta mal, porque há tanta informação disponível e você ainda gasta o seu tempo vendo tv, na internet ou pior: com a sua família e amigos!

Assim, montei uma pequena lista de listas de links para aprender data science e machine learning (mesmo que você seja um completo iniciante):

  • Uma das primeiras a circular por aí foi a “A practical intro to data Science“, que é bem completa, cobrindo boa parte dos tópicos necessários para você, finalmente, pode se intitular um Data Scientist.
  • Mais recentemente, a Radical Data Science “pseudo degree program” foi publicada. Gostei do formato e também porque não é tão extensa, dá pra você encarar mais facilmente essa. Ah, sim. Há uma interseção entre as listas
  • Outras lista interessante também é  a “A list of  Data Science and Machine Learning Resources”, divida em duas partes: parte 1 e parte 2.
  • Agora, se você quiser algo um pouco mais dinâmico, tem também o decidingdata.com, que possui tanto links para notícias quanto para fontes de aprendizado.
  • Tem também a wiki do Kaggle, que está bem enxuta, straight to the point.
  • Encontrei também essa que tem uns links bons para os fundamentos matemáticos: Machine Learning Self-Study Resources.

No final a lista ficou curta, mas elas vão te levar a lugares suficientes para manter-te ocupado pelos próximos 10 anos. Também acho que mais cedo do que imagino vou ter mais links para atualizar esse post.

Ah! Mas Zé, eu vou ficar só estudando? Eu quero praticar! Bom, você pode usar a sua imaginação e resolver problemas com o que você aprender. Se estiver sem imaginação você pode competir no Kaggle. Ouvi dizer que é divertido :)

————

Update 2013-06-14: Adicionei também a wiki to Kaggle.