Add to a variable multiple in cells variables

Question

I have code that is used to add all cells of a tab to a var:

#include <stdio.h> 
#include <stdlib.h> 
#include <assert.h> 
#include <malloc.h> 

#define NB 10000 

// Instruction RDTSC du Pentium 
static __inline__ unsigned long long RDTSC(void) { 
    unsigned hi, lo; 
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi)); 
    return ((unsigned long long) lo) | (((unsigned long long) hi) << 32); 
} 

// IS HERE TO CONTAIN THE TAB, IT WILL CONTAIN ALL THE NUMBERS I WILL HAVE TO ADD TO MY FINAL INT NAMES "somme" IN MY MAIN.
// Initialisation de la matrice d'entiers 
void InitTab(int **tab) { 
    int i, j; 

    for (i = 0; i < NB; i++) { 
        tab[i] = (int *) malloc(NB * sizeof(int)); 
        assert (tab[i] != NULL); 
    } 

    for (i = 0; i < NB; i++) 
        for (j = 0; j < NB; j++) 
            tab[i][j] = rand()%100000; 
} 


// IT WILL RETURN ME THE MINIMUM OF A COLUMN OF MY TABLE BECAUSE WHE WANT TO ADD THE MINIMUM OF ALL COLUMNS OF THE TABLE TO THE FINAL INT NAMES "somme" IN MY MAIN.
// Calcul du minimum d'une colonne 
int MinColonne(int **tab, int colonne) { 
    int i, min; 

    min = tab[0][colonne]; 
    for (i = 1; i < NB; i++) 
        if (min > tab[i][colonne]) min = tab[i][colonne]; 

    return (min); 
} 


// MAIN 
int main(void) { 
    int somme = 0; 
    int i,z; 
    int **tab; 


    unsigned long long t1, t2; // chronometrage 
    srand(1); 

    tab = (int **) malloc(NB * sizeof(int *)); 
    assert(tab != NULL); // exit si erreur d'allocation 

    InitTab(tab);// permet aussi de mettre le processeur en pleine puissance 


    t1 = RDTSC(); 
    for (z=0; z<10; z++) // pour avoir une moyenne du temps d'execution 
    for (i = 0; i < NB; i++) 
         somme += MinColonne(tab, i); 
t2 = RDTSC(); 

    printf("Somme des minima de chaque colonne : %d \n", somme); 

    printf("Temps en cycles d'horloge : %llu \n", (t2 - t1)); 

    return EXIT_SUCCESS; 
}

I have to optimize this code but I don't find any for to break, while to optimize and no multiple if ... (These are the only things I know how to optimize)

Do you know how to?

I can't touch at InitTab(tab); line and the double for.

Welcome to Code Review. Please write a title that describes what your code does, rather than how you would like to improve it. — Phrancis
– Phrancis, Commented Nov 27, 2015 at 13:29
Hi. I appreciate that you may not be a fluent english speaker but could you provide an overview of what each part of your code does / is supposed to be doing? — Kaz
– Kaz, Commented Nov 27, 2015 at 13:34

Community · Accepted Answer · 2020-06-10 13:24:26Z

Utilizing the cache

The reason your function is so slow is because you are traversing your matrix by rows instead of by columns. This means that every time you load a value from a new row, you are loading it from a different cache line, which is slow compared to reading nearby values (from the same row and cache line).

I modified your function to take the whole table as input and traverse it in linear fashion, reading all entries in one row before going to the next row. Your program took 11 seconds, and mine took 1.2 seconds, for an almost 10x speedup.

Here are my changes:

int FindSumOfMinOfColumns(int **tab, int size)
{
    int *minVals = malloc(size * sizeof(*minVals));
    int  row     = 0;
    int  col     = 0;
    int  sum     = 0;

    // Initialize with 0th element of each column.
    memcpy(minVals, tab[0], size * sizeof(*minVals));

    // Compute the minimum of each column.
    for (row = 1; row < size; row++) {
        int *pRow = tab[row];
        for (col = 0; col < size; col++) {
            if (pRow[col] < minVals[col])
                minVals[col] = pRow[col];
        }
    }

    // Sum up the minimum of each column and return it.
    for (col = 0; col < size; col++)
        sum += minVals[col];
    free(minVals);
    return sum;
}

int main(void) {
    // ...

    t1 = RDTSC();
    for (z=0; z<10; z++) // pour avoir une moyenne du temps d'execution
        somme += FindSumOfMinOfColumns(tab, NB);
    t2 = RDTSC();

    // ...
}

Stack Exchange Network

Add to a variable multiple in cells variables

1 Answer 1

Utilizing the cache

You must log in to answer this question.

Hot Network Questions

Add to a variable multiple in cells variables

1 Answer 1

Utilizing the cache

You must log in to answer this question.

Related

Hot Network Questions