bugGNU nano - Bugs: bug #62442, update_softwrapped_line() takes...


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

bug #62442: update_softwrapped_line() takes quadratic time

Submitted by:  easyaspi314 <easyaspi314>
Submitted on:  Wed 11 May 2022 03:58:59 PM UTC
Severity:  3 - Normal Status:  None
Assigned to:  None Open/Closed:  Open
* Mandatory Fields

Add a New Comment (Rich Markup)

Comment Type & Canned Response:


( Jump to the original submission )

Sun 15 May 2022 06:26:39 AM UTC, comment #9: 

I mentioned this a few times. Basically the primary problem with regex is that it is done inside the loop instead of outside.

When each partial line is displayed, nano will parse the entire string with regex again (from the start of the string, of course), just to paint the small amount that is visible on that line, which is obviously quadratic, and quadraticness aside, this is horribly inefficient due to how (relatively) slow regexec() is.

The solution would be to break up the line, print each subline, THEN paint over all the lines together.

One thing that would make things easier (and more efficient) would be to replace the wattron()/mvwaddnstr()/wattroff() dance with mvwchgat() which does effectively the same thing without redundantly painting over the string that was just printed.

-     wattron(midwin, varnish->attributes);
-     mvwaddnstr(midwin, row, col, thetext, paintlen);
-     wattroff(midwin, varnish->attributes);
+     mvwchgat(midwin, row, col, paintlen, varnish->attributes, varnish->pairnum, NULL);

This will eliminate the need for having the converted text available when printing regex, as long as we know the correct columns. Therefore, there can be no additional space complexity used.


As a smaller issue, the regexec loops are also quadratic themselves because of the actual_x() and wideness() calls from the beginning of the string. However, this can be fixed with some pointer/column arithmetic.

easyaspi314 <easyaspi314>
Fri 13 May 2022 03:31:44 PM UTC, comment #8: 

Yes, there is still a LOT of quadratic behavior to fix, namely in regex and all the actual_x/wideness/xplustabs calls. It is going to take a lot of work, especially with regex which would need a whole restructure.

easyaspi314 <easyaspi314>
Fri 13 May 2022 03:26:03 PM UTC, comment #7: 

Thanks.  After some quick tests, things seem to work fine.  With --atblanks, lines are softwrapped correctly at blanks.  <End> <End> goes first to the end of the row, and then to the end of the real line.  And spotlight_softwrapped() correctly spotlights things, also when crossing a softwrap boundary.

But the speed-up is less than I had hoped: rendering time at the end of a looong softwrapped line is about halved, from 300 ms to around 160 ms.  It's definitely better, but something is still being quadratic, because the rendering time increases on each PageDown on the same looong XML line.

Benno Schulenberg <bens>
Project Administrator
Thu 12 May 2022 05:38:43 PM UTC, comment #6: 

New patch is up, with the function name now changed to next_softwrap_breakpoint, reverting the function with the original behavior to the old name.

Nothing else changes.

(file #53192)

easyaspi314 <easyaspi314>
Thu 12 May 2022 04:03:54 PM UTC, comment #5: 

Savannah really needs an edit feature :(

I can change that.

In the meantime, since I am not really familiar with how these features are supposed to behave, do atblanks, do_end, and spotlight work correctly?

easyaspi314 <easyaspi314>
Thu 12 May 2022 03:32:37 PM UTC, comment #4: 

Correction: update_softwrapped_line -- reading is hard.

Benno Schulenberg <bens>
Project Administrator
Thu 12 May 2022 03:31:20 PM UTC, comment #3: 

It is far from pretty.  :)  One improvement would be is to rename the new get_softwrap_breakpoint() function, because you change its parameters anyway, so that the wrapper function can keep the old name, so that the calls that do not need optimization do not need to be changed.  It makes the patch smaller.

To rephrase the explanation of the observed slowness but now with the correct names of the functions: update_softwrap_line() takes quadratic time because each cycle through its main loop calls get_softwrap_breakpoint() from the very start of the line, instead of resuming from where the last chunk ended.

Benno Schulenberg <bens>
Project Administrator
Thu 12 May 2022 05:04:53 AM UTC, comment #2: 

I created a patch, which I believe to still be a work-in-progress. It isn't the prettiest solution by any means.

Basically, it gives output parameters for the advanced text pointer and the actual start column, which can be reused to make the loops that use it linear instead of quadratic.

It hasn't been thoroughly tested, but this was better than my previous attempts which had issues with the off-by-one.

This makes it so flick scrolling through my single 19kB line of XML **with syntax highlighting off** is a fluid 60fps instead of choking after a few lines.

(file #53188)

easyaspi314 <easyaspi314>
Wed 11 May 2022 05:07:10 PM UTC, comment #1: 

Argh. I'm sorry, I got the function names mixed up.

update_softwrap_breakpoint itself is quadratic, because get_softwrap_breakpoint is linear from the start of the string, which is the function I meant.

Notably, this is called a LOT from various places, most notably scrolling.

The attached files are the output of gprof (with a visual version from gprof2dot which illustrates much better) from rapidly scrolling down on my touchpad in winio.c for a few seconds with softwrap, no syntax, and a 77 column wide terminal.

(file #53186,

easyaspi314 <easyaspi314>
Wed 11 May 2022 03:58:59 PM UTC, original submission:  

Not exactly sure how to fix this, as the math is really weird.

update_softwrap_breakpoint() scans from the start of the string, and most loops call this for each line breakpoint, so it ends up being quadratic.

This could, in theory, be solved by saving where the current column is in terms of bytes, similar to how advance_over() works.

I was attempting this, but I kept getting off-by-one errors.

This is likely due to this weirdness where it sometimes returns column and other times returns column - 1. I really don't understand why this is the case.

        /* If we didn't overshoot the limit, we've found a breaking point;
         * and we've reached EOL if we didn't even *reach* the limit. */
        if (column <= goal_column) {
                *end_of_line = (column < goal_column);
                return column;
        // ...

        /* Otherwise, break at the last character that doesn't overshoot. */
        return (editwincols > 1) ? breaking_col : column - 1;

easyaspi314 <easyaspi314>


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

Attach Files:

Attached Files
file #53186:  gprof.txt added by easyaspi314 (54KiB - text/plain - gprof output and visualization from gprof2dot)
file #53187:  output.png added by easyaspi314 (135KiB - image/png - gprof output and visualization from gprof2dot)


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.

    Only logged-in users can vote.





    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-05-12 easyaspi314 Attached File- => Added 0001-Reduce-quadratic-loops-in-softwrap-code.patch, #53192
    2022-05-12 bens Summaryupdate_softwrap_line() takes quadratic time => update_softwrapped_line() takes quadratic time
    2022-05-12 bens Summaryupdate_softwrap_breakpoint loops are quadratic => update_softwrap_line() takes quadratic time
    2022-05-12 easyaspi314 Attached File- => Added 0001-WIP-Reduce-redundant-string-scanning-in-softwrap.patch, #53188
    2022-05-11 easyaspi314 Attached File- => Added gprof.txt, #53186
        Attached File- => Added output.png, #53187

    Back to the top

    Powered by Savane 3.9