如何提高此代码的性能?

问题描述 投票:1回答:1

我正在编写一个程序,该程序可以使用大整数数组进行基本操作。我担心代码的性能。使用以下命令编译时,它将在47秒内执行:

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

我认为解决问题的关键是将数组的数据类型更改为unsigned long long,但是当执行此操作时,结果将有所不同。

任何建议都是欢迎的,即使它改变了我的整个程序或数据类型,只要它不改变程序的结果。

而且,我已经能够看到我的性能问题主要在LongNumAdditionLongNumAddDigit函数中,如何改善我的代码?感谢您的关注。

#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;
}

我正在编写一个程序,该程序可以使用大整数数组进行基本操作。我担心代码的性能。使用以下命令编译时,它将在47秒内执行:gcc -...

c performance vectorization biginteger processing-efficiency
1个回答
1
投票

使用分析器-强烈建议使用kcachegrind

© www.soinside.com 2019 - 2024. All rights reserved.