3 ms·
You can write code to compare strings without branches. Imagine comparing one string to every string in a database column. Pad to a fixed size first (if you fin
by zlynx 10y ago
You can write code to compare strings without branches. Imagine comparing one string to every string in a database column. Pad to a fixed size first (if you find an ambiguous match later you can do a full string compare then). Subtract the strings, aka compare, and store the result. At the end of all the commparisons you have a memory structure of negative, zero, or positive values. Then you can do something with the matching values.
There have been some very sweet algorithms for doing B+ tree searches for Itanium and for AVX and those work just as well, if not better on GPU.
With some thinking, branch operations can be converted into math and applied to masses of data without checking for branch conditions. This wastes some work but is still faster than branching.
- hendzen 10y agoThat sounds like an interesting technique - but it unfortunately does not apply on a majority of real-world data. In particular I mean sorting non-English text which any serious database needs to be able to do. Subtracting characters doesn't work when you're dealing language specific Unicode collation [0]. [0] - http://www.unicode.org/reports/tr10/ http://www.unicode.org/reports/tr10/
- zlynx 10y agoYeah, well, you just can't do it that way and be fast at the same time. I mean seriously fast. What you can do is decide how your comparison should be collated and preprocess your strings into a sort key form that is strictly big-endian binary (first byte has highest weight). Or little-endian I suppose, whichever works best for your hardware. Your sort key doesn't have to be the actual string.