Interesting. I thought modern CPU optimisation required avoiding branches, but here adding the branch allows the branch pediction to parallelise what it otherwise couldn't.

▲

zipy124 2 hours ago | parent [-]

It does and the key here is that adding the if is akin to avoiding a branch, since getting data then doing something with it is a hidden branch if you already have the data. All this code does is formalise the hidden branch so that it can be avoided when possible.

▲

summarybot 36 minutes ago | parent [-]

That's pretty cool. Is there something obcluding the compiler from noticing this parallelization opportunity without the new `if` ?

My understanding is the assignment and the evaluation are somehow coupled in this case based on the essay, but I could use an explanation.

	▲	purplesyringa 21 minutes ago \| parent [-]
		The optimization in the post is only advantageous if `next_j[i][j] == j` holds often enough. Without prior knowledge, the compiler can't know if it's going to improve performance, and the worst losses are greater than the best wins (branch misprediction is very expensive), so it decides not to interfere.