Sobrecarga de uma instrução switch em C
https://stackoverflow.com/questions/927403
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu sou um programador Java bastante competente que é muito novo para C. Eu estou tentando otimizar uma rotina que tem quatro modos de operação.
Eu loop sobre todos os pixels em uma imagem e calcular um novo valor de pixel, dependendo do modo '' passado.
A minha pergunta diz respeito à sobrecarga de um switch dentro de dois aninhados para loops. Eu estaria interessado em quaisquer links para documentação sobre a eficiência relativa de declarações C básicas, matemática e operações lógicas.
O código iria como segue;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
case 1:
weight = (float)x/width;
break;
case 2:
weight = (float)y/height;
break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
break;
case 4:
weight = dTopRight / maxDistanceCorner;
break;
default:
weight = 1;
break;
}
// Calculate the new pixel value given the weight
...
}
}
Você esperaria para ver muita sobrecarga se isso era sobre a imagem de pixel a 5000 x 5000? Eu tentei fazer alguns testes, mas os meus resultados estão por todo o lugar como o sistema (dispositivo móvel) tem todos os tipos de coisas que funcionam no fundo que podem distorcer os resultados.
A outra opção é ter um método separado para cada modo, cada um com suas próprias quatro loops. Este seria, obviamente introduzir código redundante, mas a eficiência é o nome do jogo aqui.
Agradecemos antecipadamente!
Gav
Solução
declarações switch compilar para uma mesa de salto para valores consecutivos e um monte de if-else para valores esparsas. Em qualquer caso, você não quer uma instrução switch em seu circuito interno de processamento de imagem, se você se preocupa com o desempenho. Você quer como abaixo em seu lugar.
Além disso, nota que se mudou o cálculo de peso fora do laço interior (e permutado para os lacetes caso 2, a fim de alcançar este). Este tipo de pensamento, mover coisas fora do circuito interno, você irá obter o desempenho que você quer fora de C.
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 1:
for (x = 0; x < width; x++) {
weight = (float)x/width;
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 2:
// note - the loops have been swapped to get the weight calc out of the inner loop
for (y = 0; y < height; y++) {
weight = (float)y/height;
for (x = 0; x < width; x++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 4:
weight = dTopRight / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
default:
weight = 1;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
// etc..
}
Outras dicas
Se a eficiência é mais importante do que o tamanho do código, então sim, você deve criar rotinas redundantes. A declaração caso é uma das coisas gerais mais baixos que você pode fazer em C, mas não é zero - ele vai ter que ramo com base no modo, e por isso vai levar tempo. Se você realmente quer o desempenho máximo, obter o caso fora do circuito, mesmo à custa da duplicação do loop.
declarações switch são tão eficientes quanto eles podem possivelmente ser. Eles estão compilados para uma mesa de salto. Na verdade, é por isso que interruptor é tão limitado como ele é:. Você só pode escrever um interruptor para o qual você pode compilar uma tabelas de salto com base em um valor fixo
Em comparação com as contas que você está fazendo no circuito, a sobrecarga da chave provavelmente será mínimo. tendo dito isso, a única maneira de ter certeza é criar versões diferentes para as duas abordagens diferentes, eo tempo deles.
Switch / caso é extremamente rápido em comparação com o equivalente de if / else: é tipicamente implementado como uma tabela de salto. No entanto, ainda tem um custo.
Enquanto você está otimizando coisas:
1) Tente fazer um loop através de linhas, não sobre colunas (interruptor x e y "para" laços), uma solução pode ser incrivelmente mais rápido do que o outro, devido ao gerenciamento de memória cache.
2) Substituir todas as divisões por multiplicações do) inverso (pré-calculados lhe dará ganho significativo e, provavelmente, uma perda de precisão aceitável.
Para a eficiência amor é melhor switch movimento fora do loop.
Eu usaria ponteiros de função como esta:
double fun0(void) { return dCentre/maxDistanceEdge; }
double fun1(void) { return (float)x/width; }
/* and so on ... */
double (*fun)(void);
switch (mode) /* select the type of calculation */
{
case 0: fun = fun0;
break;
case 1: fun = fun1;
break;
case 2: fun = fun2;
break;
case 3: fun = fun3;
break;
case 4: fun = fun3;
break;
default : fun = fun_default;
break;
}
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
weight = fun();
// Calculate the new pixel value given the weight
...
}
}
Acrescenta função de chamada de sobrecarga, mas não deve ser muito grande como você passar há parâmetros para a função. Eu acho que é bom trade-off entre desempenho e legibilidade.
EDIT: Se você usar GCC, para se livrar da chamada de função que você pode usar goto e rótulos como valores: encontrar a etiqueta direita dentro do interruptor e, em seguida, apenas saltar para ele o tempo todo. Eu acho que deveria poupar mais alguns ciclos.
Switches produtos should qualquer sobrecarga significativa, eles são compilados em uma espécie de matriz de ponteiros no final baixo, então é um caso de forma eficaz:
JMP {baseaddress} + switchcasenum
Este seria provavelmente dependerá de como bom preditor ramo do seu CPU é, e como o seu compilador gera o código para o switch. Para um número tão pequeno de casos, pode gerar uma árvore de decisão, caso em que CPU normal de previsão de desvios deve ser capaz de remover a maior parte da sobrecarga. As coisas podem ser um pouco pior se ele gera uma tabela interruptor ...
Dito isso, a melhor maneira de descobrir é ao perfil e veja.
Além de conselhos de Jim, tente trocar a ordem dos loops. Se loop-troca é ideal para o caso 1 exigiria testar, mas eu suspeito que é. Você quase sempre quer que seus coordenada x dentro de seu circuito interno, a fim de melhorar o desempenho de paginação, pois isso faz com que sua função para ter uma melhor tendência a permanecer na mesma área de memória geral cada iteração. E um dispositivo móvel com recursos limitted pode ter ram baixo o suficiente para que essa diferença será enfatizado.
Desculpe bater esta discussão, mas parece-me que o interruptor está longe de ser o problema.
O problema real com a eficiência nesse caso é as divisões. Parece-me que todos os denominadores das operações de divisão são constantes (largura, altura, max ...) e estes não vai mudar ao longo do curso da imagem. Se meu palpite estiver certo, então estes são variáveis ??simples que pode mudar com base na imagem carregada de modo que qualquer imagem em tamanho pode ser usado em tempo de execução, agora isso permite a qualquer tamanho de imagem a ser carregado, mas isso também significa que o compilador não pode otimizá-los para a operação de multiplicação muito mais simples que poderia fazer se eles foram declarados "const". Minha sugestão seria para pré-calcular os inversos destas constantes e multiplicar. Tanto quanto me lembro, a operação de multiplicação leva cerca de 10 ciclos de clock, onde como a divisão leva em torno de 70. Isso é um aumento de 60 ciclos por pixel, e com o acima mencionado 5000x5000, que é um aumento de velocidade estimada de 1,5 segundos em um 1 GHz CPU.
Depende do chip e do compilador e os detalhes do código, e ... mas este, muitas vezes, ser implementado como uma tabela de salto, que deve ser muito rápido.
BTW-- Compreender esse tipo de coisa é um argumento muito bom para passar um par de semanas aprendendo algum conjunto em algum momento de sua carreira ...
Usando um interruptor é provavelmente melhor tanto para a velocidade e programador tempo. Você está fazendo código menos redundante e provavelmente não vai exigir um novo quadro de pilha.
Os switches são tão eficientes que pode ser usado para muito estranho e confuso magia negra .
mas a eficiência é o nome do jogo aqui.
iteração sobre um buffer de imagem, a fim de calcular novos sons valores de pixel como um problema típico embaraçosamente paralelo, neste sentido, você pode querer considerar empurrando alguns dos trabalhos em segmentos de trabalho, isso deve acelerar sua operação mais notadamente do que micro-otimizações tais como switch / case preocupações.
Além disso, em vez de fazer as instruções de ramificação cada vez, você poderia chamar um ponteiro de função a partir de uma matriz de ponteiros de função, onde o índice serve como seu identificador de modo.
Assim que você acabar com as chamadas, tais como:
computeWeight[mode](pixel);
Com 5000x5000 pixels, a sobrecarga chamada de função também poderia ser reduzida chamando a função para uma série de pixels, em vez de pixels individuais.
Você também pode usar desdobramento de loop e passagem de parâmetros por referência / ponteiro, a fim de otimizar isso ainda mais.
Muitos pontos bons já estão dadas. Única coisa que eu poderia pensar em acrescentar a isto, é mover a maioria dos casos frequentes-se no interruptor eo baixo menos frequente.
Então, se case 4 acontece mais frequentemente do caso 1, que deve ser acima dela:
switch (mode) {
case 4:
// ..
break;
case 1:
// ..
break;
}
Pena que você não estava usando c ++, porque então a instrução switch pode ser substituído por polimorfismo.
Felicidades!
Há uma série de sugestões criativas neste segmento de maneiras ter que escrever 5 funções separadas.
A menos que você ler 'modo' de um arquivo ou de entrada digitada no método de cálculo pode ser determinado em tempo de compilação. Como regra geral, você não deseja mover cálculos de tempo de compilação para tempo de execução.
De qualquer forma, o código seria mais fácil de ler e ninguém seria confuso quanto a saber se ou não você quis colocar no comando break no primeiro caso ou não.
Além disso, quando você começa erros no código circundante você não terá que olhar para cima se a enumeração foi definido com o valor errado ou não.
No que diz respeito aos laços internos ... 0-> var é melhor feito VaR> 0 como gatilhos var-- a bandeira zero (6502 dias). Esta abordagem também significa "largura" é carregado para x e pode ser esquecido, mesmo se passa para "altura". Também pixels na memória são geralmente esquerda> direita, top-> fundo para que definitivamente tem x como o seu circuito interno.
for (y = height; y--;) {
for (x = width; x--;) {
weight = fun();
// Calculate the new pixel value given the weight
...
}
}
Além disso ... e muito importante é suas declarações switch só tem 2 casos que usam x ou y. O resto são constantes.
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
break;
//case 1:
// weight = (float)x/width;
// break;
//case 2:
// weight = (float)y/height;
// break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
break;
case 4:
weight = dTopRight / maxDistanceCorner;
break;
default:
weight = 1;
break;
}
Então, basicamente, a menos que o modo 1 ou 2 de peso é calculado antes do laço.
... Y loop code here
if (mode == 2) { weight = (float)y/height; } // calc only once per Y loop
... X loop here
if (mode == 1) { weight = (float)x/width; } // after this all cases have filled weight
calc_pixel_using_weight(weight);
Eu encontrei declarações switch para ser muito indelicado se os dados são escassos. Para <4 elementos que eu vá para if-then-else e certifique-se os casos mais comuns são a parte de cima. Se a primeira condição pega 90% dos casos você basicamente bateu um home run. Da mesma forma, se alguma outra condição é <1% colocá-lo passado.
