задний план
При использовании массивов JS обнаруживается, что массивы JS могут хранить элементы разных типов, а длина массива является переменной. какие? ? Это отличается от массивов, с которыми я сталкивался раньше. Массив, определенный в структуре данных, представляет собой структуру хранения фиксированной длины с тем же типом данных. Массивы в JS такие особенные, поэтому в название добавлено слово «массив». С растерянным выражением лица он открыл поисковик и узнал.
содержание:
- что такое массив
- Массивы в JavaScript
- Докопаемся до сути: рассмотрим реализацию массивов из исходного кода V8
- Преобразование между быстрыми массивами и медленными массивами
- Расширение: ArrayBuffer
- Суммировать
что такое массив
Давайте сначала посмотрим, что такое массив.На следующем рисунке показано определение массива в Википедии:
На рисунке есть две ключевые точки,того же типа,непрерывная память.
Эти два ключевых момента не нужно сначала углублять, продолжайте смотреть вниз и объясните ниже.
Прочитав определение в структуре данных, давайте посмотрим на реализацию массива на конкретном языке:
Реализация массивов в таких языках, как C, C++, Java, Scala и т. д., заключается в хранении ограниченного набора структур данных одного типа данных путем разделения в памяти ряда непрерывных пространств фиксированной длины. Есть также несколько важных понятий:непрерывный,Фиксированная длина,тот же тип данных, что аналогично определению в структуре данных.
Эти понятия объясняются ниже:
непрерывный
Непрерывное хранение пространства является характеристикой массивов.Следующий рисунок представляет собой схематическую диаграмму хранения массивов в памяти.
Хорошо видно, что каждый элемент является смежным в памяти, которая представляет собой линейную структуру хранения.
Фиксированная длина
Поскольку пространство массива непрерывное, это означает, что в памяти будет целый блок пространства для хранения массива.Если это не фиксированная длина, то область за массивом в памяти не сможет быть выделены, и память не знает, должен ли массив продолжаться.Сколько места использовать для хранения. Фиксированная длина определяет предел памяти, используемой массивом, а пространство за пределами массива может быть выделено другим.
тот же тип данных
Поскольку длина массива фиксирована, если это не один и тот же тип данных, один будет хранить int, а другой будет хранить строку, Два типа данных разной длины не могут гарантировать хранение нескольких, что противоречит положения фиксированной длины, поэтому и тот же тип данных.
Увидев это, большинство людей должно подумать: ну, это почти совпадает с массивом, который я знаю.
Тогда давайте немного поувлекаемся и перейдем к основному блюду, массивам в JavaScript.
Массивы в JavaScript
Давайте сначала посмотрим на код:
let arr = [100, 12.3, "red", "blue", "green"];
arr[arr.length] = "black";
console.log(arr.length); // 6
console.log(arr[arr.length-1]); //black
Эти несколько строк кода показывают, что делает массивы JS необычными. В первой строке кода в массиве хранятся три типа данных? ? Вторая строка кода действительно добавляет значение в массив? ? Третья и четвертая строки кода проверены, длина массива изменилась, добавленное значение вступило в силу.
В дополнение к этому в массивах JS есть много специальных мест, таких как:
Массив JS может хранить не только три вышеуказанных типа данных, но и массив, объект, функцию, число, неопределенное значение, нуль, строку, логическое значение и так далее.
Массивы JS могут вести себя как стеки, предоставляя массивамpush()а такжеpop()метод. Он также может вести себя как очередь, используяshift()а такжеpush()метод, вы можете использовать массивы точно так же, как очереди.
Увидев это, вы сможете увидеть некоторые подсказки и сделать смелое предположение, что в массиве JS реализована не базовая структура данных, а на его основе должна быть какая-то инкапсуляция. Просто угадывать недостаточно. Мы должны реалистично относиться к технологиям. Давайте начнем гонку и шаг за шагом проверим наши предположения.
Получение в нижней части этого: реализация массивов из исходного кода V8
Говорить дешево, покажи мне код.
На следующем рисунке показан исходный код массива в V8:
Во-первых, мы видимJSArrayунаследовано отJSObject, то есть массив — это специальный объект.
Тогда это объясняет, почему массивы JS могут хранить разные типы данных.Это объект, а также внутренняя форма хранения ключ-значение.
Давайте используем этот код для проверки:
let a = [1, "hello", true, function () {
return 1;
}];
Давайте посмотрим, как реализован нижний слой через jsvu:
Как видите, нижний слой — это Map, ключ — это индекс 0, 1, 2, 3, а значение — это элемент массива.
Индекс массива на самом деле является строкой.
После проверки этой проблемы давайте продолжим смотреть на приведенный выше исходный код V8, подготовимся и приготовимся увидеть большой шаг! Как видно из комментариев, массивы JS имеют две формы, быструю и медленную, что? не понимаете английский? Тогда я позволю Google перевести это для нас!
fast:
Структура быстрого резервного хранилища представляет собой FixedArray и длину массива
FixedArray — это похожий на массив класс, реализованный V8, который представляет фиксированную длину непрерывной памяти.
slow:
Структура медленного резервного хранилища представляет собой хэш-таблицу с числовым ключом.
HashTable, очень хорошо объяснено в Википедии:
Хеш-таблица (также называемая хеш-таблицей) — это структура данных, которая напрямую обращается к ячейке памяти в соответствии с ключом. То есть он обращается к записям, вычисляя функцию значения ключа, которая сопоставляет запрашиваемые данные с местоположением в таблице, что ускоряет поиск. Эта функция отображения называется хеш-функцией, а массив записей называется хеш-таблицей.
Быстрое и медленное в комментариях к исходному коду — это лишь краткое объяснение. Они соответствуют быстрым массивам и медленным массивам. Давайте посмотрим, как эти две формы реализованы в деталях.
Быстрые элементы
Быстрый массив — это метод линейного хранения. Методом хранения вновь созданного пустого массива по умолчанию является быстрый массив. Длина быстрого массива является переменной. Размер пространства для хранения может динамически регулироваться в соответствии с добавлением и удалением элементов. Как он расширяется и сжимается?
в исходном кодеРасширениеМетод реализации (С++):
Метод расчета новой мощности:
new_capacity = old_capacity /2 + old_capacity + 16
То есть новая емкость после расширения = в 1,5 раза больше старой емкости + 16
После расширения массив будет скопирован в новое пространство памяти, исходный код:
После прочтения расширения давайте посмотрим, как уменьшить пространство массива, когда есть лишнее пространство.
в исходном кодесокращатьМетод реализации (С++):
Можно видеть, что суждение о сжатии массива: Если емкость >= 2 x длина + 16, уменьшите регулировку емкости, в противном случае используйте объект отверстий (что такое объект отверстия? Объясняется ниже), чтобы заполнить неинициализированную позицию.
Если уменьшится, то насколько?
Посмотрите на этот код на изображении выше:
этоelements_to_trimЭто размер, который нужно уменьшить, его нужно судить по длине + 1 и old_length, нужно ли сжимать все освободившееся пространство или только 1/2.
После объяснения расширения и сокращения давайте взглянем на только что упомянутый объект отверстий.
Объект отверстия относится к массиву, в котором выделено пространство, но не размещен ни один элемент. Для отверстий в быстром массиве есть специальный режим, а в режиме Fast Elements есть расширение, котороеFast Holey Elementsмодель.
Режим Fast Holey Elements подходит для дыр в массиве, то есть только некоторые индексы имеют данные, а другие индексы не имеют значения.
Когда будет режим Fast Holey Elements?
Когда в массиве есть дыры, неназначенный индекс массива будет хранить специальное значение, так что при доступе к этим местоположениям вы получите undefined. В данном случае это будет режим Fast Holey Elements.
Режим Fast Holey Elements, как и режим Fast Elements, будет динамически выделять непрерывное пространство для хранения, а размер выделенного пространства определяется наибольшим значением индекса.
При создании нового массива, если емкость не задана, V8 по умолчанию будет использовать режим Fast Elements.
Если вы хотите задать емкость массива, но не инициализировать внутренние элементы, напримерlet a = new Array(10);, чтобы в массиве была дыра, это будет реализовано в режиме Fast Holey Elements.
Используйте jsvu для вызова базовой реализации версии v8-debug для проверки:
С одного взгляда,HOLEY_SMI_ELEMENTSЭто паттерн Fast Holey Elements.
Если массив инициализирован, напримерlet a = new Array(1,2,3);, такой дыры не существует, то есть она реализована в режиме Fast Elements.
проверять:
этоPACKED_SMI_ELEMENTSЭто режим Fast Elements.
Сначала идет быстрый массив, затем посмотрите на медленный массив:
Медленные массивы (элементы словаря)
Медленный массив — это хранящаяся в памяти форма хеш-таблицы. Нет необходимости открывать большое непрерывное хранилище, что экономит память, но из-за необходимости поддерживать такую HashTable ее эффективность будет ниже, чем у быстрого массива.
Структура словаря в исходном коде
Как видите, внутри есть HashTable, а затем определены некоторые методы работы, подобные HashMap в Java.
Поскольку есть быстрые массивы и медленные массивы, структура хранения не может быть статичной, и в определенных обстоятельствах должны быть быстрые и медленные преобразования массивов.Давайте посмотрим, что происходит в этих обстоятельствах.
Преобразование между быстрыми массивами и медленными массивами
быстро -> медленно
Во-первых, давайте посмотрим на исходный код, чтобы решить, следует ли преобразовывать быстрый массив в медленный массив в V8:
Ключевой код:
1. Новая мощность> = 3 * расширенная емкость * 2, она будет преобразована в медленный массив. 2. Когда добавленная емкость тока index> = kmaxgap (1024) (то есть существует не менее 1024 отверстий), он будет преобразован в медленный массив.
В основном мы рассматриваем случай второго кода ключа.
kMaxGap — константа в исходном коде со значением 1024.
То есть при присвоении значения массиву он использует гораздо больше, чем емкость текущего массива + 1024 (имеется больше или равно 1024 дырок, в это время выделяется большой объем пространства для массива может привести к пустой трате места для хранения, чтобы оптимизировать пространство, будет преобразован в медленный массив.
Код реального молотка:
let a = [1, 2]
a[1030] = 1;
В массиве всего три элемента, но значение хранится в позиции 1030, тогда в середине будет больше 1024 отверстий, и тогда массив станет медленным.
Давайте проверим:
Видно, что массив на данный момент действительно имеет тип словаря, успех!
Ну, после чтения быстрого массива в медленный массив, а затем посмотрите на преобразование медленного массива в быстрый массив.
медленно -> быстро
Для массива, реализованного в виде хеш-таблицы, каждый раз, когда пространство увеличивается, эвристический алгоритм V8 будет проверять занятость его пространства, и если его пустые элементы уменьшатся до определенной степени, он будет преобразован в режим быстрого массива.
Исходный код решения о том, следует ли его преобразовать в быстрый массив в V8:
Ключевой код: Когда элементы медленного массива могут быть сохранены в быстром массиве, а длина находится между smi и сохраняется только 50% пространства, он будет преобразован в быстрый массив.
Напишем код для проверки:
let a = [1,2];
a[1030] = 1;
for (let i = 200; i < 1030; i++) {
a[i] = i;
}
Как мы сказали выше, добавление значения в позицию 1030 вызовет более 1024 отверстий, и массив будет реализован с использованием режима Словаря.
Итак, теперь мы добавляем в этот массив еще несколько значений, чтобы заполнить дыры, и присваиваем значения 200-1029, чтобы медленный массив больше не экономил 50% места по сравнению с быстрым массивом. вещи будут происходить?
Видно, что массив стал режимом Fast Holey Elements быстрого массива, и проверка прошла успешно.
Это потому, что объем памяти быстрого массива непрерывен, а эффективность высока, он должен быть лучше? вообще-то нет.
У каждого есть преимущества и недостатки
Быстрый массив предназначен для применения к большому блоку непрерывной памяти путем обмена пространства на время для повышения эффективности. Медленные массивы обменивают время на пространство, не нуждаются в непрерывном пространстве, экономят память, но расплачиваются низкой эффективностью.
Расширение: ArrayBuffer
JS также представил массивы в ES6, которые могут выделять непрерывную память по мере необходимости.ArrayBuffer.
ArrayBuffer будет претендовать на заданный размер бинарного пространства из памяти, но с ним нельзя напрямую манипулировать.Вам нужно построить представление через ArrayBuffer и оперировать этой памятью через представление.
var bf = new ArrayBuffer(1024);
Эта строка кода применяется для области памяти размером 1 КБ. Но он не может работать напрямую с arrayBuffer, вам нужно назначить его представлению для работы с памятью.
var b = new Int32Array(bf);
Эта строка кода создает массив 32-битных целых чисел со знаком, каждое из которых занимает 4 байта, с длиной 1024/4 = 256.
Проверка кода:
Суммировать
Увидев это, голова гудит? Сделайте вдох, давайте подведем итоги, в этой статье в основном обсуждаются несколько вещей:
1. Что такое массив в традиционном понимании?
2. Что особенного в массивах в JavaScript
3. Исследуйте базовую реализацию массивов JS из исходного кода V8.
4. Как преобразовать два режима массивов JS
5. Массивный буфер
В целом, массивы JS кажутся отличными от традиционных массивов.На самом деле, V8 сделал слой инкапсуляции базовой реализации, используя две структуры данных для реализации массивов и оптимизируя производительность массивов за счет выбора времени и пространственной широты. .
Понимание базовой реализации массивов может помочь нам писать более эффективный код.