Quando começamos a administrar a frota da Visual Units, uma coisa que foi muito difícil de conseguir fazer direito foi o cálculo das distâncias. Não havia um fim das informações disponíveis e quase tudo estava em um nível de matemática muito além de um pobre desenvolvedor que considera que qualquer coisa além de matemática discreta (ou finita), geometria básica e estatística, já é problema de outra pessoa. As implementações que puderam ser encontradas eram versões proprietárias com que não podíamos arcar naquele estágio.

Por um tempo, resolvemos o problema utilizando uma solução que dependia da projeção cônica de Lambert – era precisa o suficiente, mas não perfeita, e nossos mapas utilizavam a mesma projeção, portanto funcionou – apesar do fardo de ter que transformar nossas coordenadas WGS-84 em Lambert toda vez que o cálculo precisasse ser feito. Alguns anos atrás, entretanto, mudamos para a API do Google Mapas e por isso o Lambert não tinha mais serventia alguma – e o aumento da demanda por carga e precisão fez com que utilizar a solução atual fosse uma escolha cada vez pior.

Aqui entra Chris Veness. Ou melhor, sua implementação da fórmula de inversão de Vincenty (pdf). Apesar de a matemática estar além da minha compreensão, portar a implementação JavaScript para Python foi algo objetivo e direto e alguns testes mostraram que o resultado era mais rápido e preciso do que a solução anterior.

Adiantando alguns meses, de repente o desempenho começa a parecer algo que podia se tornar um problema. Temos muitos motivos para calcular distâncias, e enquanto os trabalhos em lote não fossem um problema, qualquer quantidade de tempo que pudesse ser economizada de ações iniciadas por usuários é muito bem-vinda.

Então, pensei comigo mesmo: “eu portei uma vez, seria difícil fazer isso de novo”? Afinal, quando velocidade torna-se um problema, o programador Python acaba deparando-se com o C. Portar o código foi novamente algo bem objetivo, ao mapear as funções do Python

    def distance(x1, y1, x2, y2):
        ...

em

const double distance(const double x1, const double y1,
                      const double x2, const double y2)

O código C resultante é quase idêntico às implementações em Python (e JavaScript), mas executa 6 vezes mais rápido do que a implementação em Python. Permitir que submissões de cálculos em lote, em vez de chamadas para cada cálculo, e eliminar algum overhead FFI, iriam aumentar a velocidade um pouco.

$ python2.7 -m tests.test_distance
Time elapsed for 100000 calculations in
    Python: 1952.70
    C: 300.46
    Factor: 6.50

Embrulhar o código C e chamá-lo foi simples utilizando ctypes, e adicionei um fallback para a implementação em Python caso a biblioteca compartilhada em C não puder ser encontrada; um pequeno __init__.py no pacote conecta a versão correta:

from .distance import distance as _py_distance
try:
    from ctypes import cdll, c_double
    dll = cdll.LoadLibrary('cDistance.so')
    dll.distance.restype = c_double
    dll.distance.argtypes = [c_double, c_double, c_double, c_double]
    distance = dll.distance
    _c_distance = dll.distance
except OSError: #Fall back to Python implementation
    distance = _py_distance

É claro que isso depende do código C ser compilado com cDistance.so e que o arquivo esteja disponível para um link – e que ele mantenha o .so inseridos diretamente no programa (hardcoded) para que uma DLL do windows não realize o trabalho. Eu pretendia trabalhar na limpeza do código um pouco mais antes de torná-lo open source, mas já que venho querendo abrir algumas de nossas ferramentas há anos e nunca encontro tempo, pensei que era melhor jogá-lo lá, e adiar a intenção de deixá-lo mais bonito. Espero que alguém ache algum uso para ele. Eu vou tentar fazer uma limpeza e empacotá-lo assim que possível.

***

Artigo traduzido pela Redação iMasters, com autorização do autor. Publicado originalmente em http://blaag.haard.se/WGS-84-distance-calculations-at-the-speed-of-C/#disqus_thread