Custos de pesquisas versus cálculos

12

Estou interessado em estabelecer cálculos para verificar se um critério de distância é atendido: ou seja, a distância entre um vetor vetor x j deve ser menor que algum valor r m a x . Meus dados são particionados de acordo com uma grade ortogonal de coordenadas. Como meu ponto de corte é menor que a distância entre os pontos finais das coordenadas do vizinho mais próximo, gostaria de adicionar uma variável "octant" para verificar se as coisas estão configuradas corretamente:xixjrmax

if octant[j] in allowed_list continue

como um "curto-circuito" para

if dist(x[i], x[j]) < r_max

Minha pergunta é: qual é a eficiência computacional das pesquisas e comparações booleanas em relação às operações de ponto flutuante? Vale a pena fazer isso nas arquiteturas modernas?

aeismail
fonte
3
Você gostaria de ramificar seu código e testá-lo? Sinto que a resposta padrão para a maioria delas é "melhor codificá-la (de uma maneira) ou (de outra maneira)?" tipos de perguntas é "Experimente e faça o benchmark".
Geoff Oxberry
1
Apenas meus 2 centavos. Como Geoff escreveu, esse tipo de conselho é o que sempre recebo quando fazia perguntas semelhantes no stackoverflow, sobre o código C ++: codifique tudo primeiro, organize o código para que eu permaneça modular e reutilizável e só então comece a refatorar. Existe uma regra 80-20: o software gasta 80% do tempo em 20% do código. Aguardar até que a estrutura é para cima, e, em seguida, a mudança, o teste, a mudança, o teste ..
tmaric
@ GeoffOxberry: Minha pergunta não é tão específica: eu só quero saber se há uma vantagem de hardware ou compilador em fazer uma verificação booleana em comparação a uma operação de ponto flutuante.
precisa saber é
3
Mas sua pergunta é muito geral. Ninguém pode dizer sem ver algum código concreto. Existe uma regra prática que diz que mesmo os melhores programadores não sabem dizer onde estão os gargalos do código sem criar um perfil. Passei meus últimos 25 anos programando e sei que é verdade para mim.
Wolfgang Bangerth

Respostas:

15

Minha regra geral é que, se você puder calcular alguma quantidade com eficiência (boa utilização da FPU) em menos de 50 flops por valor de precisão dupla, é melhor recalcular do que armazenar. A tendência, que é constante há décadas, é que a capacidade do ponto flutuante melhore mais rapidamente do que o desempenho da memória e provavelmente não cederá devido a restrições físicas e requisitos de energia da memória rápida. O valor de 50 é da magnitude certa para todas as plataformas de computação populares (Intel / AMD, Blue Gene e GPUs).

Estimativas de custo aproximadas por núcleo

[diretrizes para máquinas baseadas em Intel e AMD 2011/2012]

  • 0.05
  • 0.2
  • 0.4
  • 0.40.8
  • 2
  • 35
  • 35
  • 5
  • 48
  • 12
  • 12
  • 3050
  • 100
  • 1031 μ
  • 10410 μ
  • 106
  • 2106MPI_Allreduce
  • 107
  • 5108
  • 1.81012

Leitura adicional

Jed Brown
fonte
Achei essas informações realmente úteis. A propósito, de onde você tirou esses dados? Estou procurando referências para citar.
eldila