lexing algorithm is O(n^2) #3

New issue

Closed

opened 2021-01-27 05:59:33 +13:00 by nbryant42 · 1 comment

nbryant42 commented

2021-01-27 05:59:33 +13:00

(Migrated from github.com)

The lexing algorithm appears to be O(n^2) due to this snippet around line 93:

        # Are we at the end of the string?
        if String.length(string) == len do
          { :ok, Enum.reverse lexer.tokens }
        else
          { _ , new_string } = String.split_at string, len
          do_lex module, rules, new_string, lexer
        end

It appears that this calls String.length() on an input length that grows to the full input source; so, on average, that's half the input source, every time a token is consumed. It appears to take about 18 seconds of CPU time to analyze a 1,000-line source file in the custom DSL I'm implementing.

The lexing algorithm appears to be O(n^2) due to this snippet around line 93: ``` # Are we at the end of the string? if String.length(string) == len do { :ok, Enum.reverse lexer.tokens } else { _ , new_string } = String.split_at string, len do_lex module, rules, new_string, lexer end ``` It appears that this calls String.length() on an input length that grows to the full input source; so, on average, that's half the input source, every time a token is consumed. It appears to take about 18 seconds of CPU time to analyze a 1,000-line source file in the custom DSL I'm implementing.

jimsynz commented

2021-01-27 08:56:52 +13:00

(Migrated from github.com)

Oh yeah. That's super dumb. Should be easy enough to fix. Thanks for your report.