486321 - Large arrays that start out sparse/slowified waste memory if they are filled in so that they effectively become dense

Status: RESOLVED DUPLICATE of bug 835102

(Core :: JavaScript Engine, defect)

Description

[Oleg Romashin (:romaxa)]

Attachment: Testcase

Allocation of js array with 2000000 elements takes about ~85000Kb in mozilla-jsEngine

The same array allocated in webkit r41418 ~22000Kb

Why is there so big difference?

Comment 1

[Oleg Romashin (:romaxa)]

I have tested with latest mozilla-central, and situation the same, it is still eating ~80Mb...
Seems bug 491126 did not help.

Comment 2

[Oleg Romashin (:romaxa)]

mem monitor output

		system	process		private	/------ dirty ---------\
time:		avail:	size:	rss:	clean:	shared:	private: change:
13:41:07	118868	131980	24776	9108	0	9304	   +0 kB
13:41:08	117108	142092	26820	9348	0	11084	+1780 kB
13:41:10	113508	145536	30316	9348	0	14580	+3496 kB
13:41:11	109236	149648	34452	9348	0	18716	+4136 kB
13:41:12	106508	152488	37332	9348	0	21596	+2880 kB
13:41:14	103712	155464	40220	9348	0	24484	+2888 kB
13:41:15	99604	159936	44716	9348	0	28980	+4496 kB
13:41:16	96176	163432	48224	9348	0	32488	+3508 kB
13:41:17	93352	166536	51348	9348	0	35632	+3144 kB
13:41:19	90220	170032	54828	9336	0	39156	+3524 kB
13:41:20	88796	171928	56608	9332	0	40944	+1788 kB
13:41:21	83608	177096	61880	9332	0	46216	+5272 kB
13:41:23	81400	179656	64420	9332	0	48756	+2540 kB
13:41:24	79264	181948	66704	9368	0	51004	+2248 kB
13:41:25	79160	181948	66708	9368	0	51004	   +0 kB
13:41:27	79068	181948	66728	9368	0	51024	  +20 kB
13:41:28	77032	184100	68872	9368	0	53168	+2144 kB
13:41:29	74912	186392	71192	9368	0	55488	+2320 kB
13:41:31	72644	188680	73452	9364	0	57796	+2308 kB
13:41:32	70064	191384	76160	9360	0	60508	+2712 kB
13:41:34	67744	193812	78572	9348	0	62936	+2428 kB
13:41:35	65388	196236	80980	9340	0	65356	+2420 kB
13:41:36	63308	198528	83040	9332	0	67584	+2228 kB
13:41:38	61608	200412	84604	9284	0	69456	+1872 kB
13:41:39	60004	202024	86104	9200	0	71148	+1692 kB
13:41:41	59224	202836	86832	9148	0	71932	 +784 kB
13:41:42	42432	220700	103200	8536	0	89732	+17800 kB
13:41:43	42452	220700	102604	8104	0	89732	   +0 kB
13:41:45	50540	212504	94452	8120	0	81548	-8184 kB
13:41:46	50508	212504	94460	8120	0	81548	   +0 kB
13:41:48	49940	213048	94976	8120	0	82064	 +516 kB
13:41:49	47736	215200	97248	8120	0	84336	+2272 kB
13:41:50	45512	217492	98988	7668	0	86528	+2192 kB
13:41:52	43100	219780	99892	6492	0	88856	+2328 kB
13:41:53	41312	221936	99868	4460	0	91052	+2196 kB
13:41:55	39280	224360	101796	4356	0	93368	+2316 kB
13:41:56	37164	226516	104068	4356	0	95640	+2272 kB
13:41:57	36164	228748	105236	4472	0	96760	+1120 kB
13:41:59	37892	227464	105160	4636	0	96604	 -156 kB
13:42:00	39100	258216	110028	6656	0	99272	+2668 kB
13:42:02	39348	258216	110028	6608	0	99272	   +0 kB

Comment 3

[Igor Bukanov]

The changes for the bug 491126 could not help this test case. Its essence is the following code:

var alloc = function(size) {
    var arr = new Array(size);
    arr[size-1] = 123;
    for (var i = 0; i < size; i++) {
        arr[i] = i * 2;
    }
}
...
alloc(2000*1000)

So the problem here is that due to the initial arr[size-1] = 123 and the following array[0] the array becomes slow allocating effectively JSScopeProperty (32 bytes on 32 bit platforms) per each array element in addition to the storage for the slot array. That explains the memory usage. 

The optimization from the bug 491126 that saves 12 bytes per each dense array instance cannot help here.

What could help here is a special support for sparse arrays using some kind of a tree structure or a hash table to store the elements.

Comment 4

[Marco Castelluccio [:marco]]

Still an issue with Firefox 8.0a2.

Comment 5

[Nicholas Nethercote [inactive]]

about:memory says this on my Linux64 build:

│  ├──180,622,424 B (41.79%) -- compartment(file:///home/njn/arraytest.html)
│  │  ├──130,199,552 B (30.12%) -- gc-heap
│  │  │  ├──128,059,392 B (29.63%) -- shapes
│  │  │  ├────1,018,328 B (00.24%) -- arena-padding
│  │  │  ├────1,017,184 B (00.24%) -- arena-headers
│  │  │  ├───────65,216 B (00.02%) -- objects
│  │  │  ├───────35,424 B (00.01%) -- arena-unused
│  │  │  ├────────3,008 B (00.00%) -- type-objects
│  │  │  └────────1,000 B (00.00%) -- scripts
│  │  ├───33,559,488 B (07.76%) -- property-tables
│  │  ├───16,787,232 B (03.88%) -- object-slots
│  │  ├───────65,536 B (00.02%) -- mjit-code
│  │  │       ├──47,152 B (00.01%) -- unused
│  │  │       └──18,384 B (00.00%) -- method
│  │  ├────────4,416 B (00.00%) -- type-inference
│  │  │        ├──3,040 B (00.00%) -- object-main
│  │  │        ├────864 B (00.00%) -- script-main
│  │  │        └────512 B (00.00%) -- tables
│  │  ├────────4,088 B (00.00%) -- analysis-temporary
│  │  ├────────1,632 B (00.00%) -- object-empty-shapes
│  │  └──────────480 B (00.00%) -- script-data

CC'ing some JS folks -- do we have existing bugs on file for this issue (where a huge array gets slowified because it's sparse to begin with, but is then filled in)?

Comment 6

[Nicholas Nethercote [inactive]]

The sparse/dense array distinction was removed a while back. Things are now much better:

│   │  │  ├──19,243,792 B (08.33%) -- js-compartment(file:///home/njn/tmp/arraytest.html)
│   │  │  │  ├──19,020,256 B (08.23%) -- objects
│   │  │  │  │  ├──18,891,520 B (08.18%) -- malloc-heap
│   │  │  │  │  │  ├──16,781,312 B (07.26%) ── elements/non-asm.js
│   │  │  │  │  │  └───2,110,208 B (00.91%) ── slots
│   │  │  │  │  ├─────128,736 B (00.06%) ── gc-heap/function
│   │  │  │  │  └───────────0 B (00.00%) ── non-heap/code/asm.js
│   │  │  │  ├─────210,936 B (00.09%) -- shapes
│   │  │  │  │     ├──154,264 B (00.07%) -- gc-heap
│   │  │  │  │     │  ├───77,184 B (00.03%) ── base
│   │  │  │  │     │  ├───67,680 B (00.03%) ── tree/global-parented
│   │  │  │  │     │  └────9,400 B (00.00%) ── dict
│   │  │  │  │     └───56,672 B (00.02%) -- malloc-heap
│   │  │  │  │         ├──45,248 B (00.02%) ── compartment-tables
│   │  │  │  │         └──11,424 B (00.00%) ── tree-tables
│   │  │  │  └──────12,600 B (00.01%) -- sundries
│   │  │  │         ├───6,568 B (00.00%) ── malloc-heap
│   │  │  │         └───6,032 B (00.00%) ── gc-heap

This compares favorably with the 22000KB mentioned for Webkit in comment 0.