Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

icgrep (http://www.icgrep.com) has a clever approach to searching text for arbitrary sets of characters in a parallel manner. If 128-bit registers are available and we're processing 8-bit characters (for example), the next 128 characters from a file are first loaded into 8 SIMD registers. Then a bitwise transposition is performed so that r0 contains bit 0 of each input character, r1 contains bit 1, etc., up to r7. Then with a series of logic operations across those registers (imagine the sum-of-product result of a k-map of characters of interest), searches for any arbitrary subset of characters can be performed in parallel, leaving 1s in the corresponding position of the result register for each match and 0s elsewhere. icgrep supports full regex patterns and Unicode (using 21 registers instead of 8), but what interests me are the elegant transpose and logic steps.


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: