Home / Questions / 329089
Accepted
Marcos Cerioni
Asked: 2020-02-14 04:04:51 +0800 CST 2020-02-14 04:04:51 +0800 CST

Structures in C, time difference of 40% without knowing why

  • 772

I am wanting to access already given graphs. I have thousands of lines of code. Here are some before and after examples.

typedef unsigned int u32;
typedef struct GrafoSt *Grafo;
typedef struct DuplaSt *Dupla;

struct GrafoSt
{
    ...
    Dupla colorVer;

    ...
};

struct DuplaSt
{
    u32 v1;
    u32 v2;
};

// Ejemplo: 

Grafo ConstruccionGrafo() {

    g->colorVer = malloc(n*sizeof(struct DuplaSt));
    ...
    g->colorVer[0].v2 = 0;
    u32 posVer = 0;
    for(u32 i = 1; i < 2*n; i++)
    {
        if (...)
        {
            posVer++;
            g->colorVer[posVer].v2 = posVer;
        }
        else
            ...
    }

}

What I want to do is take out the "DuplaSt" structure.

What I thought was:

struct GrafoSt
{
    ...
    u32** colorVer;

    ...
};

// Ejemplo

Grafo ConstruccionGrafo() {
    for(u32 i = 0; i < n; i++)
        g->colorVer[i] = malloc(n*sizeof(unsigned int));

    g->colorVer[0][1] = 0;
    u32 posVer = 0;
    for(u32 i = 1; i < 2*n; i++)
    {
        if (...)
        {
            posVer++;
            g->colorVer[posVer][1] = posVer;
        }
        else
            ...

    }

And ready.

In other words, I have very large graphs, and with the first option, loading the degree, running the greedy algorithm many times with different reordering, etc, etc, takes much less time than with the second technique.

I can not say why. Because it seems to me that they are almost very similar actions but a very high optimization difference.

c

1 Answers

  1. Best Answer

    In other words, I have very large graphs, and with the first option, loading the degree, running the greedy algorithm many times with different reordering, etc, etc, takes much less time than with the second technique.

    Dynamic memory allocation is a heavy process. On each request, the OS has to allocate a portion of memory that is not already allocated... if it doesn't find any block within the application's memory, then it has to allocate a new block for that application and allocate memory from that block... It's a time-consuming process.

    That said, in the first case we have a single memory reservation :

    g->colorVer = malloc(n*sizeof(struct DuplaSt));

    While in the second, we have n:

    for(u32 i = 0; i < n; i++)
    g->colorVer[i] = malloc(n*sizeof(unsigned int));

    So it seems obvious to think that the second algorithm will be slower than the first.

    • 2