Bug 56823 - REGRESSION: Allocation of memory is slow when building a 2GB tree
Summary: REGRESSION: Allocation of memory is slow when building a 2GB tree
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Mac OS X 10.6
: P2 Normal
Assignee: Geoffrey Garen
Keywords: InRadar
Depends on:
Reported: 2011-03-22 04:30 PDT by Alan Tam
Modified: 2011-04-07 19:59 PDT (History)
3 users (show)

See Also:

Test case (1.45 KB, text/html)
2011-03-22 10:19 PDT, Alan Tam
no flags Details
Patch (1.82 KB, patch)
2011-03-28 13:57 PDT, Geoffrey Garen
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Alan Tam 2011-03-22 04:30:37 PDT
1. Open the attached html using webkit r78249 or later.

Try the same for:
* Safari 5.0
* WebKit trunk r78794 or before
* Any version of Chrome

Notice how it is 10x slower than all others, where a pass (after the first dozen passes) takes >1000ms, rather than <100ms as other browsers do.
Comment 1 Alexey Proskuryakov 2011-03-22 10:03:09 PDT
There is no test case attached at the moment, please attach it.
Comment 2 Alan Tam 2011-03-22 10:19:14 PDT
Created attachment 86471 [details]
Test case

Really attach the test case.
Comment 3 Alexey Proskuryakov 2011-03-22 10:39:11 PDT
Comment 4 Geoffrey Garen 2011-03-25 15:09:02 PDT
Initial times are even (between Safari 5.0.3 and TOT), but TOT starts to skyrocket upward from there. Safari 5.0.3 does have one or two very long pauses on the order of TOT, but TOT has very long pauses during each iteration.
Comment 5 Geoffrey Garen 2011-03-25 15:10:20 PDT
Safari 5.0.3 beginning:
[A] Last pass took 43ms
[A] Last pass took 48ms
[A] Last pass took 65ms
[A] Last pass took 30ms
[A] Last pass took 31ms
[A] Last pass took 101ms

TOT beginning:
[A] Last pass took 52ms
[A] Last pass took 58ms
[A] Last pass took 60ms
[A] Last pass took 69ms
[A] Last pass took 84ms
[A] Last pass took 95ms

TOT later:
[A] Last pass took 1119ms
[A] Last pass took 1153ms
[A] Last pass took 1168ms
[A] Last pass took 1184ms
[A] Last pass took 1200ms
[A] Last pass took 1215ms
Comment 6 Geoffrey Garen 2011-03-28 13:57:13 PDT
Created attachment 87197 [details]
Comment 7 Geoffrey Garen 2011-03-28 15:00:54 PDT
Committed r82162: <http://trac.webkit.org/changeset/82162>
Comment 8 Geoffrey Garen 2011-03-28 15:02:12 PDT
Reopening, since my patch didn't fix the whole regression.
Comment 9 Geoffrey Garen 2011-03-28 16:43:29 PDT
Updating title to reflect the specific constraints of this test: it allocates a 2GB tree!

Most of the run-time is dominated by OS virtual memory allocation, fault, and zero fill calls.
Comment 10 Geoffrey Garen 2011-03-29 16:58:33 PDT
Some regression ranges:

77699 (fast) - 80051 (slow) [actually 78312]
-> The capacity() bug, which was fixed in <http://trac.webkit.org/changeset/82162>.

80051 (fast) - 80052 (slow)
-> Changing the block size to 16KB.
Comment 11 Geoffrey Garen 2011-03-29 17:14:15 PDT
Testing in other browsers:

Firefox aggressively grows the heap to 2GB, and never shrinks it. This is the fastest possible policy for this stress test (~2s total), but a very bad policy for memory footprint!

Chrome is pretty fast (~3.5s total) on its first run, but gets very slow (>30s total or complete hang) on later runs.
Comment 12 Geoffrey Garen 2011-03-29 17:29:53 PDT
> Firefox aggressively grows the heap to 2GB, and never shrinks it.

Correction: It looks like Firefox will eventually shrink from 2GB if you give it enough cajoling.
Comment 13 Geoffrey Garen 2011-03-29 19:56:57 PDT
It looks like the fundamental underlying problem here is that vm_map is O(N^2).
Comment 14 Geoffrey Garen 2011-04-07 19:59:49 PDT
Comment on attachment 87197 [details]

Clearing review flag to get this out of the list.