malloc on different platforms

Question

I am testing a red-black tree implementation (repository) and I find that with Windows 10 and gcc, malloc starts returning NULL after inserting approx. 50 million nodes but on Linux it works at least up to 100 million nodes.

What conclusion can I make from this result? Is it a bug in my program or is it that malloc is "more efficient" (how?) on Linux?

int test() {
    int T = 1000000000; //test case 1,000,000,000 nodes
    int r2;
    struct node *root = NULL;
    srand(time(NULL));
    struct node *z;
    LEAF = malloc(sizeof(struct node));
    LEAF->color = BLACK;
    LEAF->left = NULL;
    LEAF->right = NULL;
    LEAF->key = 0;

    while (T-- > 0) {
        r2 = (2 + T) * (rand() % 100); // data
        z = malloc(sizeof(struct node));

        if (z != NULL) {

            z->key = r2;
            z->left = NULL;
            z->right = NULL;
            z->parent = NULL;
            z->color = RED;

            root = insert(root, z);

        } else printf("malloc failed at node number %d", T);
    }
    root = NULL;
    return 0;
}

I wonder if there are differences in the default alignment provided by `malloc()` on the 2 platforms? Perhaps either the `struct` size differs, or the allocation of the `struct` is happening differently because of alignment issues? — user1118321, Nov 17 '18 at 06:01
Those are two entirely different stacks and implementations of the standard library, the kernel etc. etc. A behavioural difference by a factor of two is not in the least surprising and could result from many different details. — Kilian Foth, Nov 17 '18 at 07:20
Probably you would get better perspective if you inspect memory consumption by the process, and compare it with the system's resources — max630, Nov 17 '18 at 08:12
be aware also of [memory overcommit](http://engineering.pivotal.io/post/virtual_memory_settings_in_linux_-_the_problem_with_overcommit/) — max630, Nov 17 '18 at 08:21

score 4 · Accepted Answer · answered Nov 17 '18 at 16:44

You can draw the conclusion that you can't make an unlimited number of successful malloc() calls if you don't release memory in-between.

You may have run 32 bit code in one case and 64 bit code in the other case. Compilers might allocate different amounts of memory for a small struct. malloc() might consume different amounts of memory for small allocations. Many possible differences.

You can also draw the conclusion that if you really need to allocate tens of millions of nodes then maybe a malloc() call for each node is not the best way to go. You can also draw the conclusion that if you really need to allocate tens of millions of nodes then maybe a different data structure is more useful.

score 1 · Answer 2 · answered Nov 17 '18 at 20:07

One possibility is that a 32 bit process on Linux has access to more memory (4GB) than a standard Windows 32 bit process (2GB).

You haven't shown the definition of your Node class in the question, but from your usage it consists of 3 pointers and two data fields (possibly an int and a char). On a 32 bit build, that is a minimum of 17 bytes. With padding for alignment, and a malloc overhead of 8 bytes, that comes to 32 bytes per allocation. With 50 million allocations, that works out to 1.6GB of memory, close to the 2GB limit a 32 bit process normally has on Windows. This can be expanded using the /LARGEMEMORYAWARE linker flag, which can give close to 4GB of process memory on a 64-bit Windows OS. This would then allow you to allocate around 100 million nodes, matching the Linux version.

malloc on different platforms

2 Answers2