bugGrammatica - Bugs: bug #3603, Tokenizer: Improve processing speed


You are not allowed to post comments on this tracker with your current authentication level.

bug #3603: Tokenizer: Improve processing speed

Submitter:  Per Cederberg <cederberg>
Submitted:  Wed 14 May 2003 03:54:17 PM UTC
Severity:  5 - Major Item Group:  Future Improvement
Status:  Fixed Assigned to:  cederberg
Open/Closed:  Closed

Discussion locked!

Sat 14 Mar 2009 09:35:05 AM UTC, comment #4: 

Version 1.5 was released on 2009-03-07. Closing this issue.

Per Cederberg <cederberg>
Group administrator
Tue 24 Feb 2009 10:01:54 PM UTC, comment #3: 

The NFA implementation has landed in trunk (for version 1.5). Further quick gains in tokenizer processing speed seems improbable.

Per Cederberg <cederberg>
Group administrator
Fri 19 Mar 2004 10:17:42 AM UTC, comment #2: 

Pending the implementation of a DFA or NFA. Dependency on bug #8202 added.

Per Cederberg <cederberg>
Group administrator
Mon 26 May 2003 07:22:02 AM UTC, comment #1: 

The worst performance problems are associated with the
greedy and reluctant quantifiers, as they need to support
backtracking. When the tokenizer buffer doesn't contain a
complete match, a quantifier regular expression will
backtrack until all possibilities have been evaluated. The
backtracking cannot be removed, as regular expressions such
as "a*a" must be allowed.

In order to avoid the backtracking, and thus improve
performance, the possessive quantifiers can be used
instead. These are the '*+' and '++' quantifiers that
only match the maximum number of characters.

Per Cederberg <cederberg>
Group administrator
Wed 14 May 2003 03:54:17 PM UTC, original submission:  

There are probably still substantial parsing speed improvements to gain by improving the tokenizer performance. All the obvious optimizations have already been done, however. The next step is probably to create a DFA.

Per Cederberg <cederberg>
Group administrator


(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

No files currently attached


   bug dependencies.

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by cederberg (Posted a comment)

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.


    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2009-03-14 cederberg Open/ClosedOpen Closed
        Discussion LockNone Locked
    2009-02-24 cederberg StatusNone Fixed
        Assigned toNone cederberg
    2004-03-19 cederberg Dependencies- Depends on bugs #8202

    Back to the top

    Powered by Savane 3.13-4b48.
    Corresponding source code