1533032 - Extremely bad performance on scytale site

Status: NEW

(Core :: DOM: Core & HTML, defect, P2)

Description

[Boris Zbarsky [:bzbarsky]]

STEPS TO REPRODUCE:

1. Load https://www.cryptool.org/en/cto-ciphers/scytale
2. Try typing quickly in the "Plaintext" textarea.

EXPECTED RESULTS: Typing works, cyphertext appears in the "Encrypted text" textarea and the "Rendering" space.

ACTUAL RESULTS: Typing is very laggy, browser starts freezing up.

I did a profile, and we're spending tons of time notifying ranges during various editor and DOM operations.

I then added logging to the nsRange constructor and destructor, and every keypress in the "Plaintext" textarea allocates about 6700 ranges. That includes things like arrow keys. The ranges are deallocated fairly quickly, but definitely async; when typing I can easily get to a state where there are 150k+ live ranges.

I'm still investigating why all these ranges get allocated, but wanted to get this on file just in case.

Comment 1

[Olli Pettay [:smaug][[e-mail]]]

https://perfht.ml/2Tm2LA7

Comment 2

[Olli Pettay [:smaug][[e-mail]]]

FWIW, it is rather janky on Chrome too.

Comment 3

[Boris Zbarsky [:bzbarsky]]

So a few things going on here:

1. On every keyup on the plaintext, the site re-encrypts the plaintext. That leads to a bunch of .value += stuff calls on the "Rendering" textarea, like so:

            document.getElementById("railfence-display").value = "";
            for (var f = 0; f < p.length; f++) {
                document.getElementById("railfence-display").value += "| ";
                for (var u = 0; u < h; u++) document.getElementById("railfence-display").value += p[f].charAt(u) + " | ";
                document.getElementById("railfence-display").value += "\n"
            }

That looks like one value set per char of text, plus two value sets per line of rendering plus one overall set to "". For the default text, we have 35 chars and three lines (until we start typing), so that means 42 value sets. As we type, it should get worse.

2. Every .value += call ends up doing TextEditor::SetText which calls TextEditor::SetTextAsSubAction which does EditorBase::SelectEntireDocument which does Selection::Extend, which calls nsRange::CloneRange. That's one range created.

3. Selection::Extend also directly constructs a range for difRange.

4. TextEditor::SetText then does TextEditor::SetTextAsSubAction -> TextEditor::ReplaceSelectionAsSubAction -> ... -> TextEditor::DeleteSelectionWithTransaction -> DeleteRangeTransaction::DeleteRangeTransaction which clones another range.

5. Still continuing with the "delete selection" thing, we land in DeleteRangeTransaction::DoTransaction which calls Selection::Collapse, which creates another range.

OK, so that's 4 ranges, 42 value sets = 168 ranges. That's not 6000...

I guess the Selection::Extend issues are largely tracked by bug 1367744. The Selection::Collapse bit is bug 1365874.

Anyway, I actually measured how many .value sets happen on every keypress, and it's 1716, not 42. That matches the number of ranges I see created (1716 * 4 = 6864), but I don't quite understand why there are so many yet.

Comment 4

[Boris Zbarsky [:bzbarsky]]

I don't see much jank here in Chrome, fwiw. Certainly nothing like us (complete with slow script dialogs).

Comment 5

[Boris Zbarsky [:bzbarsky]]

Oh, the relevant JS file, by the way, is https://www.cryptool.org/_ctoApps/skytale/skytale-de.js. Which is of course minified.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Oh, I see. Each keypress does one call to process() but then each call to process() does a bunch of encrypt() calls. In fact it seems to do one call per character of cyphertext or so (!). In this case that's 35 calls. 35 * 42 = 1470, which is still not 1716, but at least approaching the right ballpark...

OK, so the site is pretty buggy, but our handling of it is still terrible. :(

Comment 7

[Boris Zbarsky [:bzbarsky]]

I tried to send a note to the website about the O(N^2) behavior. We'll see whether they fix that...

Comment 8

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

Selection::Extend issues are largely tracked by bug 1367744

Yeah, but I guess Selection::Extend() cannot be so fast since it requires to compare DOM points a lot. Therefore, as far as possible, we shouldn't use it in our code.

Comment 9

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

I avoided calling Selection::Extend() internally in most cases by fixing bug 1533293. How about the result? If it's not enough, I'll investigate TextEditor::DeleteSelectionWithTransaction() and DeleteRangeTransaction::DeleteRangeTransaction.

Comment 10

[Boris Zbarsky [:bzbarsky]]

I should probably wait until bug 1533293 relands...

Comment 11

[Boris Zbarsky [:bzbarsky]]

Just retested with bug 1533293 and things are not noticeably better...

The profile is at http://bit.ly/2FzppLA

One interesting thing I see in there is a bunch of time spent messing with the clipboard on every value set, afaict. See this stack: http://bit.ly/2Fw9Yny

Comment 12

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

(In reply to Boris Zbarsky [:bzbarsky, bz on IRC] from comment #11)

Just retested with bug 1533293 and things are not noticeably better...

The profile is at http://bit.ly/2FzppLA

Well, I need to work on DeleteRangeTransaction::DoTransaction()... And also, looks like that nsRange::SetSelection() is too expensive even though it's called when adding new range to a Selection.

One interesting thing I see in there is a bunch of time spent messing with the clipboard on every value set, afaict. See this stack: http://bit.ly/2Fw9Yny

Hmm...
https://searchfox.org/mozilla-central/rev/3d469329a42644b41e66944d8da22d78d8c0f5ec/layout/generic/nsFrameSelection.cpp#2819-2821

Comment 13

[Boris Zbarsky [:bzbarsky]]

Maybe we can keep track of whether the selection was already empty?

Comment 14

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

(In reply to Boris Zbarsky [:bzbarsky, bz on IRC] from comment #13)

Maybe we can keep track of whether the selection was already empty?

No idea because selection change notifications may be batched.

Comment 15

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

Oh, I realized that setting <textarea>.value wasn't optimized by bug 1358025. Looks like that I can do it without big patch.

Comment 16

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

According to http://bit.ly/2FzppLA, it spent in SetTextAsSubAction() 29% of the period but it's a slow path to setting new value from JS. Now, bug 1548751 is fixed, so, most of the time is saved by using the fast path.

Comment 17

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

Under editor, most time spends in mozilla::dom::CharacterData::SetData() and mozilla::dom::Selection::Collapse(). I think that Editor should save touching Selection in the future, but I have no idea for the former issue.

Comment 18

[Olli Pettay [:smaug][[e-mail]]]

I guess the site is now https://www.cryptool.org/en/cto/scytale ?
That is about equally bad in all the browsers. Chrome is perhaps worse and Safari keep queuing key events so that even after typing
they keep coming in for seconds.

https://share.firefox.dev/3WWvXdF

Flattening JS rope is taking quite a bit time, among other things