Как управлять памятью в javascript?

Question

[randomguyasking]

В процессе тестирования алгоритма бинарного поиска мне стало любопытно как будет работать алгоритм на массиве чисел размером 4 миллиарда. Ожидаемо, при попытке создать такой массив, nodejs говорит нам, что места в куче больше нет:

<--- Last few GCs --->

[133294:0x5da3760]     1203 ms: Scavenge 1148.2 (1181.1) -> 1148.2 (1181.1) MB, 42.9 / 0.0 ms  (average mu = 1.000, current mu = 1.000) allocation failure 
[133294:0x5da3760]     2175 ms: Mark-sweep 1722.0 (1755.0) -> 1709.7 (1743.0) MB, 479.6 / 0.0 ms  (+ 37.7 ms in 11 steps since start of marking, biggest step 4.7 ms, walltime since start of marking 2099 ms) (average mu = 1.000, current mu = 1.000) allocat

<--- JS stacktrace --->

FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory
 1: 0xa295e0 node::Abort() [node]
 2: 0x9782df node::FatalError(char const*, char const*) [node]
 3: 0xb99c2e v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [node]
 4: 0xb99fa7 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [node]
 5: 0xd3a3b5  [node]
 6: 0xd1fe8d  [node]
 7: 0xe7fc9e  [node]
 8: 0xe837fa  [node]
 9: 0x10243a3 v8::internal::Runtime_GrowArrayElements(int, unsigned long*, v8::internal::Isolate*) [node]
10: 0x13a5a99  [node]
[4]    133294 abort (core dumped)  node --heap-prof binarySearch.js

Возникает два вопроса:
1) В Javascript тип Number занимает 64 бита (альтернатив поменьше я не нашел). Соответственно, массив с 4 миллиардами таких элементов будет занимать 4 000 000 000 * 64 = 256000000000 бит или 32 гигабайта. Верно ли мое рассуждение?
2) Можно ли как-то решить данную проблему? Или только увеличение размера памяти и кучи поможет?

Answer 1

[ayazer]

это не относится в джаваскрипту, это типичная проблема когда данных слишком много чтоб с ними работать "в лоб".

так что (если уж хочется ради интереса решить эту задачу через бинарный поиск) распиливайте дерево на несколько мелких. Ведь с каждым шагом область поиска сужается в 2 раза. Если все данные занимают 60Гб (как написал Сергей Соколов), то после первых 5 шагов искать нужно будет уже только в 3.25Гб. Как вариант - используйте 1 дерево чтоб сузить область поиска до того размера который уже влазит в память, и потом уже загружайте второе дерево и ищите в нем

Comments

[randomguyasking]

Посмотрел на типизированные массивы, для моих целей подойдет uInt32 (вмещает 4 млрд), но все равно много памяти потребуется, если помнить про то, что там еще дополнительно сколько-то байт навешивается (как говорил Сергей). 4e9 * (4 + 8) = 48000000000 бит = 6 гигов. В принципе, уже лучше, но все равно очень много. Видимо, нужно распиливать данные, 4 млрд слишком много, чтобы с ними вот так просто работать, тут вы правы

[randomguyasking]

"используйте 1 дерево чтоб сузить область поиска"
да, вот этот вариант мне кажется самым оптимальным. Изначальный массив распилить на половину или даже 4 части, и тем самым не держать в памяти все данные целиком

[ayazer]

randomguyasking, адаптация существующего алгоритма (даже тривиального) к работе на больших объемах данных - это всегда весело и немного больно :)

[ayazer]

randomguyasking, можете распиливать на части пока любой кусок не станет достаточно мелким чтоб влезть в память (просто так распилить на 4 части нельзя, есть риск что разрежете группу). Тогда на первом шаге вы будете определять какой набор загрузить, а потом искать по нему. Можете распилить на очень много частей и разложить по папочкам в виде бинарного дерева. Тогда сначала вы будете использовать бинарный поиск чтоб найти в файловой системе нужный файл, а потом - чтоб найти в этом файле нужное значение. Можно вообще все хранить в одном файле, но рядом создать индекс который будет говорить с какой позиции и сколько значений надо загрузить в память. Главное вовремя остановится и не написать свою субд ;)

[randomguyasking]

ayazer, да, главное воврем остановиться) у меня изначальная задача была просто изучить как работает данный алгоритм)

Answer 2

[Сергей Соколов]

Объект числа занимает больше памяти, чем само число. Где-то пишут, что байты числа (8) + ещё 8 байт. Поэтому в 2 раза больше памяти потребуется только на числа: 4e9 * 16 байт = 64e9 байт примерно 60 Гб.
Эффективнее использовать память можно было бы с помощью ArrayBuffer.

Comments

[randomguyasking]

ArrayBuffer, как я понимаю, новая тема. Раньше про нее не слышал. В любом случае выходит, что простой тип number для этого не годится. В спеке нашел только то, что он 64 бита занимает, а про доп. 8 байт не увидел пока, но я тоже слышал что-то подобное.

[randomguyasking]

Посмотрел на typedArray, дл моих целей подойдет uInt32, но все равно много памяти потребуется, если помнить про то, что там еще дополнительно сколько-то байт навешивается. 4e9 * (4 + 8) = 48000000000 бит = 6 гигов. В принципе, уже лучше, но все равно очень много. Должен быть какой-то способ сделать это и не тратить столько памяти

[Сергей Соколов]

randomguyasking, можно компрессировать, исходя из дополнительных условий. Числа отсортированы? Тогда можно было бы записывать небольшое число разницы с предыдущим.