TM: Grow array capacity exponentially

RESOLVED DUPLICATE of bug 477279

Status

()

Core
JavaScript Engine
P3
normal
RESOLVED DUPLICATE of bug 477279
9 years ago
9 years ago

People

(Reporter: gal, Assigned: gal)

Tracking

unspecified
mozilla1.9.1
x86
Mac OS X
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

Comment hidden (empty)
(Assignee)

Comment 1

9 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

9 years ago
Created attachment 363335 [details] [diff] [review]
patch
Assignee: general → gal
(Assignee)

Updated

9 years ago
Attachment #363335 - Attachment is patch: true
Attachment #363335 - Attachment mime type: application/octet-stream → text/plain

Comment 3

9 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

9 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

9 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

9 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

9 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?
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

9 years ago
Status: NEW → RESOLVED
Last Resolved: 9 years ago
Resolution: --- → DUPLICATE
Duplicate of bug: 477279
You need to log in before you can comment on or make changes to this bug.