Как улучшить производительность этого кода? - PullRequest
Новая
       57

Как улучшить производительность этого кода?

0 голосов
/ 07 апреля 2020

Я пишу программу, которая работает с массивами больших целых чисел и выполняет основные операции c. Я беспокоюсь о производительности моего кода. Он выполняется за 47 секунд при компиляции с: 

gcc -Ofast -funroll-all-loops -ftree-vectorize -fopt-info-vec -g -lm $1 -o ${2}.Ofast

Я думал, что ключом к решению моей проблемы является изменение типа данных моих массивов на unsigned long long, но когда я это сделаю, результат будет другим.

Любое предложение приветствуется, даже если оно меняет всю мою программу или типы данных, если это не меняет результат моей программы.

Кроме того, я смог визуализировать, что моя производительность проблема в основном в функциях LongNumAddition и LongNumAddDigit, как я могу улучшить свой код? Спасибо за ваше внимание. 

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
// Variable used to generate pseudo-random numbers
unsigned int seed;
unsigned int temp;
unsigned int var1 = 214013;
unsigned int var2 = 2531011;
#define val13 13
#define ten 10

// Function to generate pseudo-random numbers
inline int myRandom() {
  temp = var1*seed;
  seed = temp + var2;
  return (seed>>val13);
}

void LongNumInit( uint8_t *L, size_t N )
{
  for(size_t i = 0; i < N; ++i){
    L[i] = myRandom() % 10;
  }

}

void LongNumPrint( uint8_t *L, size_t N, uint8_t *Name )
{
  printf("%s:", Name);
  for ( size_t i=N; i>0;--i )
  {
    printf("%d", L[i-1]);
  }
  printf("\n");
}

void LongNumSet( uint8_t *L, size_t N){
    memset(L,0,N);
}


void LongNumCopy( const uint8_t *Vin, uint8_t *Vout, size_t N )
{
  memcpy(Vout,Vin,N);
}
uint8_t LongNumAddition( uint8_t *Vin1, uint8_t *Vin2,uint8_t *Vout, size_t N)
{
  uint8_t CARRY = 0;

  for ( size_t i=0; i< N; ++i )
  {

        Vout[i] = Vin1[i] + Vin2[i] + CARRY;
        CARRY = (Vout[i] > 9);
        if(CARRY){
           Vout[i] -= ten;
        }
      }
  return CARRY;
}


uint8_t LongNumAddDigit( uint8_t *V, uint8_t digit, size_t N )
{
  size_t i=0;
  V[0] += digit;

  if ( V[0] < ten){
        return 0;
  }
  V[0] -=ten;

  // add carry, maybe iteratively for all digits

  while ((++i < N) && (V[i] >= 9))
  {
    V[i] = 0;
  }
  if((i != N) && (V[i] < 9)){
    V[i]++;
    return 0;
  }
  return 1;
}

uint8_t LongNumHorizAdd( uint8_t *Vin, uint8_t *Vout, size_t N )
{
  uint8_t CARRY = 0;
  LongNumSet ( Vout, N);
  for ( size_t i=0; i< N; ++i )
  {
    LongNumAddDigit ( Vout, Vin[i], N );

  }

  return 0; // CARRY can never be set
}
uint8_t LongNumConstMult( uint8_t *V, size_t N, uint8_t digit )
{
  uint8_t CARRY = 0;
  for ( size_t i=0; i< N; ++i )
  {
    V[i] = V[i] * digit + CARRY;
    CARRY = ((u_int32_t)V[i] * (u_int32_t)0xCCCD) >> 19;
    V[i] -= (CARRY << 3) + (CARRY << 1);
  }
  return CARRY; // may be from 0 to 9
}
void LongNumMultiply( uint8_t *Vin1, uint8_t *Vin2, uint8_t *VoutH, uint8_t *VoutL, size_t N)
{

  // Create Temporal Long Integer with double size
  uint8_t *TEMP = (uint8_t*) malloc(2*N*sizeof(uint8_t));
  uint8_t *RES = (uint8_t*) malloc( 2*N*sizeof(uint8_t));

  LongNumSet  ( RES, 2*N);    // Set RES to 0

  for ( size_t i=0; i<N; ++i )
  {
    LongNumSet  ( TEMP, 2*N);            // Set TEMP to 0
    LongNumCopy ( Vin1, TEMP+i, N );         // Copy Vin1 -> TEMP, with offset i
    LongNumConstMult( TEMP, 2*N, Vin2[i] );  // TEMP * Vin2[i] -> TEMP
    LongNumAddition ( TEMP, RES, RES, 2*N ); // TEMP + RES -> RES
  }

  // Result goes to VoutH-VoutL
  LongNumCopy ( RES,   VoutL, N );  // Copy RES   -> VoutL
  LongNumCopy ( RES+N, VoutH, N );  // Copy RES+N -> VoutH
}
int main (int argc, char **argv)
{
  int i, sum1, sum2, sum3, N=10000, Rep=50;

  seed = 12345;

  // obtain parameters at run time
  if (argc>1) { N    = atoi(argv[1]); }
  if (argc>2) { Rep  = atoi(argv[2]); }
  printf("Challenge #3: Vector size is %d. Repeat %d times\n", N, Rep);
 // Create Long Nums
  unsigned char *V1= (unsigned char*) malloc( N*sizeof(unsigned char) );
  unsigned char *V2= (unsigned char*) malloc( N*sizeof(unsigned char) );
  unsigned char *V3= (unsigned char*) malloc( N*sizeof(unsigned char) );
  unsigned char *V4= (unsigned char*) malloc( N*sizeof(unsigned char) );

  LongNumInit ( V1, N ); LongNumInit ( V2, N ); LongNumInit ( V3, N );
   // Repeat
  for (i=0; i<Rep; i++)
  {
    LongNumAddition ( V1, V2, V4, N );
    LongNumMultiply ( V3, V4, V2, V1, N );
    LongNumHorizAdd ( V1, V2, N );
    LongNumAddDigit ( V3, V2[0], N );
  }

  // Print last 32 digits of Long Numbers
  LongNumPrint( V1, 32, "V1" );
 LongNumPrint( V2, 32, "V2" );
  LongNumPrint( V3, 32, "V3" );
  LongNumPrint( V4, 32, "V4" );

  free(V1); free(V2); free(V3); free(V4);
  return 0;
}

1 Ответ

2 голосов
/ 08 апреля 2020

Используйте профилировщик - настоятельно рекомендуем сначала kcachegrind

https://kcachegrind.github.io/html/Usage.html

, установить valgrind и kcachegrind, а затем скомпилировать бинарный файл с помощью '-g', используя g cc, а затем запустите ваш двоичный файл, используя 

valgrind --tool=callgrind ./yourbinary parameters ...

, затем запустите kcachgrind в текущем каталоге, переключите представление для отображения строчной информации о синхронизации, как это

https://kcachegrind.github.io/html/Shot4Large.html

это говорит вам, какие строки вашего кода занимали большую часть времени выполнения.

...