Hacker News Reader

Comment by slashdev | Hacker News Reader

pext/pdep are awesome, but I imagine you'd never notice the difference in real world usage. You'd have to use a program often where those instructions are on the critical path and comprise a significant percentage of execution time. The chances of that are slim to none. You may well notice the extra cores though, to a point, depending what you do.

View on HN

I was writing a program similar to the 4-coloring problem. I represented colors as 2-bits (color 0, 1, 2, and 3).

I also created a bitmask representation of relations, which would represent 1-variable in 4-bits, 2-variables in 16-bits, 3-variables in 64-bits, and 4-variables in 256 bits.

Ex: Texas / Oklahoma / Arizona relation would be a 64-bit number ("true" means a color-set is in the relation. "False" means the color-set is not in the relation), and extracting or packing the data into these three variables would be a pdep or pext operation.

Extracting data (pext) would be a "select" operation. While PDEP + OR would be a "update" operation over the relation. I've written a join for fun, but I haven't gotten much further than that. First, because pdep / pext were slow on my machine. Second, because I figured out an alternative solution to my particular problem.

---------

I think the pext / pdep instructions have HUGE implications to 4-coloring problem, 3-SAT, Constraint Solvers, etc. etc. More researchers probably should look into those two instructions.

Just look at Binary Decision Diagrams, and other such combinatorial data structures, and you can definitely see the potential uses of PEXT / PDEP all over the place.

https://en.wikipedia.org/wiki/Binary_decision_diagram

Wouldn't this sort of thing be also very common in applying bit map masks to bit arrays in frameworks like numpy?

I can't say that I've used numpy before. But this function looks similar to pext / pdep:

https://docs.scipy.org/doc/numpy-1.15.0/reference/generated/...

Hobby code: I slowly developing a Gin rummy [1] engine. Card sets are represented by 64 bit integers and all operations (findig melds, sets, etc...) are implemented with bitwise operators.

I have used pext/pdep for the iterator implementation (iterate over all subset of a card set, or all combination of n cards).

(e.g. To iterate over all 10 card combination brute-force and filter and print out all the ones which can be knocked (evaluating 15_820_024_220 hands) takes 70 seconds - one threaded - on my 7th gen intel i3.)

[1] https://en.wikipedia.org/wiki/Gin_rummy

A while back, I was working on a fun little video game side project which used BMI2 instructions to compute Morton codes on the critical path.

Voxels were stored in a buffer sorted in Morton order. The idea was to balance performance improvements realized by increased spatial locality against the cost of computing the Morton codes. The trade-off was only worthwhile on Intel because of the use of pdep/pext in optimized encode/decode functions.

I imagine something similar would probably apply to texture lookups in a software 3D renderer.

> I imagine something similar would probably apply to texture lookups in a software 3D renderer.

Except that for a 3D rasterizer you'd probably be better off calculating Morton code for 8 pixels at once in a SIMD register and then using vpgatherdd to fetch 8 ARGB pixel values "in parallel" (in theory, in practice AVX2 gather might not be any faster than scalar loads).

https://www.felixcloutier.com/x86/vpgatherdd:vpgatherqd

I will agree with dragon tamer that for some real-world codes PEXT/PDEP sits right in the middle of the hot path. It isn't just the clock cycle savings either, for some logic it can substantially simplify the code path. There's a lot of neat wizardry that can be done by composing sequences of those two instructions (mixed with other basic integer ops).

I don't use them often, but there are cases where I would not want to try to write code without them.

Reply on news.ycombinator.com