[TxMt] TM tokenizer is taking 100% CPU for long while using 100-200KB text files with single line
cskiadas at gmail.com
Wed Feb 27 15:50:34 UTC 2008
You missed the "line-based" part. This means that each regular
expression must be checked against each entire line. Unless I'm
mistaken, the time taken by any regexp mechanism is going to be much
more than linear in the length of the string, probably exponential in
the worst case. On the other hand, if you test it on strings of fixed
length, it will be linear on the number of strings tested, which is
the second case you described. In other words, when using a line-
based system it takes longer to process a single string, that to
process many strings of small length.
So it is not so much a question of compiling, the timing is very
different because newlines do matter, the parser matches single lines
via regular expressions. The longer the line, the harder it is to
determine if one of the regular expressions matches the whole line or
If the parser was ignoring newlines, it would mean that every regexp
would need to be tested against the entire document every single
moment. This would be an even worse slowdown.
Allan is certainly aware of this slowdown on long lines, it is
definitely in the top 5 complaints. If there was an easy solution,
that doesn't sacrifice on the richness of the highlighting and the
flexibility in user customization of it, it would probably have
already been implemented.
Department of Mathematics and Computer Science
On Feb 27, 2008, at 9:59 AM, Adam Strzelecki wrote:
>> But in TextMate the syntax highlighter (and more) is line-based and
>> works with regular expressions and not a precompiled lexer/parser,
>> yes, the line length does matter.
> I thought length doesn't matter ;)
> Anyway I'm not convinced :) I agree that precompiled lexer/parser
> is simply faster, however I don't see the point that regexp
> tokenizer works 1000x slower on file that has single 200'000
> characters line, rather than 20000 x 10 character lines (while both
> files are exactly same size,... ouch, faster one is slightly bigger
> because of extra \n ;P)
> I hope TM compiles its regular expressions just once, moreover
> execute single regexp made from merge of all regexp, rather all
> regular expressions separately.
> With this belief and fact that compiled regexp is an automaton
> similar to the one in pre-compiled parsers & lexers, line length
> shouldn't IMHO matter.
> So if it does, there's a place for optimization.
> Adam Strzelecki |: nanoant.com :|
More information about the textmate