3
\$\begingroup\$

Can you help me verify my test result? I'm testing different malloc() implementations with a small program that allocates gigabytes many times:

int main(int agrc, char **argv) {
    int i;
    for (i = 0; i < 1000000; i++) {
        void *p = malloc(1024 * 1024 * 1024);
        free(p);
    }
    return (0);
}

If I run it and time it, then it takes 5 seconds:

$ time ./gig 

real  0m5.140s
user  0m0.384s
sys   0m4.752s

Now I try my custom malloc() with exactly the same program and it seems unreasonable faster.

$ time ./gb_quickfit

real  0m0.045s
user  0m0.044s
sys   0m0.000s

Why is the custom malloc() so much faster? I used the "quick malloc()" algorithm.

void *malloc_quick(size_t nbytes) /* number of bytes of memory to allocate */
{
    Header *moreroce(unsigned);
    int index, i;
    index = qindex(nbytes);

    /* 
     * Use another strategy for too large allocations. We want the allocation
     * to be quick, so use malloc_first().
     */

    if (index >= NRQUICKLISTS) {
        return malloc_first(nbytes);
    }

    /* Initialize the quick fit lists if this is the first run. */
    if (first_run) {
        for (i = 0; i < NRQUICKLISTS; ++i) {
            quick_fit_lists[i] = NULL;
        }
        first_run = false;
    }


    /*
     * If the quick fit list pointer is NULL, then there are no free memory
     * blocks present, so we will have to create some before continuing.
     */

    if (quick_fit_lists[index] == NULL) {
        Header* new_quick_fit_list = init_quick_fit_list(index);
        if (new_quick_fit_list == NULL) {
            return NULL;
        } else {
            quick_fit_lists[index] = new_quick_fit_list;
        }
    }


    /*
     * Now that we know there is at least one free quick fit memory block,
     * let's use return that and also update the quick fit list pointer so that
     * it points to the next in the list.
     */

    void* pointer_to_return = (void *)(quick_fit_lists[index] + 1);
    quick_fit_lists[index] = quick_fit_lists[index]->s.ptr;
   /* printf("Time taken %d seconds %d milliseconds", msec/1000, msec%1000);*/
    return pointer_to_return;
}

I'm sure there is a catch because I don't have much experience in this detailed level of C. Why are the results so different? Does the system malloc() only have one algorithm?

Can I be sure that the test is correct? If I run Valgrind with the test, it reports no error . I try again run the test, check with Valgrind that the test doesn't generate error with Valgrind and get the result again

$ time ./gb_quickfit 

real    0m0.759s
user    0m0.584s
sys 0m0.172s
dac@dac-Latitude-E7450:~/ClionProjects/omalloc/openmalloc/overhead$ time ./a.out 

real    0m0.826s
user    0m0.644s
sys 0m0.180s

Now the result is more reasonable, my custom malloc is only slightly faster. The reason I got so large difference first time might have been of errors in the test allocating too much. The second test looks like:

/* returns an array of arrays of char*, all of which NULL */
char ***alloc_matrix(unsigned rows, unsigned columns) {
    char ***matrix = malloc(rows * sizeof(char **));
    unsigned row = 0;
    unsigned column = 0;
    if (!matrix) abort();

    for (row = 0; row < rows; row++) {
        matrix[row] = calloc(columns, sizeof(char *));
        if (!matrix[row]) abort();
        for (column = 0; column < columns; column++) {
            matrix[row][column] = NULL;
        }
    }
    return matrix;
}

/* deallocates an array of arrays of char*, calling free() on each */
void free_matrix(char ***matrix, unsigned rows, unsigned columns) {
    unsigned row = 0;
    unsigned column = 0;
    for (row = 0; row < rows; row++) {
        for (column = 0; column < columns; column++) {
            /*    printf("column %d row %d\n", column, row);*/
            free(matrix[row][column]);
        }
        free(matrix[row]);
    }
    free(matrix);
}


int main(int agrc, char **argv) {
    /* int i;

    for (i = 0; i < 1000000; i++) {
        void *p = malloc(1024 * 1024 * 1024);
        free(p);
    }*/
    int x = 10000;
    char *** matrix = alloc_matrix(x, x);
    free_matrix(matrix, x, x);
    return (0);
}
\$\endgroup\$
2
\$\begingroup\$

It's very possible that the memory is not really being allocated in RAM, but is in the virtual address space. I couldn't guess why your implementation causes this, but if you keep the memory allocated and sleep, you may find (assuming your on Linux, I don't know about Windows) that the memory is allocated but not backed by anything till you use it, due to the size.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.