O(n*n) performance on long lines

[Martin Dorey]

I imagine this is not really a surprise but being able to call it definitively O(n*n), rather than just "painfully slow", might encourage action.  For something painfully slow, I'd want to think about how we could make it better.  For something O(n*n), I'd accept a hard-coded limit.

martind@swiftboat:~$ for meb in $(seq 0 4); do DEBUGGING_TERMINATOR=y \time -p terminator -e ruby -we 'puts("_" * 1024 * 1024 * '$meb')' 2>&1 | grep real | cut -f2 -d" " | xargs --replace echo $meb,'{}'; done

0,3.45

1,5.11

2,9.99

3,19.01

4,30.98

martind@swiftboat:~$

x: mebibytes

y: seconds

blue: actual

pink: mebibytes squared * 1.65 + 3.45

Pasting graphs from Gnumeric straight into Gmail, whatever next.  I see Phil's right about Linux changing but, heh, I have the opposite reaction.

[Phil Norman]

Hi

This is running terminator with it displaying a massive horizontal line of underscores? If so then yes, the complexity of expanding a row like that is hideous. I think there's even a to-do in the code about it. It's because a line of text in terminator is a list or array of character things, and as the list grows it keeps copying the contents. Also the operations on the list are most likely linear in the length of the list.

Maybe it's time I looked at fixing it. It's been over ten years since I knew about the problem.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to terminator-use...@googlegroups.com.
To post to this group, send email to terminat...@googlegroups.com.
Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

[Phil Norman]

I had a play this evening, and figured out a simple way of solving this problem. Java can't display anything more than 32768 pixels wide with any reliability anyway, so I've simply told Terminator to drop character that go over that limit.

If you happen to trigger this limitation, and scroll far enough to the right, you should see a nice 45 degree warning about truncated text, just so we don't silently swallow anything without at least warning people.

Cheers,

Phil

On 17 July 2018 at 22:31, Phil Norman <phil...@gmail.com> wrote:

Hi

This is running terminator with it displaying a massive horizontal line of underscores? If so then yes, the complexity of expanding a row like that is hideous. I think there's even a to-do in the code about it. It's because a line of text in terminator is a list or array of character things, and as the list grows it keeps copying the contents. Also the operations on the list are most likely linear in the length of the list.

Maybe it's time I looked at fixing it. It's been over ten years since I knew about the problem.

On Tue, 17 Jul 2018, 21:13 Martin Dorey, <marti...@gmail.com> wrote:

I imagine this is not really a surprise but being able to call it definitively O(n*n), rather than just "painfully slow", might encourage action.  For something painfully slow, I'd want to think about how we could make it better.  For something O(n*n), I'd accept a hard-coded limit.

martind@swiftboat:~$ for meb in $(seq 0 4); do DEBUGGING_TERMINATOR=y \time -p terminator -e ruby -we 'puts("_" * 1024 * 1024 * '$meb')' 2>&1 | grep real | cut -f2 -d" " | xargs --replace echo $meb,'{}'; done

0,3.45

1,5.11

2,9.99

3,19.01

4,30.98

martind@swiftboat:~$

x: mebibytes

y: seconds

blue: actual

pink: mebibytes squared * 1.65 + 3.45

Pasting graphs from Gnumeric straight into Gmail, whatever next.  I see Phil's right about Linux changing but, heh, I have the opposite reaction.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-users+unsubscribe@googlegroups.com.
To post to this group, send email to terminator-users@googlegroups.com.

[Martin Dorey]

Thanks, though am I right in thinking that'll truncate copy and paste of longer lines?  A 32 KiB line isn't very long - I've had recent reason to deal with 8 MiB lines - and I imagine each character is considerably more than one pixel.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-use...@googlegroups.com.
To post to this group, send email to terminat...@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-use...@googlegroups.com.
To post to this group, send email to terminat...@googlegroups.com.

[Phil Norman]

Hi

Yes, it will. We could change it so it only reduces the display, but keeps the text. Then triple-click would select everything but you just wouldn't see it. How does that sound?

Cheers,

Phil

[Martin Dorey]

Would that mean that Alt-F would still let me find text there, though it would be hidden under the watermark?  That might save me from making mistakes too.  Yeah, this is sounding good.

[Phil Norman]

It could let you find text there, but it'd be tricky to show it, as it'd be off the right-hand edge of the screen. How about, if you jump to a found thing which is off-screen, we scroll the visible area to the closest we can get to (remaining within 32k pixels of the origin), but instead of showing a highlight bit of text, we show some kind of yellow arrow, indicating "it's thataway"? That would be relatively easy to do.

The alternative would be to have some way of showing text off the screen, which is feasible but much more code, and I'm not sure quite how to make it look good and natural.

Had you ever considered piping through fmt?

Oh, there is one alternative solution, which might be quite simple. Rather than never inserting unwanted line-breaks, we could relax that policy a little, and auto-insert them when we get close to the 32k horizontal width. That might mess up 'find' though, for cases where a possible match straddles lines.

Ideas?

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-users+unsubscribe@googlegroups.com.
To post to this group, send email to terminator-users@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-users+unsubscribe@googlegroups.com.
To post to this group, send email to terminator-users@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-users+unsubscribe@googlegroups.com.
To post to this group, send email to terminator-users@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-users+unsubscribe@googlegroups.com.
To post to this group, send email to terminator-users@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-users+unsubscribe@googlegroups.com.
To post to this group, send email to terminator-users@googlegroups.com.

[Martin Dorey]

I don't think I'm bothered about showing it, just about knowing that there was something worth looking at with eg fmt.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-use...@googlegroups.com.
To post to this group, send email to terminat...@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-use...@googlegroups.com.
To post to this group, send email to terminat...@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-use...@googlegroups.com.
To post to this group, send email to terminat...@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-use...@googlegroups.com.
To post to this group, send email to terminat...@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-use...@googlegroups.com.
To post to this group, send email to terminat...@googlegroups.com.

Visit this group at https://groups.google.com/group/terminator-users.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "terminator-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to terminator-use...@googlegroups.com.
To post to this group, send email to terminat...@googlegroups.com.