bugGNU nano - Bugs: bug #61799, inefficient string handling for...

 
 

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

bug #61799: inefficient string handling for long lines

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

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>
Project 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>

 

No files currently attached

 

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)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

     

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-01-12 bens SummaryInefficient string handling for long lines => inefficient string handling for long lines

    Back to the top


    Powered by Savane 3.7