nsXULKeyListenerImpl::HandleEventUsingKeyset is inefficient

VERIFIED FIXED in M18

Status

()

P3
normal
VERIFIED FIXED
19 years ago
10 years ago

People

(Reporter: waterson, Assigned: hyatt)

Tracking

({perf})

Trunk
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [nsbeta3+][pdtp3]WORK IN PROGRESS, URL)

(Reporter)

Description

19 years ago
This method is very inefficiently implemented, and accounts for 20-25% of typing
time in a small text document. The inefficiency stems from the fact that it is
called once for each key down, press, and up event, and will walk the entire
<keyset> using the DOM APIs for each event! (The worst case scenario ends up
being the common case, where the key has *no* binding.)

Hyatt and I discussed, and believe that lazily constructing an in-memory table
of the keybindings the first time this method is invoked would be an enormous
win (probably could drive this function down to near zero).

It's a fairly straight-forward, encapsulated task.
(Reporter)

Updated

19 years ago
Keywords: perf
(Reporter)

Comment 1

19 years ago
cc'ing dprice, who was interested in looking into it...

Comment 2

19 years ago
nominating for nsbeta3, reassigning to hyatt.  Could anyone else (e.g., dprice)
do this if you're overloaded?
Assignee: trudelle → hyatt
Keywords: nsbeta3
Target Milestone: --- → M18
(Assignee)

Comment 3

19 years ago
Maybe dr would want to tackle this?
(Assignee)

Comment 4

19 years ago
This is a pretty neat and self-contained bug.  Assigning to dr so he has at 
least one fun bug to work on. :)

waterson or I can help you out with this one as needed.
Assignee: hyatt → dr

Updated

19 years ago
Status: NEW → ASSIGNED

Comment 5

19 years ago
There are already numerous bugs citing user perception of slowness in typing,
and metrics for particular usage cases.  I think we need to fix this, and 20-25%
is enough of the problem to make optimization worthwhile.  Should coordinate
with other folks working on this area.

Updated

19 years ago
Whiteboard: [nsbeta3+]

Comment 6

18 years ago
attempting to coordinate with sfraser of bug 6259 and a couple others...

Comment 7

18 years ago
sfraser, re: 6259: "The aim of this bug was to implement a key handling
optimization that was in 4.x, which was to look ahead in the native event queue
for key presses, and handle them all at one time. It it not clear to me that we
need this optimization in Mozilla. It should be treated independently of 47395."

and there you have it.

Comment 8

18 years ago
still trying to understand this code... could also be
LocateAndExecuteKeyBinding()...

Comment 9

18 years ago
I think there are also a bunch of string comparisons done in a tight loop in
these functions -- if so, eliminating the string comparisons and replacing them
with atoms or keycodes could be a big win.  Hint, look for the comment that
says:
        // This is gross -- we're doing string compares
        // every time we loop over this list!

Comment 10

18 years ago
akkana -- yeah, hyatt just helped me come up with a plan:

Every window has its own keybindings, in addition to a bunch of weird global
keybindings for if they're a browser or editor window (which ought to be in xbl,
but at some later date). HandleEventUsingKeyset gets passed the keybindings (and
knows about the global keybindings because they're a static member), and
traverses them each time. Instead, we're going to hash them on first use into a
static member, and then the only comparisons would be in using the hash (O(1),
with no string comparisons -- should make things suck much less).

The conceivable bug this could cause would be, that if the DOM for the
keybindings gets modified in any one of the windows, then the hash would not be
up to date, and if the /static/ cache were kept up to date, it would mess up the
rest of the windows which use it. So, once I get the simple solution working,
i'll add some code to make per-instance copies as needed (copy-on-write) in the
rare case that the keyset stuff does get mucked with at runtime.

Updated

18 years ago
Blocks: 50440

Updated

18 years ago
Blocks: 51233

Comment 11

18 years ago
Hyatt made changes to XBL keylisteners recently which are much more efficient
than the XUL keylistener code. The browser and editor bindings files are
currently hardcoded XUL, and therefore use this sucky code, so what we'll
probably end up doing is migrating them to XBL. That won't make the code here
any better, but will make it cycle through fewer cases (fewer string
comparisons, nsCOMPtr traversals, and so forth) and make it much less of a
concern for overall performance. We'll fix it the right way later.

beta3-, per trudelle.
Summary: nsXULKeyListenerImpl::HandleEventUsingKeyset accounts for 20-25% of typing time → nsXULKeyListenerImpl::HandleEventUsingKeyset is inefficient
Whiteboard: [nsbeta3+] → [nsbeta3-]
Target Milestone: M18 → Future

Comment 12

18 years ago
I agree that converting to use XBL would be a better fix.  But is that being
pulled back into nsbeta3 (or at least before FCS), or does this mean that we can
no longer hope for performance help for our poor typing performance?

Comment 13

18 years ago
Per beppe@netscape.com, removing nsbeta3- and TM, this can't be futured. This is
a significant performance hit. We need to take care of this before RTM.

I commented out nsXULKeyListenerImpl::HandleEventUsingKeyset() and found typing
to be much faster. On windows, mjudge did some profiling and found that 25% of
the time it took to process the keypress was spent in
nsXULKeyListenerImpl::HandleEventUsingKeyset().
Whiteboard: [nsbeta3-]
Target Milestone: Future → ---

Comment 14

18 years ago
We either need this, or the switch to XBL.  If the switch to XBL can happen in
time, that would be better still (then this bug would no longer apply).

Comment 15

18 years ago
Yeah, we haven't migrated the XUL browser and editor bindings to XBL yet (bug
52359), so this method is still doing an awful DOM tree traversal with lots of
string comparisons at each node. Commenting this method out would obviously
speed things up (but then of course you don't get your keybindings), but
migrating to XBL will make the data set which this function operates on minimal.

Uh, or "yeah, what Akkana said."

Comment 16

18 years ago
Actually, converting to XBL will be incredibly difficult, because lots of event
targeting and ordering stuff needs to get hacked for that to work...
*cough*regressions*cough*

This bug may be necessary for beta3 or at least RTM...
Priority: P3 → P2

Comment 17

18 years ago
nsbeta3+, p2 for M18.
Whiteboard: [nsbeta3+]
Target Milestone: --- → M18

Updated

18 years ago
Blocks: 48758

Comment 18

18 years ago
spam:  added self to cc list.

Comment 19

18 years ago
PDT would like to have some quantifiable way to describe the performance
problem. On the Win32 build, for example, typing speed for small documents is
acceptable for RTM.

Comment 20

18 years ago
Did you try Mac and linux typing performance? Perhaps PDT should have one of each 
kind of machine in their meeting, and test bugs on all 3, so XP status could be 
more quickly determined.

Comment 21

18 years ago
work in progress on this. hyatt is merging code for xul and xbl keylisteners as
part of 48758. reassigning.
Assignee: dr → hyatt
Status: ASSIGNED → NEW
Whiteboard: [nsbeta3+] → [nsbeta3+]WORK IN PROGRESS

Comment 22

18 years ago
phil, sfraser: cross-platform, this function comprises 25% of typing time. on
linux, this function is significantly slower (mjudge quantified it at around
90%, which is why linux typing performance has been reported as unacceptable).
Status: NEW → ASSIGNED

Comment 23

18 years ago
I find it very hard to believe that the linux performance profile is so 
different. Are different tools giving us different data?

Comment 24

18 years ago
On my linux debug build, typing speed is approx. 2-3 chars/second.  It's faster
on optimized builds (enough that I'm not sure how to time it with a stopwatch --
suggestions?), but still slow enough that it can't keep up with typing and would
be an embarrassment to ship.

The timing of the slowdown coincided with a big nsString landing, jprof shows
nearly all of typing time being spent in string functions, and the known
performance problem involves doing excessive numbers of string comparisons. 
Given that strings are known to be implemented differently on linux from the
other platforms (because linux doesn't support ucs-2 natively and so conversions
have to be done at runtime), is it really surprising that there might be a big
difference in performance?

Comment 25

18 years ago
PDT: please note that at least one PDTP1 bug has cited this as a dependency.

Comment 26

18 years ago
pdtp3 on its own merits, but we understand if it gets checked in with 48758.
Priority: P2 → P3
Whiteboard: [nsbeta3+]WORK IN PROGRESS → [nsbeta3+][pdtp3]WORK IN PROGRESS
(Assignee)

Comment 27

18 years ago
Fixed.
Status: ASSIGNED → RESOLVED
Last Resolved: 18 years ago
Resolution: --- → FIXED

Comment 28

18 years ago
verified fixed. In my linux debug build, update of the text in composer
keeps up with keypresses no matter how fast I enter text, or in an HTML
textarea. (Note typing is slow when in the bugzilla form pages but that
is a different bug -- bug 51392).
Status: RESOLVED → VERIFIED

Updated

10 years ago
Component: XP Toolkit/Widgets: XUL → XUL
QA Contact: jrgmorrison → xptoolkit.widgets
You need to log in before you can comment on or make changes to this bug.