0

I'm studying about the mechanism of malloc() and free() function in C. After few test, I discern that the mechanism of those function follows worst fit algorithm, doesn't it.

#include <stdio.h>
#include <stdlib.h>
int main()
{
    void* base;
    void* a = malloc(100);
    base = a;
    void* b = malloc(60);
    printf("%ld   %ld\n", a-base, b-base);
    free(a);
    a = malloc(40);
    printf("Free then reallocate a\n%ld   %ld\n", a-base, b-base);
    void* c= malloc(1);
    printf("Allocate c c\n%ld   %ld   %ld\n", a-base, b-base, c-base);
    free(b);
    b = malloc(1);
    printf("Free then reallocate b\n%ld   %ld   %ld\n", a-base, b-base, c-base);
    return 0;
}

Output:

0   112
Free then reallocate a
720   112
Allocate c c
720   112   768
Free then reallocate b
720   800   768
Cường Đặng Cao
  • 47
  • 5
  • 1
    None of those 3 algorithms are "optimal algorithms". They're just "algorithms". They're optimal for some usage patterns, and brutally terrible for others. – Alexander May 14 '21 at 15:38
  • 1
    Related?: [c++ - How do malloc() and free() work? - Stack Overflow](https://stackoverflow.com/questions/1119134/how-do-malloc-and-free-work) – MikeCAT May 14 '21 at 15:39
  • 2
    Malloc's allocation strategies vary between implementations. To get a good answer, you should pick one OS in particular, and ask about it. For the most part, malloc has different memory pools dedicated to objects of various sizes. It attempts to hit a trade off between minimizing memory waste, maximizing speed, and minimizing CPU/Memory overhead of overly-granular book keeping. – Alexander May 14 '21 at 15:40
  • 2
    As always, if you have specific memory usage requirements in your program that are super important, you should code for them. You cannot rely on any particular allocation strategy in the standard library, and implementations will vary. BTW, you really shouldn't be doing pointer arithmetic on unrelated objects. – paddy May 14 '21 at 15:40
  • 3
    You can look up the implementation of malloc and free with whatever library you're using. For example, there's some documentation for the glibc versions here: https://sourceware.org/glibc/wiki/MallocInternals . – Paul Hankin May 14 '21 at 15:40
  • I have just edit my post, sorry everyone – Cường Đặng Cao May 14 '21 at 15:43
  • 1
    (ps: pointer arithmetic on void* is not legal c, although it's a gcc extension). The correct printf format for intptr_t is not `%ld` but `PRIdPTR` (or some other options from stdint.h) – Paul Hankin May 14 '21 at 15:44
  • "best fit, first fit or worst fit". Those are strategies that you can apply *as is* in an idealized world. In the real world the answer is: "is complicated". – bolov May 14 '21 at 15:45
  • It's possible there was some dynamic allocation when you called `printf()`, so the memory you think should be reused is no longer available. – Barmar May 14 '21 at 15:49

0 Answers0