Closed Bug 479468 Opened 16 years ago Closed 16 years ago

TM: Grow array capacity exponentially

Categories

(Core :: JavaScript Engine, defect, P3)

Product:
Core
Component:
JavaScript Engine
Platform:
x86
macOS
Type:
defect

Tracking

()

Status:
RESOLVED DUPLICATE of bug 477279
Milestone:
mozilla1.9.1

People

(Reporter: gal, Assigned: gal)

Details

Attachments

(1 file)

patch
745 bytes, patch
Details | Diff | Splinter Review
No description provided.
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
Attached patch patch — — Splinter Review
Assignee: general → gal
Attachment #363335 - Attachment is patch: true
Attachment #363335 - Attachment mime type: application/octet-stream → text/plain
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
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
Brendan is suggesting to limit the growth to a large increment past a certain threshold to avoid 2GB -> 4GB jumps and such.
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.
hmm, looking at your testcase again, it might be more useful on Mac than on Windows or Linux. Do you have numbers from those?
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
Status: NEW → RESOLVED
Closed: 16 years ago
Resolution: --- → DUPLICATE
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: