Hacker News Reader

Comment by stephc_int13 | Hacker News Reader

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.

View on HN

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

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

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

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.

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

Always hilariously slow? That must have been before Ivy Bridge.

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.

Hilariously slow before Intel engineers decided to optimize the shit out of the construction. :)

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

Reply on news.ycombinator.com