Question about alignment in a custom memcpy implementation

[u/xmanotaur]

I'm implementing my own memcpy as an exercise.

My current approach is:

1. Copy bytes until dst reaches a 4-byte-aligned address.
2. Copy 4 bytes at a time using uint32_t.
3. Copy the remaining bytes one by one.

I understand that this optimization works nicely when src and dst have the same alignment offset, e.g.:

src = 0x1001
dst = 0x2001

src % 4 == dst % 4

What I don't understand is why I can't simply perform an unaligned 32-bit load/store when the offsets are different.

For example:

src = 0x1001
dst = 0x2002

Why can't I simply do:

uint32_t x = *(uint32_t *)src;
*(uint32_t *)dst = x;

This seems like it should copy exactly the desired 4 bytes.

I understand that unaligned accesses may be slower, fault on some architectures, or have restrictions for MMIO. But assuming I'm on an architecture where unaligned 32-bit accesses are supported, is there actually a correctness problem?

I'm trying to understand the fundamental reason rather than just memorize the "same alignment" rule.

Thanks!

[u/gnolex]

Unaligned memory access is undefined behavior. C doesn't target a specific processor, it targets an abstract machine where this kind of operation is invalid. So even if your specific processor says this is fine, your C compiler doesn't have to care about that and may do whatever it wants.

[u/DawnOnTheEdge]

This is going to be highly architecture'dependent. Most modern CPUs are designed so that sequences of unaligned loads and stores have no penalty.

However, if you’re targeting an architecture where naturally'aligned loads and stores have perform better, you should start by calculating the length of the unaligned prefix, which will be smaller than the maximum chunk size.

if prefix_len & 0x1 != 0, copy one byte, and increment the source and destination pointers. Whether or not the bit was set, your pointer is now aligned on a two-byte boundary. If prefox_len & 0x2 != 0, copy two bytes, and increment the source and destination pointers by 2. Whether or not the bit was set, your pointer is now aligned on a four-byte boundry. If prefix_len & 0x4 != 0, copy four bytes, and increment the source and destination pointers by 4, Whether or not the bit was set, your pointer is now aligned on an 8-bit boundary. Repeat for every power of 2 until the largest chunk you can copy at once. Then, copy chunks that size, incrementing by the chunk size, so the pointers stay aligned. Calculate the length of the remaining suffix, which unlike the prefix starts out aligned. Process this in reverse order, from larger to smaller powers of 2, so that your pointer always remains aligned to the next-smaller power of 2 (and the next power of two as well).

Some architectures do have an instruction to load and store bytes with a bitmask, which could be used for the prefix and suffix instead.

[u/NukiWolf2]

As an addition to the other answers:

Maybe you should ask whether implementing memcpy() as an exercise is a good idea, because when people usually run in such issues with unaligned access, one answer would be to use memcpy(), which obviously is no solution for you. The reason is that when memcpy() is called the compjler doesn't necessarily need to call memcpy() but replace it with some appropriate instructions for that copy. Furthermore, I'd assume that memcpy() implementations that are supposed to be efficient, e.g. by using architecture specific features, aren't necessarily written in C but in assembly language to avoid the problems that you ran into.

Btw. do you already know Duff's device? :p Not sure if it's of any use to you but it's nice to know :D

[u/tstanisl]

Note that converting incorrectly aligned pointer is UB according to standard. It may cause unexpected problems like (int*)x != x or some disastrous overzealous optimizations.

[u/pskocik]

From the C perspective expressing it like that is a bit problematic because (1) imagining uint32_t where they might not be the effective type is a strict aliasing violation (UB) (2) just casting an unaligned address to a pointer type requiring target alignment is UB.

You could express it differently (memcpy(dst,src,4), attribute((may_alias)) ) or you might get away with it due to translation unit isolation and the compiler not freaking out about about unaligned pointers. I'd try expressing it differently without the UB.

For archs like x86-64, an unaligned movl is fine and unpenalized if not crossing cachelines, and costing only a little bit extra if 2 cachelines are straddled.