4 ms·

Modern compilers have quite a deep understanding of memcpy, and they will recognize the pattern and put in optimal assembly (on x86, probably "rep movsb" or wha

by OskarS 5y ago

Modern compilers have quite a deep understanding of memcpy, and they will recognize the pattern and put in optimal assembly (on x86, probably "rep movsb" or whatever), even if you don't literally call memcpy. This is why the GCC implmentation of memcpy is, like, trivial: [1]. The compiler will recognize that this is a memcpy and sub the better implementation. I wonder though: it seems to me that memory bandwidth should far and away be the limiting factor for a memcpy, so I would think even a straight-forward translation of the "trivial" implementation wouldn't be that far off from an "optimal" one. I guess memory prefetching would make a difference, but would minimizing the number of loads/stores (or unrolling the loop) really matter that much? [1]: https://github.com/gcc-mirror/gcc/blob/master/libgcc/memcpy.c https://github.com/gcc-mirror/gcc/blob/master/libgcc/memcpy....

saagarjha 5y ago
> on x86, probably "rep movsb" or whatever Only on recent x86, and with a long list of caveats. Look up discussion about erms online. > I wonder though: it seems to me that memory bandwidth should far and away be the limiting factor for a memcpy, so I would think even a straight-forward translation of the "trivial" implementation wouldn't be that far off from an "optimal" one. I guess memory prefetching would make a difference, but would minimizing the number of loads/stores (or unrolling the loop) really matter that much? Memory bandwidth is often the limiting factor, but not always. But your simple byte-by-byte loop is not going to get anywhere near saturating that; you'll need to unroll and use vector instructions, which might dispatch slower but copy several orders of magnitude more data.
stephc_int13 5y ago
From my experience, good prefetching and pre-alignment changes a lot of things/ Compiler optimized memcpy are good for small copies that will be inlined, but copying big chunks is an other story and I've seen non-marginal differences depending on implementation. The most difficult problem is that each implementation is usually tuned for a specific CPU and might be sub-optimal with a different brand or revision...
stephc_int13 5y ago
If you think that a specific routine or algorithm is memory bound, you should always do a quick benchmark to check this assumption. In practice everything is memory bound because of course the CPU is faster than memory, but you'd be surprised by how difficult it can be to reach the full CPU capacity. "Memory bound" or "Network bound" are way too frequently used as poor excuses by lazy coders.
josefx 5y ago
> on x86, probably "rep movsb" or whatever) Sadly I don't have a link, but as far as I remember rep movsb was always hilariously slow. So memcpy implementations tried to optimize copies using half a page of vector instructions with size and alignment tests, which of course killed the CPUs instruction cache.
- benttoothpaste 5y ago
  Always hilariously slow? That must have been before Ivy Bridge.
- sedatk 5y ago
  Yes, a compiler would at least add a combo of rep movsq + rep movsd + rep movsw to the mix before finishing the final remainder with rep movsb. Vector instructions might help tremendously too.
- bjourne 5y ago
  Hilariously slow before Intel engineers decided to optimize the shit out of the construction. :)

by OskarS 5y ago

saagarjha 5y ago

> on x86, probably "rep movsb" or whatever Only on recent x86, and with a long list of caveats. Look up discussion about erms online. > I wonder though: it seems to me that memory bandwidth should far and away be the limiting factor for a memcpy, so I would think even a straight-forward translation of the "trivial" implementation wouldn't be that far off from an "optimal" one. I guess memory prefetching would make a difference, but would minimizing the number of loads/stores (or unrolling the loop) really matter that much? Memory bandwidth is often the limiting factor, but not always. But your simple byte-by-byte loop is not going to get anywhere near saturating that; you'll need to unroll and use vector instructions, which might dispatch slower but copy several orders of magnitude more data.

stephc_int13 5y ago

From my experience, good prefetching and pre-alignment changes a lot of things/ Compiler optimized memcpy are good for small copies that will be inlined, but copying big chunks is an other story and I've seen non-marginal differences depending on implementation. The most difficult problem is that each implementation is usually tuned for a specific CPU and might be sub-optimal with a different brand or revision...

stephc_int13 5y ago

If you think that a specific routine or algorithm is memory bound, you should always do a quick benchmark to check this assumption. In practice everything is memory bound because of course the CPU is faster than memory, but you'd be surprised by how difficult it can be to reach the full CPU capacity. "Memory bound" or "Network bound" are way too frequently used as poor excuses by lazy coders.

josefx 5y ago

> on x86, probably "rep movsb" or whatever) Sadly I don't have a link, but as far as I remember rep movsb was always hilariously slow. So memcpy implementations tried to optimize copies using half a page of vector instructions with size and alignment tests, which of course killed the CPUs instruction cache.

benttoothpaste 5y ago
Always hilariously slow? That must have been before Ivy Bridge.
sedatk 5y ago
Yes, a compiler would at least add a combo of rep movsq + rep movsd + rep movsw to the mix before finishing the final remainder with rep movsb. Vector instructions might help tremendously too.
bjourne 5y ago
Hilariously slow before Intel engineers decided to optimize the shit out of the construction. :)