4 ms·

As far as I know, grep uses Boyer-Moore for string matching when possible. Giving a variable char size encoding such as UTF8, plain Boyer-Moore isn't possible,

As far as I know, grep uses Boyer-Moore for string matching when possible. Giving a variable char size encoding such as UTF8, plain Boyer-Moore isn't possible, but it is the asymptotically faster algorithm known. Hence even perfect versions of grep will slower by arbitrarily large factors, depending on the input. So while there may be problems, expecting no difference or no significant difference between encodings is not correct either

dexen 15y ago
> Giving a variable char size encoding such as UTF8, plain Boyer-Moore isn't possible (...) That you get UTF-8 input and produce UTF-8 output doesn't imply you are better off using UTF-8 for processing. Translating UTF-8 to fixed-width UTF-32 and back is of linear complexity and takes small, fixed amount of memory. The only trade-off is when processing /very/ long lines -- up to four time more memory would be used for buffer. As mentioned in other posts, Unicode requires normalization of certain character combinations into other characters, so you'll be processing all input characters anyway. Just prefix an extra step to it, not even a separate loop. And so you can do Boyer-Moore with Unicode at very little extra cost :-) Some text-intensive programs of Plan 9, including grep, use internally fixed-widht format called `Rune' for unicode, exactly for reasons of performance. UTF-8 input is translated into strings of Runes for processing and translated back for output.
- deleted 15y ago
  [deleted]
  - deleted 15y ago
    [deleted]