Complexity of the memset function in C

Question

I was discussing with some friends a piece of code, and we discussed about using memset function in C, which is the order in Big-O notation for this function if we initialize an array of size N?

Answer 1

You asked about complexity, but you probably intended to ask about performance.

Complexity, referred to with the notation O(n), is a concept relating to how the number of operations in an algorithm is compelled to grow as the problem size grows. O(n) means that at most some number of steps proportional to the problem size must be performed. It does not say what that proportion is. memset is O(n). O(n²) means at most some number of steps proportional to n² must be performed. memset is better than just O(n²) because setting 2n bytes takes only twice as much work as n bytes, not four times as much work, in general.

You are likely more interested in the performance of memset, because the library version of memset performs much more quickly than a simple C version you might write.

The library version performs much more quickly because it uses specialized instructions. Most common modern processors have instructions that allow them to write 16 bytes to memory in one instruction. The library implementors write critical functions like memset in assembly language or something close to it, so they have access to all these instructions.

When you write in C, it is difficult for the compiler to take advantage of these instructions. For example, the pointer to the memory you are setting might not be aligned to a multiple of 16 bytes. The memset authors will write code that tests the pointer and branches to different code for each case, with the goal of setting some bytes individually and then having a pointer that is aligned, so they can use the fast instructions that store 16-bytes at a time. This is only one of a number of complications that the library implementors deal with when writing routines like memset.

Because of those complications, the compiler cannot easily take your C implementation of memset and turn it into the fast code that experts write. When the compiler sees, in C code, a loop that writes one byte at a time, it typically generates assembly language that writes one byte at a time. Optimizers are getting smarter, but the complications limit how much they are allowed to do and how much they can do without generating a lot of code to handle cases that might rarely occur.