311524 - E4X is slow in building nodes compared to DOM

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect)

Description

[Eric Murphy]

I have attached an example that runs JavaScript to add 5000 <li> to an <ol>. The
DOM code many times faster than the E4X code.

I would guess that E4X is just a fancy wrapper for the DOM interfaces. Why is
this wrapper such a perf problem?

Comment 1

[Eric Murphy]

Attachment: E4X vs. DOM. Change onload parameter to switch modes.

Comment 2

[Brendan Eich [:brendan]]

The problem is that E4X is *not* a layer on top of the DOM APIs.  See bug 270553.

/be

Comment 3

[Brendan Eich [:brendan]]

Attachment: testcase showing workaround, or fix, really

Extract xmlOl.li once before the loop.	Evaluating that expression in the loop
creates an XMLList per iteration, each time with one more child, for O(n^2)
growth rate.  Don't do that, it's not going to be fast in any E4X
implementation.

An optimizer that knew enough about the runtime namespaces might be able to
hoist this for you, but it would be "hard".

I'm inclined to mark this bug INVALID.

/be

Comment 4

[Brendan Eich [:brendan]]

Comment on attachment 198816 [details]
testcase showing workaround, or fix, really

Note the Date.now() timestamping changes too.

/be

Comment 5

[Eric Murphy]

It's amazing that "var li = xmlOl.li;" now makes the code nearly twice as quick
with 5000 items. Logically, I would define it as a workaround, but I just
started working with E4X today. I understand your comment, however.

Pushing it up to 20,000 items the perf difference between the two is not much,
with E4X a bit faster.

Pushing it to 30,000 items with the E4X mode ***crashes*** Firefox for me.

I have to ask, why not implement something like this using an instance of the
DOM? I would imagine it to be more simple and robust. I looked that the E4X
code, and it's not simple. Maybe because of perf (which doesn't seem like too
much of a problem to me)?

Comment 6

[Eric Murphy]

Also, 30,000 does not crash DOM and take 5 seconds on my machine to complete the
routine which is acceptable.

Comment 7

[Bob Clary [:bc] (inactive)]

(In reply to comment #5)

Please file a separate bug and attach a test case for the crash. Thanks!

Comment 8

[timeless]

among other things, js can run on multiple threads. dom is bound to the ui
thread. this might not matter if you're just a web page author. but if you're a
server or extension or xulrunner dev, this is of significant interest.

Comment 9

[Brendan Eich [:brendan]]

The reason to implement E4X per spec is because the spec is *not* the DOM spec.
 The reason to implement E4X in SpiderMonkey (mozilla/js/src) not based on the
Gecko DOM (mozilla/dom) is because SpiderMonkey is used in many, many embeddings
other than Mozilla, or Gecko, ones (e.g., Adobe Acrobat).

Abstracting a DOM interface into SpiderMonkey, plugable by the Gecko DOM or some
other DOM, is an interesting idea, but seems overkill, and a mismatch for the
E4X spec.  The DOM has getElementById and getElementsByTagName on document,
e.g., but E4X has multi-names (XMLList-valued properties) and other magic.

Did your crash bug generate talkback, or if a DEBUG build, did you get the stack
backtrace?  Please cite or attach here if you can.

/be

Comment 10

[Brendan Eich [:brendan]]

(In reply to comment #8)
> among other things, js can run on multiple threads. dom is bound to the ui
> thread. this might not matter if you're just a web page author. but if you're a
> server or extension or xulrunner dev, this is of significant interest.

Except the SpiderMonkey E4X implementation is not thread-safe.  A bug to be
fixed (it can't be done using existing JS thread safety, because you need to
protect whole trees, not just nodes one at a time -- and not all nodes have
objects that have scopes, anyway).

/be

Comment 11

[Eric Murphy]

Talkback was sent. I put a comment in there about E4X. Sorry to leave that
information out of my comment.

Testcase is to use the attached document and change 5000 to 30000. Do you want
ME to open the bug? Brenden may be able to "do it" better than me.

(In reply to comment #8)

The DOM is bound only to the UI thread? With the DOM, I can create a whole new
document and work with it... without it ever being displayed. If I ran a custom
mozilla tech-based process without a UI, are you saying that to use the DOM, a
UI thread has to be created, even though it may never be displayed?

P.S. I am not a DOM cheerleader :-) However, I believe it's the best way to work
with XML in-memory. I am not convinced that E4X would make my life easier... yet.

Comment 12

[Aiko]

Attachment: Easier to compare testcase

This doesn't crash for me, it just generates an out of memory error for N near
31500 (Gecko 1.9a1/20051005).

Comment 13

[Bob Clary [:bc] (inactive)]

(In reply to comment #12)
ditto, no crash in Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8b5)
Gecko/20051007 Firefox/1.4.1

Comment 14

[Stephen Donner [:stephend] Not actively reading bugmail]

I crashed with build 2005-10-07-05 SeaMonkey trunk, and will be filing a bug as
soon as I get the Talkback incident pulled up.

Comment 15

[Brendan Eich [:brendan]]

(In reply to comment #11)
> The DOM is bound only to the UI thread?

Technically, the DOM is single-threaded code.  It can be used without a UI, and
is (and has been) in various embeddings for years.  For example, danger.com's
hiptop device uses content transcoded from the web via Gecko in a proxy farm.

/be

Comment 16

[Stephen Donner [:stephend] Not actively reading bugmail]

(In reply to comment #14)
> I crashed with build 2005-10-07-05 SeaMonkey trunk, and will be filing a bug as
> soon as I get the Talkback incident pulled up.

I filed bug 311580.

Comment 17

[Brendan Eich [:brendan]]

(In reply to comment #6)
> Also, 30,000 does not crash DOM and take 5 seconds on my machine to complete the
> routine which is acceptable.

Now that 311580, how long does the equivalent E4X version take on your machine?

/be

Comment 18

[Eric Murphy]

> Now that 311580, how long does the equivalent E4X version take on your machine?

E4X is now about 4.2 - 5.1 seconds with today's build for 30,000. DOM is about
5.2 seconds consistently. No crash.

Glad to see the crash fix make it in.

Comment 19

[Eric Murphy]

I tried to push the limits more. The highest I could push E4X was 32133.
Anything higher I got an out of memory error. This machine has 512 MB of memory.

For times with 32133, E4X was 8-9 secnds. That is a big difference by adding
only 2133. DOM was consistently aroud 5.5 seconds.

DOM was able to handle 333000 and would take about 1 minute. I assume it can
handle much more. At that point Firefox was using about 250 MB of memory.

Comment 20

[Brendan Eich [:brendan]]

I guess I can mark this WORKSFORME.  The crash was an independent bug from this
report, which was about slowness extracting an E4X XMLList in a loop.  I
hesitate to mark this INVALID given the trap E4X's designers laid.  Someone hack
up some warnings on MDC (formerly DevMo), ok?

/be

Comment 21

[Brendan Eich [:brendan]]

(In reply to comment #19)
> I tried to push the limits more. The highest I could push E4X was 32133.
> Anything higher I got an out of memory error. This machine has 512 MB of memory.

Sorry, I was reading bugmail and made my last comment before reading this one.

> For times with 32133, E4X was 8-9 secnds. That is a big difference by adding
> only 2133. DOM was consistently aroud 5.5 seconds.

This is due to the JS runtime's GC heap limit of 4MB.  It's too small a limit
for the modern world.  We need a separate bug on this.

/be