Thread: memset vs. for loop

Hey,

I was wondering if you guys could explain in detail the time-space differences between memset and a for loop. For example, consider the two pieces of code:

Code:

char arr[10];
for (int i = 0; i < 10; i++)
arr[i] = '\0';

Code:

char arr[10];
memset( arr, '\0', sizeof(arr) );

How much faster is the second version versus the first version? I know you save space since you don't need to allocate anything for i or get it's value, but how exactly does memset work? Does it go through the bytes specified and put in a 0, or does it do it more efficiently?

Thanks.

Originally Posted by Ach1lles

Hey,

I was wondering if you guys could explain in detail the time-space differences between memset and a for loop. For example, consider the two pieces of code:

Code:

char arr[10];
for (int i = 0; i < 10; i++)
arr[i] = '\0';

Code:

char arr[10];
memset( arr, '\0', sizeof(arr) );

How much faster is the second version versus the first version? I know you save space since you don't need to allocate anything for i or get it's value, but how exactly does memset work? Does it go through the bytes specified and put in a 0, or does it do it more efficiently?

Thanks.

It is very likely that memset internally uses a loop... so there's really not that much difference.

This would be only marginally more efficient than a for() loop...

Code:

void *my_memset(void *dst, int c, size_t num)
  { while( num--)
       *(dst+num) = c;
     return dst; }

But you can also do this to initize your array...

Code:

char arr[10] = {0};

So it is actually cleared automatically...

Originally Posted by laserlight

Actually, it would result in a compile error since you can neither do pointer arithmetic on nor dereference a pointer to void.

Oh crap! You're right... My bad.

Thanks for pointing that out...

Tater's right about the initializer, it's a nice, easy, clean way, and probably calls memset under the hood. He's also right about memset using a loop internally (it has to). But, in many implementations, memset may be optimized to set entire words at once, instead of individual bytes. This would be a roughly 4x increase on a 32-bit system for a sufficiently large piece of memory. memset should never be slower than your loop, so there's no speed advantage to your loop, at best it would be a tie. Add to that the fact that using memset is good "code reuse", i.e. using a well-tested library instead of reinventing the wheel, and the clear winner is memset.

Tater's my_memset has a slight problem of needing to cast dst (to a char *) before dereferencing it.

I was under the impression that memset and others were implemented in assembly for utmost speed. I realize there are "source" files for library functions but they are mostly for illustration purposes. A well established compiler would have tweaked the standard functions because compiled code is often benchmarked and their performance reflects the quality of the compiler / company. I'd be very shocked and surprised if a programmer's loop can outperform memset.

Originally Posted by nonoob

I was under the impression that memset and others were implemented in assembly for utmost speed. I realize there are "source" files for library functions but they are mostly for illustration purposes. A well established compiler would have tweaked the standard functions because compiled code is often benchmarked and their performance reflects the quality of the compiler / company. I'd be very shocked and surprised if a programmer's loop can outperform memset.

What gives you the idea that assembler code is always faster than C code?
That hasn't actually been true since the days of interpreters.

Think about what a compiler does... It tranlates C source in to object code... the same object code an Assembler creates... At that level C and ASM code is indistinguishable. If it were otherwise, the linker couldn't build the executable...

Yes there are some cases where ASM is faster than C because of human optimizations using obscure op-codes the compiler does not. But as time marches on those cases are becoming fewer and a lot further between.

Originally Posted by nonoob

I was under the impression that memset and others were implemented in assembly for utmost speed. I realize there are "source" files for library functions but they are mostly for illustration purposes. A well established compiler would have tweaked the standard functions because compiled code is often benchmarked and their performance reflects the quality of the compiler / company. I'd be very shocked and surprised if a programmer's loop can outperform memset.

On the one hand, optimized general purpose memset - one which has to deal with different behavior in caching as the size changes, has to worry about the various combinations of cache and page table alignment of source and data arrays, has to worry about which instructions are implemented on various processors (SSE, SSE2, SSE3, SSE4, AVX, etc), needs to handle prefetching without causing cache and TLB misses, and so on to get the best average performance in all cases. On the other hand, you have a simple loop to initialize 10 characters to zero written in C with no function calling overhead. Which is going to be more efficient? Probably neither in this case - performance doesn't matter for something so insignificant. But even in general it's hard to answer.

Plus in many compilers a simple loop like the one in the original example can be replaced with a few loads and stores right in line with the program - so you get the benefit of assembler code without the difficulty.