Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

That XOR Trick (2020)

florian.github.io

Post reply on HN
Print view View original

231–240 of 243 posts

Re: That XOR Trick (2020)

#231

Post by jl2718 »

simias wrote: post #46

Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…

I like this as an example of how compilers cause bugs. This code looks reasonable and concise, but it shouldn’t. If you were writing microcode for a non-superscalar processor, you would do two separate memory to register loads and then three xors and then two register to memory stores. But the compiler teaches us to use shorthand and it will fill in the details. In this case the resulting code is ridiculous with loads and stores on each xor because the compiler can’t guarantee that i!=j, and it would normally perform terribly, but we’ve architected CPUs around compilers to use caches that make up for these problems, and they are so prevalent that it’s worth it to dedicate most of the CPU die area to branch prediction based on conventions of the C compiler, and most of the compiler code to conventions of the CPU branch predictor. It’s getting quite ridiculous, and maybe it’s time to move to architectures and languages that make everything explicit.

Edit: also, there is an xchg instruction that you have to pull out of intrinsics to use in C (good luck in most other HLL). It seems like a language should be more about how to use vocabulary than restricting it.

Re: That XOR Trick (2020)

#232

Post by tomtomtom777 »

FartyMcFarter wrote: post #24
nickelpro wrote: post #19

Earlier quoted context omitted.

Xor'ing registers isn't a compiler trick or arcane piece of lore, it's the canonical way to zero a register on most architectures. It's the only universally recommended way for both Intel and AMD x86 and x64 processors.

In fact, modern x86 CPUs know that the result of "x XOR x" is independent of x, and use this fact to optimize operations that would otherwise have a dependency.

You are correct but using programmers terminology here is confusing.

The opcodes 31 C0 mean "Set EAX register to zero"

The opcodes 31 D8 mean "Set EAX to EAX xor EBX"

The trick part is in the mnemonics used by assemblers and literature that transcribe the first as "XOR EAX, EAX".

It isn't actually implemented as such, so it isn't really an "optimization"

Re: That XOR Trick (2020)

#233

Post by nickelpro »

Kwpolska wrote: post #225
nickelpro wrote: post #19

Earlier quoted context omitted.

Xor'ing registers isn't a compiler trick or arcane piece of lore, it's the canonical way to zero a register on most architectures. It's the only universally recommended way for both Intel and AMD x86 and x64 processors.

You make it sound as if there were four Intel/AMD x86/x64 architectures. And well, there aren’t. The vendor split is not a thing, we’re all running the same software on Intel and AMD x86/x64 processors. And you could argue that the x86/x64 split doesn’t really matter for this, since x64 is a superset of x86 and inherits this tradition from the 16-bit and 32-bit eras.

There are dozens of x86/x64 uarchs, x86 is just an ISA, doesn't say anything about how the chip is built.

Re: That XOR Trick (2020)

#234

Post by FartyMcFarter »

tomtomtom777 wrote: post #232
FartyMcFarter wrote: post #24

Earlier quoted context omitted.

In fact, modern x86 CPUs know that the result of "x XOR x" is independent of x, and use this fact to optimize operations that would otherwise have a dependency.

You are correct but using programmers terminology here is confusing. The opcodes 31 C0 mean "Set EAX register to zero" The opcodes 31 D8 mean "Set EAX to EAX xor EBX" The trick part is in the mnemonics used by assemblers and literature that transcribe the first as "XOR EAX, EAX". It isn't actually implemented as such, so it isn't really an "optimization"

I'm not sure what you mean by "programmers terminology".

0x31 0xC0 is disassembled to "xor eax, eax".

This is not nitpicking, as there's an important difference. The "xor eax, eax" instruction affects CPU flags [1], while "mov eax, 0" doesn't [2].

> It isn't actually implemented as such

The implementation is independent of the meaning of the instruction set. There are many implementations of x86 instructions with differing levels and kinds of optimization, so we can't make general statements about that.

[1] https://c9x.me/x86/html/file_module_x86_id_330.html

[2] https://c9x.me/x86/html/file_module_x86_id_176.html

Re: That XOR Trick (2020)

#235

Post by abalaji »

shiftingleft wrote: post #107
abalaji wrote: post #89

Earlier quoted context omitted.

right but OP’s solution for this part of the problem is assumed to be instantaneous (ie O(0))

You probably mean O(1). Although: that's not true for arbitrarily sized integers either. Multiplication in O(1) implies P = NP (which further implies NP = PSPACE): https://cs.stackexchange.com/a/1661/129151

Yeah I meant O(1), whoops

Re: That XOR Trick (2020)

#236

Post by bonzini »

dan-robertson wrote: post #197
bonzini wrote: post #28

Earlier quoted context omitted.

Compilers can optimize "a != b" to "a xor b" if they know that both operands are 0 or 1. There are crazy many expression rewriting rules.

They don’t need to be 0 or 1. We already know that a ^ a = 0, a ^ 0 = a, and a ^ (b ^ c) = (a ^ b) ^ c, so we must have a ^ b = 0 only when a = b. Therefore in the C convention where 0 means false, a ^ b = not (a = b) = (a!=b) (this equality only holds for expressions that are going straight into a Boolean operation (or test in eg an if statement), as a!=b should always evaluate to 0 or 1. The compiler may use this b…

> (this equality only holds for expressions that are going straight into a Boolean operation

Right, though that's more commonly turned into just a cmp instruction (a subtraction).

However, if the result is assigned to a variable, on x86 "a != b" would be two or three instructions (possibly clearing a register because setne takes an 8-bit register operand only, and then a cmp/setne pair). Instead the xor would be one instruction, or two if a mov is needed.

Re: That XOR Trick (2020)

#237

Post by beeforpork »

NieDzejkob wrote: post #157
beeforpork wrote: post #151

Hmm, I would have used + and -, I suppose. The sum of 1..n is (n*(n+1))/2. Subtract from that all numbers in the array and what is left is the missing number.

I suppose one downside of this approach is that you need a bigger datatype to contain the result.

No, not really, because you just need the lower half bits of the multiplication result, i.e., the size you need for your numbers. You do need to care about overflow: the /2 operation must not remove an upper bit from those lower bits. But you can easily do that before *: either n or n+1 is even. Divide the even number by two, then multiply by the odd one and keep only the lower bits. These lower bits are all you need, because the missing number is representable in it: subtracting may use wrap-around, but still, the remaining bits will be the missing number.

Re: That XOR Trick (2020)

#238

Post by loeg »

layer8 wrote: post #165
loeg wrote: post #152

Earlier quoted context omitted.

Your linked comment only quotes excerpts saying it's implementation-defined, rather than undefined. Can you point to the part that is undefined? (You would use a uintptr_t for the xor'd prev-next pointers instead of void*.)

To be precise, it's implementation-defined whether it's undefined behavior, prior to C11. You are right that in C11, if uintptr_t is used to store the xored value, behavior is defined.

Implementation-defined whether it's UB or not is still implementation-defined, I think.

Which change are you thinking of in C11? (I'm just curious.) Thanks!

Re: That XOR Trick (2020)

#240

Post by PufPufPuf »

tlb wrote: post #3

> XOR all values between 1 and n An O(n) algorithm!? You'd expect there to be a closed-form solution for this, analogous to summing a series using n*(n-1)/2. OEIS to the rescue. http://oeis.org/A077140 gives ((n+1)%2)*n + (n+(n%2))//2 % 2

...or simply

switch(n % 4) { case 0: return n; case 1: return 1; case 2: return n + 1; case 3: return 0; }

Post reply on HN