De arriba de una sentencia switch en C

Question

Soy un programador de Java bastante competente, que es muy nuevo en C. Estoy tratando de optimizar una rutina que tiene cuatro modos de funcionamiento.

bucle I sobre todos los píxeles de una imagen y calcular un nuevo valor de píxel en función de la 'modo' pasado.

Mi pregunta se refiere a la sobrecarga de una sentencia switch dentro de los dos bucles for anidados. Yo estaría interesado en cualesquiera enlaces a la documentación relativa a la eficiencia relativa de los estados C básicas, matemáticas y operaciones lógicas.

El código iría de la siguiente manera;

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
             ...
            }             

    }

¿Es de esperar para ver muchos gastos si se trataba de una imagen de píxeles 5000 x 5000 de nuevo? He tratado de hacer algunas pruebas pero mis resultados están por todo el lugar como el sistema (dispositivo móvil) tiene todo tipo de cosas que se ejecutan en segundo plano que pueden sesgar los resultados.

La otra opción es tener un método diferente para cada modo, cada uno con sus propias cuatro bucles. Esto, obviamente, introducir código redundante pero la eficiencia es el nombre del juego aquí.

Gracias de antemano!

Gav

Answer 1

sentencias switch compilan a una tabla de saltos de valores consecutivos y un montón de declaraciones si-si no para los valores dispersos. En cualquier caso, no desea que una sentencia switch en su bucle interno para el procesamiento de imágenes si se preocupan por el rendimiento. ¿Quieres que realizar lo siguiente en su lugar.

Además, observe que moví el cálculo de peso fuera del bucle interior (y Intercambié los bucles para el caso 2 con el fin de lograr esto). Este tipo de pensamiento, moviendo cosas fuera del circuito interno, obtendrá el rendimiento que desea salir 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..
}

Answer 2

Si la eficiencia es más importante que el tamaño del código, entonces sí debe crear rutinas redundantes. La declaración de caso es una de las cosas menos gastos generales que se pueden hacer en C, pero no es cero - que va a tener que ramificar basado en el modo, y por lo que va a tomar tiempo. Si realmente quieres un rendimiento máximo, conseguir que el caso fuera del circuito, incluso a costa de duplicar el bucle.

Answer 3

declaraciones del interruptor son casi tan eficientes como pueden ser. Están compilados a una tabla de saltos. De hecho, es por eso interruptor está tan limitada como lo es: sólo se puede escribir un interruptor para el que puede compilar una tablas de salto en base a un valor fijo

.

Answer 4

En comparación con las matemáticas que está haciendo en el bucle, la sobrecarga del interruptor probablemente será mínimo. Una vez dicho esto, la única manera de estar seguro es crear diferentes versiones de los dos enfoques diferentes, y los tiempo.

Answer 5

Interruptor / caso es extremadamente rápido en comparación con el equivalente a if / else: se implementa típicamente como una tabla de saltos. Sin embargo, todavía tiene un costo.

Si bien se trata de optimizar cosas:

1) Trate de bucle a través de líneas, no sobre columnas (interruptor de X e Y "para" loops), una solución puede ser increíblemente más rápido que el otro, debido a la gestión de memoria caché.

2) Sustitución de todas las divisiones por multiplicación de la inversa (calculado previamente) le dará una ganancia significativa, y probablemente una pérdida de precisión aceptable.

Answer 6

Por el amor de eficiencia a moverse mejor switch fuera del bucle.

que haría uso de punteros de función 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
             ...
        }
}

Se añade la función de llamada de arriba, pero no debe ser demasiado grande a medida que pasan no params a la función. Creo que es un buen compromiso entre el rendimiento y la facilidad de lectura.

EDIT: Si utiliza GCC, deshacerse de la función de llamada puede utilizar goto y noreferrer etiquetas como valores: encontrar la etiqueta correcta en el interruptor y luego simplemente saltar a él cada vez. Creo que debe ahorrar algunos ciclos más.

Answer 7

Interruptores shouldnt producir cualquier sobrecarga significativa, que se compilan en una especie de matriz de punteros en el extremo inferior, a continuación, que es un caso de eficacia:

JMP {+} baseaddress switchcasenum

Answer 8

Esto probablemente dependerá de qué tan buen predictor rama de la CPU es, y cómo su compilador genera el código para el interruptor. Para un pequeño número de casos de este tipo, que podría generar un árbol de decisión, en cuyo caso la CPU normal de predicción de saltos debe ser capaz de eliminar la mayor parte de los gastos generales. Las cosas podrían ser un poco peor si se genera una tabla de interruptor ...

Dicho esto, la mejor manera de averiguarlo es el perfil it y ver.

Answer 9

Además de los consejos de Jim, intentar cambiar el orden de los bucles. Ya sea en bucle intercambio es ideal para el caso 1 requeriría pruebas, pero sospecho que es. Casi siempre quiere que sus coordenadas x dentro de su bucle interno con el fin de mejorar el rendimiento de paginación, ya que esto hace que su función para tener una mejor tendencia a permanecer en la misma área general de la memoria de cada iteración. Y un dispositivo móvil con recursos limitted podría tener poca RAM suficiente como para que se hará hincapié en esta diferencia.

Answer 10

Lo sentimos topar este hilo, pero me parece que el interruptor está lejos de ser el problema.

El verdadero problema de la eficiencia en este caso es la división. Me parece que todos los denominadores de las operaciones de división son constantes (anchura, altura, máximo ...) y estos no va a cambiar en el transcurso de la imagen. Si mi suposición es correcta, entonces estos son variables simples que pueden cambiar en función de la imagen cargada de modo que cualquier imagen a tamaño se puede utilizar en tiempo de ejecución, ya que esto permite a cualquier tamaño de imagen a cargar, pero esto también significa que el compilador no puede optimizarlos en la operación de multiplicación mucho más simple que se podría hacer si se les declaró "const". Mi sugerencia sería comprobar la validez de calcular las inversas de estas constantes y multiplicarse. Por lo que puedo recordar, la operación de multiplicación tarda unos 10 ciclos de reloj, en tanto que la división se lleva alrededor de 70. Eso es un aumento de 60 ciclos por píxel, y con las 5000x5000 mencionados anteriormente, que es un aumento de la velocidad estimada de 1,5 segundos en una 1 GHz CPU.

Answer 11

Depende del chip y el compilador y los detalles del código, y ... pero esto a menudo implementarse como una tabla de salto, que debe ser bastante rápido.

BTW-- La comprensión de este tipo de cosas es un buen argumento para pasar un par de semanas aprendiendo un poco de montaje en algún momento de su carrera ...

Answer 12

El uso de un interruptor es probablemente mejor tanto para la velocidad y el tiempo de programador. Estás haciendo código sea menos redundante y probablemente no será necesario un nuevo marco de pila.

Los conmutadores son tan eficientes que pueden utilizar para realmente extraño y confuso negro mágica .

Answer 13

  

pero la eficiencia es el nombre del juego aquí.

iterar a través de una memoria intermedia de imagen con el fin de calcular nuevos valores de píxeles suena como un problema típico vergonzosamente paralelas, en este sentido, es posible que desee considerar empujar algunos de los trabajos en los subprocesos de trabajo, esto debería acelerar su funcionamiento más notable de micro-optimizaciones tales como preocupaciones interruptor / caja.

Además, en lugar de hacer las instrucciones de ramificación cada vez, se podría invocar un puntero de función de una serie de punteros de función, donde el índice sirve de identificador de modo.

Para que usted termina con llamadas tales como:

computeWeight[mode](pixel);

Con 5000x5000 pixeles, la sobrecarga llamada de función podría también ser reducido llamando a la función de una serie de píxeles, en lugar de píxeles individuales.

También puede utilizar desenroscado de bucles y el paso de parámetros por referencia / puntero, con el fin de optimizar más a fondo.

Answer 14

Muchos buenos puntos ya están dadas. Lo único que podía pensar en añadir a esto, es mover los casos más frecuentes en el interruptor y el plumón menos frecuente.

Así que si el caso 4 ocurre con más frecuencia que el caso 1, debe estar por encima de ella:

switch (mode) {
    case 4:
        // ..
        break;
    case 1:
        // ..
        break;
}

Es una lástima que no estuviera usando C ++, porque entonces la instrucción switch podría ser sustituido por el polimorfismo.

Saludos!

Answer 15

Hay una gran cantidad de sugerencias creativas en este hilo de maneras no tener que escribir 5 funciones separadas.

A menos que se lee 'modo' de un archivo o de la entrada escrita el método de cálculo se puede determinar en tiempo de compilación. Como norma general no se quiere mover cálculos de tiempo de compilación de tiempo de ejecución.

De cualquier manera, el código sería más fácil de leer y nadie se confundiría en cuanto a si está o no destinado a poner en la sentencia break en el primer caso o no.

Además, cuando se obtiene errores en el código que le rodea no tendrá que mirar hacia arriba si la enumeración se establece en el valor equivocado o no.

Answer 16

Con respecto a los bucles internos ... 0-> var se hace mejor Var-> 0 como var-- desencadena la bandera de cero (6502 días). Este enfoque también significa "ancho" se carga en x y puede ser olvidado, lo mismo que "altura". También píxeles en la memoria son generalmente izquierda> derecha, top-> parte inferior por lo que definitivamente tiene x como el bucle interno.

for (y = height; y--;) {
    for (x = width; x--;) {
         weight = fun();
         // Calculate the new pixel value given the weight
         ...
    }
}

También ... y muy importante es sus estados de conmutación sólo tienen 2 casos que utilizan xoy. El resto son 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;
 }

Así que básicamente menos que el modo 1 o 2 peso se calcula antes del bucle.

... 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);

He encontrado instrucciones switch a ser muy desagradable si los datos son escasos. Para <4 elementos me gustaría ir para si-entonces-else y me aseguro de los casos más comunes son hasta la parte superior. Si la primera condición capta el 90% de los casos que haya básicamente conectó un jonrón. Asimismo, si alguna otra condición es <1% puso pasado.