Таблица соединений: этап 0.0.16

Таблица реализована средствами языка; в 0.0.17 вынесена в модуль. Таблица имеет фиксированную вместимость, хранит копируемые записи и не выделяет heap-память. В проверенном тракте единственного владельца edit обновляет выбранную запись без копирования всей таблицы, включая последовательные итерации цикла. Если прежнее значение ещё наблюдаемо, оно сохраняется независимо.

python3 -m liza run examples/connection_table.liza -O 2

Пример возвращает 0 после добавления, изменения, удаления и повторного использования слота с проверкой устаревшего идентификатора. Вывода в консоль нет. Он не открывает сетевые соединения и не является готовой серверной библиотекой.

Идентификатор и запись

struct ConnectionId { slot: u32, generation: u32 }
struct Connection { user_id: u64, state: u32, packets: u64 }

Идентификатор действителен, только если слот находится в границах таблицы, занят, не выведен из обращения и его поколение совпадает с generation. Проверка границ выполняется до индексации: произвольный внешний ID, включая slot = 4294967295, возвращает ожидаемую ошибку, а не trap.

Контракт операций предполагает таблицу, созданную tables.connections.empty и изменяемую через её функции. Служебные поля таблицы и слотов приватны для потребителей модуля. Открытые поля ConnectionId позволяют представлять внешние ID, поэтому операции по-прежнему проверяют индекс, поколение и занятость. В тесте исчерпания поколений специально создаётся допустимое состояние около предела, без миллиардов удалений.

Это идентификатор внутри конкретной таблицы. Он не является адресом, глобальным ID пользователя или защищённой от подделки capability. slot — внутренний номер ячейки текущей реализации; перемещение записей между слотами не поддерживается. Поколение различает последовательные записи в одном слоте.

Две независимые таблицы могут иметь одинаковые пары slot/generation. После copy обе ветви сохраняют действительность существующих ID относительно своих значений. ID нельзя переносить между ветвями, рассчитывая на глобальную идентичность. Для нескольких таблиц или перезапусков сервера потребуется отдельный контракт домена/эпохи.

user_id — данные записи, а не уникальный ключ таблицы. Несколько соединений одного пользователя разрешены. Ресурсы File, сокеты и деструкторы в записи этого примера не входят.

Поколения и исчерпание

Свободный новый слот имеет поколение 1. Поколение 0 не выдаётся.
add выбирает первый свободный слот, который не выведен из обращения.
Успешный del освобождает слот, обнуляет данные записи и увеличивает поколение. Поэтому старый ID недействителен сразу после удаления.
Поколение 4294967295 можно использовать для одной записи. После её удаления слот навсегда получает признак retired; поколение не оборачивается в 0.
Ошибочная операция не меняет ни данные, ни поколение.
Full означает отсутствие пригодного свободного слота: часть ячеек может быть незанятой, но навсегда выведенной из обращения.

Обычные функции над значениями

В языке пока нет изменяемых параметров-ссылок. Функции обновления принимают таблицу по значению и возвращают новую таблицу вместе со статусом:

Функция	Результат	Работа с записями без учёта физической передачи таблицы
`tables.connections.empty()`	`ConnectionTable`	Инициализация N слотов
`tables.connections.get(table, id)`	`Option<Connection>`	O(1): проверка одного слота
`tables.connections.add(table, value)`	`AddResult { table, result: Result<ConnectionId, TableError> }`	O(N): поиск первого свободного слота
`tables.connections.edit(table, id, value)`	`ChangeResult { table, result: Result<Done, TableError> }`	O(1): проверка и замена записи
`tables.connections.del(table, id)`	`ChangeResult { table, result: Result<Done, TableError> }`	O(1): проверка и освобождение слота

Done — пустая структура, используемая вместо пока отсутствующего (). TableError содержит Full и NotFound: add возвращает только Full, edit/del — только NotFound. При ошибке результат содержит неизменённую таблицу.

import tables.connections

added = tables.connections.add(tables.connections.empty(), tables.connections.Connection(42, 1, 0))
match added.result {
    Err(error) => { return 1 }
    Ok(id) => {
        changed = tables.connections.edit(added.table, id, tables.connections.Connection(42, 2, 10))
        // changed.table — новое значение; added.table сохраняет прежнее.
    }
}

Структуры и имена функций принадлежат модулю tables.connections. Они не вводят встроенный Map, generics или стандартный тип Handle. Вместимость 64 явно записана в examples/tables/connections.liza. Конфигурация 4096 использует те же алгоритмы с другой длиной массива и развёрнутым списком начальных значений; операции таблицы не реализуются генератором или C-кодом.

Что проверяется

Одинаковые сценарии выполняются для 64 и 4096 слотов на O0/O2:

Пустая и заполненная таблица, выбор свободного слота, несколько записей одного пользователя.
Чтение и замена данных, независимость copy.
Удаление, повторное использование слота, запрет чтения/изменения/удаления через старый ID.
Некорректные индексы, последние поколения, окончательное исчерпание слота.
Одинаковые результаты при значениях, поступающих от внешнего нативного вызывающего кода.

Матрица включает Linux, macOS и Windows. Условия запуска и воспроизведение измерений описаны в CONTRIBUTING.md репозитория.

Результат проверки стоимости

Первое измерение показало материализацию всей таблицы даже в get. После изменения представления крупных агрегатов чтение использует хранилище входного значения и обращается только к выбранному слоту. Это проверяется по оптимизированной функции с неизвестными на этапе компиляции входами.

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

Проверка охватывает 64, 4096 и 16384 записи: runtime-индексы, миллион обновлений за вызов, повторные обращения к записям и сравнение результата с независимым расчётом. На O0/O2 в выбранной реализации edit и на циклических путях обновления полных копий нет. Проверяются LLVM IR и машинный код. Входная таблица вызывающей стороны остаётся неизменной: перед циклом создаётся один логический снимок (две физические передачи на O0, одна на O2). Это начальная стоимость O(N), а не копирование на каждом обновлении.

Локальный замер macOS ARM64 / Apple Clang 21, O2:

Записей	Медиана, нс на обновление
64	1,08
4096	1,09
16384	1,11

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

Оптимизация консервативна: она не обещает O(1) для любого move, обновления или вызова. Добавление, инициализация, независимые снимки и неподходящие формы функций могут копировать агрегаты. Синтаксис, правила заимствований, границы и обязательные traps остались прежними; пользовательские указатели не появились.

Модульная граница 0.0.17

Два потребителя — connection_table.liza и connection_lookup.liza — импортируют одну реализацию. Отдельный межмодульный тест сохраняет отсутствие полных копий в выбранном edit и на циклических путях для 64/4096/16384 записей, O0/O2. Начальная копия входа остаётся. Правила доступа и идентичности типов описаны в контракте модулей.

Generic-вариант 0.0.18

tables/value_table.liza содержит общую реализацию Table<T,N>. Начальное значение T передаётся явно; generic_table.liza использует её для соединений. Проверка стоимости повторяет тот же цикл для 64/4096/16384 записей. Конкретная таблица 0.0.16/0.0.17 сохраняется как сравнительный пример. Контракт generics.