Este é um acompanhamento de Quão lento é realmente o Python? (Ou quão rápido é o seu idioma?) .
Aconteceu que foi um pouco fácil obter uma aceleração de x100 para minha última pergunta. Para aqueles que gostaram do desafio, mas querem algo mais difícil, onde realmente podem usar suas habilidades de baixo nível, aqui está a parte II. O desafio é obter uma aceleração de x100 para o seguinte código python, testado no meu computador.
Para tornar mais difícil, estou usando o pypy neste momento. O tempo atual para mim é de 1 minuto e 7 segundos usando o pypy 2.2.1.
Regras
- A primeira pessoa a enviar o código que eu posso executar, está correta e é 100 vezes mais rápida na minha máquina, receberá uma recompensa de 50 pontos.
- Atribuirei a vitória ao código mais rápido depois de uma semana.
import itertools
import operator
import random
n = 8
m = 8
iters = 1000
# creates an array of 0s with length m
# [0, 0, 0, 0, 0, 0, 0, 0]
leadingzerocounts = [0]*m
# itertools.product creates an array of all possible combinations of the
# args passed to it.
#
# Ex:
# itertools.product("ABCD", "xy") --> Ax Ay Bx By Cx Cy Dx Dy
# itertools.product("AB", repeat=5) --> [
# ('A', 'A', 'A', 'A', 'A'),
# ('A', 'A', 'A', 'A', 'B'),
# ('A', 'A', 'A', 'B', 'A'),
# ('A', 'A', 'A', 'B', 'B'),
# etc.
# ]
for S in itertools.product([-1,1], repeat = n+m-1):
for i in xrange(iters):
F = [random.choice([-1,0,0,1]) for j in xrange(n)]
# if the array is made up of only zeros keep recreating it until
# there is at least one nonzero value.
while not any(F):
F = [random.choice([-1,0,0,1]) for j in xrange(n)]
j = 0
while (j < m and sum(map(operator.mul, F, S[j:j+n])) == 0):
leadingzerocounts[j] +=1
j += 1
print leadingzerocounts
A saída deve ser semelhante a
[6335185, 2526840, 1041967, 439735, 193391, 87083, 40635, 19694]
Você deve usar uma semente aleatória no seu código e qualquer gerador de números aleatórios que seja bom o suficiente para fornecer respostas próximas ao acima será aceito.
Minha máquina Os horários serão executados na minha máquina. Esta é uma instalação padrão do ubuntu em um processador AMD FX-8350 de oito núcleos. Isso também significa que eu preciso poder executar seu código.
Explicação do código
Esse código itera sobre todas as matrizes S de comprimento n + m-1 compostas por -1s e 1s. Para cada matriz S, são amostradas 1000 matrizes aleatórias diferentes de zero, F, de comprimento n, compostas de -1,0 ou 1, com probabilidade de 1/4, 1/2 / / 14 de obter cada valor. Ele calcula os produtos internos entre F e cada janela de S de comprimento n até encontrar um produto interno diferente de zero. Ele adiciona 1 a leadingzerocounts
cada posição em que encontrou um produto interno zero.
Status
Perl . 2,7 vezes mais lento por @tobyink. (Comparado com pypy, não cpython.)
J . 39 vezes acelerado por @Eelvex.
- C . 59 vezes mais rápido por @ace.
- Julia . 197 vezes mais rápido, sem incluir o tempo de inicialização por mais um minuto. Acelerar 8,5 vezes, incluindo o tempo de inicialização (neste caso, é mais rápido usar 4 processadores do que 8).
- Fortran . 438 vezes mais rápido por @ semi-extrínseco.
- Rpython . 258 vezes mais rápido por @primo.
- C ++ . 508 vezes mais rápido por @ilmale.
(Parei de cronometrar as novas melhorias porque elas são muito rápidas e o iter era muito pequeno.)
Observou-se que os intervalos abaixo de um segundo não são confiáveis e também alguns idiomas têm um custo inicial. O argumento é que, se você incluir, inclua também o tempo de compilação do C / C ++ etc. Aqui estão os horários para o código mais rápido, com o número de iterações aumentado para 100.000.
- Julia . 42 segundos por mais um minuto.
- C ++ . 14 segundos por @GuySirton.
- Fortran . 14s por @ semi-extrínseco.
- C ++ . 12s por @ilmale.
- Rpython . 18s por @primo.
- C ++ . 5s por @Stefan.
O vencedor é .. Stefan!
Desafio de acompanhamento publicado. Quão alto você pode ir? (Um desafio de codificação + algoritmos) . Este é mais difícil.
fonte
Respostas:
C ++ bit magic
~ 16ms multithread, 56ms singlethreaded. ~ 4000 aceleração.
(a aceleração é baseada no código multithread no meu i7-2820QM e nos 1 min e 9 segundos mencionados na pergunta. Como o sistema do OP tem pior desempenho de thread único do que minha CPU, mas melhor desempenho multithread, espero que esse número seja preciso)
A peça multithread é bastante ineficiente devido à geração de threads. Provavelmente, eu poderia fazer melhor aproveitando minha biblioteca de tarefas personalizada, mas essa possui bugs nos sistemas unix. Para obter uma explicação e código quase idêntico sem o encadeamento, consulte https://codegolf.stackexchange.com/a/26485/20965 .
editar
Eu dei a cada thread o seu próprio RNG e reduzi o tamanho do bit para 32, o que reduziu o tempo de execução em alguns ms.
Saída de amostra:
fonte
C ++
x150x450x530Em vez de array, usei bits (e magia negra).
Obrigado @ace pela função aleatória mais rápida.
Como funciona: os primeiros 15 bits do número inteiro
s
representam a matrizS[15]
; os zeros representam -1, os que representam +1. A matrizF
é construída de maneira semelhante. Mas com dois bits para cada símbolo.Causar
S
eF
ter uma representação diferente. Tenho que intercalarS
consigo mesmo para ser comparávelF
.F
)F
)Agora podemos simplesmente usar o Carnot para calcular o produto interno. Lembre-se de que uma variável pode assumir apenas o valor 00 ou 11
0 00 = 11 (-1 * -1 = +1)
0. 01 = 10 (-1 * 0 = 0)
0. 10 = 01 (-1 * 0 = 0)
0. 11 = 00 (-1 * +1 = -1)
1. 00 = 00 (+1 * -1 = -1)
1. 10 = 10 (+1 * 0 = 0)
1. 01 = 01 (+1 * 0 = 0)
1. 11 = 11 (+1 * +1 = +1)
Parece um não xor para mim. :)
Resumindo, esses são apenas um jogo de mudança e máscara, nada realmente complexo.
Aqui está um exemplo de saída:
O programa foi compilado com:
no Fedora 20 com gcc 4.8.2 O processador é um i7 8core.
Provavelmente eu posso obter alguns parâmetros de compilação do ms.
Embora este seja o tempo da solução OP na minha máquina:
Editar:
Apenas adicionando o openmp e altere a ordem dos, pois tenho um ganho de x3, levando a uma melhoria de desempenho do x450 em relação ao código OP. : D Nesse caso, o
leadingZero
array deve ser atômico. O aleatório global ... são aleatórios, eles serão mais aleatórios.precisa adicionar
-fopenmp
ao sinalizador do compiladorEdit: 2 Como sugerido pelo user71404 eu mudei as funções sumOnes e sumArray e agora é super rápido.
Com o openmp é mais lento, os átomos acrescentam muita sobrecarga.
Sem atômica é ainda mais rápido, mas obtenho resultado errado.
2137992 1147218 619297 321243 155815 70946 32919 15579
Para entender o sumArray, considere que 16 bits representam e um array de 8 números.
00 não tem 1 e representa -1
01 e 10 tem um 1 e representa 0
11 tem dois 1s e representa 1
Portanto, a contagem interna do número de bits definido como 1 [ http://en.wikipedia.org/wiki/ Hamming_weight] e para cada grupo removemos 1. Cool.
sumOnes é apenas magia negra.
Aqui estão os últimos sinalizadores e códigos de compilação.
gcc -std = c ++ 11 -mfpmath = sse -O3 -flto -march = loops -funroll-nativos -Wall -lstdc ++
fonte
inline int32_t sumOnes(int32_t v) { /* 0xAAAA == 0b1010 1010 1010 1010 */ return !! (0xAAAA & (v ^ ~(v << 1))); } inline int32_t sumArray(int32_t v) { return __builtin_popcount(v) - 8; }
isso foi sugerido por @ user71404Julia: 0,7s, 120x mais rápido
Como o usuário20768 demonstrou, uma porta direta do código para Julia é cerca de duas vezes mais rápida que o PyPy. Mas podemos fazer muito melhor que isso.
Você pode executar isso usando
julia -p 8 -e 'require("golf.jl");main()'
(o 8 é o número de processos, convém brincar com ele). No pré-lançamento mais recente da Julia, são necessários 0,7s vs. 1m22s para o PyPy.Se você possui núcleos suficientes no seu computador e, talvez, gere algumas instâncias da AWS, poderá economizar um pouco mais :)
fonte
C, 1.210s
Com o código do OP executando 1m45.729s na minha máquina.
Compilação:
Agradecimentos especiais: @dyp para sinalizadores de compilação e idéias para otimizações.
Saída de amostra:
fonte
-march=native -fwhole-program -fstrict-aliasing -ftree-vectorize
Btw. Eu cheguei a <4 s usando algum C ++ 11, incluindo um MT19937 mais umuniform_int_distribution
.F
.n
é igual a8
, você provavelmente pode usar o AVX (ou 2 * SSE) para calcular o produto escalar com umS
armazenamento adequado .smmintrin.h
)Perl
Isso não chega nem perto da velocidade da solução C, mas é bastante rápido para uma linguagem interpretada de alto nível, eu acho. Ele reduz cerca de 40% do tempo de execução da implementação do Python.
O Algorithm :: Combinatorics está disponível no Ubuntu (
sudo apt-get install libalgorithm-combinatorics-perl
). Os outros módulos usados são os principais módulos Perl, portanto já devem estar instalados como parte da instalação básica do Ubuntu.fonte
0..N-1
alcance no últimomap
, certo? Você esqueceuuse warnings
? :-) Embora a lógica no OP seja confusa, a janela deslizante nunca chega ao último elemento deS
.warnings
permissão para que os elementos ausentes fossem tratados como zero.N-1
melhora isso. E, na verdade, melhora muito ligeiramente a velocidade - agora é cerca de 40% mais rápida que a implementação do Python.any
Como alternativa, pode ser encontrado em List :: MoreUtils, que embora não seja um módulo principal, é um dos módulos CPAN mais usados.Julia: 4,66x mais lenta!
Estou realmente começando a duvidar das estatísticas em seu site ...
Observe que o código Julia a seguir é efetivamente uma transcrição direta do código Python do OP sem nenhuma otimização. Eu uso a
time()
função para excluir o tempo lento de inicialização de Julia ...Julia: 5 m 32.912 s
Código do OP em PyPy: 1 m 11.506 s
Produção de Julia:
fonte
RPython 0.187s (258x mais rápido)
Fonte original com PyPy2.2.1: 1m 6.718s
Agora, com o encadeamento, o suporte para o Python padrão foi descartado. O número de threads de trabalho pode ser especificado como um parâmetro da linha de comandos; o padrão é dois.
O RPython é um subconjunto restrito do Python, que pode ser traduzido para C e compilado usando o RPython Toolchain . Seu objetivo expresso é ajudar na criação de intérpretes de linguagem, mas também pode ser usado para compilar programas simples como o descrito acima. A maioria dos recursos mais sofisticados do Python, como
itertools
ou mesmomap
não estão disponíveis.Para compilar, faça um clone local do repositório pypy atual e execute o seguinte:
O executável resultante será nomeado
convolution-c
ou semelhante no diretório de trabalho atual.Eu parametrizei as variáveis de entrada, então o programa deve ser executado como:
para corresponder ao código de exemplo.
Notas de implementação
S in itertools.product([-1,1], repeat = n+m-1)
torna-seS in xrange(1<<n+m-1)
, interpretandoS
como um mapa de bits: [0
,1
] → [-1
,1
]Da mesma forma,
F
é também um mapa de bits, com cada um de dois bits que representam um único valor:[
00
,01
,10
,11
] → [-1
,0
,0
,1
]Uma tabela verdade é usada para procurar o produto, em vez de executar uma multiplicação.
Como números inteiros assinados de 32 bits são usados,
n
podem não ser maiores que 15 en+m
maiores que 31. Suporte inteiro arbitrário pode ser obtido com orpython.rlib.rbigint
módulo, se necessário.A primeira iteração do loop do produto escalar é desenrolada e combinada com o teste de nulidade de
F
.Um PRNG homebrew é usado, fonte listada. O autor do artigo demonstra um período de 2 32 -1 e afirma que passa em todos os testes de Diehard, exceto um, embora eu pessoalmente não tenha confirmado isso.
A semente aleatória muda a cada milissegundo, o que é tão bom quanto o uso de um carimbo de data / hora permitirá. Além disso, cada thread de trabalho tem
xor
seu ID de processo com esse valor, para garantir que cada um tenha uma semente diferente.Exemplo de tempos
2 threads de trabalho:
4 threads de trabalho:
8 threads de trabalho:
Fonte original do OP:
Tempo para 100000 iterações:
fonte
Julia: 1 min 21,4s (2,2x mais rápido) (modificação do código de Arman)
Código do Op em PyPy: 3 min 1.4 s
Ambos feitos no REPL, não incluindo tempo para carregar pacotes.
Existem alguns problemas com o código de Arman, tornando-o muito lento: ele usa muitas funções anônimas e funções de ordem superior desnecessariamente. Para testar se todo um vetor F é zero, por que não escrever todos (F == 0) em vez de todos (x-> x == 0, F)? É mais curto e literalmente mil vezes mais rápido.
Ele também usa soma (mapa (*, x, y)) como produto escalar em vez de simplesmente ponto (x, y). A primeira versão 650 vezes mais lenta para um vetor de 10k dobra. E a função do produto de ponto é implementada como um loop for na Julia pura.
Além disso, a compreensão da matriz é lenta. É melhor escrever [0,1,0, -1] [rand (1: 4, n)] em vez de [[-1 0 0 1] [rand (1: 4)] para j = 1: n] .
Finalmente, variáveis globais são péssimas em Julia. Julia é rápida apenas se você escrever código de forma que permita que o JIT e a inferência de tipo funcionem. Uma grande parte disso é a estabilidade do tipo: o compilador deve ter certeza de que o tipo de uma variável não será alterado enquanto estiver dentro de um loop, por exemplo.
fonte
Nimrod
Exemplo de saída:
O Nimrod compila para C, portanto, a escolha do compilador C para o back-end também é importante.
Usando clang, compile com:
Usando o gcc, compile com:
Omita
--passc:-flto
se você tem um compilador C mais antigo que não suporta LTO. Omita a--cc=...
opção se você estiver bem com a opção padrão para o compilador C. O código requer o Nimrod 0.9.4 ou 0.9.5 .No meu quadcore iMac (2,66 GHz core i5), o código é executado em cerca de 0,15 segundo com gcc 4,9, 0,16 segundo com clang, em comparação com 88 segundos no PyPy 2.2.1 (ou seja, mais de 500 vezes mais). Infelizmente, não tenho acesso a uma máquina com mais de quatro núcleos que também possua o PyPy instalado ou onde eu possa instalar facilmente o PyPy, embora eu receba cerca de 0,1 segundos (com muito ruído de medição) em uma AMD de 64 núcleos. Opteron 6376 1,4 GHz (de acordo com / proc / cpuinfo) com gcc 4.4.6.
A implementação tenta ser fiel ao código original em vez de otimizar o custo da legibilidade, sem renunciar às otimizações óbvias. Curiosamente, a recursão da cauda
initVecRand()
é um pouco mais rápida que um loop com uma instrução de interrupção com o gcc e o clang. Desenrolar manualmente uma iteração doconvolve
loop de teste dentro do loop principal também produziu uma aceleração, provavelmente devido a uma melhor previsão de ramificação.fonte
Java
Traduzi a solução C ++ acima para Java:
Na minha máquina, recebo a seguinte saída para o programa java:
O programa OPs executa cerca de 53 segundos na minha máquina:
O programa c ++ executou apenas cerca de 0,15 segundo:
Isso é cerca de 2,5x mais rápido que a solução java correspondente (não excluí a inicialização da VM). Essas soluções java são 142x mais rápidas que o programa executado com o PyPy.
Como eu estava pessoalmente interessado, configurei
iters
para 100_000 para Java e C ++, mas o fator 2,5 não diminuiu em favor do Java se algo aumentasse.Edição: Eu executei os programas em um PC Arch Linux de 64 bits.
EDIT2: Quero acrescentar que comecei com uma tradução aproximada do código python:
Este programa executou cerca de 3,6 segundos:
O que é cerca de 14 vezes mais rápido que a solução PyPy. (Escolher a função aleatória padrão sobre a função fastRandom leva a um tempo de execução de 5 segundos)
fonte
Python 3.5 + numpy 1.10.1, 3.76 segundos
Os testes foram executados no meu Macbook Pro. O código do OP levou ~ 6 minutos na mesma máquina.
A razão pela qual estou respondendo a essa pergunta é que não tenho 10 reputações e não posso responder à Parte I :-p
Nos últimos dias, eu tenho tentado descobrir como executar voltas maciças eficientemente com numpy (sem depender de um pacote de terceiros, nem de um scipy). Quando me deparei com essa série de desafios durante minha pesquisa, decidi experimentá-la. Posso ter chegado tarde a este jogo, mas aqui está minha tentativa de usar o Python 3.5 e o numpy 1.10.1.
Eu pré-calculei as matrizes S e F e aplainou a matriz S enquanto realizava a convolução, que (com base em minhas experiências) poderia tirar proveito da velocidade do np.convolve. Em outras palavras, como não encontrei uma rotina de convolução vetorizada, fiz uma vetorização falsa do código achatando toda a matriz e esperei que o np.convolved fizesse a vetorização para mim, o que parecia estar funcionando. Observe que usei mode = 'same' e aparei os elementos iniciais e finais que eram inúteis.
No meu Macbook Pro, os resultados do teste dão 3,76 segundos . Quando executei o código do OP (modificado para Python 3.5), recebi cerca de 6 minutos . A aceleração é de cerca de 100 vezes.
Uma desvantagem é que, como as matrizes S e F devem ser armazenadas, o requisito de memória pode ser um problema se os tamanhos forem muito grandes.
Eu usei o mesmo método para a Parte I e recebi uma aceleração de ~ 60-100x no meu laptop.
Como fiz tudo no meu Macbook Pro, se alguém pudesse testar meu código e me informar como ele funciona na sua máquina, eu agradeceria muito!
fonte
J, aumento de
130x~ 50x?Vezes em um debian aleatório:
Eu acho que há espaço para melhorias.
fonte
pypy
, nãopython
, e é por isso que seu script parece estar dando velocidade 130x.C ++: x200 (i7 de 4 núcleos, deve ser dimensionado para x400 em 8 núcleos)
Tentando uma solução C ++ 11 mais simples (testada com o VS 2012, gcc e clang) com paralelização.
Para que isso seja compilado e executado no Linux com o gcc 4.8.1:
No Linux, também precisamos
std::launch::async
forçar vários threads. Eu estava sentindo falta disso em uma versão anterior.No Visual Studio (2012+), isso deve funcionar, mas criar uma compilação para o tempo ...
No meu antigo dual core i3, isso é executado em ~ 0,9 segundos. No meu i7 quad core, isso é 0,319s vs. pypy 66 segundos.
Em um i7 de 8 núcleos, isso deve estar na faixa de aceleração x400. Mudar para matrizes de estilo C aceleraria, mas eu estava interessado em ficar com contêineres C ++. Para mim, é interessante ver a velocidade que você pode obter mantendo-se relativamente próximo do domínio do problema e em um nível relativamente alto, algo em que eu acho que o C ++ é realmente bom. Também digno de nota é a relativa facilidade de paralelização usando construções C ++ 11.
A solução de bits do @ ilmale é muito legal e funciona para -1/1/0. Pode-se também jogar SSE nisso e talvez obter uma aceleração significativa.
Além da paralelização, há outro "truque" que reduz o número de somatórios. Resultados da amostra: 6332947 2525357 1041957 438353 193024 87331 40902 19649
fonte
Fortran: 316x
Ok, Fortran: consegui uma
velocidadede106x155x160x316x ao usar um Xorshift RNG e OpenMP em uma CPU i7 de 4 núcleos. Fora isso, não há grandes truques. Para o iterador construir S, eu apenas uso a representação binária do inteiro de 16 bits i. Você observará que, além do RNG embutido e do "iterador" / mapeamento de i para S, o código é tão alto quanto o código Python.Edit: removeu o "if" no Xorshift, agora usando "r = abs (w / ...)" em vez de "r = w / ...". Vai de 106x para 155x.
Edit2: Isso gera 15x tantos números aleatórios quanto a solução C ++. Se alguém tiver uma solução zero de sobrecarga para converter um int aleatório em uma matriz de 0s e 1s no Fortran, eu sou todo ouvidos. Então poderíamos vencer C ++ :)
Edit3: A primeira edição introduziu um bug, como Lembik apontou. Isso foi corrigido agora, com uma pequena melhoria no aumento de velocidade. Vou tentar usar a sugestão da Eelvex para obter mais velocidade.
Edit4: a criação de perfil indicava que a conversão para real e de volta para inteiro com nint () era lenta. Substituí isso por uma divisão inteira fazendo o dimensionamento e o arredondamento, passando de 160x para 316x.
Ajuntar com:
Exemplo de saída:
Código do OP:
fonte