malloc と配列の切り出し

2021年1月9日

はじめに

C 言語の malloc 関数はそこそこ時間がかかる印象があるが、大きな配列をひとつ確保してそれから小さな配列を切り出したほうが速かったりするのか、比較してみた。

環境

• Ubuntu 16.04 LTS

malloc 版

malloc1.c

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

#define N_TRIES 10000
#define N_MIN 2
#define N_MAX 500
#define V_MIN 0.
#define V_MAX 1.


int randi(int rmin, int rmax)
{
    return (int)(rmin + (rand()/(double)RAND_MAX)*(rmax - rmin));
}


double randf(double rmin, double rmax)
{
    return rmin + (rand()/(double)RAND_MAX)*(rmax - rmin);
}


int main(int argc, char *argv[])
{
    clock_t start_time;
    clock_t end_time;
    double elapsed_time;
    FILE *fp;
    int i, j, k;

    srand(0);

    start_time = clock();

    for(i = 0; i < N_TRIES; i++){
        int n = randi(N_MIN, N_MAX);
        double *a = malloc(sizeof(double)*n*n);
        double *b = malloc(sizeof(double)*n*n);
        double *c = malloc(sizeof(double)*n*n);

        for(j = 0; j < n; j++){
            for(k = 0; k < n; k++){
                a[j*n + k] = randf(V_MIN, V_MAX);
                b[j*n + k] = randf(V_MIN, V_MAX);
                c[j*n + k] = randf(V_MIN, V_MAX);
            }
        }

        free(a);
        free(b);
        free(c);
    }

    end_time = clock();

    elapsed_time = (end_time - start_time)/(double)CLOCKS_PER_SEC;
    printf("Elapsed Time: %f s\n", elapsed_time);

    return 0;
}

正方行列を考え、ランダムにサイズを決めて、3 つ配列を作り、それらをそれぞれ乱数で初期化する。領域は都度 malloc で確保し、それを繰り返す。

本当は行列演算を入れようかと思ったが、入れなくても検証できそうだったので、省いた。

配列切り出し版

malloc2.c

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

#define N_TRIES 10000
#define N_MIN 2
#define N_MAX 500
#define V_MIN 0.
#define V_MAX 1.


int randi(int rmin, int rmax)
{
    return (int)(rmin + (rand()/(double)RAND_MAX)*(rmax - rmin));
}


double randf(double rmin, double rmax)
{
    return rmin + (rand()/(double)RAND_MAX)*(rmax - rmin);
}


double *mem;
size_t mem_current_size = 0;


void mem_create(size_t n)
{
    mem = malloc(sizeof(double)*n);
}


void mem_delete()
{
    free(mem);
}


double* mem_alloc(size_t n)
{
    double *p = &mem[mem_current_size];
    mem_current_size += n;
    return p;
}


int main(int argc, char *argv[])
{
    clock_t start_time;
    clock_t end_time;
    double elapsed_time;
    FILE *fp;
    int i, j, k;

    srand(0);

    start_time = clock();

    mem_create(N_MAX*N_MAX*3);

    for(i = 0; i < N_TRIES; i++){
        int n = randi(N_MIN, N_MAX);
        double *a = mem_alloc(n*n);
        double *b = mem_alloc(n*n);
        double *c = mem_alloc(n*n);

        for(j = 0; j < n; j++){
            for(k = 0; k < n; k++){
                a[j*n + k] = randf(V_MIN, V_MAX);
                b[j*n + k] = randf(V_MIN, V_MAX);
                c[j*n + k] = randf(V_MIN, V_MAX);
            }
        }

        mem_current_size = 0;
    }

    mem_delete();

    end_time = clock();

    elapsed_time = (end_time - start_time)/(double)CLOCKS_PER_SEC;
    printf("Elapsed Time: %f s\n", elapsed_time);

    return 0;
}

領域を都度 malloc で確保する代わりに、一度だけ malloc で確保し、そこから必要なサイズ分だけ切り出す。

Makefile

all: gcc-noopt clang-noopt gcc-opt clang-opt

gcc-noopt:
	gcc -omalloc1 malloc1.c
	gcc -omalloc2 malloc2.c
	./malloc1
	./malloc2
clang-noopt:
	clang -omalloc1 malloc1.c
	clang -omalloc2 malloc2.c
	./malloc1
	./malloc2
gcc-opt:
	gcc -O2 -omalloc1 malloc1.c
	gcc -O2 -omalloc2 malloc2.c
	./malloc1
	./malloc2
clang-opt:
	clang -O2 -omalloc1 malloc1.c
	clang -O2 -omalloc2 malloc2.c
	./malloc1
	./malloc2

GCC と Clang で、最適化ありなしで比較してみる。

比較

実行。

$ make
gcc -omalloc1 malloc1.c
gcc -omalloc2 malloc2.c
./malloc1
Elapsed Time: 22.165162 s
./malloc2
Elapsed Time: 19.312167 s
clang -omalloc1 malloc1.c
clang -omalloc2 malloc2.c
./malloc1
Elapsed Time: 22.337604 s
./malloc2
Elapsed Time: 19.472669 s
gcc -O2 -omalloc1 malloc1.c
gcc -O2 -omalloc2 malloc2.c
./malloc1
Elapsed Time: 17.939730 s
./malloc2
Elapsed Time: 15.563940 s
clang -O2 -omalloc1 malloc1.c
clang -O2 -omalloc2 malloc2.c
./malloc1
Elapsed Time: 15.151976 s
./malloc2
Elapsed Time: 15.336044 s

概ね配列切り出しのほうが速いが、Clang の最適化ありだとあまり変わらなくなっている。単体で見ると malloc のほうが遅いのは間違いないのだが (配列の初期化を外してみれば確認できる)、その後のアクセスも含めると、最適化によっては変わらなかったり、むしろ malloc のほうが速くなったりするようである。速度が気になるなら、妙なことをするよりも動的確保自体を減らすことを考えよ、ということだろう。