4 ms·

A long time ago, as I was working with the Nintendo SDK for the DS console I wondered if the provided memcpy implementation was optimal. Turned out it was quit

A long time ago, as I was working with the Nintendo SDK for the DS console I wondered if the provided memcpy implementation was optimal. Turned out it was quite slow. I replaced it with an Intel hand optimized version made for the StrongARM, and replaced the prefetch opcode by a simple load because this opcode was not supported by the arch of the CPU of this console. 50% faster, this is quite significant for such a low-level, already optimized routine, used extensively in many stages of a game engine. I think that we should never assume that standard implementations are optimal, trust but verify.

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. :)
gavinray 5y ago
This is brilliant and really interesting/neat, thanks for posting.

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. :)

gavinray 5y ago

This is brilliant and really interesting/neat, thanks for posting.