Estoy escribiendo un simulador de hormigas de Langton (para la regla RLR) y estoy tratando de optimizarlo para la velocidad. Aquí está el código pertinente tal como está:

#define AREA_X 65536
#define AREA_Y 65536
#define TURN_LEFT 3
#define TURN_RIGHT 1
int main()
{
  uint_fast8_t* state;
  uint_fast64_t ant=((AREA_Y/2)*AREA_X) + (AREA_X/2);
  uint_fast8_t ant_orientation=0;
  uint_fast8_t two_pow_five=32;
  uint32_t two_pow_thirty_two=0;/*not fast, relying on exact width for overflow*/
  uint_fast8_t change_orientation[4]={0, TURN_RIGHT, TURN_LEFT, TURN_RIGHT};
  int_fast64_t* move_ant={AREA_X, 1, -AREA_X, -1};
  ... initialise empty state
  while(1)
  {
    while(two_pow_five--)/*removing this by doing 32 steps per inner loop, ~16% longer*/
    {
      while(--two_pow_thirty_two)
      {
        /*one iteration*/
        /* 54 seconds for init + 2^32 steps
        ant_orientation = ( ant_orientation + (117>>((++state[ant])*2 )) )&3;
        state[ant] = (36 >> (state[ant] *2) ) & 3;
        ant+=move_ant[ant_orientation];
        */

        /* 47 seconds for init + 2^32 steps
        ant_orientation = ( ant_orientation + ((state[ant])==1?3:1) )&3;
        state[ant] += (state[ant]==2)?-2:1;
        ant+=move_ant[ant_orientation];
        */

        /* 46 seconds for init + 2^32 steps
        ant_orientation = ( ant_orientation + ((state[ant])==1?3:1) )&3;
        if(state[ant]==2)
        {
          --state[ant];
          --state[ant];
        }
        else
          ++state[ant];
        ant+=move_ant[ant_orientation];
        */

        /* 44 seconds for init + 2^32 steps
        ant_orientation = ( ant_orientation + ((++state[ant])==2?3:1) )&3;
        if(state[ant]==3)state[ant]=0;
        ant+=move_ant[ant_orientation];
        */

        // 37 seconds for init + 2^32 steps
        // handle every situation with nested switches and constants
        switch(ant_orientation)
        {
          case 0:
            switch(state[ant])
            {
              case 0:
                ant_orientation=1;
                state[ant]=1;
                ++ant;
                break;
              case 1:
                ant_orientation=3;
                state[ant]=2;
                --ant;
                break;
              case 2:
                ant_orientation=1;
                state[ant]=0;
                ++ant;
                break;
            }
            break;
          case 1:
            switch(state[ant])
            {
              ...
            }
            break;
          case 2:
            switch(state[ant])
            {
              ...
            }
            break;
          case 3:
            switch(state[ant])
            {
              ...
            }
            break;
        }

      }
    }
    two_pow_five=32;
    ... dump to file every 2^37 steps
  }
  return 0;
}

Tengo dos preguntas:

He intentado optimizar lo mejor que puedo con c mediante pruebas de prueba y error, ¿hay algún truco que no haya aprovechado? Por favor, intente hablar en c no en ensamblaje, aunque probablemente lo intentaré en algún momento.

¿Hay una mejor manera de modelar el problema para aumentar la velocidad?

Más información: La portabilidad no importa. Estoy en Linux de 64 bits, usando gcc, un i5-2500k y 16 GB de RAM. El conjunto de estados en su forma actual utiliza 4GiB, el programa podría usar 12GiB de RAM. sizeof (uint_fast8_t) = 1. Los controles de límites no están presentes intencionalmente, la corrupción es fácil de detectar manualmente desde los volcados.

editar: Quizás de manera contraproducente, acumular en las declaraciones de cambio en lugar de eliminarlas ha dado como resultado la mejor eficiencia hasta el momento.

editar: He vuelto a modelar el problema y se me ha ocurrido algo más rápido que un solo paso por iteración. Antes, cada elemento de estado usaba dos bits y describía una sola celda en la cuadrícula de hormigas de Langton. La nueva forma utiliza los 8 bits y describe una sección 2x2 de la cuadrícula. En cada iteración, se realiza una cantidad variable de pasos, buscando valores precalculados de conteo de pasos, nueva orientación y nuevo estado para el estado actual + orientación. Suponiendo que todo sea igual de probable, el promedio es de 2 pasos tomados por iteración. Como beneficio adicional, utiliza 1/4 de la memoria para modelar la misma área:

while(--iteration)
{
        // roughly 31 seconds per 2^32 steps
        table_offset=(state[ant]*24)+(ant_orientation*3);
        it+=twoxtwo_table[table_offset+0];
        state[ant]=twoxtwo_table[table_offset+2];
        ant+=move_ant2x2[(ant_orientation=twoxtwo_table[table_offset+1])];
}

Aún no he intentado optimizarlo, lo siguiente que debe intentar es eliminar la ecuación de compensación y las búsquedas con interruptores y constantes anidados como antes (pero con 648 casos internos en lugar de 12).