A bug story: data alignment on x86 • Hacker News Board

Re: A bug story: data alignment on x86

#101

Post by loup-vaillant » Tue, Nov 08, 2016, 6:03 PM UTC

benchaney wrote: post #95

loup-vaillant wrote: post #64

Earlier quoted context omitted.

Again someone blaming the victim. I'm kind of sick of this. While true, your comment doesn't get at the root of the problem. The obvious fact here is that there is a mismatch between the C standard and how the users really use it. The less obvious fact/opinion/fallacy, is that it is not automatically the user's fault. The standard could be wrong. Sure, there are reasons why such and such behaviour ended up undefined.…

You are missing the point. The standard could be wrong, but it is still the standard. You still have an obligation to conform to it if you are writing C code. It is a prescriptive document, not a descriptive one. It can only be wrong to the extent that it can make poor decisions. Regardless of what it says it is authoritative.

Did I gave the impression we don't need to conform to that standard? That wasn't my intention. I just wanted to point out the standard is sometimes stupid.

Of course we have to conform to the standard, however crazy. The only alternative is forking the language itself.

Re: A bug story: data alignment on x86

#102

Post by loup-vaillant » Tue, Nov 08, 2016, 6:12 PM UTC

saynsedit wrote: post #91

loup-vaillant wrote: post #64

Earlier quoted context omitted.

Again someone blaming the victim. I'm kind of sick of this. While true, your comment doesn't get at the root of the problem. The obvious fact here is that there is a mismatch between the C standard and how the users really use it. The less obvious fact/opinion/fallacy, is that it is not automatically the user's fault. The standard could be wrong. Sure, there are reasons why such and such behaviour ended up undefined.…

Undefined behavior is one of the most intelligent things the C designers did when designing the language. It's a fact of life that not all syntactic forms will have meaning. What's sqrt(-1)? Trick question, There's no meaningful answer (in terms of real numbers alone)! Why should anyone specify if it crashes the program, returns 0, throws an exception, etc.? Who cares? garbage in, garbage out. Another example, "the f…

> Undefined behavior is one of the most intelligent things the C designers did when designing the language.

I agree, actually. They just went too far. Too many things are undefined for no good reason. Even sqrt(-1) is debatable, by the way: if your platform provides an efficient way to trap, it should probably trap, and the compiler should not assume it will never happen.

And if you want crazy optimizations, consider introducing unsafe assertions into the language. That is, arbitrary boolean expressions the compiler is allowed to assume will always return true.

Re: A bug story: data alignment on x86

#103

Post by qb45 » Tue, Nov 08, 2016, 6:16 PM UTC

saynsedit wrote: post #92

qb45 wrote: post #11

The correct solution for GCC is specifying 1-byte alignment for this particular array: #include #include typedef uint32_t __attribute__((__aligned__(1))) uint32_t_unaligned; uint64_t sum (const uint32_t_unaligned * p, size_t nwords) { uint64_t res = 0; size_t i; for (i = 0; i Probably works on clang too and IIRC the MS compiler provides similar functionality with different syntax. AFAIK there is no portable solution.…

Nah, correct solution is simply to use memcpy(), works on all compilers, all platforms, all versions, with SSE and with any flags specified: #include #include uint64_t sum (char *p, size_t nwords) { uint64_t res = 0; size_t i; for (i = 0; i

Nitpick: memcpy is string.h not stdlib.h, the type was uint32_t not uint64_t and you are making some unwarranted assumptions about sizeof(uint64_t), not to mention that the existence of this type is merely implementation defined ;)

Deal breaker: your memcpy invocation requires a sufficiently smart compiler to convert into normal unaligned load on x86 and seems to prevent GCC autovectorization. In this case OP actually didn't want vectorization, but in general it happens that such workarounds confuse compilers and produce worse code.

Re: A bug story: data alignment on x86

#104

Post by saynsedit » Tue, Nov 08, 2016, 6:50 PM UTC

qb45 wrote: post #103

saynsedit wrote: post #92

Earlier quoted context omitted.

Nah, correct solution is simply to use memcpy(), works on all compilers, all platforms, all versions, with SSE and with any flags specified: #include #include uint64_t sum (char *p, size_t nwords) { uint64_t res = 0; size_t i; for (i = 0; i

Nitpick: memcpy is string.h not stdlib.h, the type was uint32_t not uint64_t and you are making some unwarranted assumptions about sizeof(uint64_t), not to mention that the existence of this type is merely implementation defined ;) Deal breaker: your memcpy invocation requires a sufficiently smart compiler to convert into normal unaligned load on x86 and seems to prevent GCC autovectorization. In this case OP actuall…

I'm not sure I understand your deal breaker. For the platform he was targeting it produces optimal code, for other platforms it's merely slower (but not specifically slower, since the compiler is likely not a great optimizer across the board).

Vectorization is in general not applicable here since it usually requires aligned memory... not all implementations do, but most. In any case, benchmarking is more appropriate than armchair optimizing.

Re: A bug story: data alignment on x86

#105

Post by qb45 » Tue, Nov 08, 2016, 7:37 PM UTC

saynsedit wrote: post #104

qb45 wrote: post #103

Earlier quoted context omitted.

Nitpick: memcpy is string.h not stdlib.h, the type was uint32_t not uint64_t and you are making some unwarranted assumptions about sizeof(uint64_t), not to mention that the existence of this type is merely implementation defined ;) Deal breaker: your memcpy invocation requires a sufficiently smart compiler to convert into normal unaligned load on x86 and seems to prevent GCC autovectorization. In this case OP actuall…

I'm not sure I understand your deal breaker. For the platform he was targeting it produces optimal code, for other platforms it's merely slower (but not specifically slower, since the compiler is likely not a great optimizer across the board). Vectorization is in general not applicable here since it usually requires aligned memory... not all implementations do, but most. In any case, benchmarking is more appropriate…

You are writing convoluted code and hoping that your compiler will figure it out and convert it internally to the form I posted. Sometimes it does, sometimes it doesn't. In this case it generates reasonable code but doesn't vectorize it for some reason. WTF.

I prefer to just add alignment specification and move on, assuming I don't care about portability. If portability matters, reread my original post ;)

Re: A bug story: data alignment on x86

#106

Post by qb45 » Tue, Nov 08, 2016, 8:12 PM UTC

jjoonathan wrote: post #16

userbinator wrote: post #13

Earlier quoted context omitted.

Agreed, I've always found them unusual and perhaps a bit of a shortsighted decision --- they've been making processors seamlessly handle any alignment with perhaps an extra cycle, even for the MMX instructions, yet somehow felt the need to restrict much of the SSE ones into aligned and only provide one unaligned move. The stack alignment restriction is also annoying when handwriting Asm, although fortunately it's onl…

> seamlessly handle any alignment with perhaps an extra cycle I'm not up to date on the latest mitigation strategies, but the hairball of cache implications caused by unaligned access make me suspicious of that claim. If you (or your compiler) signal that you want performance by using vector instructions, I think it's completely fair for Intel to demand that you pay attention to alignment.

Case in point: a simple example of code which copies 1MB of data with SSE and slows down on misalignment:

https://news.ycombinator.com/item?id=12718625

Presumably due to the hairball of cache implications, as you put it.

But it also is true that the choice of aligned/unaligned instructions makes no difference if the array is aligned.

Re: A bug story: data alignment on x86

#107

Post by qb45 » Tue, Nov 08, 2016, 8:32 PM UTC

amadvance wrote: post #78

GlitchMr wrote: post #22

Compiler is allowed to assume alignment of pointers (what are you doing is creating a pointer to a value with invalid alignment, hence undefined behaviour (just creating a pointer is undefined behaviour)). The correct solution would be to read values indirectly. For example, a function like that could be used to replace every access to "q" variable. static uint32_t read(const char *p, size_t index) { uint32_t out; me…

Is this equivalent ? At least to me this seems a more common pattern than using memcpy(), and I expect to work better on old compilers. static uint32 read(const void *ptr) { const uint8 *b = (const uint8 *)ptr; return (b[3]

Functionally it seems equivalent, except that it doesn't work on big endian machines (assuming the ints are in native endian).

On dumb compilers it may be faster if a few bitops happen to be faster than a call to memcpy. Which sounds plausible.

On modern compilers it boils down to whether your compiler can optimize either one or both of these patterns into a single unaligned load. GCC for example certainly optimizes 4 byte memcpy, probably already at -O2, but whether it recognizes your pattern I don't know. Compile it and check.

Re: A bug story: data alignment on x86

#108

Post by Someone » Tue, Nov 08, 2016, 9:23 PM UTC

bertit wrote: post #89

Someone wrote: post #53

Earlier quoted context omitted.

You can also defensively add a quick test to your program's startup code and unit tests. Startup will take a tiny bit longer, but those porting your code will be thankful if they hit the problem, double so if you manage to emit a useful diagnostic.

That would not work. Since the test may not cause any problems. While the compiler might find more optimzation opportuinities in the real program. (Just as the begining of the function did not have problem, but the for loop had.) Just don't use undefined behavior.

1. You write a few versions of a program.

2. Users report that it started crashing sometimes in version V.

3. After lots of debugging, you discover an input that reliably crashes your program after 30 minutes.

4. A bit later, you discover that your compiler started compiling function f so that it no longer works with unaligned data/buffers of exactly 8 bytes/whatever.

5. At the start of main, you add a dummy call to f with data that reliably crashes if your compiler decides to do that optimization again.

6. The program has become worse: it now always crashes, independent of its input, but you don't have to wait 30 minutes before finding out. That makes it way less likely that you ship a binary again that has the problem. It also makes it easier to tweak source code/compiler flags/whatever until the problem disappears.

Is that perfect? Absolutely not, it is more something of last resort, but depending on the costs of crashing versus those of sometimes crashing half-way through a run, it can be an improvement.

(this technique also can be used when your code hits compiler bugs)

Re: A bug story: data alignment on x86

#109

Post by startling » Tue, Nov 08, 2016, 11:11 PM UTC

scott_s wrote: post #97

startling wrote: post #93

Earlier quoted context omitted.

Undefined behavior is not illegal. The compiler can do anything with undefined behavior, including exactly what the author expected.

It is illegal, for any reasonable definition of illegal. See my comment from earlier in the year: https://news.ycombinator.com/item?id=10840497

"Illegal" seems stronger to me than "not strictly conforming", I guess (and so does "well-formed", for that matter). But I think we basically agree.

Re: A bug story: data alignment on x86

#110

Post by saynsedit » Wed, Nov 09, 2016, 9:16 PM UTC

qb45 wrote: post #105

saynsedit wrote: post #104

Earlier quoted context omitted.

I'm not sure I understand your deal breaker. For the platform he was targeting it produces optimal code, for other platforms it's merely slower (but not specifically slower, since the compiler is likely not a great optimizer across the board). Vectorization is in general not applicable here since it usually requires aligned memory... not all implementations do, but most. In any case, benchmarking is more appropriate…

You are writing convoluted code and hoping that your compiler will figure it out and convert it internally to the form I posted. Sometimes it does, sometimes it doesn't. In this case it generates reasonable code but doesn't vectorize it for some reason. WTF. I prefer to just add alignment specification and move on, assuming I don't care about portability. If portability matters, reread my original post ;)

It's not convoluted. It's actually clear and well-defined making it easier to reason about.

I'd call compiler specific alignment attributes more arcane, convoluted, and susceptible to future bugs.

Vectorization isn't a panacea. You need to benchmark to be sure, lacking that I expect GCC to be better at optimizing code than you. If you disagree, please manually write a vectorized one that handles non-aligned addition and post your results :)