Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Going faster than memcpy

squadrick.dev

Post reply on HN
Print view View original

31–40 of 83 posts

Re: Going faster than memcpy

#31

Post by bob1029 »

adwn wrote: post #17

> The operation of copying data is super easy to parallelize across multiple threads. […] This will make the copy super-fast especially if the CPU has a large core count. I seriously doubt that. Unless you have a NUMA system, a single core in a desktop CPU can easily saturate the bandwidth of the system RAM controller. If you can avoid going through main memory – e.g., when copying between the L2 caches of different…

> a single core in a desktop CPU can easily saturate the bandwidth of the system RAM controller.

Modern x86 machines offer far more memory bandwidth than what a single core can consume. The entire architecture is designed on purpose to ensure this.

The interesting thing to note is that this has not always been the case. The 2010s is when the transition occurred.

Re: Going faster than memcpy

#32

Post by orlp »

Sesse__ wrote: post #22

There's an error here: “NT instructions are used when there is an overlap between destination and source since destination may be in cache when source is loaded.” Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon, so it shouldn't push out other things…

> Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon

I disagree with this statement (taken at face value, I don't necessarily agree with the wording in the OP either). Non-temporal instructions are unordered with respect to normal memory operations, so without a _mm_sfence() after doing your non-temporal writes you're going to get nasty hardware UB.

Re: Going faster than memcpy

#33

Post by m0th87 »

Sesse__ wrote: post #22

There's an error here: “NT instructions are used when there is an overlap between destination and source since destination may be in cache when source is loaded.” Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon, so it shouldn't push out other things…

I work on optimizations like this at work, and yes this is largely correct. But do you have a source on this?

> or (more likely) go into just some special small subsection of it reserved for non-temporal writes only.

I hadn’t heard of this before. It looks like older x86 CPUs may have had a dedicated cache.

Re: Going faster than memcpy

#34

Post by davrosthedalek »

> Since the loop copies data pointer by pointer, it can handle the case of overlapping data.

I don't think this loop does the right thing if destination points somewhere into source. It will start overwriting the non-copied parts of source.

Re: Going faster than memcpy

#35

Post by m0th87 »

orlp wrote: post #32
Sesse__ wrote: post #22

There's an error here: “NT instructions are used when there is an overlap between destination and source since destination may be in cache when source is loaded.” Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon, so it shouldn't push out other things…

> Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon I disagree with this statement (taken at face value, I don't necessarily agree with the wording in the OP either). Non-temporal instructions are unordered with respect to normal memory operations, so…

I had interpreted GP to mean that you don’t slap on NTs for correctness reasons, rather you do it for performance reasons.

Re: Going faster than memcpy

#36

Post by orlp »

m0th87 wrote: post #35
orlp wrote: post #32

Earlier quoted context omitted.

> Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon I disagree with this statement (taken at face value, I don't necessarily agree with the wording in the OP either). Non-temporal instructions are unordered with respect to normal memory operations, so…

I had interpreted GP to mean that you don’t slap on NTs for correctness reasons, rather you do it for performance reasons.

That is something I can agree with, but I can't in good faith just let "it's just a hint, they don't have anything to do with correctness" stand unchallenged.

Re: Going faster than memcpy

#37

Post by Sesse__ »

orlp wrote: post #32
Sesse__ wrote: post #22

There's an error here: “NT instructions are used when there is an overlap between destination and source since destination may be in cache when source is loaded.” Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon, so it shouldn't push out other things…

> Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon I disagree with this statement (taken at face value, I don't necessarily agree with the wording in the OP either). Non-temporal instructions are unordered with respect to normal memory operations, so…

You mean if you access it from a different core? I believe that within the same core, you still have the normal ordering, but indeed, non-temporal writes don't have an implicit write fence after them like x86 stores normally do.

In any case, if so they are potentially _less_ correct; they never help you.

Re: Going faster than memcpy

#38

Post by Sesse__ »

m0th87 wrote: post #33
Sesse__ wrote: post #22

There's an error here: “NT instructions are used when there is an overlap between destination and source since destination may be in cache when source is loaded.” Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon, so it shouldn't push out other things…

I work on optimizations like this at work, and yes this is largely correct. But do you have a source on this? > or (more likely) go into just some special small subsection of it reserved for non-temporal writes only. I hadn’t heard of this before. It looks like older x86 CPUs may have had a dedicated cache.

A source on what? The Intel optimization manuals explain what MOVNTQ is for. I don't think they explain in detail how it is implemented behind-the-scenes.

See e.g. https://cdrdv2.intel.com/v1/dl/getContent/671200 chapter 13.5.5:

“The non-temporal move instructions (MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, and MOVNTPD) allow data to be moved from the processor’s registers directly into system memory without being also written into the L1, L2, and/or L3 caches. These instructions can be used to prevent cache pollution when operating on data that is going to be modified only once before being stored back into system memory. These instructions operate on data in the general-purpose, MMX, and XMM registers.”

I believe that non-temporal moves basically work similar to memory marked as write-combining; which is explained in 13.1.1: “Writes to the WC memory type are not cached in the typical sense of the word cached. They are retained in an internal write combining buffer (WC buffer) that is separate from the internal L1, L2, and L3 caches and the store buffer. The WC buffer is not snooped and thus does not provide data coherency. Buffering of writes to WC memory is done to allow software a small window of time to supply more modified data to the WC buffer while remaining as non-intrusive to software as possible. The buffering of writes to WC memory also causes data to be collapsed; that is, multiple writes to the same memory location will leave the last data written in the location and the other writes will be lost.”

In the old days (Pentium Pro and the likes), I think there was basically a 4- or 8-way associative cache, and non-temporal loads/stores would go to only one of the sets, so you could only waste 1/4 (or 1/8) on your cache on it at worst.

Re: Going faster than memcpy

#39

Post by Tuna-Fish »

m0th87 wrote: post #33
Sesse__ wrote: post #22

There's an error here: “NT instructions are used when there is an overlap between destination and source since destination may be in cache when source is loaded.” Non-temporal instructions don't have anything to do with correctness. They are for cache management; a non-temporal write is a hint to the cache system that you don't expect to read this data (well, address) back soon, so it shouldn't push out other things…

I work on optimizations like this at work, and yes this is largely correct. But do you have a source on this? > or (more likely) go into just some special small subsection of it reserved for non-temporal writes only. I hadn’t heard of this before. It looks like older x86 CPUs may have had a dedicated cache.

IIRC they used the write-combining buffer, which was also a cache.

A common trick is to cache it but put it directly in the last or second-to-last bin in your pseudo-LRU order, so it's in cache like normal but gets evicted quickly when you need to cache a new line in the same set. Other solutions can lead to complicated situations when the user was wrong and the line gets immediately reused by normal instructions, this way it's just in cache like normal and gets promoted to least recently used if you do that.

Re: Going faster than memcpy

#40

Post by makach »

brucehoult wrote: post #6

Conclusion Stick to `std::memcpy`. It delivers great performance while also adapting to the hardware architecture, and makes no assumptions about the memory alignment. ---- So that's five minutes I'll never get back. I'd make an exception for RISC-V machines with "RVV" vectors, where vectorised `memcpy` hasn't yet made it into the standard library and a simple ... 0000000000000000 : 0: 86aa mv a3,a0 0000000000000002…

You pre-stole my comment, I was about to make the exact same post :-D

Although the blog post is about going faster and him showing alternative algorithms, conclusion remains for safety which makes perfect sense. However, he did show us a few strategies which is useful. The five minutes I spent, will never be returned to me but at least I learned something interesting...

Post reply on HN