Комментарии 20
Если вы нашли неточности/ошибки в статье
местами ересь какая-то написана
Очевидным расточительством в этой процедуре является операция копирования содержимого старого массива в новый при каждом удвоении размера массива.
автор не в курсе о существовании в сях функции realloc() и и реализацию динамических массивов через указатели.
Достоинства массивов
Постоянное время доступа при условии наличия индекса. Поскольку каждому элементу массива соответствует определенный адрес в памяти, доступ к произвольному элементу массива осуществляется практически мгновенно при наличии соответствующего индекса.
постоянное время доступа будет только для архитектур без кешей памяти и многозадачности, плюс память должна быть одно типа.. И что значит - при условии наличия индекса? А что будет без наличия? Постоянное время не означает "практически мгновенно". Если у вас массив лежит в тормозной флеш-памяти, то это будет одно время, а если в каких-нибудь регистрах процессора, то совсем другое. А если память в своп на диске улетела - то третье.
Как хранить массив строк? Строки ведь имеют разную длину, а значит требуют разное количество памяти для своего хранения. Один из способов сохранить строки в массиве на языке Си – создать массив массивов (тут нужно понимать, что любая строка в Си это массив символов). Вложенные массивы обязательно должны быть одного размера, невозможно обойти физические ограничения массивов.
вероятно автор хотел сказать, что для массива строк можно использовать двумерный массив. До массива указателей он еще не дорос.
Описание массивов в статье на 95% касается Kotlin. Про Си лишь упоминания в качестве контраста реализаций. Детально о массивах в Си можно прочитать в других статьях :D
За замечание о доступе к элементам — спасибо!
ну тогда во введении/преамбуле не надо было замахиваться на все разные языки
В этой статье расскажу о массивах. Вы узнаете: как они устроены в памяти компьютера, особенности реализации в разных ЯП,
С другой стороны, Kotlin все равно реализован на сях (ИМХО), поэтому, мне кажется что и переписывание памяти в динамических массивах там должно быть аналогичными, т.е. должно случаться по необходимости, а не всегда
Kotlin все равно реализован на сях (ИМХО)
Эээ, нет
а на чем?
На Java и Kotlin. В частности, ArrayList для JVM BE просто алиасится в java.util.ArrayList, написанный на Java
А java на чем?
Компилятор Java написан, не поверите, на Java. JVM написана на C++, но там на C++ написан рантайм, интерпретатор и JIT. Внутри себя они, возможно, где-то и используют массивы C. При этом уже в Java массив не имеет ничего общего C++, не инстанциируется через него и вообще иначе реализован, иначе аллоцируется. При этом следующий уровень абстракции, ArrayList, написан на Java.
Компилятор можно хоть на бейсике писать вообще-то.
Где-то ж должно быть пересечение с системными вызовами [Dos]Alloc/Realloc/Free, логично это делать через Це malloc/realloc/free ну или делая вид, что их нет - через классы Це++. Вот оно и есть в рантайме.
При этом уже в Java массив не имеет ничего общего C++
ну не знаю. Мне иногда прямо кажется, что вот прямо вижу, как конструкции java на ++ реализованы
Где-то ж должно быть пересечение с системными вызовами [Dos]Alloc/Realloc/Free
Извините, вы про какие системные вызовы? В какой операционной системе? Если богомерзкой, то там LocalAlloc/LocalFree. Если в православной, то mmap. Но это не относится к языку C, это просто системные вызовы, которые можно вызывать откуда угодно. malloc/realloc/free - это уже часть стандарта C, но это уже shared libraries, которые линкуются (статически или динамически) и выполняются в user space. Внутри себя реализации malloc могут использовать системные вызовы для аллокации хипа в целом, но вряд ли вызывают их на каждый чих. И строго говоря, к массивам эти функции не имеют отношения.
JVM для объектов не использует ничего близко похожего на malloc, ибо управляемая куча принципиально иначе функционирует. И в управляемой куче, строго говоря, нет такой операции как free (даже GC внутри не "освобождает" память в хипе в том же смысле, в каком это делает free).
Массивы в Java принципиально иначе устроены. Начнём с того, что в C как таковых массивов-то и нет, есть просто арифметика указателей и синтаксический сахар, совмещающий арифметику указателей с дереференсом. В массивах Java есть длина, если полноценный vtable, ибо они тоже объекты и у них можно вызвать, например, toString или clone. При обращении к элементам массива индекс проверяется на выход за границы (если только не удалось доказать во время компиляции, что индекс не выходит), кидается исключение.
Ну вот и как можно утверждать, что массивы в JVM реализованы через массивы C? Не, ну в каком-то смысле можно так натянуть. В том, что данные массива так же расположены в памяти один за другим. Но это как утверждать, что человек - это такой же камень, потому что тоже состоит из атомов.
Небольшое уточнение. Какие там в Windows системные вызовы, никто не знает, всё вызывается через user-level DLL. Есть подозрение, что VirtualAlloc (а не LocalAlloc) реализован практически через прямой вызов в ядро, а вот всякие LocalAlloc/HeapAlloc - это по сути реализованый из коробки в dll аналог какого-нибудь jemalloc.
Извините, вы про какие системные вызовы? В какой операционной системе? Если богомерзкой, то там LocalAlloc/LocalFree.
Я эти вызовы видел еще когда они были маленькими и обзывались DosXXX, но какой фиг разница как назвать - внутре почти всегда все равно будут жить вызовы на уровне ассемблера.
В массивах Java есть длина, если полноценный vtable, ибо они тоже объекты
вообще говоря в утверждении "попа равно попа с ручкой" есть некое противоречие. Ручка - это длина. В парадигмах жабы не бывает попы без руки..
Ну вот и как можно утверждать, что массивы в JVM реализованы через массивы C?
я этого не утверждал
JVM для объектов не использует ничего близко похожего на malloc, ибо управляемая куча принципиально иначе функционирует. И в управляемой куче, строго говоря, нет такой операции как free (даже GC внутри не "освобождает" память в хипе в том же смысле, в каком это делает free).
Вот допустим, вам потребовался объект/массив на сколько-нибудь гигабайт памяти, вы поюзали и бросили, и далее ждете реакции допустим пользователя до потери пульса - что будет дальше? Отдаст java системе гигабайты?
> Ну вот и как можно утверждать, что массивы в JVM реализованы через массивы C?
я этого не утверждал
Выше было
С другой стороны, Kotlin все равно реализован на сях (ИМХО), поэтому,
мне кажется что и переписывание памяти в динамических массивах там
должно быть аналогичными,
А так же
Где-то ж должно быть пересечение с системными вызовами
[Dos]Alloc/Realloc/Free, логично это делать через Це malloc/realloc/free
ну или делая вид, что их нет - через классы Це++. Вот оно и есть в
рантайме.
вообще говоря в утверждении "попа равно попа с ручкой" есть некое
противоречие. Ручка - это длина. В парадигмах жабы не бывает попы без
руки..
Ваши указатели и malloc - это тоже ручка. Есть только регистры и числа в них. Остальное - от лукавого. А вообще, я сейчас даже ещё более смелое утверждение выскажу: Жаба, как и C (ИМХО) написаны на Verilog.
Вот допустим, вам потребовался объект/массив на сколько-нибудь гигабайт
памяти, вы поюзали и бросили, и далее ждете реакции допустим
пользователя до потери пульса - что будет дальше? Отдаст java системе
гигабайты?
Нет, не отдаст. Это как раз отличная иллюстрация того, что JVM не использует никак рантайм C для работы с массивами. И, кстати, для таких вот целей аллокации гигантских массивах в Java есть всяческие offheap решения (взять хотя бы тот же ByteBuffer).
Нет, не отдаст. Это как раз отличная иллюстрация того, что JVM не использует никак рантайм C для работы с массивами.
не, это не может быть иллюстрацией. Это как в Си - сделал malloc и забыл free
И, кстати, для таких вот целей аллокации гигантских массивах в Java есть всяческие offheap решения (взять хотя бы тот же ByteBuffer).
И как оно работает? Зовет напрямую системные вызовы? Я ByteBuffer пользую только для выкусывания данных из тср пакетов и вкусывания их взад (с матерями "ну че так чрезпопно, а не как у людей"), а про offheap как то и не задумывался.
А вообще, я сейчас даже ещё более смелое утверждение выскажу: Жаба, как и C (ИМХО) написаны на Verilog.
не канает для C " Verilog был создан Phil Moorby и Prabhu Goel зимой 1983—1984 годов "
JVM написана на C++
Хех, тоже не обязательно.
Мы как-то написали JVM на... Java. Вместо интерпретатора был baseline JIT compiler, который тоже был на... Java (правда использовал хитрые GCC конструкции для генерации binary code). И даже Memory Manager c GC был написан на... Java.
постоянное время доступа будет только для архитектур без кешей памяти и многозадачности, плюс память должна быть одно типа
Под постоянным, как я понял, имеется в виду O(1) (например, в отличие от связного списка с его O(n)). Это не отменяет наличия константы, которая так или иначе связана с особенностями оборудования. Иначе тогда и сортировку можно вместо O(N * log(N)) притянуть всякое . Кстати, кэш - не единственный источник тормозов. Может быть так же
Страничная адресация. Кэш страниц в ЦП + всякие особенности управления страницами в ОС
Банальное обновление памяти
Fun fact
Условно есть массив на 100к элеметов типа
String. В каждой ячейки массива лежит строка на 100к символов кодировки UTF-8. Сколько памяти потребуется, чтобы разместить такой массив в памяти компьютера?
Вообще-то в JVM в ячейке массива лежит указатель на строку, а не строка, как и для любого массива, содержащего не примитивы. Т.е. для 64-битной JVM это 100к 8-байтовых указателей, т.е. 800к. А строки лежат например в куче. Кроме того, длина строки не является частью сигнатуры типа для массива, поэтому при создании массива никакие 100к под один элемент не выделяются и не предполагаются, потому что эти строки уже где-то размещены к этому моменту (например в куче). И они могут быть разной длины.
Массивы в Kotlin