News for hackers. Stuff that matters.
Re:2000x performance win by Nitramp on Saturday December 10, 2011 @08:54AM (#3337566)
Does anyone understand what the bug in grep was?

UTF-8 regular expression matching shouldn't be different from ASCII at all, as far as I can tell. In UTF-8, every byte by itself can be identified as a start byte or trail byte, so if you want to match a regular expression, you don't even have to care about UTF-8 in any way. Any legal character in the regexp you want to look for can only match at a legal character start in the haystack.

Re:2000x performance win by EdiX on Saturday December 10, 2011 @09:43AM (#3337642)
> UTF-8 regular expression matching shouldn't be different from ASCII at all, as far as I can tell.

Not really. First the '.' operator needs to work differently. This can be still done fast, but if you actually want to claim unicode support you should also consider:

- Unicode collation orders

- Unicode string equivalence algorithms

- Unicode normalization algorithms

This will also take care of all the unicode weirdnesses that no one actually uses or cares about but you still must implement to claim compatibility like: presentational forms, combining diacritics, ligatures, double sized characters and other odd stuff.

Re:2000x performance win by 4ad on Saturday December 10, 2011 @09:12AM (#3337590)
GNU grep uselessly converts UTF-8 to some multibyte char internal representation.

You are completely right, matching regular expressions with UTF-8 text is the same as with ASCII text, one of the reasons why UTF-8 is so good.

Re:2000x performance win by omgtehlion on Saturday December 10, 2011 @09:14AM (#3337597)
You both are wrong. If you take arbitrary byte in ascii stream you can be sure that this is a whole char, but if you take arbitrary byte in utf-8 stream you can get a start of a char / end of char / or whole char.
Re:2000x performance win by 4ad on Saturday December 10, 2011 @09:22AM (#3337607)
Obviously choosing an arbitrary offset in the byte stream might not align on rune boundary, but UTF-8 is great because you can determine that. You can determine the start/end boundaries in any subset of the byte stream, as opposed to most other encodings.

The issue is completely unrelated to the fact that matching regexps in UTF-8 text is the same as matching regexp in ASCII text. The regular expression tool doesn't even need to care that the text is UTF-8. It's just byte comparisons, the tool doesn't even need to be aware of rune boundaries.

Re:2000x performance win by colomon on Saturday December 10, 2011 @09:42AM (#3337641)
Don't some of the common cases of searching require the ability to quickly skip forward N characters for high efficiency? That's simple pointer arithmetic in the ASCII case, but requires reading each byte skipped in UTF-8, right?

(I'm particularly thinking of Boyer-Moore -- http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sear... -- but I'm sure there are other examples as well.)

Re:2000x performance win by _delirium on Saturday December 10, 2011 @12:53PM (#3338014)
> It's just byte comparisons

If it's just doing byte comparisons, then the tool isn't properly implementing http://en.wikipedia.org/wiki/Unicode_equivalence, unless it can assume that all input text was already normalized.

Re:2000x performance win by omgtehlion on Saturday December 10, 2011 @09:37AM (#3337633)
just look into grep’s sources. it has loads of low-level optimizations to make string search faster. But all these optimizations work only with exact-witdth encodings, thats why it is related.

P.S.: and sometimes there are a lot of problems with lower and upper-case letters http://www.gnu.org/s/grep/devel.html

Re:2000x performance win by vilya on Saturday December 10, 2011 @09:45AM (#3337645)
Character classes would trip you up, I think. e.g. \w for word characters.