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

51–60 of 243 posts

Re: That XOR Trick (2020)

#51

Post by detaro »

oconnor663 wrote: post #32
mytailorisrich wrote: post #23

Earlier quoted context omitted.

xor reg, reg is indeed the standard way to zero out a register in x86 assembly (it's not just a compiler trick) as it is both shorter and faster than loading the register with zero via a mov . Apart from that, I'd say that a common use of XOR operations in general are interactions with hardware peripherals where manipulating bit fields are needed.

Why does mov'ing a constant end up having overhead?

It's larger, because it needs to fit a 32bit value of 0 in the instruction, and thus e.g. on x86 needs 5 bytes, whereas xor reg,reg needs 2. As such it was a common code size optimization, which in turn has lead to CPU manufacturers optimizing their CPUs to recognize it and treat it even more efficiently.

Re: That XOR Trick (2020)

#52

Post by nickelpro »

oconnor663 wrote: post #32
mytailorisrich wrote: post #23

Earlier quoted context omitted.

xor reg, reg is indeed the standard way to zero out a register in x86 assembly (it's not just a compiler trick) as it is both shorter and faster than loading the register with zero via a mov . Apart from that, I'd say that a common use of XOR operations in general are interactions with hardware peripherals where manipulating bit fields are needed.

Why does mov'ing a constant end up having overhead?

It's not overhead, it's about dependency breaking. 32-bit xors on a single register are universally recognized as a zeroing idiom, which means the CPU doesn't have to wait for the results of previous operations in order to set the value of the applicable register to zero.

In modern CPUs zero'ing idioms aren't even executed, they only get as far as the register allocater. The register allocater will allocate a zero'd physical register for the architectural register that had the idiom applied to it and the job is done.

Re: That XOR Trick (2020)

#53

Post by johnfn »

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

Err... if you sum all the numbers that’s O(n) as well.

Re: That XOR Trick (2020)

#54

Post by whimsicalism »

exabrial wrote: post #21

> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). I'd rather know w…

> pleasant person, are a team player, whether they have leadership aspirations, and take responsibility.

I know the above is a popular opinion, but I've worked as a SWE at a company A that had a "technical interview" process and Company B that didn't have a formalized one.

I would much, much prefer to work at company A (pay differences aside) because of the type of person who passes these interviews. It can be quite difficult to determine someone's capability at interview-time. But company B had lots of competency "false positives" (in my view) whereas company A had very few. That's the value of a technical interview.

That said, of course the XOR solution would never be the only one accepted, but it would probably get you brownie points here.

Re: That XOR Trick (2020)

#55

Post by tlb »

diegocg wrote: post #8

The xor swap can be dangerous: if variables have the same value, they xor to zero so you end up losing the values of both variables.

Not if they have just the same value, but if they're the same memory location. So check the pointers:

  void swap(T &x, T &y) {
    if (&x == &y) return;
    x ^= y;
    y ^= x;
    x ^= y;
  }

Re: That XOR Trick (2020)

#56

Post by dragontamer »

exabrial wrote: post #21

> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). I'd rather know w…

> I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_).

Erasure correction is a very useful trick for data-engineers. I don't think this is a microcontroller trick, as much as a data-resliliency trick.

The XOR-trick is how you implement RAID5 most efficiently. A proper discussion / interview would probably describe the XOR trick, and then see if the engineer is smart enough to understand the difference between erasure and errors.

--------------

With a blog post describing the XOR trick ahead of us: now I ask you (the audience): what is the difference between an erasure and an error? Why can this XOR-trick protect against an erasure, but NOT an error? And how does this relate to RAID5's known failure cases?

But at that point, I'm interviewing for someone who has passed a data communications class.

Re: That XOR Trick (2020)

#57

Post by user-the-name »

diegocg wrote: post #8

The xor swap can be dangerous: if variables have the same value, they xor to zero so you end up losing the values of both variables.

You are confused about the problem here. It is not that both values are the same, it is you are applying the xor swap using pointers to values, and both pointers point to the same value in memory.

Re: That XOR Trick (2020)

#58

Post by whimsicalism »

webel0 wrote: post #5

I hope this article takes off so that my company will have to change its initial code screen. We make no use of xor in our rather large codebase (I’ve checked) yet pin a lot on whether an interviewee is aware of this trivia.

You have a single question that is always present in your "initial code screen"?

XOR-only questions are poor unless you're interviewing someone for a very specific kind of role.

Re: That XOR Trick (2020)

#59

Post by woofie11 »

exabrial wrote: post #21

> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). I'd rather know w…

I think it kind of depends on the type of programmer one wants to hire. There are different roles, solving different types of problems.

There are places for people with technical brilliance, there are places for people with social brilliance, with both, and with neither. That's healthy. You want a diverse economy with different types of positions for different types of folks, and vice-versa.

If I ask a half-dozen questions like the xor trick, I'll have a filter for one type of technical background. Whether you know each of them is pretty random, but whether you know none of them or most of them is not.

Re: That XOR Trick (2020)

#60

Post by nickelpro »

bonzini wrote: post #44
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.

Not necessarily true for most architectures. Many RISC architectures have a "zero" register, so a canonical "move short immediate" instruction could be "OR Rn, R0, #n" ("OR R0 which is always zero with n and store into Rn") or the same with ADD. Then clearing Rn will usually be "OR Rn, R0, R0", "ADD Rn, R0, #0" or something like that.

I should have been clearer, when I say most architectures I mean most x86/x64 architectures not most ISAs. Obviously ISAs with a dedicated zero register don't need the zeroing idioms of x86.
Post reply on HN