bugGNU nano - Bugs: bug #61799, colorizing very long lines can...

 
 

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

bug #61799: colorizing very long lines can take ages

Submitter:  easyaspi314 <easyaspi314>
Submitted:  Wed 12 Jan 2022 05:13:07 AM UTC
   
 
Severity:  3 - Normal Status:  Fixed
Assigned to:  bens Open/Closed:  Closed

Jump to the original submission

Fri 29 Apr 2022 07:34:08 AM UTC, comment #7: 

The bail-out at two thousand bytes has been released in nano-6.3.

Benno Schulenberg <bens>
Group administrator
Sun 03 Apr 2022 10:38:13 AM UTC, comment #6: 

The slowdown caused by coloring very long lines has been mitigated in git, commit fe42eb7a, by stopping to paint the line after two thousand bytes.

(If there are other things that need improvement, please file separate, focussed issues.)

Benno Schulenberg <bens>
Group administrator
Fri 01 Apr 2022 02:51:16 PM UTC, comment #5: 

As slightly more realistic reproduction recipe I use this:

for i in {1..888}; do printf '<tag data="%03d"/>' $i; done >looong.xml


As mitigation I propose the attached patch.  Lacking a proper solution, would something like this be good enough for you, Devin?

(file #53029)

Benno Schulenberg <bens>
Group administrator
Tue 22 Feb 2022 11:19:26 AM UTC, comment #4: 

Highlighting the entire string (before slicing it into displayable chunks) would require a complete rewrite of the coloring routines.  Assembling multiple rules into a single super-regex... I don't see how that could work -- how is nano to know whether rules may or may not overlap or recolor previously matched stuff?  Using fastmap... that works only with re_search() and we're not using that; and using it would require a complete rewrite of the coloring routines.

So...  It seems the only viable and easy way to reduce the coloring time of super-long lines is to do what vim does: stop coloring after a certain number of characters.  As a default terminal normally has 80 columns and 24 rows, I suggest we stop coloring after 2000 bytes.  What do you think?

Benno Schulenberg <bens>
Group administrator
Wed 12 Jan 2022 05:51:38 PM UTC, comment #3: 

Additionally, it seems like we can use the GNU extension re_compile_fastmap() to further increase performance, as that will skip over characters that don't match any rules.

easyaspi314 <easyaspi314>
Wed 12 Jan 2022 05:31:34 PM UTC, comment #2: 

When looking at the source code, it seems that we are highlighting each softwrapped line in draw_row() instead of highlighting the line before breaking it.

Since the regex loop has strnlen-ish functions in the main loop making it O(n^2), and we are calling it roughly n times, we end up with an O(n^3) loop which totally explains the 5 minute wait for it to highlight.

Meanwhile, if the entire line was highlighted beforehand, and the strnlen-ish calls in the regex loop were fixed, it should be O(n).

Another trick that could probably be done is to assemble a "super-regex" containing all rules concatenated together and do some group matching magic to find which rule matched which. Then, we only call regexec n times instead of nĂ—rules. However, I'm not entirely familiar about how regexec works.

As for limiting, it is to be noted that Vim bails after 3000 characters. However, Vim's rules are far more complex than nano's.

easyaspi314 <easyaspi314>
Wed 12 Jan 2022 03:05:24 PM UTC, comment #1: 

One possible mitigation for when syntax highlighting is slowing things down, is to say at the tenth or twentieth start match in a single line: "Fack it. I stop coloring. This is taking too long."  That is: add an iteration counter in the main while loop of 'step_two' and break out when counter > 10.  That will make the file look ugly, but...

Benno Schulenberg <bens>
Group administrator
Wed 12 Jan 2022 05:13:07 AM UTC, original submission:  

nano has performance issues on extremely long lines. While this isn't usually a noticable issue, it can affect the following:
 - minified source code (especially since syntax highlighting is usually involved)
 - text with long paragraphs that aren't hand wrapped (common in some styles of wikitext and markdown from what I heard)
 - Unicode files (since now it is spamming wcwidth())
 - Enabling and disabling softwrap on an open file where the effect is magnified

This is primarily due to the strcat problem, where many of nano's loops include unnecessary scans from the start of the string to the middle instead of starting in the middle. This results in loops that would theoretically be O(n) to become O(n^2).

The most noticeable slowdown is syntax highlighting, cursor movement near the end of lines, and softwrap.

This screencap shows the effect of softwrap and scrolling on a file generated from this script. Yes, it's on my phone. Watch the delay from when I press the softkey.

for i in {1..9999}; do
    printf '<x y="%04d"/>' $i >> test.xml
done

https://streamable.com/jkgmzz

When I enable the default XML syntax highlighting rules along with softwrap, nano locks up for a few MINUTES just loading that file. I can't even close it because nano is not polling inputs when it is stuck on these loops. (It does make timing it easy because I can just buffer ^X :P)

Meanwhile, if I wrap the same file to separate lines, it loads instantly and scrolls smoothly.

I am attempting to fix a slowdown with softwrap that eliminates the loading and page scroll lag, but it still lags on smooth scroll, the patch is buggy, and syntax highlighting is still the biggest culprit.

easyaspi314 <easyaspi314>

 

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

Attached Files
file #53029:  stop-coloring-at-4000.patch added by bens (421B - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by bens (Posted a comment)
  • -email is unavailable- added by easyaspi314 (Submitted the item)
  •  

    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 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-04-29 bens Open/ClosedOpen Closed
    2022-04-03 bens StatusReady For Test Fixed
        Summaryinefficient string handling for long lines colorizing very long lines can take ages
    2022-04-01 bens Attached File- Added stop-coloring-at-4000.patch, #53029
        StatusNone Ready For Test
        Assigned toNone bens
    2022-01-12 bens SummaryInefficient string handling for long lines inefficient string handling for long lines

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code