Cap length of an array with spread to MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.
[WebKit-https.git] / Source / JavaScriptCore / runtime / ArrayConventions.h
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003-2019 Apple Inc. All rights reserved.
4  *
5  *  This library is free software; you can redistribute it and/or
6  *  modify it under the terms of the GNU Lesser General Public
7  *  License as published by the Free Software Foundation; either
8  *  version 2 of the License, or (at your option) any later version.
9  *
10  *  This library is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  *  Lesser General Public License for more details.
14  *
15  *  You should have received a copy of the GNU Lesser General Public
16  *  License along with this library; if not, write to the Free Software
17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18  *
19  */
20
21 #pragma once
22
23 #include "IndexingHeader.h"
24 #include "PureNaN.h"
25 #include "WriteBarrier.h"
26
27 namespace JSC {
28
29 // Overview of JSArray
30 //
31 // Properties of JSArray objects may be stored in one of three locations:
32 //   * The regular JSObject property map.
33 //   * A storage vector.
34 //   * A sparse map of array entries.
35 //
36 // Properties with non-numeric identifiers, with identifiers that are not representable
37 // as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
38 // (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
39 // integer) are not considered array indices and will be stored in the JSObject property map.
40 //
41 // All properties with a numeric identifier, representable as an unsigned integer i,
42 // where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
43 // storage vector or the sparse map. An array index i will be handled in the following
44 // fashion:
45 //
46 //   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector,
47 //     unless the array is in SparseMode in which case all properties go into the map.
48 //   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
49 //     be stored in the storage vector or in the sparse array, depending on the density of
50 //     data that would be stored in the vector (a vector being used where at least
51 //     (1 / minDensityMultiplier) of the entries would be populated).
52 //   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
53 //     in the sparse array.
54
55 // Define the maximum storage vector length to be 2^32 / sizeof(JSValue) / 2 to ensure that
56 // there is no risk of overflow.
57 #define MAX_STORAGE_VECTOR_LENGTH (static_cast<unsigned>(IndexingHeader::maximumLength))
58
59 // These values have to be macros to be used in max() and min() without introducing
60 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
61
62 // If you grow an ArrayStorage array by more than this, then the array will go sparse. Note that we
63 // could probably make this smaller (it's large because it used to be conflated with
64 // MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH).
65 #define MIN_SPARSE_ARRAY_INDEX 100000U
66 // If you try to allocate a contiguous array larger than this, then we will allocate an ArrayStorage
67 // array instead. We allow for an array that occupies 1GB of VM.
68 #define MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH (1024 * 1024 * 1024 / 8)
69 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
70 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
71 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
72
73 static_assert(MIN_SPARSE_ARRAY_INDEX <= MAX_STORAGE_VECTOR_INDEX, "MIN_SPARSE_ARRAY_INDEX must be less than or equal to MAX_STORAGE_VECTOR_INDEX");
74 static_assert(MAX_STORAGE_VECTOR_INDEX <= MAX_ARRAY_INDEX, "MAX_STORAGE_VECTOR_INDEX must be less than or equal to MAX_ARRAY_INDEX");
75
76 // The value BASE_XXX_VECTOR_LEN is the maximum number of vector elements we'll allocate
77 // for an array that was created with a sepcified length (e.g. a = new Array(123))
78 #define BASE_CONTIGUOUS_VECTOR_LEN 3U
79 #define BASE_CONTIGUOUS_VECTOR_LEN_EMPTY 5U
80 #define BASE_CONTIGUOUS_VECTOR_LEN_MIN 3U
81 #define BASE_CONTIGUOUS_VECTOR_LEN_MAX 25U
82 #define BASE_ARRAY_STORAGE_VECTOR_LEN 4U
83
84 // The upper bound to the size we'll grow a zero length array when the first element
85 // is added.
86 #define FIRST_ARRAY_STORAGE_VECTOR_GROW 4U
87
88 #define MIN_BEYOND_LENGTH_SPARSE_INDEX 1000
89
90 // Our policy for when to use a vector and when to use a sparse map.
91 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
92 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
93 // as long as it is 1/8 full. If more sparse than that, we use a map.
94 static const unsigned minDensityMultiplier = 8;
95
96 inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
97 {
98     return length / minDensityMultiplier <= numValues;
99 }
100
101 inline bool indexIsSufficientlyBeyondLengthForSparseMap(unsigned i, unsigned length)
102 {
103     return i >= MIN_BEYOND_LENGTH_SPARSE_INDEX && i > length;
104 }
105
106 inline IndexingHeader indexingHeaderForArrayStorage(unsigned length, unsigned vectorLength)
107 {
108     IndexingHeader result;
109     result.setPublicLength(length);
110     result.setVectorLength(vectorLength);
111     return result;
112 }
113
114 inline IndexingHeader baseIndexingHeaderForArrayStorage(unsigned length)
115 {
116     return indexingHeaderForArrayStorage(length, BASE_ARRAY_STORAGE_VECTOR_LEN);
117 }
118
119 #if USE(JSVALUE64)
120 JS_EXPORT_PRIVATE void clearArrayMemset(WriteBarrier<Unknown>* base, unsigned count);
121 JS_EXPORT_PRIVATE void clearArrayMemset(double* base, unsigned count);
122 #endif // USE(JSVALUE64)
123
124 ALWAYS_INLINE void clearArray(WriteBarrier<Unknown>* base, unsigned count)
125 {
126 #if USE(JSVALUE64)
127     const unsigned minCountForMemset = 100;
128     if (count >= minCountForMemset) {
129         clearArrayMemset(base, count);
130         return;
131     }
132 #endif
133     
134     for (unsigned i = count; i--;)
135         base[i].clear();
136 }
137
138 ALWAYS_INLINE void clearArray(double* base, unsigned count)
139 {
140 #if USE(JSVALUE64)
141     const unsigned minCountForMemset = 100;
142     if (count >= minCountForMemset) {
143         clearArrayMemset(base, count);
144         return;
145     }
146 #endif
147     
148     for (unsigned i = count; i--;)
149         base[i] = PNaN;
150 }
151
152 } // namespace JSC