Is C malloc slow?

CoderMan · 02-11-2009, 04:01 PM

Is using dynamic memory allocation with malloc (in C) significantly slower than regular assignments?

I'm writing this application that is supposed to be minimalistic, so speed and storage space are important. In my case, I have an array of structs, which each contain a character array of 256 elements. I chose 256 (non-dynamically) because that was the upper-limit needed, but I know usually the strings stored in these character arrays will only be about 50 to 80 characters.

In my case, I typically have between 10 and 60 structs (the memory for the structs themselves is assigned dynamically as needed). So I know that if I used char pointers in the structs, and implemented dynamic memory allocation for each pointer once it was ready to receive a value of known length, I'd probably be using several KB less of the user's volatile memory. But I also read somewhere that malloc can be slower than the non-dynamic allocation, because it has to scan for free memory first. (?)

Any insights into this or any other issues I should take into account here?

jailbait · 02-11-2009, 04:21 PM

There are three ways that using malloc can affect speed. Using malloc creates a smaller binary and your program will load from disk faster.

Using malloc and free judiciously can keep peak memory demand low and reduce system paging. Paging (misnamed swapping in Linux) is horribly slow.

Using malloc and free cost cpu time and used stupidly can significantly slow down a program. Malloc is a kernel call and the kernel has to scan its free memory queue and move some free memory to your program's exclusive use. Non-dynamic allocation does not involve the kernel at all.

--------------------
Steve Stites

johnsfine · 02-11-2009, 05:09 PM

Quote:

Originally Posted by CoderMan

Is using dynamic memory allocation with malloc (in C) significantly slower than regular assignments?

Using malloc and free take some time, each time you call them. But if you aren't allocating and freeing things a super large number of times per run of your program, that doesn't matter much.

I think you are also asking about the relative performance after allocation, I think comparing an array of char as a member of a struct vs. a pointer to char as a member of a struct.

The code will be different and one might be faster than the other, and it seems more likely that this performance difference would matter rather than the malloc overhead mattering.

Depending on exactly how you use it, a char* as a structure member might be faster or slower than a char[256] as a structure member. More often the char* would be slower.

Odds are, other aspects of your code take long enough that this difference wouldn't matter.

Quote:

(the memory for the structs themselves is assigned dynamically as needed).

Do you know the char array length for a given struct at the time you malloc that struct? If so, it should be practical to make the variable length char array directly a member of the struct. Just make it the last member, make it as small or smaller than the smallest valid size and know the difference between sizeof() the struct and the true size is the difference in that array length.

Some C implementations allow a char array dimensioned [] to be the last member of a struct others allow [0]. I don't recall which is correct. When I do such things, I tend to use [1] instead.

Quote:

I also read somewhere that malloc can be slower than the non-dynamic allocation, because it has to scan for free memory first. (?)

Would you allocate the char array just once per struct? If so, the work inside malloc is trivial. Your comparing 10 to 60 malloc calls to allocate the structs with included char arrays, vs. 20 to 120 calls to allocate the structs with separate char arrays.

Quote:

Originally Posted by jailbait

Malloc is a kernel call and the kernel has to scan its free memory queue and move some free memory to your program's exclusive use.

More accurately, malloc can be a kernel call. Most calls to malloc find memory already committed to the process, and do not involve any kernel call. Some calls to malloc require kernel calls. In the context of the questions in the first post of this thread, it is a reasonable assumption that doubling the number of malloc calls by splitting each struct from its char array, while reducing the total memory allocated, will not increase the total number of kernel calls (more likely it would decrease it).

wje_lq · 02-11-2009, 06:51 PM

Quote:

Using malloc creates a smaller binary

Not so much. When I run this shell script:

Code:

#!/bin/bash

cat > using_global.c <<EOD
char x[1024*1024];

int main(void)
{
  x[0]=5;
  x[1024*1024-1]=7;

  return 0;
}
EOD
cat > using_local.c <<EOD
int main(void)
{
  char x[1024*1024];

  x[0]=5;
  x[1024*1024-1]=7;

  return 0;
}
EOD
cat > using_malloc.c <<EOD
#include <stdlib.h>

int main(void)
{
  char *x;

  x=malloc(1024*1024);

  x[0]=5;
  x[1024*1024-1]=7;

  return 0;
}
EOD
gcc -Wall using_global.c -o using_global
gcc -Wall using_local.c  -o using_local
gcc -Wall using_malloc.c -o using_malloc
ls -l using_global using_local using_malloc

I get this output:

Code:

-rwx------ 1 wally wally 6143 2009-02-11 16:52 using_global
-rwx------ 1 wally wally 6140 2009-02-11 16:52 using_local
-rwx------ 1 wally wally 6239 2009-02-11 16:52 using_malloc

irey · 02-12-2009, 03:03 AM

At most 60 structs? each of them up to 256 chars? That's 15KB. If this much memory is a problem I guess you're designing your program to run in an embedded system, right?

If it's an embedded system with so little memory then I imagine there won't be any operating system and your situation would be different. If it is a PC then you don't have to worry, your process will already have much more then 15KB allocated when it starts running.

Quote:

Originally Posted by johnsfine

The code will be different and one might be faster than the other, and it seems more likely that this performance difference would matter rather than the malloc overhead mattering.

I don't think so. Access to an array element in both cases will be a base address+offset calculation. When translated to asm a pointer access will only add a load instruction before the calculation.

ErV · 02-12-2009, 04:19 AM

Quote:

Originally Posted by CoderMan

Is using dynamic memory allocation with malloc (in C) significantly slower than regular assignments?

Define "slow".
Memory allocation may or may not be program bottleneck - it depends on your program. malloc can be a bottleneck if it is called few million times per second. If you are trying to make your program run faster, then don't waste your time by trying to optimize randomly picked portion of program. Instead, use program profilers to find slowest portion of code and optimize it.

Example you provided is trivial, malloc isn't program bottleneck and you are wasting your time right now. In your example malloc is called once per program to allocate ridiculously small block of memory. You won't get any improvement in terms of speed by optimizing that.

To get problems you will need to allocate/release memory at least few dozen million times per second.