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

Submitter:  easyaspi314 <easyaspi314>
Submitted:  Wed 11 May 2022 03:58:59 PM UTC
   
 
Severity:  3 - Normal Status:  Fixed
Assigned to:  bens Open/Closed:  Closed

Jump to the original submission

Wed 20 Jul 2022 12:25:13 PM UTC, comment #12: 

Patch (file #53192) has been applied to master, commit 0e9bef34.  This fixes the main actionable part of this issue.  If there are other parts you want to have addressed, please file a new issue.

Benno Schulenberg <bens>
Group administrator
Sun 17 Jul 2022 07:22:02 AM UTC, comment #11: 

Hi Devin,

Coming back to your patch (file #53192).  I was reluctant to apply it as I didn't like having to declare two extra variables in various places that didn't actually get used in the places where they were declared.  And I didn't like the name 'real_col' as it doesn't express that it corresponds to where *text is pointing.

So, finally I rewrote the patch: changing two variables of get_softwrap_breakpoint() to be static, using a single parameter to trigger the initialization of those two variables, and without using a wrapper function as it takes fewer lines and doesn't add another function name.  See the attached file.  What do you think?

(file #53447)

Benno Schulenberg <bens>
Group administrator
Sun 22 May 2022 09:21:24 AM UTC, comment #10: 

What I don't understand is: why does mvwchgat() need both the attributes and the pairnum while the three-function dance uses just the attributes.  But if this reduction in number of function calls actually improves things -- and mvwchgat() does not call wattron() and mvwin() and wattroff() and such internally) -- then please provide a patch that makes the relevant changes.

Benno Schulenberg <bens>
Group administrator
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>
Group 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>
Group 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>
Group 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.)

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.

     

    Follow 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-08-03 bens Open/ClosedOpen Closed
    2022-07-20 bens StatusReady For Test Fixed
    2022-07-17 bens Attached File- Added 0001-display-remember-text-and-column-positions-when-soft.patch, #53447
        StatusNone Ready For Test
        Assigned toNone bens
    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.13-758e.
    Corresponding source code