Строим свой full-stack на JavaScript: Основы. Механизмы времени выполнения
Стек вызова функций (Call stack in programming languages)
Как рассматривать стек вызова функции (Call Stack) в контексте языков программирования. Хочу сказать, что стек вызова не совсем то, что демонстрирует нам большинство материалов. Чтобы окончательно понять что такое стек вызова, необходимо вернуться к азам и рассмотреть как работает стек вызова в операционной системе, почему именно так? Потому что нельзя рассматривать стек вызова функций оторванно от физической памяти и возможностью управления ею и тем самым не надо забывать, что стек вызова функций это не «виртуальная» операция, а конкретное место в памяти выделяемое операционной системой для выполнение программного кода функции, которая была запущена внутренним или внешним API (будь-то браузера, IDE или движка какого либо языка).
Хочу определить что такое стека вызова функции в низкоуровневых (low-level programming languages) языках (Assembler, C++):
На примере Ci++:
(В современных низкоуровневых языках есть современные библиотеки позволяющие поддерживать работу ООП и контролировать стек функции не на физическом уровне, а использованием вывода консоли: Poppy, Pantheios)
Шаг 1: запуск лейаута кода.
В лейауте кроме самих инструкций находится дополнительная информация (переменные, декларативные данные, дополнительные технические данные и …)
Получив первую инструкцию о запуске ОС начинает строить стек. Сначала выделяет физическое место на кластерах памяти и заполняет его данными, но какими:
Инструкция получена, создается сам стек в котором основная часть - выделенное место для выполнения операций, а сегмент стека для хранения данных для возврата результата выполнения функции.
На рисунке 1 показаны стеки (участки памяти) предназначенные для выполнения кода для каждой функции, с правой стороны находится сегмент, куда отправляются инструкции возврата в порядке вызова функций.
На определенном этапе, функция либо возвращает результат либо вызывает следующую функцию. В сегмент стека кладется информация не о времени, месте или каких-то других параметрах вызова функции, только адрес(в бинарной нотации), куда надо вернуть результат вызова функции. Так же в этот сегмент попадают локальные переменные.
Инструкция возврата вызова, это не место вызова этой функции, а следующая за ней инструкция.
Сегмент стека (который мы сейчас по простоте называем стеком вызова) это отдельный участок памяти, в котором храняться инструкции о возврате результатов вызванных функции. Используется метод: кто пришел последний - уйдет первый (LIFO).
В языках подобных С++ имплементированы два метода: Call и Ret, Call создает инструкцию с адресом(в бинарной нотации) и кладет на верхний уровень стека, Ret не содержит адреса, этот метод просто забирает верхнюю инструкцию и возвращает нас по указанному адресу. Сам стек, после возвращения данных и выполнения функций уничтожается и данные из него недоступны.
На рисунке 2 схематично нарисован сегмент стека вызова функций и указаны локальные переменные и инструкции по возврату.
Далее необходимо понять, как высокоуровневые языки реализовывают работу стека вызова. Давайте рассмотрим два случая: языки использующие многопоточность и однопоточные языки. Почему именно такие варианты? Потому что именно многопоточность (multithreading) и однопоточность определяет взаимодействие виртуальной и физической памяти ресурса.
Языки использующие многопоточность рассмотрим на примере Java.
На рис 3 приведена простая схема распределения динамической памяти. (Здесь тоже хочу сказать, что динамическая память также использует физические кластеры, то есть общее представление стека вызовов будет таким же как у низкоуровневых языков), на этом рисунке еще более схематично динамическая память при вызове функции.
В движок java имплементирована специальная коллекция Stack, у которой есть два метода push(добавит данные) и pop(удалить данные). Виртуальная машина Javaведет запись всех вызванных функций и с каждым вызовом функции создает StackTraceElement. После завершения выполнения функции StackTraceElement уничтожается, поэтому информация о стеке вызовов всегда актуальная. С Помощью метода getMethodName можно всегда получить информацию о методе верхнего элемента StackTraceElement, а значит о методе вызова функции.
На рисунке представлен стек вызова с переменными и методами объектов, реализованных в Java
Javascript: Javascript однопоточный скриптовый язык использующий очередь функций обратного вызова(callback functions queue) с методом FIFO (первый пришел - первый уйдешь).
Два варианта взаимодействия физической и виртуальной памяти в Javascript:
Сам стек как и базовые использует LIFO, а очередь колбэков - FIFO. Так же в V8 имплементированы методы push и pop, декларация идентична методам, реализованным в Java.
Таймеры в JS
Методы Javascript использующие таймеры использующие API OS и таймеры которые работают на API браузера. Таймеры всегда передвигают выполнение функции-колбэка в конец стека вызовов. Что это значит? Это значит, что в браузере выполняя методы setTimeout, setInterva сначала запускается таймер, а лишь потом функция-колбэк попадает в очередь ожидания. Если в момент попадания колбэка стек переполнен, колбэку приходится ждать своей очереди. Таймеры запущенные вне браузера реализованы на основании либо внутренних методов V8 либо при обращении к API окружения (API OS).
Особенностью языка Javascript является технология ajax или иначе возможность отправки асинхронных запросов (XMLHTTPRequest) и выполнения каких либо операций без задержки выполнения основного кода. XMLHTTPRequest может быть отправлен синхронно, но при этом весь остальной код будет дожидаться либо результата отправки запроса, что порой нецелесообразно. Технология ajax реализована исключительно в браузерах, что делает выделяет Javascript из группы языков использующих async. Асинхронные запросы в JS используют цикл событий с очередью колбэков (event loop with callback queue). В остальных языках программирования тоже есть возможность запуска асинхронного кода (Python (asyncio), C#(async/await)), что позволяет выполнять какие-то операции без задержки выполнения основных функций, принципом тут тоже выступает цикл событий, где функция колбэк помещается в очередь ожидания. Принцип работы очереди - FIFO.
Наиболее часто используемыми в веб-программировании структурами данных являются стек и очередь. При этом многие не знают этого удивительного факта.
СтекПоследовательный порядок стека обычно описывается как стопка тарелок в кафетерии. Когда тарелка добавляется — стопка сохраняет порядок, который существовал до этого. Каждый раз, когда мы добавляем новую тарелку, она подвигает нижнюю часть стопки и одновременно становится верхней тарелкой.
Этот процесс складывания тарелок сохраняет последовательный порядок, когда каждая тарелка добавляется в стопку. Снятие тарелки из стопки также не нарушит последовательность всех тарелок. Если тарелка снимается сверху стека, каждая тарелка в стопке по-прежнему будет сохранять тот же порядок в стопке.
В качестве более технологичного примера стека можно привести операцию «Отменить » (Undo ) в текстовом редакторе. Каждый раз, когда текст вводится в текстовый редактор, он помещается в стек. Самое первое изменение текста представляет собой дно стека; самое последнее — вершину. Если пользователь хочет отменить самое последнее изменение, удаляется верх стека. Этот процесс может повторяться до тех пор, пока не останется ни одного изменения.
Операции стекаТак как теперь у нас есть концептуальная модель стека, давайте определим две операции стека:
- push(data) — добавляет данные;
- pop() — удаляет последние добавленные данные.
Теперь давайте напишем код для стека.
Свойства стекаМы создадим конструктор с именем Stack . Каждый экземпляр Stack будет иметь два свойства: _size и _storage :
function Stack() { this._size = 0; this._storage = {}; }
this._storage — позволяет каждому экземпляру Stack иметь собственный контейнер для хранения данных; this._size отображает сколько раз данные были добавлены в текущую версию Stack . Если создается новый экземпляр Stack и в хранилище добавляются данные, то this._size увеличится до 1. Если данные снова добавляются в стек, this._size увеличится до 2. Если данные удаляются из стека, this._size уменьшается до 1.
Методы стекаОпределим методы, с помощью которых можно добавлять (push ) и удалять (pop ) данные из стека. Начнем с добавления данных.
Метод push(data)Этот метод может быть общим для всех экземпляров Stack , так что мы добавим его в прототип Stack .
Требования к этому методу:
Stack.prototype.push = function(data) { // увеличение размера хранилища var size = this._size++; // назначает размер в качестве ключа хранилища // назначает данные в качестве значения этого ключа this._storage = data; };
Объявляем переменную size и присваиваем ей значение this._size ++ . Устанавливаем переменную size в качестве ключа this._storage , data — в качестве значения соответствующего ключа.
Если стек вызывал push(data) пять раз, то размер стека будет 5. Первое добавление данных в стек назначит этим данным ключ 1 в this._storage . Пятый вызов push(data) присвоит данным ключ 5 в this._storage . Мы только что задали порядок для наших данных.
Метод 2 из 2: pop()Следующий логический шаг заключается в удалении данных из стека. Удаление данных из стека подразумевает удаление только последних добавленных элементов.
Цели для этого метода:
Stack.prototype.pop = function() { var size = this._size, deletedData; deletedData = this._storage; delete this._storage; this.size--; return deletedData; };
pop() выполняет все перечисленные нами задачи. Мы объявляем две переменные: size инициализируется значением размера стека; deletedData назначается для последних добавленных в стек данных. Затем мы удаляем пару ключ-значение из последних добавленных элементов. После этого мы уменьшаем размер стека на 1, и возвращаем данные, которые были удалены из стека.
Если мы протестируем текущую реализацию pop() , то увидим, что она работает в следующих случаях: если мы передаем данные в стек, то размер стека увеличивается на один; если мы удаляем данные из стека, его размер уменьшается на один.
Но если мы выполним все операции в обратном порядке, то возникает проблема. Рассмотрим следующий сценарий: мы вызываем pop() , а затем push(data) . Размер стека становится -1, а затем 0. Но корректный размер нашего стека 1.
Чтобы решить эту проблему, мы добавим в pop() оператор if :
Stack.prototype.pop = function() { var size = this._size, deletedData; if (size) { deletedData = this._storage; delete this._storage; this._size--; return deletedData; } };
После добавления оператора if , тело кода выполняется только тогда, когда в нашем хранилище есть данные.
Полная реализация стекаНаша реализация стека завершена. Вот окончательный вариант кода:
function Stack() { this._size = 0; this._storage = {}; } Stack.prototype.push = function(data) { var size = ++this._size; this._storage = data; }; Stack.prototype.pop = function() { var size = this._size, deletedData; if (size) { deletedData = this._storage; delete this._storage; this._size--; return deletedData; } };
От стека к очередиСтек может оказаться полезным, если мы хотим добавлять и удалять данные в последовательном порядке. Исходя из определения, из стека можно удалять только последние добавленные данные. Но что, если мы хотим удалить старые данные? Для этого нам нужно использовать структуру данных под названием очередь.
ОчередьПодобно стеку, очередь является линейной структурой данных. Но в отличие от него, из очереди удаляются только элементы, добавленные раньше других.
Чтобы помочь вам понять, как это работает, я приведу одну аналогию. Представьте себе очередь по записи по талонам. Каждый клиент берет талон и обслуживается, когда называется его номер. Клиент, который получил талон с номером один, должен быть обслужен первым.
Клиент, который получил второй талон, будет обслужен вторым. Если бы наша система обслуживания работала как стек, клиент, который был добавлен в стек первым, был бы обслужен последним.
Практическим примером реализации очереди является цикл событий веб-браузера. В нем различные события, которые были инициированы, например, нажатием кнопки мыши, добавляются в очередь цикла событий и обрабатываются в порядке их поступления.
Операции очередиКак вы заметили, операции очереди очень похожи на стек. Разница заключается в том, откуда убираются данные:
- enqueue(data) — добавляет элементы в очередь;
- dequeue — удаляет самые старые данные из очереди.
Теперь давайте напишем код для очереди.
Свойства очередиДля реализации мы создадим конструктор с именем Queue . Затем мы добавим три свойства: _oldestIndex , _newestIndex и _storage :
function Queue() { this._oldestIndex = 1; this._newestIndex = 1; this._storage = {}; }
Методы очередиТеперь мы создадим три метода, распространяющиеся на все экземпляры очереди: size(), enqueue(data) и dequeue(data).
Метод size()Цели этого метода:
Queue.prototype.size = function() { return this._newestIndex - this._oldestIndex; };
Реализация size() может показаться вам слишком простой, но вы быстро поймете, что это не так. Давайте ненадолго вернемся к реализации метода size() для стека.
Представим, что мы добавляем в стек пять тарелок. Размер нашего стека — пять, и каждая тарелка имеет соответствующий ей номер от 1 (первая добавленная тарелка ) до 5 (последняя добавленная тарелка ). Если мы уберем три тарелки, то у нас останется две тарелки.
Мы можем просто вычесть три из пяти, чтобы получить правильный размер — два. Вот основной принцип для размера стека: текущий размер представляет собой корректный ключ, связанный с номером тарелки в верхней части стека (2) и другой тарелки в стеке (1). Другими словами, диапазон ключей всегда имеет границы от текущего размера до одного.
Теперь давайте применим эту реализацию размера стека для очереди. Представьте себе, что пять клиентов получили талоны. Первый клиент имеет талон с номером 1, пятый клиент имеет талон с номером 5. В очереди клиент с первым талоном обслуживается первым.
Давайте представим, что первый клиент обслужен и этот талон удаляется из очереди. По аналогии со стеком мы можем получить корректный размер очереди путем вычитания 1 из 5. В очереди в настоящее время есть четыре необслуженных талона. Тут и возникает проблема: размер больше не соответствует номерам, указанным на талонах. Если мы просто вычтем 1 из 5, мы получим размер 4. Мы не можем использовать 4 для определения текущего диапазона талонов, оставшихся в очереди. В очереди остались талоны с номерами от 1 до 4 или от 2 до 5? Ответ неясен.
Вот для чего нам нужны два свойства _oldestIndex и _newestIndex . Представьте себе, что наша система обслуживания клиентов имеет две системы выдачи талонов:
Когда числа в обеих системах одинаковы, это значит, что каждый клиент в очереди был обслужен, и очередь пуста. Мы будем использовать следующий сценарий, чтобы доказать эту логику:
Для enqueue у нас есть две задачи:
Мы создадим следующую реализацию enqueue(data) :
Queue.prototype.enqueue = function(data) { this._storage = data; this._newestIndex++; };
В первой строке мы используем this._newestIndex , чтобы создать новый ключ для this._storage и присвоить ему значение data. this._newestIndex всегда начинается с 1. Во второй строке кода, мы увеличиваем this._newestIndex на 1, и значение теперь равняется 2.
Метод dequeue()Задачи для этого метода:
Queue.prototype.dequeue = function() { var oldestIndex = this._oldestIndex, deletedData = this._storage; delete this._storage; this._oldestIndex++; return deletedData; };
В теле dequeue() мы объявляем две переменные. Первой переменной, oldestIndex , присваивается текущее значение очереди для this._oldestIndex . Второй переменной, deletedData , присваивается значение, содержащееся в this._storage .
Но в этой реализации dequeue() не учтена ситуация, когда данные удаляются еще до того, как в очередь были добавлены какие-либо элементы. Нам нужно создать условие, чтобы решить эту проблему.
What You"ll Be Creating
Две из наиболее часто используемых структур данных в веб-разработке - это стеки и очереди. Многие пользователи Интернета, в том числе веб-разработчики, не знают об этом удивительном факте. Если вы один из этих разработчиков, тогда подготовьтесь к двум просветительским примерам: операция «отменить» текстового редактора использует стек для организации данных; Цикл событий веб-браузера, который обрабатывает события (клики и т.д.), использует очередь для обработки данных.
Теперь остановитесь на мгновение и представьте, сколько раз мы, как пользователь и разработчик, используем стеки и очереди. Это потрясающе, не так ли? Из-за их повсеместности и сходства в дизайне я решил использовать их для ознакомления со структурами данных.
СтекВ информатике стек представляет собой линейную структуру данных. Если это предложение имеет для вас предельное значение, как оно изначально имело для меня, рассмотрим эту альтернативу: стек организует данные в последовательный порядок.
Этот последовательный порядок обычно описывается как стопка блюд в столовой. Когда тарелку добавляют в стопку блюд, она сохраняет порядок, когда она была добавлена; кроме того, когда добавляется другая тарелка, ее подталкивают к нижней части стопки. Каждый раз, когда мы добавляем новую тарелку, тарелка подталкивается к нижней части стопки, но она также представляет собой верхнюю часть стопки тарелок.
Этот процесс добавления тарелок сохранит последовательный порядок, когда каждая тарелка была добавлена в стек. Удаление тарелок из стека также сохранит последовательный порядок всех тарелок. Если тарелка удаляется из верхней части стека, каждая другая тарелка в стеке по-прежнему сохраняет правильный порядок в стеке. То, что я описываю, возможно, слишком выглядит чересчур подробно, но смысл заключается в том, как тарелки добавляются и удаляются в большинстве кафетерий!
Чтобы предоставить более технический пример стека, вспомним операцию «отменить» текстового редактора. Каждый раз, когда текст добавляется в текстовый редактор, этот текст помещается в стек. Первое дополнение к текстовому редактору представляет собой нижнюю часть стека; Последнее изменение представляет собой верхнюю часть стека. Если пользователь хочет отменить последнее изменение, верхняя часть стека будет удалена. Этот процесс можно повторить до тех пор, пока в стек не будет добавлено больше дополнений, это пустой файл!
Операции стекаПоскольку теперь у нас есть концептуальная модель стека, определим две операции стека:
- push(data) добавляет данные.
- pop() удаляет последние добавленные данные.
Теперь давайте напишем код для стека!
Для нашей реализации мы создадим конструктор Stack . Каждый экземпляр Stack будет иметь два свойства: _size и _storage .
Function Stack() { this._size = 0; this._storage = {}; }
this._storage позволяет каждому экземпляру Stack иметь собственный контейнер для хранения данных; this._size отражает количество попыток передачи данных в текущую версию Stack . Если создается новый экземпляр Stack и данные помещаются в его хранилище, то this._size будет увеличиваться на 1. Если данные снова вставляются в стек, this._size будет увеличиваться до 2. Если данные удаляются из стека, то this._size будет уменьшаться до 1.
Методы стекаНам нужно определить методы, которые могут добавлять (push) и удалять (pop) данные из стека. Начнем с добавления данных.
Метод 1 из 2: push(data)
(Этот метод можно использовать для всех экземпляров Stack , поэтому мы добавим его в прототип Stack .)
У нас есть два требования к этому методу:
Наше реализация push(data) включает в себя следующую логику. Объявите переменную с именем size и присвойте ей значение this._size ++ . Определите size в качестве ключа this._storage . И определите data как значение соответствующего ключа.
Если бы наш стек вызывал push(data) пять раз, тогда размер нашего стека был бы 5. Первое добавление данных в стек присвоит этим данным ключ из 1 в этом._storage . Пятый вызов push(data) присваивает этим данным ключ из 5 в this._storage . Мы только что присвоили порядок нашим данным!
Метод 2 из 2: pop()
Теперь мы можем передавать данные в стек; Следующий логический шаг - выталкивание (удаление) данных из стека. Забор данных из стека - это не просто удаление данных; Он удаляет только самые последние добавленные данные.
Вот наши цели для этого метода:
pop() соответствует каждой из наших четырех целей. Сначала мы объявляем две переменные: size инициализируется размером стека, а deletedData присваивается последним данным, добавленным в стек. Во-вторых, мы удаляем пару ключ-значение наших последних добавленных данных. В-третьих, мы уменьшаем размер стека на 1. В-четвертых, мы возвращаем данные, которые были удалены из стека.
Если мы протестируем нашу текущую реализацию pop() , мы обнаружим, что она работает для следующего прецедента. Если мы вставляем данные push(data) в стек, размер стека увеличивается на единицу. Если мы достаем pop() данные из нашего стека, размер нашего стека уменьшается на единицу.
Однако возникает проблема, когда мы меняем порядок вызова. Рассмотрим следующий сценарий: мы вызываем pop() , а затем делаем push(data) . Размер нашего стека меняется на -1, а затем на 0. Но правильный размер нашего стека равен 1!
Чтобы обработать этот вариант использования, мы добавим оператор if в pop() .
Stack.prototype.pop = function() { var size = this._size, deletedData; if (size) { deletedData = this._storage; delete this._storage; this._size--; return deletedData; } };
С добавлением нашего оператора if тело нашего кода выполняется только при наличии данных в нашем хранилище.
Полная реализация стекаНаша реализация Stack завершена. Независимо от порядка, в котором мы ссылаемся на любой из наших методов, наш код работает! Вот окончательная версия нашего кода:
Function Stack() { this._size = 0; this._storage = {}; } Stack.prototype.push = function(data) { var size = ++this._size; this._storage = data; }; Stack.prototype.pop = function() { var size = this._size, deletedData; if (size) { deletedData = this._storage; delete this._storage; this._size--; return deletedData; } };
От стека к очередиСтек полезен, когда мы хотим добавить данные в последовательном порядке и удалить эти данные. Основываясь на своем определении, стек может удалить только самые последние добавленные данные. Что произойдет, если мы хотим удалить самые старые данные? Мы хотим использовать структуру данных под названием очередь.
Подобно стеку, очередь представляет собой линейную структуру данных. В отличие от стека, очередь удаляет только самые старые добавленные данные.
Чтобы помочь вам концептуализировать, как это будет работать, давайте возьмем минутку, чтобы использовать аналогию. Представьте себе, что очередь очень похожа на систему билетов в гастроном. Каждый клиент берет билет и обслуживается при вызове их номера. Сначала нужно обслуживать клиента, который берет первый билет.
Давайте далее предположим, что этот билет имеет номер «один», отображаемый на нем. Следующий билет имеет номер «два», отображаемый на нем. Клиент, который берет второй билет, будет обслуживаться вторым. (Если бы наша система билетов работала как стек, то клиент, который первым вступил в стек, был бы последним, который будет обслуживаться!)
Более практичным примером очереди является цикл событий веб-браузера. По мере запуска различных событий, таких как щелчок кнопки, они добавляются в очередь цикла событий и обрабатываются в том порядке, в котором они попали в очередь.
Операции очередиПоскольку теперь у нас есть концептуальная модель очереди, определим ее операции. Как вы заметили, операции очереди очень похожи на стек. Разница заключается в том, где данные удаляются.
- enqueue(data) добавляет данные в очередь.
- dequeue удаляет самые старые добавленные данные в очередь.
Теперь давайте напишем код для очереди!
Для нашей реализации мы создадим конструктор с именем Queue . Затем мы добавим три свойства: _oldestIndex , _newestIndex и _storage . Потребность в _oldestIndex и _newestIndex станет более понятной в следующем разделе.
Function Queue() { this._oldestIndex = 1; this._newestIndex = 1; this._storage = {}; }
Методы очередиТеперь мы создадим три метода, разделяемых между всеми экземплярами очереди: size() , enqueue(data) и dequeue(data) . Я опишу цели для каждого метода, покажу код для каждого метода, а затем объясню код для каждого метода.
Метод 1 из 3:
size()
У нас есть две цели для этого метода:
Реализация size() может показаться тривиальной, но вы быстро обнаружите, что это не так. Чтобы понять, почему так, мы должны быстро вернуться к тому, как размер был реализован для size .
Используя нашу концептуальную модель стека, давайте представим, что мы добавляем пять тарелок в стек. Размер нашего стека равен пяти, и каждая тарелка имеет число от одного (первая добавленная тарелка) до пяти (последняя добавленная тарелка). Если мы удалим три тарелки, то у нас будет две тарелки. Мы можем просто вычесть три из пяти, чтобы получить правильный размер, который равен двум. Вот наиболее важный вопрос о размере стека: Текущий размер представляет собой правильный ключ, связанный с тарелкой наверху стека (2), а другой - в стеке (1). Другими словами, диапазон ключей всегда от текущего размера до 1.
Теперь давайте применим эту реализацию size стека к нашей очереди. Представьте, что пять клиентов берут билет из нашей системы билетов. У первого клиента есть билет, показывающий номер 1, а пятый клиент имеет билет с номером 5. С очередью сначала обслуживается клиент с первым билетом.
Давайте теперь представим, что первый клиент обслуживается и этот билет удаляется из очереди. Подобно стеку, мы можем получить правильный размер нашей очереди, вычитая 1 из 5. В нашей очереди в настоящее время есть четыре небронированных билета. Теперь возникает проблема: размер больше не соответствует правильным номерам билетов. Если мы просто вычтем один из пяти, мы будем иметь размер 4. Мы не можем использовать 4 для определения текущего диапазона оставшихся билетов в очереди. Есть ли у нас билеты в очереди с номерами от 1 до 4 или от 2 до 5? Ответ непонятен.
Это преимущество наличия следующих двух свойств в очереди: _oldestIndex и _newestIndex . Все это может показаться запутанным - меня все еще иногда они путают. Что помогает мне рационализировать все, это следующий пример, который я разработал.
Представьте, что в нашем гастрономе есть две системы продажи билетов:
Вот самая сложная концепция в отношении наличия двух систем продажи билетов: когда номера в обеих системах идентичны, каждый клиент в очереди обработан и очередь пуста. Для усиления этой логики мы будем использовать следующий сценарий:
Теперь у нас есть свойство (_newestIndex), которое может указать нам наибольшее число (ключ), назначенное в очереди, и свойство (_oldestIndex), которое может рассказать нам самый старший номер индекса (ключа) в очереди.
Мы достаточно изучили size() , поэтому перейдем теперь к enqueue(data) .
Метод 2 из 3: enqueue (data)
Для enqueue у нас есть две цели:
На основе этих двух целей мы создадим следующую реализацию enqueue(data) :
Queue.prototype.enqueue = function(data) { this._storage = data; this._newestIndex++; };
Тело этого метода содержит две строчки кода. В первой строке мы используем this._newestIndex для создания нового ключа для this._storage и назначения ему data . this._newestIndex всегда начинается с 1. На второй строке кода мы увеличиваем значение this._newestIndex на 1, которое обновляет его значение до 2.
Это весь код, который нам нужен для enqueue(data) . Давайте теперь реализуем dequeue() .
Метод 3 из 3:
dequeue()
Вот цели для этого метода:
В теле dequeue() мы объявляем две переменные. Первой переменной oldestIndex присваивается текущее значение очереди для this._oldestIndex . Второй переменной, deletedData , присваивается значение, содержащееся в this._storage .
Затем мы удаляем самый старый индекс в очереди. После его удаления мы увеличиваем значение this._oldestIndex на 1. Наконец, мы возвращаем данные, которые мы только что удалили.
Подобно проблеме в нашей первой реализации pop() с стеком, наша реализация dequeue() не обрабатывает ситуации, когда данные удаляются до добавления каких-либо данных. Нам нужно создать условное выражение для обработки этого прецедента.
Queue.prototype.dequeue = function() { var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; if (oldestIndex !== newestIndex) { deletedData = this._storage; delete this._storage; this._oldestIndex++; return deletedData; } };
Всякий раз, когда значения oldestIndex и newestIndex не равны, мы выполняем ранее имевшуюся логику.
Полная реализация очередиНаша реализация очереди завершена. Давайте рассмотрим весь код.
Function Queue() { this._oldestIndex = 1; this._newestIndex = 1; this._storage = {}; } Queue.prototype.size = function() { return this._newestIndex - this._oldestIndex; }; Queue.prototype.enqueue = function(data) { this._storage = data; this._newestIndex++; }; Queue.prototype.dequeue = function() { var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; if (oldestIndex !== newestIndex) { deletedData = this._storage; delete this._storage; this._oldestIndex++; return deletedData; } };
ЗаключениеCho is a full-stack web-application developer. He dislikes mean people but likes the MEAN stack (MongoDB, ExpressJS, AngularJS, Node.js). During a typical week, he"ll be coding in JavaScript, writing about JavaScript, or watching movies NOT about JavaScript.
Популярность JavaScript растёт, его возможности используют на разных уровнях применяемых разработчиками стеков технологий и на множестве платформ. На JS делают фронтенд и бэкенд, пишут гибридные и встраиваемые приложения, а также многое другое.
С другой системой статистических сведений по GitHub можно ознакомиться , она подтверждает то, что было сказано выше.
Если множество проектов плотно завязаны на JavaScript, значит, разработчикам необходимо как можно более эффективно использовать всё, что даёт им язык и его экосистема, стремясь, на пути разработки замечательных программ, к глубокому пониманию внутренних механизмов языка.
Как ни странно, существует множество разработчиков, которые регулярно пишут на JavaScript, но не знают, что происходит в его недрах. Пришло время это исправить: этот материал посвящён обзору JS-движка на примере V8, механизмов времени выполнения, и стека вызовов.
Обзор Почти все слышали, в самых общих чертах, о JS-движке V8, и большинству разработчиков известно, что JavaScript - однопоточный язык, или то, что он использует очередь функций обратного вызова.Здесь мы поговорим, на довольно высоком уровне, о выполнении JS-кода. Зная о том, что, на самом деле, происходит при выполнении JavaScript, вы сможете писать более качественные программы, которые выполняются без «подвисаний» и разумно используют имеющиеся API.
Если вы недавно начали писать на JavaScript, этот материал поможет вам понять, почему JS, в сравнении с другими языками, может показаться довольно-таки странным.
Если вы - опытный JS-разработчик, надеемся, этот материал поможет вам лучше понять, как на самом деле работает то, чем вы пользуетесь каждый день.
Движок JavaScript V8 от Google - это широко известный JS-движок. Он используется, например, в браузере Chrome и в Node.js. Вот как его, очень упрощённо, можно представить:
Упрощённое представление движка V8
На нашей схеме движок представлен состоящим из двух основных компонентов:
- Куча (Memory Heap) - то место, где происходит выделение памяти.
- Стек вызовов (Call Stack) - то место, куда в процессе выполнения кода попадают так называемые стековые кадры.
Откуда же они берутся? Оказывается, что реальность выглядит немного сложнее, чем может показаться на первый взгляд.
Движок, цикл событий, очередь функций обратного вызова и API, предоставляемые браузером
Итак, помимо движка у нас есть ещё очень много всего. Скажем - так называемые Web API, которые предоставляет нам браузер - средства для работы с DOM, инструменты для выполнения AJAX-запросов, нечто вроде функции setTimeout , и многое другое.
Стек вызовов JavaScript - однопоточный язык программирования. Это означает, что у него один стек вызовов. Таким образом, в некий момент времени он может выполнять лишь какую-то одну задачу.Стек вызовов - это структура данных, которая, говоря упрощённо, записывает сведения о месте в программе, где мы находимся. Если мы переходим в функцию, мы помещаем запись о ней в верхнюю часть стека. Когда мы из функции возвращаемся, мы вытаскиваем из стека самый верхний элемент и оказываемся там, откуда вызывали эту функцию. Это - всё, что умеет стек.
Рассмотрим пример. Взгляните на следующий код:
Function multiply(x, y) {
return x * y;
}
function printSquare(x) {
var s = multiply(x, x);
console.log(s);
}
printSquare(5);
Когда движок только начинает выполнять этот код, стек вызовов пуст. После этого происходит следующее:
Стек вызовов в ходе выполнения программы
Каждая запись в стеке вызовов называется стековым кадром .
На механизме анализа стековых кадров основана информация о стеке вызовов, трассировка стека, выдаваемая при возникновении исключения. Трассировка стека представляет собой состояние стека в момент исключения. Взгляните на следующий код:
Function foo() {
throw new Error("SessionStack will help you resolve crashes:)");
}
function bar() {
foo();
}
function start() {
bar();
}
start();
Если выполнить это в Chrome (предполагается, что код находится в файле foo.js), мы увидим следующие сведения о стеке:
Трассировка стека после возникновения ошибки
Если будет достигнут максимальный размер стека, возникнет так называемое переполнение стека. Произойти такое может довольно просто, например, при необдуманном использовании рекурсии. Взгляните на этот фрагмент кода:
Function foo() {
foo();
}
foo();
Когда движок приступает к выполнению этого кода, всё начинается с вызова функции foo . Это - рекурсивная функция, которая не содержит условия прекращения рекурсии. Она бесконтрольно вызывает сама себя. В результате на каждом шаге выполнения в стек вызовов снова и снова добавляется информация об одной и той же функции. Выглядит это примерно так:
Переполнение стека
В определённый момент, однако, объём данных о вызовах функции превысит размер стека вызовов и браузер решит вмешаться, выдав ошибку:
Превышение максимального размера стека вызовов
Модель выполнения кода в однопоточном режиме облегчает жизнь разработчика. Ему не нужно принимать во внимание сложные схемы взаимодействия программных механизмов, вроде возможности взаимной блокировки потоков, которые возникают в многопоточных окружениях.
Однако, и у исполнения кода в однопоточном режиме тоже есть определённые ограничения. Учитывая то, что у JavaScript имеется один стек вызовов, поговорим о том, что происходит, когда программа «тормозит».
Параллельное выполнение кода и цикл событий Что происходит, когда в стеке вызовов имеется функция, на выполнение которой нужно очень много времени? Например, представьте, что вам надо выполнить какое-то сложно преобразование изображения с помощью JavaScript в браузере.«А в чём тут проблема?», - спросите вы. Проблема заключается в том, что до тех пор, пока в стеке вызовов имеется выполняющаяся функция, браузер не может выполнять другие задачи - он оказывается заблокированным. Это означает, что браузер не может выводить ничего на экран, не может выполнять другой код. Он просто останавливается. Подобные эффекты, например, несовместимы с интерактивными интерфейсами.
Однако, это - не единственная проблема. Если браузер начинает заниматься обработкой тяжёлых задач, он может на достаточно долгое время перестать реагировать на какие-либо воздействия. Большинство браузеров в подобной ситуации выдают ошибку, спрашивая пользователя о том, хочет ли он завершить выполнение сценария и закрыть страницу.
Браузер предлагает завершить выполнение страницы
Пользователям подобные вещи точно не понравятся.
Итак, как же выполнять тяжёлые вычисления, не блокируя пользовательский интерфейс и не подвешивая браузер? Решение этой проблемы заключается в использовании асинхронных функций обратного вызова. Это - тема для отдельного разговора.
Итоги Мы, в общих чертах, рассмотрели устройство JS-движка, механизмов времени выполнения и стека вызовов. Понимание изложенных здесь концепций позволяет улучшить качество кода.Уважаемые читатели! Этот материал - первый в серии «How JavaScript Works» из блога SessionStack . Уже опубликован второй - посвящённый особенностям V8 и техникам оптимизации кода. Как по-вашему, стоит ли его переводить?
В наши дни, какое бы веб-приложение Вы не писали, Вам приходится принимать множество архитектурных решений. И Вам хочется принимать их правильно: использовать технологии быстрой разработки, непрерывные итерации, максимально эффективно, быстро, надежно и др. Вы хотите делать меньше и получать больше, используя различные технологии. Но не всегда такие технологии просты в освоении.
По моему опыту (под которым далее будем понимать полный цикл разработки на JavaScript) выполняет все вышеперечисленные задачи. Возможно, Вы где-то с ним сталкивались; вероятно, Вы убеждены в его эффективности и даже спорили с друзьями по этому поводу. А сами пробовали? В этом посте я сделаю обзор full-stack JavaScript, расскажу зачем он Вам нужен и как все это работает.
Почему я использую JavaScriptЯ веб-разработчик с 1998 года. В те времена чаще всего мы использовали Perl для серверной разработки, но уже тогда на стороне клиента был JavaScript . С тех пор серверные технологии сильно изменились: одна за другой нас накрывали волны языков и технологий, таких как PHP, ASP, JSP, .NET, Ruby, Python и др. Разработчики стали осознавать, что использование двух разных языков на клиенте и сервере всё усложняет.
В начале эпохи PHP и ASP, когда шаблонизаторы были лишь в зачаточной стадии, разработчики встраивали код приложений прямо в HTML. Например:
alert("Welcome");
Или еще хуже:
var users_deleted = ; users_deleted.push("");
У начинающих существовали типичные проблемы с пониманием операторов в разных языках, к примеру таких, как for или foreach . Более того, написание подобного кода на сервере и на клиенте для обработки одних и тех же данных – неудобно даже сегодня:
$.ajax({ url:"/json.php", success: function(data){ var x; for(x in data){ alert("fruit:" + x + " points:" + data[x]); } } });
Первые попытки делать всё на одном языке заключались в создании клиентских компонентов на сервере и компиляции их в JavaScript. Это не работало так, как ожидалось, и многие их тех проектов провалились (к примеру, ASP MVC, заменивший ASP.NET Web forms , и GWT , которому на смену пришел весьма сомнительный Polymer). Но сама по себе идея была замечательной, а особенно: единый язык на клиенте и сервере, позволяющий нам повторно использовать компоненты и средства (ключевое слово здесь: средства).
Решение было простым: запустить JavaScript на сервере.
Одностраничные приложенияПри работе с full-stack JavaScript часто приходится создавать одностраничные приложения (SPA). Многие веб-разработчики ни раз искушались попробовать себя в SPA. Вы когда-нибудь сравнивали SPA и обычное веб-приложение при мобильном соединении? Разница в отклике порядка десятков секунд.
(Примечание: некоторые могут с этим не согласиться. Twitter, например,
