1

Recebi um código implementando Dijkstra em C, e minha missão é otimizar esse código. O código é esse:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM_NODES                          1000
#define NONE                               9999

struct _NODE
{
  int iDist;
  int iPrev;
};
typedef struct _NODE NODE;

struct _QITEM
{
  int iNode;
  int iDist;
  int iPrev;
  struct _QITEM *qNext;
};
typedef struct _QITEM QITEM;

QITEM *qHead = NULL;




short int AdjMatrix[NUM_NODES][NUM_NODES];

int g_qCount = 0;
NODE rgnNodes[NUM_NODES];
int ch;
int iPrev, iNode;
int i, iCost, iDist;


void print_path (NODE *rgnNodes, int chNode)
{
  if (rgnNodes[chNode].iPrev != NONE)
    {
      print_path(rgnNodes, rgnNodes[chNode].iPrev);
    }
  printf (" %d", chNode);
  fflush(stdout);
}


void enqueue (int iNode, int iDist, int iPrev)
{
  QITEM *qNew = (QITEM *) malloc(sizeof(QITEM));
  QITEM *qLast = qHead;

  if (!qNew) 
    {
      fprintf(stderr, "Out of memory.\n");
      exit(1);
    }
  qNew->iNode = iNode;
  qNew->iDist = iDist;
  qNew->iPrev = iPrev;
  qNew->qNext = NULL;

  if (!qLast) 
    {
      qHead = qNew;
    }
  else
    {
      while (qLast->qNext) qLast = qLast->qNext;
      qLast->qNext = qNew;
    }
  g_qCount++;
  //               ASSERT(g_qCount);
}


void dequeue (int *piNode, int *piDist, int *piPrev)
{
  QITEM *qKill = qHead;

  if (qHead)
    {
      //                 ASSERT(g_qCount);
      *piNode = qHead->iNode;
      *piDist = qHead->iDist;
      *piPrev = qHead->iPrev;
      qHead = qHead->qNext;
      free(qKill);
      g_qCount--;
    }
}


int qcount (void)
{
  return(g_qCount);
}

int dijkstra(int chStart, int chEnd) 
{



  for (ch = 0; ch < NUM_NODES; ch++)
    {
      rgnNodes[ch].iDist = NONE;
      rgnNodes[ch].iPrev = NONE;
    }

  if (chStart == chEnd) 
    {
      printf("Shortest path is 0 in cost. Just stay where you are.\n");
    }
  else
    {
      rgnNodes[chStart].iDist = 0;
      rgnNodes[chStart].iPrev = NONE;

      enqueue (chStart, 0, NONE);

     while (qcount() > 0)
 {
      dequeue (&iNode, &iDist, &iPrev);
      for (i = 0; i < NUM_NODES; i++)
        {
          if ((iCost = AdjMatrix[iNode][i]) != NONE)
        {
          if ((NONE == rgnNodes[i].iDist) || 
              (rgnNodes[i].iDist > (iCost + iDist)))
            {
              rgnNodes[i].iDist = iDist + iCost;
              rgnNodes[i].iPrev = iNode;
              enqueue (i, iDist + iCost, iNode);
            }
        }
        }
    }

      printf("Shortest path is %d in cost. ", rgnNodes[chEnd].iDist);
      printf("Path is: ");
      print_path(rgnNodes, chEnd);
      printf("\n");

    }
}

  int main(int argc, char *argv[]) {
  int i,j,k;
  FILE *fp;
  char line[2048];
  char* token;

  if (argc<2) {
    fprintf(stderr, "Usage: dijkstra <filename>\n");
    fprintf(stderr, "Only supports matrix size is #define'd.\n");
  }

  /* open the adjacency matrix file */
  fp = fopen (argv[1],"r");

   /*
  // make a fully connected matrix 
  for (i=0;i<NUM_NODES;i++) {
    for (j=0;j<NUM_NODES;j++) {
      // make it more sparce 
       fscanf(fp,"%d",&k);
            AdjMatrix[i][j]= k;
    }
 }
  */

  for (i=0;i<1000;i++) {
      for (j=0;j<1000;j++) {
        AdjMatrix[i][j] = NONE;
      }
  }  

   while (fgets(line, sizeof(line), fp)) {
       token = strtok(line," ");
       i = atoi(token);
       token = strtok(NULL, " \n");
        while (token) {
            j = atoi(token);
            AdjMatrix[i][j]= 1;
            token = strtok(NULL, " \n");
        }
    }  


  // nao mudar esta lista de caminhos a serem pesquisados
  for (i=0,j=50;i<50;i++,j--) {
      printf("Path %d => %d\n",i,j);
     dijkstra(i,j);

  }

  for (i=50,j=100;i<100;i++,j--) {
      printf("Path %d => %d\n",i,j);
      dijkstra(i,j);

  }  

/*
  for (i=0;i<300;i++) {
      for (j=0;j<300;j++) {
        printf("%d ",AdjMatrix[i][j]);
      }
      printf("\n");
  }  
*/

/*
  printf("Path %d => %d\n",0,13);
  dijkstra(0,13);
  printf("Path %d => %d\n",1,77);
  dijkstra(1,77);
*/
  printf("Path %d => %d\n",51,99);
  dijkstra(51,99);
  exit(0);


}

Bom, eu fiz algumas otimizações, que não são nada demais, trocar int por short int, mudar NUM_NODES para 300 porque sei que o arquivos com de teste tem 300 nodos, diminuir o tamanho do array de char que lê as linhas porque sei que uma linha não tem 2048 caracteres, adicionar um ponteiro para o ultimo elemento da fila e mudar a ordem dos atributos da struct, mas a principal otimização, e que eu pensei que mudaria drasticamente o número de misses da cache, só piorou. No código dado a matriz é declarada assim: int AdjMatrix[NUM_NODES][NUM_NODES]; Andei pesquisando, e alocar na memória essa matriz seria muito mais cache-friendly devido à contiguidade dos endereços, e o mesmo vale para o Array rgnNodes, meu código ficou assim:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM_NODES                          300
#define NONE                               9999

struct _NODE
{
  short int iDist;
  short int iPrev;
};
typedef struct _NODE NODE;

struct _QITEM
{
  struct _QITEM *qNext;
  short int iNode;
  short int iDist;
  short int iPrev;
};
typedef struct _QITEM QITEM;

short int *mat;
QITEM *qHead = NULL;
QITEM *qTail = NULL;


short int g_qCount = 0;
NODE *rgnNodes;
short int ch;
short int iPrev, iNode;
short int i, iDist;
int offset;

void print_path (NODE *rgnNodes, short int chNode)
{
  if (rgnNodes[chNode].iPrev != NONE)
    {
      print_path(rgnNodes, rgnNodes[chNode].iPrev);
    }
  printf (" %d", chNode);
  fflush(stdout);
}


void enqueue (short int iNode, short int iDist, short int iPrev)
{
  QITEM *qNew = (QITEM *) malloc(sizeof(QITEM));

  if (!qNew) 
    {
      fprintf(stderr, "Out of memory.\n");
      exit(1);
    }
  qNew->iNode = iNode;
  qNew->iDist = iDist;
  qNew->iPrev = iPrev;
  qNew->qNext = NULL; //qNew recebe os parametros

  if (!qHead)
    {
      qHead = qTail = qNew;

    }
  else
    {
      qTail->qNext = qNew;
      qTail=qNew;
    }
  g_qCount++;
  //               ASSERT(g_qCount);
}


void dequeue (short int *piNode, short int *piDist, short int *piPrev)
{
  QITEM *qKill = qHead;

  if (qHead)
    {
      //                 ASSERT(g_qCount);
      *piNode = qHead->iNode;
      *piDist = qHead->iDist;
      *piPrev = qHead->iPrev;
      qHead = qHead->qNext;
      free(qKill);
      g_qCount--;
    }
}


short int qcount (void)
{
  return(g_qCount);
}

int dijkstra(short int chStart, short int chEnd) 
{



  for (ch = 0; ch < NUM_NODES; ch++)
    {
      rgnNodes[ch].iDist = NONE;
      rgnNodes[ch].iPrev = NONE;
    }

  if (chStart == chEnd) 
    {
      printf("Shortest path is 0 in cost. Just stay where you are.\n");
    }
  else
    {
      rgnNodes[chStart].iDist = 0;
      rgnNodes[chStart].iPrev = NONE;

      enqueue (chStart, 0, NONE);

     while (qcount() > 0)
    {
      dequeue (&iNode, &iDist, &iPrev);
      for (i = 0; i < NUM_NODES; i++)
        {
          offset= iNode * NUM_NODES + i;
          if (mat[offset] != NONE && ((NONE == rgnNodes[i].iDist) || (rgnNodes[i].iDist > (1 + iDist))))  
        {
              rgnNodes[i].iDist = iDist + 1;
              rgnNodes[i].iPrev = iNode; 
              enqueue (i, iDist + 1, iNode);
            }

        }
    }

      printf("Shortest path is %d in cost. ", rgnNodes[chEnd].iDist);
      printf("Path is: ");
      print_path(rgnNodes, chEnd);
      printf("\n");

    }
}

int main(short int argc, char *argv[]) {
  short int i,j,k;
  FILE *fp;
  char line[512];
  char* token;
  mat=(short int *)malloc(NUM_NODES * NUM_NODES * sizeof(short int));
  rgnNodes = (NODE *)malloc(NUM_NODES * sizeof(NODE));
  if (argc<2) {
    fprintf(stderr, "Usage: dijkstra <filename>\n");
    fprintf(stderr, "Only supports matrix size is #define'd.\n");
  }

  /* open the adjacency matrix file */
  fp = fopen (argv[1],"r");

/*
  // make a fully connected matrix 
  for (i=0;i<NUM_NODES;i++) {
    for (j=0;j<NUM_NODES;j++) {
      // make it more sparce 
      fscanf(fp,"%d",&k);
            mat[i][j]= k;
    }
  }
  */

  for (i=0;i<300;i++) {
      for (j=0;j<300;j++) {
        offset= i * NUM_NODES + j;
        mat[offset]=NONE;
      }
  }  

   while (fgets(line, sizeof(line), fp)) { //completa a matriz com as devidas adjacencias
       token = strtok(line," ");
       i = atoi(token);
       token = strtok(NULL, " \n");
        while (token) {
            j = atoi(token);
            offset=i*NUM_NODES+j;
            mat[offset]= 1;
            token = strtok(NULL, " \n");
        }
    }  


  // nao mudar esta lista de caminhos a serem pesquisados
  for (i=0,j=50;i<50;i++,j--) {
      printf("Path %d => %d\n",i,j);
      dijkstra(i,j);

  }

  for (i=50,j=100;i<100;i++,j--) {
      printf("Path %d => %d\n",i,j);
      dijkstra(i,j);

  }  

/*
  for (i=0;i<300;i++) {
      for (j=0;j<300;j++) {
        printf("%d ",mat[i][j]);
      }
      printf("\n");
  }  
*/

/*
  printf("Path %d => %d\n",0,13);
  dijkstra(0,13);
  printf("Path %d => %d\n",1,77);
  dijkstra(1,77);
*/
  printf("Path %d => %d\n",51,99);
  dijkstra(51,99);


  exit(0);


}

É importante mencionar que os testes estão sendo realizados no valgrind com a seguinte configuração:

valgrind --tool=cachegrind --I1=16384,1,32 --D1=16384,1,32 --LL=16384,1,32 ./dijkstra_large test300.adjlist

ou seja, L1 de dados e instruções = 16KB,associatividade 1, tamanho da linha 32bytes L2 = 16KB,associatividade 1, tamanho da linha 32bytes

E claro, o código que eu otimizei está melhor do que o original, mas a otimização da matriz e o array pioraram o código, e eu gostaria de saber o por que. Além disso, se alguém tiver alguma dica de otimização eu seria muito grato.

Não posso mudar as configurações da cache

1 Resposta 1

1

TLDR the code ... int é mais rápido que short int; os elements dum array são contíguos (não precisas de malloc()/free()).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .