Eu tenho 2 colunas de números inteiros delimitados por tabulação, a primeira das quais é um número inteiro aleatório, a segunda é um número inteiro que identifica o grupo, que pode ser gerado por este programa. ( generate_groups.cc)
#include <cstdlib>
#include <iostream>
#include <ctime>
int main(int argc, char* argv[]) {
int num_values = atoi(argv[1]);
int num_groups = atoi(argv[2]);
int group_size = num_values / num_groups;
int group = -1;
std::srand(42);
for (int i = 0; i < num_values; ++i) {
if (i % group_size == 0) {
++group;
}
std::cout << std::rand() << '\t' << group << '\n';
}
return 0;
}
Em seguida, uso um segundo programa ( sum_groups.cc) para calcular as somas por grupo.
#include <iostream>
#include <chrono>
#include <vector>
// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
for (size_t i = 0; i < n; ++i) {
p_out[p_g[i]] += p_x[i];
}
}
int main() {
std::vector<int> values;
std::vector<int> groups;
std::vector<int> sums;
int n_groups = 0;
// Read in the values and calculate the max number of groups
while(std::cin) {
int value, group;
std::cin >> value >> group;
values.push_back(value);
groups.push_back(group);
if (group > n_groups) {
n_groups = group;
}
}
sums.resize(n_groups);
// Time grouped sums
std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
for (int i = 0; i < 10; ++i) {
grouped_sum(values.data(), groups.data(), values.size(), sums.data());
}
std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
std::cout << (end - start).count() << std::endl;
return 0;
}
Se eu executar esses programas em um conjunto de dados de determinado tamanho e, em seguida, embaralhar a ordem das linhas do mesmo conjunto de dados, os dados embaralhados calcularão as somas ~ 2x ou mais rápido que os dados ordenados.
g++ -O3 generate_groups.cc -o generate_groups
g++ -O3 sum_groups.cc -o sum_groups
generate_groups 1000000 100 > groups
shuf groups > groups2
sum_groups < groups
sum_groups < groups2
sum_groups < groups2
sum_groups < groups
20784
8854
8220
21006
Eu esperava que os dados originais, classificados por grupo, tivessem uma melhor localização de dados e fossem mais rápidos, mas observo o comportamento oposto. Fiquei me perguntando se alguém pode hipótese a razão?
fonte
.at()ou um modo de depuraçãooperator[]que limita verificando você veria.sum. Em vez desums.reserve(n_groups);você deve ligarsums.resize(n_groups);- era o que @Shawn estava sugerindo.p_out[p_g[i]] += p_x[i];. Talvez na ordem codificada original, os grupos estejam exibindo um bom agrupamento em relação ao acesso àp_outmatriz. A classificação dos valores talvez cause um padrão de acesso indexado a grupo ruimp_out.Respostas:
Configurar / tornar lento
Primeiro de tudo, o programa é executado aproximadamente na mesma hora, independentemente:
A maior parte do tempo é gasta no loop de entrada. Mas, como estamos interessados no
grouped_sum()assunto, vamos ignorar isso.A alteração do loop de referência de 10 para 1000 iterações
grouped_sum()começa a dominar o tempo de execução:diff diff
Agora podemos usar
perfpara encontrar os pontos mais quentes do nosso programa.E a diferença entre eles:
Mais tempo
main(), o que provavelmente foigrouped_sum()inline. Ótimo, muito obrigado, perf.anotação perf
Existe alguma diferença em onde o tempo é gasto lá dentro
main()?Aleatório:
Ordenado:
Não, são as mesmas duas instruções dominantes. Portanto, eles demoram muito tempo em ambos os casos, mas são ainda piores quando os dados são classificados.
estatísticas de desempenho
OK. Mas devemos executá-los o mesmo número de vezes, para que cada instrução esteja ficando mais lenta por algum motivo. Vamos ver o que
perf statdiz.Apenas uma coisa se destaca: front-cycles-stalled .
Ok, o pipeline de instruções está parado. No frontend. Exatamente o que isso significa provavelmente varia entre microarquiteturas.
Eu tenho um palpite, no entanto. Se você é generoso, pode até chamá-lo de hipótese.
Hipótese
Ao classificar a entrada, você aumenta a localidade das gravações. De fato, eles serão muito locais; quase todas as adições feitas serão gravadas no mesmo local da anterior.
Isso é ótimo para o cache, mas não para o pipeline. Você está introduzindo dependências de dados, impedindo que a próxima instrução de adição prossiga até que a adição anterior seja concluída (ou disponibilizou o resultado para as instruções seguintes )
Esse é o seu problema.
Eu acho que.
Consertando-o
Vetores de soma múltipla
Na verdade, vamos tentar algo. E se usássemos vários vetores de soma, alternando entre eles para cada adição e depois os somamos no final? Custa-nos um pouco de localidade, mas deve remover as dependências de dados.
(o código não é bonito; não me julgue, internet !!)
(ah, e também corrigi o cálculo de n_groups; foi desativado por um).
Resultados
Depois de configurar meu makefile para fornecer um
-DNSUMS=...argumento ao compilador, eu poderia fazer isso:O número ideal de vetores de soma provavelmente dependerá da profundidade do pipeline da sua CPU. Minha CPU ultrabook de 7 anos de idade provavelmente pode maximizar o pipeline com menos vetores do que uma nova CPU de desktop precisa.
Claramente, mais não é necessariamente melhor; quando fiquei louco com 128 vetores de soma, começamos a sofrer mais com falhas de cache - como evidenciado pela entrada aleatória se tornando mais lenta do que classificada, como você esperava inicialmente. Nós fizemos um círculo completo! :)
Soma por grupo no registro
(isso foi adicionado em uma edição)
Agh, nerd cortou ! Se você sabe que sua entrada será classificada e procura desempenho ainda maior, a seguinte reescrita da função (sem matrizes de soma extra) é ainda mais rápida, pelo menos no meu computador.
O truque deste é que ele permite que o compilador mantenha a
gsumvariável, a soma do grupo, em um registro. Estou supondo (mas pode estar muito errado) que isso seja mais rápido porque o loop de feedback no pipeline pode ser mais curto aqui e / ou menos acessos à memória. Um bom preditor de filial tornará barata a verificação extra da igualdade de grupo.Resultados
É terrível para entrada aleatória ...
... mas é cerca de 40% mais rápido que a minha solução "muitas somas" para entrada classificada.
Muitos grupos pequenos serão mais lentos que alguns grandes; portanto, se essa é a implementação mais rápida, dependerá realmente dos seus dados aqui. E, como sempre, no seu modelo de CPU.
Vários vetores de somas, com deslocamento em vez de mascaramento de bits
Sopel sugeriu quatro adições desenroladas como alternativa à minha abordagem de mascaramento de bits. Eu implementei uma versão generalizada de sua sugestão, que pode lidar com diferentes
NSUMS. Estou contando com o compilador desenrolando o loop interno para nós (o que aconteceu, pelo menos paraNSUMS=4).Resultados
Hora de medir. Observe que desde que eu estava trabalhando no / tmp ontem, não tenho exatamente os mesmos dados de entrada. Portanto, esses resultados não são diretamente comparáveis aos anteriores (mas provavelmente próximos o suficiente).
Sim, o loop interno
NSUMS=8é o mais rápido do meu computador. Comparado à minha abordagem "gsum local", ela também tem o benefício adicional de não se tornar terrível para as informações embaralhadas.Interessante notar:
NSUMS=16torna - se pior queNSUMS=8. Isso pode ser porque estamos começando a ver mais falhas de cache ou porque não temos registros suficientes para desenrolar o loop interno corretamente.fonte
perf.Aqui está o porquê de grupos classificados serem mais lentos que grupos não-gravados;
Primeiro, aqui está o código de montagem para o loop de soma:
Vamos analisar a instrução add, que é o principal motivo desse problema;
Quando o processador executar esta instrução primeiro, ele emitirá uma solicitação de leitura de memória (carga) para o endereço no edx, em seguida, adicionará o valor de ecx e emitirá uma solicitação de gravação (armazenamento) para o mesmo endereço.
há um recurso no reordenamento de memória do chamador do processador
e existe uma regra
Portanto, se a próxima iteração atingir a instrução add antes que a solicitação de gravação seja concluída, ela não esperará se o endereço edx for diferente do valor anterior e emitirá a solicitação de leitura, reordenando a solicitação de gravação mais antiga e a instrução add continuará. mas se o endereço for o mesmo, a instrução add aguardará até que a gravação antiga seja concluída.
Observe que o loop é curto e o processador pode executá-lo mais rapidamente do que o controlador de memória conclui a solicitação de gravação na memória.
portanto, para grupos classificados, você lerá e gravará do mesmo endereço várias vezes consecutivas, a fim de perder o aprimoramento de desempenho usando o reordenamento de memória; enquanto isso, se forem utilizados grupos aleatórios, cada iteração provavelmente terá um endereço diferente, de modo que a leitura não espere a gravação mais antiga e reordenada antes dela; A instrução add não aguardará a anterior.
fonte