News for hackers. Stuff that matters.
Re:Rejit - prototype of a non-backtracking, just-in-time, SI... by tambourine_man on Monday August 26, 2013 @11:21AM (#6277598)
Whenever I see something like this, I'm always reminded of this great post:

http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...

Re:Rejit - prototype of a non-backtracking, just-in-time, SI... by adobriyan on Tuesday August 27, 2013 @05:20AM (#6282369)
Even the dumbest SSE2 based code will kick the living shit out of any byte-at-a-time super-optimized grep.

> we shall make a one gigabyte file with one thousand x's per line, and time grep searching for "yy" (a two character best case) and "yx" (a two character worst case).

In this case SSE based code will be a) several times faster because SSE loads will be used, b) time difference between "yy" and "xx" cases will be minimal (several ticks to accumulate result from second PMOVMSKB+PCMPEQB combo and c) time of search will be background-independent.

Paraphasing Linux CodingStyle text, first off, I'd suggest printing out a copy of the "why GNU grep is fast", and NOT read it. Burn them, it's a great symbolic gesture.

The trivial exercise is to disassemble x86-64 version of glibc memchr(3) and try to outperform it with byte-at-a-time based code.

Hint: you won't be able to do it.

Re:Rejit - prototype of a non-backtracking, just-in-time, SI... by rames on Monday August 26, 2013 @01:21PM (#6278391)
Note that I didn't chose the worst case for grep. But probably not the best either. First thing I tried just now:

$ time grep -R "yoyo\|regexp" linux-3.10.6 > /dev/null real 0m2.138s user 0m1.875s sys 0m0.252s

$ time jrep -R "yoyo|regexp" linux-3.10.6 > /dev/null real 0m0.411s user 0m0.135s sys 0m0.270s