Comment by gens | Hacker News Reader

Comment by gens | Hacker News Reader

I don't want to register to download the code, so take my comment as such.

I wrote an (actually) fast memcpy() in assembly. There are more problems then just different size-s. Hardest problem is actually alignment, particularly 1 byte unaligned buffers.

A couple things (if hn doesn't autoformat): 1. SSE2 non-temporal MOV (one that doesn't go through cache) is basically required when going over ~cache_size. 2. One byte unaligned (or any odd number) to cpu alignment buffers need to have the first n bytes copied first to get to that alignment (16byte for SSE; also couple bytes at the end). 3. Buffers not aligned to each other are the biggest mess. SSSE3 actually helps with that as it can shuffle bytes around, but i found it easier (and probably faster) to shift-or the things.

There's probably more that i forgot. I lost the original code but i have a half-arsed version somewhere around here if someone wants to see. It is only for 8 or 16 bytes aligned buffers (to each other) but the grand structure is there.

PS To those saying "REP MOV* is faster": In theory, yes, but no, not really.

Such a fascinating problem! For efficiency you want large aligned loads and stores. The source and destination alignment are independent issues; so the CPU uses registers for a sort of shift-and-realign engine.

And you want to unroll each case, because speed is the goal.

The longer the alignment size (4-byte? 8-byte? 16-byte?) the more permutations of start and end conditions there are. E.g. moving from a 15-byte aligned source to a 3-byte aligned destination. Maybe 256 combinations? Only 1 of which is zero-aligned source and destination (full-register move) which is all most folks think of writing to begin with.

Add in cache-line size considerations, and overlap possibilities (are we moving a string in-place left or right by 7 characters?) Can the bus do unaligned loads? Stores? How do they compare in performance to multiple single-byte transfers? So many things can affect performance, each case becomes a heuristic. After all the theorizing, testing is the only real metric.

I've dived down this rabbit hole before. Wrote a test app to move 0-128 bytes from source aligned 0-128 to destination aligned 0-128. The memcpy I was testing on a RISC architecture hit 11 bugs (processor faults, incorrect result) before I was through.

Its refreshing to find somebody else with an appreciation for the depth of this problem. Thanks for posting, gens!

> I wrote an (actually) fast memcpy() in assembly. There are more problems then just different size-s. Hardest problem is actually alignment, particularly 1 byte unaligned buffers.

It is, but in performance critical code there is never any reason to use unaligned buffers or copying byte sizes not a multiple of the machine's register size. E.g you can have a memcpy_fast() which demands correct alignment, and the standard memcpy() which is slower but has no such requirements.

>I don't want to register to download the code

BugMeNot has you covered: http://bugmenot.com/view/codeproject.com

Reply on news.ycombinator.com