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

71–80 of 83 posts

Re: Going faster than memcpy

#71

Post by fc417fc802 »

AlotOfReading wrote: post #66
t00 wrote: post #65

Earlier quoted context omitted.

That is a really good advice, copying data everywhere makes only sense if the data will be mutated. I only wonder why, why C-style strings were invented with 0 termination instead of varint prefix, this would have saved so much copying and so many bugs knowing the string length upfront.

Pascal strings have the issue that you need to agree on an int size to cross an ABI boundary, unless you want to limit all strings to 255 characters and what the prefix means is ambiguous if you have variable length characters (e.g. Unicode). These were severe enough that Pascal derivatives all added null terminated strings. Took a bit for languages to develop the distinction between string length in characters and b…

If we're specifying the size of a buffer we obviously work in bytes as opposed to some arbitrary larger unit.

Agreed that passing between otherwise incompatible ABIs is likely what drove the adoption of null termination. The only other option that comes to mind is a bigint implementation, but that would be at odds with the rest of the language in most cases.

Re: Going faster than memcpy

#72

Post by teo_zero »

t00 wrote: post #65
commandlinefan wrote: post #64

I've gotten a lot of gains in this area in the past by just - not memcpy'ing. A good percentage of the time, somebody assumes that they need to copy something somewhere when in fact, the original never gets referenced. I can often get away with reading a buffer off the wire, inserting null terminators to turn bits of the buffer into proper C-style strings and just using them in-place.

That is a really good advice, copying data everywhere makes only sense if the data will be mutated. I only wonder why, why C-style strings were invented with 0 termination instead of varint prefix, this would have saved so much copying and so many bugs knowing the string length upfront.

I'm not here to defend zero- terminated strings, but I register that prefixed strings would be equally bad for the goal of OP, or even worse since you would need to inject int prefixes instead of zero bytes.

Re: Going faster than memcpy

#73

Post by AlotOfReading »

fc417fc802 wrote: post #71
AlotOfReading wrote: post #66

Earlier quoted context omitted.

Pascal strings have the issue that you need to agree on an int size to cross an ABI boundary, unless you want to limit all strings to 255 characters and what the prefix means is ambiguous if you have variable length characters (e.g. Unicode). These were severe enough that Pascal derivatives all added null terminated strings. Took a bit for languages to develop the distinction between string length in characters and b…

If we're specifying the size of a buffer we obviously work in bytes as opposed to some arbitrary larger unit. Agreed that passing between otherwise incompatible ABIs is likely what drove the adoption of null termination. The only other option that comes to mind is a bigint implementation, but that would be at odds with the rest of the language in most cases.

It wasn't obvious to everyone at the time that string size in bytes and characters were often different. It was very common to find code that would treat the byte size as the character count for things like indexing and vice versa.

Re: Going faster than memcpy

#74

Post by EGreg »

CyberDildonics wrote: post #68
EGreg wrote: post #63

Earlier quoted context omitted.

From my college days, which were quite long ago. And working with Win32 "BitBlt" requests to the OS, etc. And also, it would just make sense. If copying entire blocks or memory pages, such as "BitBlt", is one command, why would I need CPU cycles to actually do it? It would seem like the lowest hanging fruit to automate in SDRAM It just seems like the easiest example of SIMD

These are contradictory things. SIMD instructions are still regular instructions, not some concurrent system for copying. When you say command, maybe you meant a windows OS function that was similar to memcpy. An OS function and individual CPU instructions are two different thing. There is something called DMA, but I don't know how much that is used for memory to memory copies.

Well CPUs already transparently handle memory paging so why not copying?

https://en.wikipedia.org/wiki/Memory_paging

Re: Going faster than memcpy

#75

Post by CyberDildonics »

EGreg wrote: post #74
CyberDildonics wrote: post #68

Earlier quoted context omitted.

These are contradictory things. SIMD instructions are still regular instructions, not some concurrent system for copying. When you say command, maybe you meant a windows OS function that was similar to memcpy. An OS function and individual CPU instructions are two different thing. There is something called DMA, but I don't know how much that is used for memory to memory copies.

Well CPUs already transparently handle memory paging so why not copying? https://en.wikipedia.org/wiki/Memory_paging

I'm not making a case for anything I'm just explaining what exists. If copying were going to be done in bulk it would have to be done asynchronously to some extent, though CPUs already work like that on a small scale due to instruction reordering.

Now it might be less necessary because CPUs are so fast with contiguous data memory that copying to other parts of memory are less of a bottleneck.

Re: Going faster than memcpy

#76

Post by kachapopopow »

viraptor wrote: post #18
kachapopopow wrote: post #5

Earlier quoted context omitted.

Yah, these benchmarks are irrelevant since the CPU executes instructions out of order. Majority of the time the cpu will continue executing assembly while a copy operation is ongoing.

The full reorder buffer is still going to be only 200-500 instructions. The actual benchmark is not linked, but it would take only a hundred or so messages to largely ignore the reordering. On the other hand, when you use the library, the write needs to actually finish in the shared memory before you notify the other process. So unless the benchmark was tiny for some reason, why would this be irrelevant?

Because unless your application is 90% memcpy, it's simply not relevant in a real world senario since it doesn't matter if it takes 2 cycles or (up to 50 in some cases) - the performance will be identical.

Re: Going faster than memcpy

#77

Post by viraptor »

kachapopopow wrote: post #76
viraptor wrote: post #18

Earlier quoted context omitted.

The full reorder buffer is still going to be only 200-500 instructions. The actual benchmark is not linked, but it would take only a hundred or so messages to largely ignore the reordering. On the other hand, when you use the library, the write needs to actually finish in the shared memory before you notify the other process. So unless the benchmark was tiny for some reason, why would this be irrelevant?

Because unless your application is 90% memcpy, it's simply not relevant in a real world senario since it doesn't matter if it takes 2 cycles or (up to 50 in some cases) - the performance will be identical.

This is a library - it doesn't know whether the app is sending one message or 10k per second. But ideally it would be as good as possible in the second case.

Also, for some uses the small time usages add up. If you're doing real time rendering or simulations, you get a small per-frame time budget. Either you hit it or not, so even tiny improvements may matter.

Re: Going faster than memcpy

#78

Post by kachapopopow »

viraptor wrote: post #77
kachapopopow wrote: post #76

Earlier quoted context omitted.

Because unless your application is 90% memcpy, it's simply not relevant in a real world senario since it doesn't matter if it takes 2 cycles or (up to 50 in some cases) - the performance will be identical.

This is a library - it doesn't know whether the app is sending one message or 10k per second. But ideally it would be as good as possible in the second case. Also, for some uses the small time usages add up. If you're doing real time rendering or simulations, you get a small per-frame time budget. Either you hit it or not, so even tiny improvements may matter.

The conclusion was is to not bother and to use something purpose-specific if you do in-fact need performance. You can generate the perfect memcpy to copy any kind of data structure technically speaking and if I remember llvm has a few tricks for that.

Anyway, the original point was that benchmarks are useless since memcpy is almost never used in isolation. And you will always be able to achieve better performance when you know what the data is in advance (as show in the article).

Re: Going faster than memcpy

#79

Post by kegior »

It seems that the performance of memory copy depends on the architecture of the CPU and the careful combination of preferching iptions, register type, and instructions. This is what we found through thorough experiments and we published on a recent paper [1].

[1] https://dl.acm.org/doi/10.1145/3477113.3487264

Re: Going faster than memcpy

#80

Post by JonChesterfield »

CyberDildonics wrote: post #62
EGreg wrote: post #57

Wait, I thought memcpy would have launched some sort of built-in mechanism (parallelized or whatever) to copy in RAM. Just indicate the start and length. Why would the CPU need to keep issuing copy instructions?

I thought memcpy would have launched some sort of built-in mechanism Where did you get this impression?

I'd expect memcpy calls to turn into builtin_memcpy and then into raw loads/stores for known small N and a call into compiler-rt for unknown or large N. If it doesn't, patches to do that for your architecture are likely appreciated.
Post reply on HN