Performance of memset()

Your best bet is probably to profile some test cases. If you are on multiple platforms/compilers, you should do tests on each. Some platforms (like the 360/PS3), have alternate functions you can use to do the same thing depending on alignment, etc. It can also depend on the value you are setting - some runtime memset implementations make 0 faster for example.

Obviously size is very small (ie 1), the loop will probably be faster than than a function call. It may also depend on the code around it - the optimizer may be able to do smarter things if there isn't a function call there.

I'd be willing to be that if size is less than 8-16, the loop would be faster. But test it! ;)

Quote:

Where can I find such information about memset() and other functions.. like malloc(), the new operator... etc. Thanks in advance. P.S: I'm using VC++ 2005 EE, in case it matters.

It matters. memset and malloc have nothing to do in C++.

There's std::fill and new to handle such tasks. Those do a few more useful things as well.

Other than that, standard library implementation should provide you with all that you want to know. While some things are standardized, the implementations will vary, especially when it comes to finer points, such as alignments and other optimizations.

Quote:

DWORD-aligned

DWORD is Windows API construct and doesn't apply to C++.

Quote:

Does it perform faster

Standard library operations are adequately optimized. If they're suitable for your task, try them with profiler.

Quote:

Which is faster, leaving "array=0;"

The fastest operation is one not performed. Can you re-organize your algorithm in such a way that you do not need to clear the array in the first place?

Otherwise, memset should outperform the for loop in any decent standard library implementation, except if compiler were so good that it would reorganize the foor loop to take all pecularities into consideration.

In general, you should find little need to poke around such details in modern compilers, since the quality of standard library tends to be quite high. In addition, relying on compiler-specific behaviour is generally a bad practices, especially since all the issues that you were asking about can be addressed through mechanisms provided for you by the standard library (allocators, for example to ensure alignment).

Quote:

Original post by BrianL Obviously size is very small (ie 1), the loop will probably be faster than than a function call...

Who said size was 1? Actually, in the case of the algorithm I'm implementing, it's the number of edges in a mesh... so it can very well be thousands per frame (multiple meshes).

Quote:

The fastest operation is one not performed. Can you re-organize your algorithm in such a way that you do not need to clear the array in the first place?

I understand that... but that's not the point actually. I asked because I wanted to learn more about memset().

Quote:

DWORD is Windows API construct and doesn't apply to C++.

Fair enough... but I meant "double word". Alignment to word boundaries and multiples of a word is not a Windows only thing, so it's not all that irrelevant.

Quote:

Other than that, standard library implementation should provide you with all that you want to know.

I don't understand! Where should I look? The docs that came with VC++ say nothing about the performance of memset()... just how to use it.

Quote:

In general, you should find little need to poke around such details in modern compilers, since the quality of standard library tends to be quite high.

I disagree. Knowledge about the implications of using or not using a certain function help you better design your algorithms and implement your solutions. I'm not saying one should know exactly how everything is implemented internally... but general info about what's involved should always be useful.

Quote:

I don't understand! Where should I look? The docs that came with VC++ say nothing about the performance of memset()... just how to use it.

Yes, because implementation may change with every new version.

Anyway... VC_Directory/crt/src.

If memory serves correctly, Visual Studio 2003's memset handles the first and last few bytes separately, if necessary, so that it can process the majority of a large buffer in 32-bit-aligned steps. The same goes for memcpy and memmove. Presumably, VC++2005 would use a similar implementation for a 32-bit target.

Anyway, I doubt there's a significant difference in your two examples. If size is small, then the overhead of preparing two loops would make the separate memset the slower option. Conversely, if size is huge (and I mean huge) then the memset will do a quicker job of clearing the buffer. In any case, it's a moot point. This kind of micro-optimisation is not conducive to productive work. Unless you are carrying out a study into processor micro-performance (in which case you should really be using unoptimised assembly), I suggest you spend your time macro-optimising [smile].

Admiral

I would say i = 0; for cache reasons.

Also, you may have the option of using an SSE instruction to fill a large array quicker than memset(). [In general the implementation of memset() will be pretty "dumb" and just use regular old instructions] I don't know about x86 but the Altivec instructions for PowerPC chips let you do stuff like that, and it can be significantly faster [like 10x faster].

Quote:

While I know that I can just write a simple test app and compare the performance, there is more that I would like to know about memset() and similar functions. For example, what's the relationship between the performance of memset and the size of the buffer? Does it perform faster if the buffer is DWORD-aligned? Has a size which is a multiple of 16? Where can I find such information about memset() and other functions.. like malloc(), the new operator... etc. Thanks in advance. P.S: I'm using VC++ 2005 EE, in case it matters.

In your case Vs memset, memset wins. The performance depends on how well the programmer understands the underlying processor architecture (which the writers of the C library did not, because no, it's not great on performance).

Alignment is critically important, but, even if said memory block is unaligned memset() "should" align it.

A few notes about performance in regards to memory:

#1: Processor's enjoy serial access to memory.
#2: Read's and Write's should be seperated in individual groups.
#3: A processor will never cache over page boundaries.
#4: Data locality is a critical performance factor, everywhere.
#5: If you've got a large structure, try to size it to fit into either the whole L1 cache, or half of the L2 cache.
#6: Keep in mind, data is prefetched (following linear address's are cached regardless if you're going to reference them or not)

Many more, but probably a bit out of scope: Anything else, just ask.

Quote:

Also, you may have the option of using an SSE instruction to fill a large array quicker than memset(). [In general the implementation of memset() will be pretty "dumb" and just use regular old instructions] I don't know about x86 but the Altivec instructions for PowerPC chips let you do stuff like that, and it can be significantly faster [like 10x faster].

Plainly incorrect. SSE is not a general-purpose (ex)instruction set, it's a domain-specific (mainly multimedia) and not to mention the fact that it's on the x87, not the MPU.

Quote:

In your case Vs memset, memset wins. The performance depends on how well the programmer understands the underlying processor architecture (which the writers of the C library did not, because no, it's not great on performance).

Let's see if I got this straight... is the visual studio implementation of memset() and other C runtime library functions generally optimized? Should I assume that it will use whatever hardware features available to do things faster? "Which the writers of the C library did not".. by that you're referring to which implementation? Which writers? Also, are such functions statically linked or dynamically linked? Sorry for the noob questions.

Finally, allow me to complement your list of "optimization guidelines" by providing this very fine document on optimizing C++ code. Thanks.

Quote:

Let's see if I got this straight... is the visual studio implementation of memset() and other C runtime library functions generally optimized? Should I assume that it will use whatever hardware features available to do things faster? "Which the writers of the C library did not".. by that you're referring to which implementation? Which writers? Also, are such functions statically linked or dynamically linked? Sorry for the noob questions. Finally, allow me to complement your list of "optimization guidelines" by providing this very fine document on optimizing C++ code. Thanks.

They are just written to do their job (meaning, there was no serious thought put into optimization.)

It's not so much hardware features, it's more hardware architecture. Anyone can write assembly, but very few know how things actually work and what the processor will actually think of your code.

Statically linking is preferable over dynamic linking in all cases for performance, but, it is not necessary since it makes upgrading much harder.

For example, another function (VS) "itoa" performs 50% slower than my equivilent. As quoted from a test I did when someone else was trying to also re-write it (Mine is IntToStr)

Quote:

Over 10,000,000 iterations: itoa -- 10439ms (10 seconds) __itoa -- 11260ms (11 seconds) IntToStr -- 5610ms (5 seconds) Over 100,000,000 iterations: itoa -- 108469ms (108 seconds) __itoa -- 117790ms (117 seconds) IntToStr -- 48700ms (48 seconds)

Quote:

Original post by Malone Also, you may have the option of using an SSE instruction to fill a large array quicker than memset(). [In general the implementation of memset() will be pretty "dumb" and just use regular old instructions] I don't know about x86 but the Altivec instructions for PowerPC chips let you do stuff like that, and it can be significantly faster [like 10x faster].

When compiling with VS8.0, intrinsics enabled and /arch:SSE2 the compiler will use an unrolled loop of movdqa's after it takes care of any starting and ending bytes which aren't aligned.

Quote:

Original post by MattJayA few notes about performance in regards to memory: #1: Processor's enjoy serial access to memory. #2: Read's and Write's should be seperated in individual groups. #3: A processor will never cache over page boundaries. #4: Data locality is a critical performance factor, everywhere. #5: If you've got a large structure, try to size it to fit into either the whole L1 cache, or half of the L2 cache. #6: Keep in mind, data is prefetched (following linear address's are cached regardless if you're going to reference them or not) Many more, but probably a bit out of scope: Anything else, just ask.

When comparing loop vs. memset for generic case, standard library should win.

But by factoring in the above criteria into application design itself, then it's possible to reasonable improve performance of certain operations.

memcpy, memset, etc. need to be generic, including all the security and alignment checks. If such guarantees can be provided by application itself (allocating certain data on appropriate boundary, possibly making fixed-size buffers, memory pool or similar), then you can skip many of the tests and conditionals.

Quote:

Let's see if I got this straight... is the visual studio implementation of memset() and other C runtime library functions generally optimized?

It's optimized for the generic case - meaning you can give it any input you want.

If you want to squeeze a bit more extra performance, you can limit yourself to a subset of possible inputs (guaranteed alignment and length, for example), and use this knowledge to gain some extra performance.

Quote:

They are just written to do their job (meaning, there was no serious thought put into optimization.) It's not so much hardware features, it's more hardware architecture. Anyone can write assembly, but very few know how things actually work and what the processor will actually think of your code.

So shouldn't there be multiple implementations of the C runtime library for different architectures such that one can link to the version corresponding to his target HW? I know that intel once released an optimized set of math functions (sin, cos.. etc) that performed much better than standard versions, I believe it was called "Approximate Math (AM) Library", or AMaths for short [EDIT]: Actually, there are four such libraries[END EDIT]. Are there any more 3rd party implementations targeting a specific platform that one should consider using instead of/alongside the one that comes with whatever compiler he is using? Thank you in advance. GameDev rocks!

[Edited by - hikikomori-san on November 18, 2007 1:03:38 PM]

Your for loop should never be faster, there is no point in trying to avoid the array = 0; write, since the array read will guarantee that the cacheline is in the l1 cache (making the write trivial). If your array was already in cache, then you would be instruction bound and the for loop would be strictly slower - if it wasn't already in cache (e.g., for large arrays), you will be data bound and the performance would be pretty much the same.

I am assuming that the memset implementation a) is inlined and b) aligns to 32byte boundaries and that c) your compiler and the memset isn't optimizing beyond the standard "x86 like" instruction set.

Your compiler or memset implementation could perform multiple writes in a single instruction (as mentioned by Malone and Julian90), if the target instruction set supports it. This will reduce the instruction overhead, and will buy you a good performance gain when the array in cache, but nothing when the array is out of L2.

In order to maximize (approx. double) memset performance in the non-cached (large array) case, you want to use non-temporal stores to write out your data, so that you don't have to both read and write the array. This is available in most extended instruction sets. I don't know of any C/C++ compiler that actually generates this code - but you can code it yourself.

Quote:

Your compiler or memset implementation could perform multiple writes in a single instruction (as mentioned by Malone and Julian90), if the target instruction set supports it. This will reduce the instruction overhead, and will buy you a good performance gain when the array in cache, but nothing when the array is out of L2.

The only instructions that actually perform multiple writes are of the SIM set, or instructions like movsx, which are not actually atomically writing more than one word, but are simply being repeated (aka; rep).

I'd say you're thinking of the fact a processor can have multiple writes (~32) in 'flight' at any given time, or maybe write-combining.

Quote:

Original post by MattJay Quote: Also, you may have the option of using an SSE instruction to fill a large array quicker than memset(). [In general the implementation of memset() will be pretty "dumb" and just use regular old instructions] I don't know about x86 but the Altivec instructions for PowerPC chips let you do stuff like that, and it can be significantly faster [like 10x faster]. Plainly incorrect. SSE is not a general-purpose (ex)instruction set, it's a domain-specific (mainly multimedia) and not to mention the fact that it's on the x87, not the MPU.

What about that statement do you think is 'plainly incorrect'? It is entirely true that the OP 'may have the option of using an SSE instruction to fill a large array quicker than memset()' (although as has already been pointed out, with appropriate compiler optimization flags VC8 will already do this for you). It's also true that the function call version of memset (what you get when you don't have intrinsic functions enabled) will not use SSE instructions with VC8 since the VC standard library does not assume SSE is available. Further, it's also true that Altivec/VMX has instructions that are significantly faster for memset than non VMX PowerPC code. The Xbox 360 has further cache control extensions that allow for even faster memsets when certain restrictions apply.

SSE is not 'on the x87'. On modern processors x87 only meaningfully refers to the legacy floating point instruction set on x86 family processors - it's not a separate processor or even a clearly defined separate execution unit any more. It's also worth noting that x87 is deprecated for 64 bit code and using the scalar SSE instructions for floating point arithmetic is the recommended replacement.

The fact is that the fastest way to memset large chunks of memory on a modern x86 processor is to use SSE instructions. Using VMX is the fastest way on the Xbox 360 and PS3 (and on other platforms that use PowerPC).

Quote:

Original post by MattJay The only instructions that actually perform multiple writes are of the SIM set, or instructions like movsx, which are not actually atomically writing more than one word, but are simply being repeated (aka; rep). I'd say you're thinking of the fact a processor can have multiple writes (~32) in 'flight' at any given time, or maybe write-combining.

I am talking about the SSE or 3dnow! mov instructions. For arrays that are currently in cache, performance is about issuing enough writes to saturate l1 or l2 bandwidth. This isn't directly related to outstanding writes or WC.

Quote:

What about that statement do you think is 'plainly incorrect'? It is entirely true that the OP 'may have the option of using an SSE instruction to fill a large array quicker than memset()' (although as has already been pointed out, with appropriate compiler optimization flags VC8 will already do this for you). It's also true that the function call version of memset (what you get when you don't have intrinsic functions enabled) will not use SSE instructions with VC8 since the VC standard library does not assume SSE is available. Further, it's also true that Altivec/VMX has instructions that are significantly faster for memset than non VMX PowerPC code. The Xbox 360 has further cache control extensions that allow for even faster memsets when certain restrictions apply. SSE is not 'on the x87'. On modern processors x87 only meaningfully refers to the legacy floating point instruction set on x86 family processors - it's not a separate processor or even a clearly defined separate execution unit any more. It's also worth noting that x87 is deprecated for 64 bit code and using the scalar SSE instructions for floating point arithmetic is the recommended replacement. The fact is that the fastest way to memset large chunks of memory on a modern x86 processor is to use SSE instructions. Using VMX is the fastest way on the Xbox 360 and PS3 (and on other platforms that use PowerPC).

You mean what I *know* is incorrect. SSE is _not_ a general purpose instruction set, as I've already stated, it is not intended for use with system memory
movement, nor is it even designed for it. I use "x87" loosely, as yes, it's no longer a seperate chip yet the SSE instructions operate directly on the FPU stack (SSE registers are aliases for the FPU stack), which is not at all meant to be for memory movement.

Simple way to end this: Find me an instruction for direct system memory movement within SSE that does not involve the FPU stack.

Quote:

I am talking about the SSE or 3dnow! mov instructions. For arrays that are currently in cache, performance is about issuing enough writes to saturate l1 or l2 bandwidth. This isn't directly related to outstanding writes or WC.

There are no system memory movement instructions in SSE, they are not designed for memory movement, they are designed for operating on >word amounts of data (hence, Single Instruction Multiple Data), not memory block movement within the system.