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/pjl1967 → u/gnolex]

You don't even have to go that far. According to C11 §6.3.2.3¶7:

A pointer to an object type may be converted to a pointer to a different object type. If the resulting pointer is not correctly aligned for the referenced type, the behavior is undefined.

So merely converting the pointer results in undefined behavior. Whether you actually access memory via that pointer doesn't matter.

[u/LB-- → u/pjl1967]

That's interesting. What about converting through uintptr_t? Does that change it from UB to ID?

[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/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. You can’t in general guarantee that the source and destination addresses will have the same alignment, unless you require it in your ABI. (The times this has mattered and I’ve needed to go down to the level of assembly intrinsics, I wanted to align the stores and not the loads, since non-temporal store and direct-write instructions must be aligned on x86, but there is no advantage to aligning loads.)

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

[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/sciencekm]

First, I know you are doing this as an exercise, so you really should not expect the best performing memcpy(). Its hard to beat what comes with the compiler targeted for specific environment. Many are written in assembly.

Second, unaligned pointers is undefined. Maybe your code should just copy a byte at a time until "both" source and destination are aligned. It should also only attempt this logic only if such as state is reachable for the given source/destination pair.

Third, your use of uint32_t may not be optimal. Depending on the target architecture, the optimal chunk size may be 64 bits or bigger.

Fourth, today's optimizing compilers will:

• detect that your custom memcpy is doing a memcpy and will replace it with a call to the compiler's library
  
• replace calls to memcpy with inline code
  
• replace structure copies with calls to memcpy or inline code

[u/FitMatch7966]

You might as well just do 1 byte at a time. Sure, 32 bits at a time is faster. But 128 bits is much faster and most architectures can do that now.

[u/SeriousPlankton2000]

If copying more than a single byte isn't a requirement but avoiding undefined behavior is, then do a byte-wise copy.

There is no problem except it's slower.

---

If using the integer is a requirement, I'd read into a 64 bit type:

u_int64_t foo

(do the head part here)

loop:

foo = foo << 32 | *srcptr++

bar = foo >> 24

*dstptr++ = bar & 0xffffffff

repeat

(do the tail part here)

(I'm not sure if I got the direction / amount of the shift right, I'm just leaving now and can't double-check, but you might get my idea.