Closed
Bug 479468
Opened 15 years ago
Closed 15 years ago
TM: Grow array capacity exponentially
Categories
(Core :: JavaScript Engine, defect, P3)
Tracking
()
RESOLVED
DUPLICATE
of bug 477279
mozilla1.9.1
People
(Reporter: gal, Assigned: gal)
Details
Attachments
(1 file)
|
745 bytes,
patch
|
Details | Diff | Splinter Review |
No description provided.
|
Assignee | |
Comment 1•15 years ago
|
||
Allocation tracking for the following code: js> var x = []; for (var i = 0; i < 4096; ++i) x.push(1); nbytes=108 nbytes=8 nbytes=4 nbytes=108 nbytes=126 nbytes=12 nbytes=36 nbytes=68 nbytes=100 nbytes=132 nbytes=164 nbytes=196 nbytes=228 nbytes=260 nbytes=292 nbytes=324 nbytes=356 nbytes=388 nbytes=420 nbytes=452 nbytes=484 nbytes=516 nbytes=548 nbytes=580 nbytes=612 nbytes=644 nbytes=676 nbytes=708 nbytes=740 nbytes=772 nbytes=804 nbytes=836 nbytes=868 nbytes=900 nbytes=932 nbytes=964 nbytes=996 nbytes=1028 nbytes=1060 nbytes=1092 nbytes=1124 nbytes=1156 nbytes=1188 nbytes=1220 nbytes=1252 nbytes=1284 nbytes=1316 nbytes=1348 nbytes=1380 nbytes=1412 nbytes=1444 nbytes=1476 nbytes=1508 nbytes=1540 nbytes=1572 nbytes=1604 nbytes=1636 nbytes=1668 nbytes=1700 nbytes=1732 nbytes=1764 nbytes=1796 nbytes=1828 nbytes=1860 nbytes=1892 nbytes=1924 nbytes=1956 nbytes=1988 nbytes=2020 nbytes=2052 nbytes=2084 nbytes=2116 nbytes=2148 nbytes=2180 nbytes=2212 nbytes=2244 nbytes=2276 nbytes=2308 nbytes=2340 nbytes=2372 nbytes=2404 nbytes=2436 nbytes=2468 nbytes=2500 nbytes=2532 nbytes=2564 nbytes=2596 nbytes=2628 nbytes=2660 nbytes=2692 nbytes=2724 nbytes=2756 nbytes=2788 nbytes=2820 nbytes=2852 nbytes=2884 nbytes=2916 nbytes=2948 nbytes=2980 nbytes=3012 nbytes=3044 nbytes=3076 nbytes=3108 nbytes=3140 nbytes=3172 nbytes=3204 nbytes=3236 nbytes=3268 nbytes=3300 nbytes=3332 nbytes=3364 nbytes=3396 nbytes=3428 nbytes=3460 nbytes=3492 nbytes=3524 nbytes=3556 nbytes=3588 nbytes=3620 nbytes=3652 nbytes=3684 nbytes=3716 nbytes=3748 nbytes=3780 nbytes=3812 nbytes=3844 nbytes=3876 nbytes=3908 nbytes=3940 nbytes=3972 nbytes=4004 nbytes=4036 nbytes=4068 nbytes=4100 nbytes=4132 nbytes=4164 nbytes=4196 nbytes=4228 nbytes=4260 nbytes=4292 nbytes=4324 nbytes=4356 nbytes=4388 nbytes=4420 nbytes=4452 nbytes=4484 nbytes=4516 nbytes=4548 nbytes=4580 nbytes=4612 nbytes=4644 nbytes=4676 nbytes=4708 nbytes=4740 nbytes=4772 nbytes=4804 nbytes=4836 nbytes=4868 nbytes=4900 nbytes=4932 nbytes=4964 nbytes=4996 nbytes=5028 nbytes=5060 nbytes=5092 nbytes=5124 nbytes=5156 nbytes=5188 nbytes=5220 nbytes=5252 nbytes=5284 nbytes=5316 nbytes=5348 nbytes=5380 nbytes=5412 nbytes=5444 nbytes=5476 nbytes=5508 nbytes=5540 nbytes=5572 nbytes=5604 nbytes=5636 nbytes=5668 nbytes=5700 nbytes=5732 nbytes=5764 nbytes=5796 nbytes=5828 nbytes=5860 nbytes=5892 nbytes=5924 nbytes=5956 nbytes=5988 nbytes=6020 nbytes=6052 nbytes=6084 nbytes=6116 nbytes=6148 nbytes=6180 nbytes=6212 nbytes=6244 nbytes=6276 nbytes=6308 nbytes=6340 nbytes=6372 nbytes=6404 nbytes=6436 nbytes=6468 nbytes=6500 nbytes=6532 nbytes=6564 nbytes=6596 nbytes=6628 nbytes=6660 nbytes=6692 nbytes=6724 nbytes=6756 nbytes=6788 nbytes=6820 nbytes=6852 nbytes=6884 nbytes=6916 nbytes=6948 nbytes=6980 nbytes=7012 nbytes=7044 nbytes=7076 nbytes=7108 nbytes=7140 nbytes=7172 nbytes=7204 nbytes=7236 nbytes=7268 nbytes=7300 nbytes=7332 nbytes=7364 nbytes=7396 nbytes=7428 nbytes=7460 nbytes=7492 nbytes=7524 nbytes=7556 nbytes=7588 nbytes=7620 nbytes=7652 nbytes=7684 nbytes=7716 nbytes=7748 nbytes=7780 nbytes=7812 nbytes=7844 nbytes=7876 nbytes=7908 nbytes=7940 nbytes=7972 nbytes=8004 nbytes=8036 nbytes=8068 nbytes=8100 nbytes=8132 nbytes=8164 nbytes=8196 nbytes=8228 nbytes=8260 nbytes=8292 nbytes=8324 nbytes=8356 nbytes=8388 nbytes=8420 nbytes=8452 nbytes=8484 nbytes=8516 nbytes=8548 nbytes=8580 nbytes=8612 nbytes=8644 nbytes=8676 nbytes=8708 nbytes=8740 nbytes=8772 nbytes=8804 nbytes=8836 nbytes=8868 nbytes=8900 nbytes=8932 nbytes=8964 nbytes=8996 nbytes=9028 nbytes=9060 nbytes=9092 nbytes=9124 nbytes=9156 nbytes=9188 nbytes=9220 nbytes=9252 nbytes=9284 nbytes=9316 nbytes=9348 nbytes=9380 nbytes=9412 nbytes=9444 nbytes=9476 nbytes=9508 nbytes=9540 nbytes=9572 nbytes=9604 nbytes=9636 nbytes=9668 nbytes=9700 nbytes=9732 nbytes=9764 nbytes=9796 nbytes=9828 nbytes=9860 nbytes=9892 nbytes=9924 nbytes=9956 nbytes=9988 nbytes=10020 nbytes=10052 nbytes=10084 nbytes=10116 nbytes=10148 nbytes=10180 nbytes=10212 nbytes=10244 nbytes=10276 nbytes=10308 nbytes=10340 nbytes=10372 nbytes=10404 nbytes=10436 nbytes=10468 nbytes=10500 nbytes=10532 nbytes=10564 nbytes=10596 nbytes=10628 nbytes=10660 nbytes=10692 nbytes=10724 nbytes=10756 nbytes=10788 nbytes=10820 nbytes=10852 nbytes=10884 nbytes=10916 nbytes=10948 nbytes=10980 nbytes=11012 nbytes=11044 nbytes=11076 nbytes=11108 nbytes=11140 nbytes=11172 nbytes=11204 nbytes=11236 nbytes=11268 nbytes=11300 nbytes=11332 nbytes=11364 nbytes=11396 nbytes=11428 nbytes=11460 nbytes=11492 nbytes=11524 nbytes=11556 nbytes=11588 nbytes=11620 nbytes=11652 nbytes=11684 nbytes=11716 nbytes=11748 nbytes=11780 nbytes=11812 nbytes=11844 nbytes=11876 nbytes=11908 nbytes=11940 nbytes=11972 nbytes=12004 nbytes=12036 nbytes=12068 nbytes=12100 nbytes=12132 nbytes=12164 nbytes=12196 nbytes=12228 nbytes=12260 nbytes=12292 nbytes=12324 nbytes=12356 nbytes=12388 nbytes=12420 nbytes=12452 nbytes=12484 nbytes=12516 nbytes=12548 nbytes=12580 nbytes=12612 nbytes=12644 nbytes=12676 nbytes=12708 nbytes=12740 nbytes=12772 nbytes=12804 nbytes=12836 nbytes=12868 nbytes=12900 nbytes=12932 nbytes=12964 nbytes=12996 nbytes=13028 nbytes=13060 nbytes=13092 nbytes=13124 nbytes=13156 nbytes=13188 nbytes=13220 nbytes=13252 nbytes=13284 nbytes=13316 nbytes=13348 nbytes=13380 nbytes=13412 nbytes=13444 nbytes=13476 nbytes=13508 nbytes=13540 nbytes=13572 nbytes=13604 nbytes=13636 nbytes=13668 nbytes=13700 nbytes=13732 nbytes=13764 nbytes=13796 nbytes=13828 nbytes=13860 nbytes=13892 nbytes=13924 nbytes=13956 nbytes=13988 nbytes=14020 nbytes=14052 nbytes=14084 nbytes=14116 nbytes=14148 nbytes=14180 nbytes=14212 nbytes=14244 nbytes=14276 nbytes=14308 nbytes=14340 nbytes=14372 nbytes=14404 nbytes=14436 nbytes=14468 nbytes=14500 nbytes=14532 nbytes=14564 nbytes=14596 nbytes=14628 nbytes=14660 nbytes=14692 nbytes=14724 nbytes=14756 nbytes=14788 nbytes=14820 nbytes=14852 nbytes=14884 nbytes=14916 nbytes=14948 nbytes=14980 nbytes=15012 nbytes=15044 nbytes=15076 nbytes=15108 nbytes=15140 nbytes=15172 nbytes=15204 nbytes=15236 nbytes=15268 nbytes=15300 nbytes=15332 nbytes=15364 nbytes=15396 nbytes=15428 nbytes=15460 nbytes=15492 nbytes=15524 nbytes=15556 nbytes=15588 nbytes=15620 nbytes=15652 nbytes=15684 nbytes=15716 nbytes=15748 nbytes=15780 nbytes=15812 nbytes=15844 nbytes=15876 nbytes=15908 nbytes=15940 nbytes=15972 nbytes=16004 nbytes=16036 nbytes=16068 nbytes=16100 nbytes=16132 nbytes=16164 nbytes=16196 nbytes=16228 nbytes=16260 nbytes=16292 nbytes=16324 nbytes=16356 nbytes=16388 With a simple exponential growth factor: js> var x = []; for (var i = 0; i < 4096; ++i) x.push(1); nbytes=108 nbytes=8 nbytes=4 nbytes=108 nbytes=126 nbytes=12 nbytes=36 nbytes=68 nbytes=132 nbytes=260 nbytes=516 nbytes=1028 nbytes=2052 nbytes=4100 nbytes=8196 nbytes=16388
Priority: -- → P3
Target Milestone: --- → mozilla1.9.1
|
|
Assignee | |
Comment 2•15 years ago
|
||
Assignee: general → gal
|
|
Assignee | |
Updated•15 years ago
|
Attachment #363335 -
Attachment is patch: true
Attachment #363335 -
Attachment mime type: application/octet-stream → text/plain
|
||
Comment 3•15 years ago
|
||
that probably won't make much different in performance or anything. jemalloc and the mac allocator will resize in-place where they can, and since allocations are chunked most of the previous ones won't actually change size and will just give you back the same pointer
|
|
Assignee | |
Comment 4•15 years ago
|
||
Testcase:
var x = [];
var y = [];
var t = Date.now();
for (var i = 0; i < 1000000; ++i)
x[i] = y[i] = 0;
print(Date.now() - t);
Without the patch:
whale:src gal$ ./Darwin_OPT.OBJ/js z.js
125
whale:src gal$ ./Darwin_OPT.OBJ/js -j z.js
73
With the patch:
whale:src gal$ ./Darwin_OPT.OBJ/js z.js
96
whale:src gal$ ./Darwin_OPT.OBJ/js -j z.js
46|
|
Assignee | |
Comment 5•15 years ago
|
||
Brendan is suggesting to limit the growth to a large increment past a certain threshold to avoid 2GB -> 4GB jumps and such.
|
|
||
Comment 6•15 years ago
|
||
Like I said, I don't see much point in adding this at all given our allocator's behavior. A more interesting log would be to look at the pointers you get back from realloc and see when they actually change.
|
|
||
Comment 7•15 years ago
|
||
hmm, looking at your testcase again, it might be more useful on Mac than on Windows or Linux. Do you have numbers from those?
|
||
Comment 8•15 years ago
|
||
Binary-exponential growth in the JS array impl is still good to reduce overhead, even if malloc size-classifies and grows by doubling up to a point. /be
|
|
Assignee | |
Updated•15 years ago
|
Status: NEW → RESOLVED
Closed: 15 years ago
Resolution: --- → DUPLICATE
You need to log in
before you can comment on or make changes to this bug.
Description
•