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

41–50 of 141 posts

Re: That XOR Trick (2020)

#41

Post by codebje »

moron4hire wrote: post #35
NoahZuniga wrote: post #33

Earlier quoted context omitted.

O(2n) doesn't exist. The whole point of big O is that you ignore such "trivial" things as what factor comes before the n

Did I not say that?

You did, but it might not be an effective strategy to mention asymptotic complexity to help forward your argument that one linear implementation is faster than another.

Whether it's a win in Python to use one or two loops isn't so clear, as a lot is hidden behind complex opcodes and opaque iterator implementations. Imperative testing might help, but a new interpreter version could change your results.

In any case, if we want to nitpick over performance we should be insisting on a parallel implementation to take advantage of the gobs of cores CPUs now have, but now we're on a micro-optimisation crusade and are ignoring the whole point of the article.

Re: That XOR Trick (2020)

#42

Post by haskellshill »

moron4hire wrote: post #35
NoahZuniga wrote: post #33

Earlier quoted context omitted.

O(2n) doesn't exist. The whole point of big O is that you ignore such "trivial" things as what factor comes before the n

Did I not say that?

>we end up performing two loops instead of one, all because sticking three operations in one statement is "yucky"

You seem to believe that "O(2n)"

  for value in range(1, n + 1):
    result ^= value
  for value in A:
    result ^= value
is slower than "O(n2)"

  for value in range(1, n + 1):
    result ^= value
    result ^= A[value-1]
simply because the latter has one "for loop" less. Am I misunderstanding you, or if not, why would this matter for speed?

Re: That XOR Trick (2020)

#43

Post by a_t48 »

haskellshill wrote: post #42
moron4hire wrote: post #35

Earlier quoted context omitted.

Did I not say that?

>we end up performing two loops instead of one, all because sticking three operations in one statement is "yucky" You seem to believe that "O(2 n)" for value in range(1, n + 1): result ^= value for value in A: result ^= value is slower than "O(n 2)" for value in range(1, n + 1): result ^= value result ^= A[value-1] simply because the latter has one "for loop" less. Am I misunderstanding you, or if not, why would this…

Unless both loops get unrolled it's ever so slightly slower due to having to check for the end value twice. Plus potentially a cache hit at the start of the second loop.

Re: That XOR Trick (2020)

#44

Post by motorest »

ameliaquining wrote: post #10

Ah, my least favorite technical interview question. (I've been asked it, but only after I first read about it online.)

> Ah, my least favorite technical interview question.

The epitome of turning technical interviews into a trivia contest to make them feel smart. Because isn't that the point of a tech interview?

Re: That XOR Trick (2020)

#45

Post by matusp »

motorest wrote: post #44
ameliaquining wrote: post #10

Ah, my least favorite technical interview question. (I've been asked it, but only after I first read about it online.)

> Ah, my least favorite technical interview question. The epitome of turning technical interviews into a trivia contest to make them feel smart. Because isn't that the point of a tech interview?

Is there any other field where they give you random brain teasers for an interview? My friends outside of IT were laughing their heads off when they hears about the usual interview process.

Re: That XOR Trick (2020)

#46

Post by sfn42 »

matusp wrote: post #45
motorest wrote: post #44

Earlier quoted context omitted.

> Ah, my least favorite technical interview question. The epitome of turning technical interviews into a trivia contest to make them feel smart. Because isn't that the point of a tech interview?

Is there any other field where they give you random brain teasers for an interview? My friends outside of IT were laughing their heads off when they hears about the usual interview process.

I've always had reasonable interview questions. Get some data from an API and display it in a table. Make a class that can store car data and get them by plate number. Make a class that calculates tax based on a bracket system.

I haven't even read the article so I don't know what this is about really but if an interviewer seriously asked me about some obscure xor trick I'd laugh at them.

Re: That XOR Trick (2020)

#47

Post by vaylian »

praptak wrote: post #37

Fun fact: the xor swap fails when the variables are aliases. This was the trick used in one of the underhanded code competitions. Basically xor swapping a[i] with a[j] triggered the evil logic when i was equal to j.

It would set a[i] to zero instead of swapping two values, right?

Re: That XOR Trick (2020)

#48

Post by Someone »

sparkie wrote: post #38
GuB-42 wrote: post #21

Earlier quoted context omitted.

"xor ax, ax" is still in use today. The main advantage is that it is shorter, just 2 bytes instead of 3 for the immediate, the difference is bigger in 32 and 64 bit mode as you have to have all these zeroes in the instruction. Shorter usually mean faster, even if the instruction itself isn't faster.

In long mode, compilers will typically emit `xor eax, eax`, as it only needs 2 bytes: The opcode and modrm byte. `xor ax, ax` takes 3 bytes due to the operand size override prefix (0x66), and `xor rax, rax` takes 3 bytes due to the REX.W prefix. `xor eax, eax` will still clear the full 64-bit register. Shorter basically means you can fit more in instruction cache, which should in theory improve performance marginally…

Size isn’t everything. You should start by reading the manual for your CPU to see what it advises. The micro-architecture may treat only one of the sequences specially. For modern x64, I think that indeed is the shorter xor sequence, where, internally, the CPU just renames the register to a register that always contains zero, making the instruction independent of any earlier instructions using eax.

IIRC, Intel said a mov was the way to go for some now ancient x86 CPUs, though.

Re: That XOR Trick (2020)

#49

Post by devjab »

moron4hire wrote: post #5

Why do people hate traditional for loops so much? In a conversation about petty micro optimizations, we end up performing two loops instead of one, all because sticking three operations in one statement is "yucky"?

I think you raise a good question, but Python doesn't have a traditional for loop. To do it in one loop, you'd either have to simulate a traditional for loop with something like range, or you'd have to build a c/zig/rust lib and use it with cffi (or whatever rust uses that I forgot what was named). Or you're going to do it the "pythonic" way and write two loops, probably with a generator. As far as micro optimisation I'd argue that it depends on what you want. Speed or stable memory consumption? The single loop will be faster (for the most part) but the flip side is that there is a limit on how big of a data set it can handle.

It's all theoretical though. On real world data sets that aren't small I don't see why you wouldn't hand these tasks off to C/Zig/Rust unless you're only running them once or twice.

Re: That XOR Trick (2020)

#50

Post by bsdz »

nullc wrote: post #14
st0le wrote: post #3

Another fun trick I've discovered. `XOR[0...n] = 0 ^ 1 .... ^ n = [n, 1, n + 1, 0][n % 4]`

Tables yuck :P, maybe XOR[0...x] = (x&1^(x&2)>>1)+x*(~x&1)

~Is there a simple proof for this type of identity?~

Actually I found something through Gemini based on the table mod 4 idea in previous post. Thanks.

Post reply on HN