Introduction to the
Arrays, linked lists, stacks and queues are all linear lists. The structures they represent are all linear structures, and the corresponding ones are nonlinear lists, such as trees, graphs and piles, which represent nonlinear structures.
This section focuses on JavaScript arrays. Before we begin, consider this question:
We know that in JavaScript, you can store different types of values in arrays, and arrays can grow dynamically, unlike other languages like C, where you have to determine the size of the array when you create it, and if the array is full, you have to reallocate memory. Why is that?
This section answers this question from the perspective of the Chrome V8 source code in four ways:
- Array Basics
- Why can arrays hold different types in JavaScript?
- How are arrays stored in JavaScript?
- Dynamic expansion and decrement of arrays in JavaScript
FastElements）
Let’s get down to business. (Surprise at the end) 😊
If you want to learn more about this series, you can follow the public account “Front-end Bottle” and my “Github”.
1. Arrays (Basic)
A basic data structure, numbering from 0 in every programming language, that represents a contiguous set of storage structures used to store the same type of data.
let arr = [1.2.3]
Copy the codeIts specific storage structure (contiguous storage space for the same type of data) determines:
advantages
- Random access: Data can be randomly accessed at any location in an array by subscript
disadvantages
- Not very friendly to data deletion and insertion
Search: the time complexity of random access based on the subscript is O(1);
Insert or delete: time complexity is O(n);
Arrays are almost universal in JavaScript. They can be used not just as an array, but as a stack or queue.
Array:
let array = [1.2.3]
Copy the codeThe stack:
let stack = [1.2.3]
/ / into the stack
stack.push(4)
/ / out of the stack
stcak.pop()
Copy the codeQueue:
let queue = [1.2.3]
/ / into the team
queue.push(4)
/ / out of the team
queue.shift()
Copy the code2. In JavaScript, arrays can hold different types of values
Take a look at Chrome V8 source code:
// The JSArray describes JavaScript Arrays
// Such an array can be in one of two modes:
// - fast, backing storage is a FixedArray and length <= elements.length();
// Please note: push and pop can be used to grow and shrink the array.
// - slow, backing storage is a HashTable with numbers as keys.
class JSArray: public JSObject {
public:
// [length]: The length property.
DECL_ACCESSORS(length, Object)
// ...
// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;
};
Copy the codeYou can see that JSArray inherits from JSObject, so in JavaScript, an array can be a special object that stores data internally as a key-value, so arrays in JavaScript can hold different types of values.
Third, in JavaScript, array storage
// The JSArray describes JavaScript Arrays
// Such an array can be in one of two modes:
// - fast, backing storage is a FixedArray and length <= elements.length();
// Please note: push and pop can be used to grow and shrink the array.
// - slow, backing storage is a HashTable with numbers as keys.
class JSArray: public JSObject {
public:
// [length]: The length property.
DECL_ACCESSORS(length, Object)
// ...
// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;
};
Copy the codeJSArray inherits from JSObject, and from the comments, it can be stored in two ways:
- Fast: The storage structure is
FixedArray, and the array length<= elements.length()，push或popMay be accompanied by dynamic capacity expansion or reduction - Slow: The storage structure is
HashTableHash table), and array subscript askey
Fast is called FastElements in the source code, while slow is called SlowElements.
1. Fast Array (FastElements)
FixedArray is an array-like class implemented by V8 that represents a contiguous segment of memory that can be located directly using an index. A newly created empty array defaults to a fast array. When the array is full, JSArray dynamically expands to store more elements as it continues to push.
2. SlowElements
Slow arrays are stored in memory space in the form of hash tables, which do not need to open up contiguous storage space, but need to maintain an additional hash table. Compared with fast arrays, the performance is relatively poor.
// src/objects/dictionary.h
class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Dictionary
: public HashTable<Derived, Shape> {
using DerivedHashTable = HashTable<Derived, Shape>;
public:
using Key = typename Shape::Key;
// Returns the value at entry.
inline Object ValueAt(InternalIndex entry);
inline Object ValueAt(const Isolate* isolate, InternalIndex entry);
// ...
};
Copy the codeAs can be seen from the source code, its internal is a HashTable.
3. When will it change from fast to slow?
From the Chrome V8 source code,
// src/objects/js-objects.h
static const uint32_t kMaxGap = 1024;
// src/objects/dictionary.h
// JSObjects prefer dictionary elements if the dictionary saves this much
// memory compared to a fast elements backing store.
static const uint32_t kPreferFastElementsSizeFactor = 3;
// src/objects/js-objects-inl.h
// If the fast-case backing storage takes up much more memory than a dictionary
// backing storage would, the object should have slow elements.
// static
static inline bool ShouldConvertToSlowElements(uint32_t used_elements,
uint32_t new_capacity) {
uint32_t size_threshold = NumberDictionary::kPreferFastElementsSizeFactor *
NumberDictionary::ComputeCapacity(used_elements) *
NumberDictionary::kEntrySize;
// The new capacity of the fast array is three times the capacity of the expanded array, which is also converted to the slow array
return size_threshold <= new_capacity;
}
static inline bool ShouldConvertToSlowElements(JSObject object,
uint32_t capacity,
uint32_t index,
uint32_t* new_capacity) {
STATIC_ASSERT(JSObject::kMaxUncheckedOldFastElementsLength <=
JSObject::kMaxUncheckedFastElementsLength);
if (index < capacity) {
*new_capacity = capacity;
return false;
}
// If the added index value (for example, 2000 in Example 3) is greater than or equal to 1024,
// Returns true to slow array
if (index - capacity >= JSObject::kMaxGap) return true;
*new_capacity = JSObject::NewElementsCapacity(index + 1);
DCHECK_LT(index, *new_capacity);
// TODO(ulan): Check if it works with young large objects.
if (*new_capacity <= JSObject::kMaxUncheckedOldFastElementsLength ||
(*new_capacity <= JSObject::kMaxUncheckedFastElementsLength &&
ObjectInYoungGeneration(object))) {
return false;
}
return ShouldConvertToSlowElements(object.GetFastElementsUsage(),
*new_capacity);
}
Copy the codeSo, a fast array is converted to a slow array when:
- When the difference between the index value added and capacity is greater than or equal to 1024 (index-capacity >= 1024)
- The new capacity of the fast array is more than three times the expanded capacity
For example, add a large index of the same type to a fast array
var arr = [1.2.3]
arr[2000] = 10;
Copy the codeWhen an index of 2000 is added to arR, the ARR is converted to a slow array. Significant memory savings (from index 2 to index 2000).
4. When does slow change to fast?
We already know when fast goes slow, so slow goes fast is easy, right
static bool ShouldConvertToFastElements(JSObject object,
NumberDictionary dictionary,
uint32_t index,
uint32_t* new_capacity) {
// If properties with non-standard attributes or accessors were added, we
// cannot go back to fast elements.
if (dictionary.requires_slow_elements()) return false;
// Adding a property with this index will require slow elements.
if (index >= static_cast<uint32_t>(Smi::kMaxValue)) return false;
if (object.IsJSArray()) {
Object length = JSArray::cast(object).length();
if(! length.IsSmi())return false;
*new_capacity = static_cast<uint32_t>(Smi::ToInt(length));
} else if (object.IsJSArgumentsObject()) {
return false;
} else {
*new_capacity = dictionary.max_number_key() + 1;
}
*new_capacity = Max(index + 1, *new_capacity);
uint32_t dictionary_size = static_cast<uint32_t>(dictionary.Capacity()) *
NumberDictionary::kEntrySize;
// Turn fast if the dictionary only saves 50% space.
return 2 * dictionary_size >= *new_capacity;
}
Copy the codeA slow array is converted to a fast array when the elements of the slow array can be stored in a fast array with a length between SMI and a space savings of only 50%
4, JavaScript, array dynamic expansion and reduction (FastElements)
The default empty array initialization size is 4:
// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;
Copy the codeIn JavaScript, when an array is pushed, if it is found to be out of memory, it is expanded.
In Chrome source code, the operation of push is implemented in assembly, which is embedded in c++ to improve the execution efficiency. Besides, a layer of c++ is encapsulated on the basis of assembly, and these c++ codes will be converted into assembly code when compiled and executed.
Function to calculate the new capacity:
// js-objects.h
static const uint32_t kMinAddedElementsCapacity = 16;
// code-stub-assembler.cc
Node* CodeStubAssembler::CalculateNewElementsCapacity(Node* old_capacity,
ParameterMode mode) {
CSA_SLOW_ASSERT(this, MatchesParameterMode(old_capacity, mode));
Node* half_old_capacity = WordOrSmiShr(old_capacity, 1, mode);
Node* new_capacity = IntPtrOrSmiAdd(half_old_capacity, old_capacity, mode);
Node* padding =
IntPtrOrSmiConstant(JSObject::kMinAddedElementsCapacity, mode);
return IntPtrOrSmiAdd(new_capacity, padding, mode);
}
Copy the codeTherefore, the new capacity calculation formula after capacity expansion is:
new_capacity = old_capacity /2 + old_capacity + 16
That’s 1.5 times the old capacity plus 16. Initialize to four, and when pushing fifth, the capacity will become:
new_capacity = 4 / 2 + 4 + 16 = 22
Copy the old data, place the new element at the current length, and then add the array length + 1 and return length.
Therefore, capacity expansion can be divided into the following steps:
pushThe array was found out of memory while operating- Apply for the memory space new_capacity = old_capacity /2 + old_capacity + 16
- Copy the array into new memory
- Put the new element at the current length position
- The length of the array + 1
- Returns the length
The user is unaware of the whole process, unlike C, which requires the user to manually apply for memory space.
When the array performs a POP operation, it will determine the capacity of the array after the pop and whether it needs to be reduced.
Unlike array push, which is implemented in assembly, pop is implemented in c++.
Determine whether to reduce capacity:
if (2 * length <= capacity) {
// If more than half the elements won't be used, trim the array.
isolate->heap()->RightTrimFixedArray(*backing_store, capacity - length);
} else {
// Otherwise, fill the unused tail with holes.
BackingStore::cast(*backing_store)->FillWithHoles(length, old_length);
}
Copy the codeTherefore, when the array pop, if the array capacity is greater than or equal to 2 times of Length, the capacity adjustment, using the RightTrimFixedArray function, calculate the space to be released, mark, wait for GC recycling; If the array is less than twice length, fill it with a holes object.
Therefore, capacity reduction can be divided into the following steps:
popGets an array when you operatelength- To obtain
length - 1Element on (element to be deleted) - An array of
length - 1 - Check whether the total size of the array is greater than or equal to 2 times length-1
- If so, use
RightTrimFixedArrayFunction, calculate the amount of space to free, and make a mark, waitGCrecycling - If not, use
holesObject with - Returns the element to be deleted
Answer the opening question
In JavaScript, JSArray inherits from JSObject, or it’s a special object that stores data internally as key-value, so arrays in JavaScript can hold different types of values. It has two storage methods, fast array and slow array. When initializing an empty array, use fast array, fast array uses continuous memory space, when the array length reaches the maximum, JSArray will dynamically expand to store more elements, compared to slow array, performance is much better. When there are too many holes in an array, it is converted to a slow array, which stores data in the form of a hash table (key-value) to save memory space.
Finally, with a front end questions (Tencent) : array flattening, to heavy, sort
The properties and methods of Array will not be introduced here. See MDN Array in detail.
Interview questions:
Known as an array: var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10].
Write a program to flatten and divide an array of duplicate data, resulting in an ascending and non-repeating array
The answer:
var arr = [ [1.2.2], [3.4.5.5], [6.7.8.9[11.12[12.13[14]]]],10]
/ / flat
let flatArr = arr.flat(4)
/ / to heavy
let disArr = Array.from(new Set(flatArr))
/ / sorting
let result = disArr.sort(function(a, b) {
return a-b
})
console.log(result)
/ / [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
Copy the codeFor Set, please refer to Set, WeakSet, Map and WeakMap
Reference links:
Explore the JS V8 engine under the “array” implementation
See JS Array implementation from Chrome source code
Seven, know more front-end road friends, together with advanced front-end development
The first phase of front-end algorithm training camp is open 🎉🎉🎉
Here, you can advance the front-end algorithm with like-minded friends, from 0 to 1 to build a complete data structure and algorithm system.
Scan code to join [front-end algorithm exchange group exchange group], if the TWO-DIMENSIONAL code fails, you can reply “algorithm” in the public number “front-end bottle Jun”
Eight, walk last
❤️ Have fun, keep learning, and always keep coding. 👨 💻
If you have any questions or more unique insights, please feel free to comment or contact Me directly (scan the following public account and reply 123)! 👀 👇
👇 welcome to pay attention to: front-end bottle jun, daily update! 👇
