Динамические структуры данных: таблицы и списки

Довольно часто невозможно предсказать ни объём обрабатываемых данных, ни то, какую часть этих данных придётся хранить в памяти одновременно — возможно, все? Чтобы поддерживать такие — динамические — типы данных, нужен механизм управления свободной памятью, в котором были бы предусмотрены две пользовательских функции — выделение адресного пространства фиксированного размера (функция возвращает адрес выделенного фрагмента) и освобождение этого пространства (функции передаётся ранее выделенный адрес). Освобождённую память можно будет выделить повторно (если позволяет размер).

Динамическое управление памятью

Главная проблема при управлении памятью — т. н. фрагментация. Предположим, некоторый процесс 200 раз запросил килобайтный блок, и теперь в динамической памяти занято 200 килобайтов. Предположим, что никаких других запросов в это время не было, и эти 200 килобайтов менеджер памяти разместил подряд (наподобие массива). Однако далее процесс освобождает каждый второй заказанный блок. У менеджера памяти образуется свободные 100 килобайтов, но это 100 несвязных килобайтных фрагментов, и превратить их в один нельзя, потому что нет возможности манипулировать занятыми фрагментами. Например, нельзя сделать «дефрагментацию», слив все занятые фрагменты в единый блок, потому что изменятся их адреса. Значит, если программа затребует двухкилобайтный блок, место для его придётся искать где-то ещё.

Нетрудно догадаться, что алгоритмы управления памятью достаточно непросты и разнообразны, потому что зависят не только от логики выделения и освобождения памяти, но и от возможностей аппаратуры и эффективности тех или иных операций. Например, алгоритм может быть таким: вся выделенная память (в т. ч. выделенная и освобождённая) помещается в связный список. Когда процесс заказывает память, менеджер памяти сначала пытается выделить свободный фрагмент подходящего размера из списка. Когда процесс освобождает память, свободный фрагмент добавляется в список, а если оказывается, что его адресное пространство находится непосредственно рядом с другим свободным фрагментом, они агрегируются — вместо добавления увеличивается размер соседа. Здесь зачинается множество вариаций: эффективно ли каждый раз проходить по списку, или лучше какое-то время очень быстро выделять и удалять блоки, а когда-нибудь потом «собирать мусор» — агрегировать свободное пространство? а что с этим пространством потом делать? дожидаться, пока оно станет достаточно большим, и только тогда использовать для выделения памяти? Почти любые ответы на эти и множество других вопросов — «правильные», в зависимости от задач менеджера памяти и возможностей архитектуры.

Как правило, менеджер памяти — это либо пользовательская библиотека, либо свойство внешнего окружения (операционной системы).

В RARS есть внешний вызов № 9 — заказ памяти в куче. Куча — это область, которая в плоской модели памяти начинается с адреса 0x10040000 и заполняется динамически «вверх», навстречу стеку. В более сложных архитектурах предполагается, что процессу доступна только та память из кучи, которую он получил в результате подобного вызова, для остальных адресов применяются различные механизмы защиты памяти. Управление памятью берёт на себя окружение (например, ядро операционной системы). Если оно достаточно умное (например, построило упомянутый выше список и следит за ним), то может и освобождать выделенную память по запросу.

Однако в RARS никакой динамической защиты памяти нет — только ограничения, предписанные моделью. В этом случае нет смысла управлять кучей, которая и так целиком доступна пользовательской программе, поэтому внешнего вызова освобождения памяти в RARS нет. Строго говоря, RARS ecall 9, который называется sbrk, вообще не манипулирует динамической памятью — он увеличивает размер области статических данных, отодвигая начало кучи.

Тем не менее нам стоит посмотреть, как на низком уровне организуются динамические структуры данных. Мы будем предполагать, что окружение поддерживает выделение и освобождение памяти в стиле malloc и free. Вместо malloc будем использовать ecall 9, а вместо free — ничего, только отмечать в комментариях «этот фрагмент памяти надо освободить».

Таблицы

Таблицы (более точно — таблицы ссылок): массивы адресов. Служат для хранения определённого числа данных переменной длины. Сами данные при этом хранятся в динамически выделенной памяти, а все операции над таблицами — это работа с массивом адресов.

В примере таблица из 8 элементов заполнена наполовину.

Удаление элемента из таблицы

Ещё раз подчеркнём, что сам удаляемый объект в результате этой операции непосредственно не удаляется (на схеме показан «висячей» красной стрелкой). Программист должен позаботиться о том, чтобы адрес объекта не пропал до тех пор, пока память, занимаемая объектом, считается занятой.

Вернейший способ замусорить всю оперативную память — заводить в ней объекты, а потом забывать, где они лежали. Особенно эффективно это делать в цикле.

Вставка элемента в таблицу

Геометрическое масштабирование статических структур данных

Большинство структур данных, для моделирования которых используется массив фиксированного размера, можно сделать масштабируемыми. Идея в том, чтобы время от времени выделять для хранилища данных оперативную память другого размера — большую в случае переполнения и меньшую в случае, когда хранимых данных остаётся мало. Почти наверняка при этом потребуется скопировать все хранимые данные в новый массив, а память, занимаемую старым, освободить.

При этом:

• Адрес начала массива может меняться

• Неизменным остаётся только описатель такой структуры, в котором хранится этот переменный адрес и, например, размер выделенного массива.

• Операция масштабирования (заказ новой памяти + копирование всех данных) при кажущейся ресурсоёмкости имеет всего лишь линейную сложность: для масштабирования массива из N элементов потребуется по N операций чтения и записи
  • Иногда копирование вектора из памяти в память ускоряется аппаратно

Геометрическое масштабирование предписывает увеличивать или уменьшать размер памяти под массив хранения в констенту раз (обычно вдвое).

Посмотрим, как ведёт себя стек, реализованный поверх динамического массива с геометрическим масштабированием.

1. Если добавление элемента на стек не приводит к его переполнению, или снятие элемента со стека не приводит к пересечению т. н. «минимальной отметки» (допустим, массив остаётся заполненным более, чем на 1/4), никакого отличия от стека с фиксированным объёмом нет: на стеке из N элементов
   • Операция поиска требует в среднем N/2 чтений (сложность линейная)
   • Операции вставки и удаления в произвольное место требуют в среднем N/2 чтений и в среднем N/2 записей (сложность линейная)
   • Операции добавления и снятия имеют константную сложность
2. Если происходит переполнение или пересечение нижней отметки
   • Операция добавления или снятия потребует N чтений и записей, сложность линейная

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

• Допустим, изначально массив был ограничен N элементами. Это значит, что для добавления первых N значений на стек потребовало N операций записи — по одной на каждое добавление.
• При добавлении N+1-го элемента происходит масштабирование: N элементов считывается, N+1 записывается на новое место
• Теперь размер нового массива — 2N, в нём N+1 ячеек занято и N-1 свободна
• Следовательно, ещё N-1 операций добавления потребует N-1 записей

Таким образом, для добавления 2*N элементов на стек потребовалось N + N+1 + N-1 = 3N операций записи и N операций чтения, т. е. 4N обращений к элементам массива.

Выходит, что в среднем операция добавления потребовала 4n / 2N = 2 действия, то есть оказалась константной сложности.

• В действительности сложность растёт, но очень медленно — логарифмически.

• Мы не можем рассчитывать на то, что любая операция добавления выполнится за константное число действий

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

Динамически масштабируемые массивы и иные структуры активно используются почти во всех современных высокоуровневых языках программирования. Например, в ЯП Python есть тип list, который реализован как динамическая таблица с геометрически масштабированием, а вовсе не как связный список (linked list).

Пример: Простейший стек с геометрическим масштабированием

Связные списки

Полный текст примеров этого раздела

Мы уже встречались со связным списком и в курсе программирования, и при разговоре о кадрах вызова подпрограмм. Главное свойство связного списка — его актуальная бесконечность: каждый новый элемент лежит в отдельно выделенном месте памяти, и количество этих мест ограничено только возможностями окружения.

Если коротко, список состоит из структур, каждая из которых в обязательном порядке включает в себя поле с адресом следующего элемента (оно называется «ссылкой») и поле с хранимыми данными. У списка есть начало — стартовый элемент, и конец — элемент, у которого в поле ссылки вместо адреса записано определённо значение, адресом не являющееся, чаще всего — ноль. В RISC-V по этому адресу не могут располагаться пользовательские данные, и к тому же на ноль проще проверить. Все элементы списка, кроме последнего, ссылаются по цепочке друг на друга.

В примере ниже мы определяем размер и смещение полей в элементе списка, а также несколько макросов для удобства вывода, после чего заводим стартовый элемент с меткой list.

   1 .eqv    cell.next       0       # смещение до ссылки
   2 .eqv    cell.data       4       # смещение до данных
   3 .eqv    cell            8       # размер структуры (1 слово данных)
   4 
   5 # Вывод регистра в нужном формате с разделителем
   6 .macro  print   %reg %ecall %sep
   7         mv      a0 %reg
   8         li      a7 %ecall
   9         ecall
  10         li      a0 %sep
  11         li      a7 11
  12         ecall
  13 .end_macro
  14 
  15 # Вывод адреса и содержимого ячейки (или просто 0, если адрес 0)
  16 .macro  printl  %reg
  17         beqz    %reg null
  18         lw      a1 cell.data(%reg)
  19         print   %reg 34 ' '
  20         print   a1 1 '\n'
  21         j       fin
  22 null:   print   %reg 1 '\n'
  23 fin:
  24 .end_macro
  25 
  26 .data
  27 list:   .align  2               # стартовый элемент списка
  28         .space  cell            # второе слово не используется

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

   1 # Добавление %data после эелемента %cell
   2 .macro  append  %cell %data
   3         mv      a0 %cell
   4         mv      a1 %data
   5         call    list_append
   6 .end_macro
   7 
   8 # Вставка после cell нового элемента со значением data
   9 list_append:    # cell data
  10         mv      t2 a0
  11         lw      t1 cell.next(t2)        # ссылка на следующий элемент
  12         li      a0 cell                 # заказ памяти под структуру
  13         li      a7 9
  14         ecall
  15         sw      t1 cell.next(a0)        # перекладывавем ссылку на следующий
  16         sw      a1 cell.data(a0)        # записываем данные
  17         sw      a0 cell.next(t2)        # подменяем ссылку на новый адрес
  18         ret

• Обратите внимание на то, что самой подпрограмме не нужно знать, где начинается список: достаточно адреса элемента, чьё поле next необходимо изменить

В основной программе заполним список, вставляя по одному элементу в его начало (т. е. после открывающего элемента).

   1 # Вывод всего списка %list
   2 .macro  print_list %list
   3         la      a0 list
   4         call    list_print
   5 .end_macro
   6 
   7 .text
   8 main:   li      s1 8
   9         la      s2 list
  10 fill:   append  s2 s1           # Добавление в начало списка
  11         addi    s1 s1 -1
  12         bgtz    s1 fill
  13         print_list a0           # Должна получиться возрастающая последовательность
  14         # … продолжение следует …
  15 

Кроме того, создадим подпрограмму, которая проходит по всему списку и выводит его элементы.

   1 # Вывод всего списка list
   2 list_print:     # list
   3         mv      t1 a0
   4 lp_nxt: lw      t1 cell.next(t1)
   5         beqz    t1 lp_end
   6         lw      t0 cell.data(t1)
   7         print   t0 1 ' '
   8         j       lp_nxt
   9 lp_end: li      a0 '\n'
  10         li      a7 11
  11         ecall
  12         ret

Макрос и подпрограмма для удаления элемента, который следует после заданного, также будут короткими. Необходимо только проверить, что мы не указали последний элемент списка (после которого удалять уже нечего).

   1 # Удаление ячейки, стоящей после %cell
   2 .macro  delete  %cell
   3         mv      a0 %cell
   4         call    list_delete
   5 .end_macro
   6 
   7 # Удаление из списка элемента, стоящего после cell
   8 # Возвращается 0, если cell — не последний элемент
   9 list_delete:    # cell
  10         mv      t1 a0                   # Предыдущий элемент
  11         lw      a0 cell.next(a0)        # Удаляемый элемент
  12         bnez    a0 ld_del               # (Если он есть)
  13         ret                             # Если там 0, вернём 0
  14 ld_del: lw      t0 cell.next(a0)        # Элемент после удаляемого
  15         sw      t0 cell.next(t1)        # Переписываем ссылку на него
  16         # здесь должно быть освобождение двух слов памяти по адресу a0
  17         ret

• Снова адрес начала списка нам не потребовался

Вставка и удаление элемента в заранее известном месте нужны в структура данных, похожих на очереди и стеки, где работа идёт с началом и концом последовательности. Если мы собираемся хранить какие-то значения в списке и искать их там, потребуется функция, аналогичная list_print, которая проходит по всему списку и возвращает адрес элемента, если он нашёлся, или 0 — если нужного элемента нет.

• Надо возвращать адрес предыдущего элемента: он требуется для операция удаления и вставки

• В макросе никто не мешает «пройти по ссылке» — вернуть содержимое поля next

Элементы списка очень часто хранятся упорядоченно — например, по возрастанию, когда data каждого следующего элемента не меньше data предыдущего. Вставка в упорядоченный список требует предварительного поиска подходящего места — последнего элемента, поле data которого всё ещё меньше добавляемого значения.

Таким образом, нам понадобятся две практически идентичные подпрограммы:

• Поиск элемента, после которого находится элемент с данным значением

• Поиск элемента, после которого можно вставить элемент с данным значением

Отличаться они будут одной инструкцией, так что сами эти подпрограммы при помощи макроса:

   1 # Поиск %value в списке %list
   2 .macro  find    %list %value
   3         la      a0 %list
   4         li      a1 %value
   5         call    list_prev
   6         lw      a0 cell.next(a0)
   7 .end_macro
   8 
   9 # Поиск по условию value в списке list, возвращается предыдущий элемент
  10 # или последний, если условие не выполняется
  11 # Условие — инструкция сравнения+перехода двух регистров %branch
  12 .macro  list_cond       %branch
  13 proc:   # list value
  14         lw      t1 cell.next(a0)        # Следующий элемент списка
  15         beqz    t1 yes                  # Список закончился, элемент не найден
  16         lw      t0 cell.data(t1)        # Значение для сравнения
  17         %branch t0 a1 yes               # Найден ли элемент?
  18         mv      a0 t1                   # Перейдём к следующему
  19         j       proc
  20 yes:    ret
  21 .end_macro
  22 list_prev:      list_cond beq           # Поиск равного
  23 list_gt:        list_cond bgt           # Поиск большего

Допишем в основную программу поиск и удаление эелментов:

   1         # …
   2         # … продолжение main
   3         find    list 5
   4         printl  a0
   5         find    list 4
   6         delete  a0              # Должен удалиться следующий элемент — 5
   7         la      a0 list
   8         delete  a0              # Должен удалиться первый элемент — 1
   9         print_list a0
  10         # …
  11 

Чтобы вставить элемент в упорядоченный список, нужно сначала найти предыдущий элемент (подпрограммой list_gt),, а затем — вставить его уже известным способом.

   1 # Вставка значения %value в упорядоченный список %list
   2 .macro  insert %list %value
   3         la      a0 %list
   4         li      a1 %value
   5         call    list_gt
   6         call    list_append
   7 .end_macro

Допишем основную программу:

   1         # …
   2         # … продолжение main
   3         insert  list 5          # Должен вставиться после 4
   4         insert  list 5          # Должен вставиться после 5
   5         insert  list 42         # Должен вставиться в конец
   6         insert  list 1          # Должен вставиться в начало
   7         print_list a0
   8         find    list 11         # Нет такого
   9         printl  a0
  10         li      a7 10
  11         ecall

Напомним основные вычислительный свойства связного списка из N элементов:

• (+) Операция вставки или удаления в любое любое заранее известное место выполняются за константное время

• Операция поиска выполняется за линейное время, в среднем требуя N/2 циклов поиска
• (-) Операция индексации (поиска элемента по порядковому номеру K) требует прохода по списку, то есть K циклов поиска
• Операция поиска или удаления элемента по критерию (например, по номеру или с упорядочиванием) в среднем требует N/2 циклов поиска (за счёт поиска)
• (-) Организация списка требует эффективного инструмента выделения и освобождения оперативной памяти, а также довольно хрупка при неосторожном обращении: если испортить одну ссылку, теряются все следующие элементы, а по испорченной ссылке есть высокий шанс начать разрушать и другие структуры данных

Таким образом, связные списки отличаются от обычных массивов в первую очередь скоростью вставки / удаления в конец / начало и возможностью хранить произвольное количество объектов.

Описанный выше кольцевой буфер обладает той же эффективностью по части вставки-удаления в начало и конец, но гораздо безопаснее в эксплуатации. Если для хранения данных вместо обычного использовать динамический массив, отпадёт и проблема с переполнением.

Улучшения и модификации

TODO расписать

• Список со стартовым элементом (часто, т. к. удобно)
  • унификация работы с первым и стальными элементами
  • поддержка проверки исчерпания списка
• Кольцевой список
• Двунаправленный список (для вставки/удаления не нужно знать предыдущий элемент заранее, достаточно текущий, но возни с перекидыванием ссылок побольше)
• Cписок адресов
• …