A Fast x86 Implementation of Select (2017) [pdf]

by espeed • 8 years ago

90 18 8 years ago

0xFFC• 8 years ago

Stony Brook University is one of those special universities which although from an academic perspective not that famous, but in Systems software, they are top-notch university.

aportnoy• 8 years ago

Their grad math program is pretty good.

lostmsu• 8 years ago

Quick tip: this is about relational algebra's select operation (which is basically row filtering; choosing columns is called 'project' there).

espeed2• 8 years ago

To be precise, this is about the bitlevel SDS rank and select operation.

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

asdfasgasdgasdg• 8 years ago

I didn't get that impression at all. This is "get me the rank (index) of the first occurrence of x" in a succinct data structure. Nothing to do with relational algebra AFAICT except to the extent I suppose that some relational algebra implementations may use such data structures under the hood.

cmrdporcupine• 8 years ago

Yes, but 'select' is the name of that operation in the relational algebra. Which confuses some people whose first exposure to that model is through SQL, where the keyword implies a combination of 'select' and 'project'. I think the commenter's intent was to clarify that.

derf_• 8 years ago

I wondered why they used TZCNT instead of BSF. If their algorithm has correctly located the word with the jth bit set, the output of PDEP shouldn't be zero, and these should be equivalent (but BSF doesn't require a dependency on BMI1 support, though if you already require BMI2 for PDEP, maybe this doesn't matter).

But then I found <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50168>.

BeeOnRope3• 8 years ago

Aside from that bug, it's like you said: might as well use tzcnt from BMI1 if you are already using BMI2 since there are no CPUs implementing the latter but not the former (and IIRC the reverse is even true).

Using tzcnt in principle is faster than bsf in many cases since bsf always has a dependency on the output register (due to the zero input case), but tzcnt doesn't. In practice tzcnt had a false dependency anyways, at least until Skylake where that was fixed (again IIRC, I recall that one of these bit manipulation didn't have their false report fixed, but the rest did).

nkurz• 8 years ago

What did you think of their explanation of "memory parallelism" in section 4.3? I read it quickly, but thought it was pretty accurate. I liked that they made explicit the link between the number of instructions and the degree of parallelism. I was a little disappointed by the final statement that they "suspect" that the CPU is capable of only 8 parallel requests.

BeeOnRope3• 8 years ago

Just double checked and the false dependency problem is fixed for tzcnt and lzcnt, but not popcnt, in Skylake. So that's one (slightly) good reason to use tzcnt over bsf if possible, as of Skylake.

ot• 8 years ago

The authors claim their algorithm is novel, but it actually had been a well known folklore technique for quite a while. For example it was used in Folly as early as Jan 2016:

https://github.com/facebook/folly/commit/b28186247104f8b90cf...

stephencanon• 8 years ago

Yeah, I definitely saw this technique in Intel sample code demonstrating use of BMI before HSW was released. Probably 2011, maybe 2012.

That said, we worry too much about who the first person to have an idea was. Any idea worth having is come upon independently by many people, and putting the idea to work and communicating it to others are more valuable contributions anyway.

Veedrac• 8 years ago

Recently, Pandey et al. [15] gave a new implementation of machine-word select, which we call PTSelect.

It's worth noting Jukka Suomela had this PDEP idea late 2014, and I've used the trick a few times from that source.

https://stackoverflow.com/a/27453505/1763356

purplezooey• 8 years ago

I thought this was about select() with file descriptors, which also needs to be fast. :)

kolderman• 8 years ago

Oh that Select. Yawn.

skissane• 8 years ago

I was confused by the conference this is submitted to: "42nd Conference on Very Important Topics (CVIT 2016)." I couldn't find any such conference with such an odd name.

Eventually I worked it out. I think they are planning to submit this as a conference paper, but at the time of creating the preprint weren't sure which conference. So "Conference on Very Important Topics" is just a placeholder for where the actual conference/proceedings info would go on the article first page.

A Fast x86 Implementation of Select (2017) [pdf]

Related Stories