# Оптимизация размера узлов SkipList — результаты реализации

## Проблема

ConstTree / ZeroTree хранят маленькие Copy-значения (8-32 байта), но каждый узел skip list добавлял ~130-152 байт инфраструктуры: SmallVec tower (40 bytes), отдельный Box для ConstData, отдельный Box для DiskLoc (VarNode), `marked: AtomicBool` с 7 байтами padding, DiskLoc с 7 байтами padding. При миллионах записей инфраструктура доминировала в потреблении памяти.

## Layout до оптимизации

### ConstNode (K=16, V=16)

```rust
pub struct ConstNode<K: Key, const V: usize> {
    pub key: K,                                  // K bytes
    pub data: AtomicPtr<ConstData<V>>,           // 8 bytes
    height: u8,                                  // 1 + 7 padding
    marked: AtomicBool,                          // 1 + 7 padding
    tower: SmallVec<[AtomicPtr<Self>; 2]>,       // 40 bytes (24 metadata + 16 inline)
}

pub struct ConstData<const V: usize> {
    pub disk: DiskLoc,    // 24 bytes (17 real + 7 padding)
    pub value: [u8; V],   // V bytes
}

pub struct DiskLoc {
    pub shard_id: u8,     // 1
    pub file_id: u32,     // 4
    pub offset: u64,      // 8
    pub len: u32,         // 4
}   // = 17 bytes, с padding = 24
```

| Компонент | Размер |
|-----------|--------|
| ConstNode struct | ~80 bytes |
| ConstData (отдельный Box) | 24 + V = 40 bytes |
| Allocator overhead (2 x Box) | ~32 bytes |
| **Итого** | **~152 bytes** (из них полезных — 32) |

### VarNode (K=16)

| Компонент | Размер |
|-----------|--------|
| VarNode struct (key + AtomicPtr + height + marked + SmallVec) | ~72 bytes |
| DiskLoc (отдельный Box) | 24 bytes |
| Allocator overhead (2 x Box) | ~24 bytes |
| **Итого** | **~120 bytes** |

### TypedNode (K=16, T=64)

| Компонент | Размер |
|-----------|--------|
| TypedNode struct | ~80 bytes |
| TypedData (отдельный Box) | 24 + T = 88 bytes, но часть overlap с node |
| Allocator overhead (2 x Box) | ~32 bytes |
| **Итого** | **~148 bytes** |

## Реализованные оптимизации

### 1. Упаковка DiskLoc: 24 -> 12 bytes

**Исходный план:** упаковать в `u64` (8 bytes) с битовыми полями (4 бита shard, 16 бит file_id, 32 бита offset, 12 бит len).

**Что сделано:** `#[repr(C)]` struct с полями фиксированных размеров:

```rust
#[repr(C)]
pub struct DiskLoc {
    pub offset: u32,    // 4 bytes — до 4 GB на файл
    pub len: u32,       // 4 bytes — до 4 GB размер значения
    pub file_id: u16,   // 2 bytes — до 65536 файлов
    pub shard_id: u8,   // 1 byte  — до 256 шардов
    _pad: u8,           // 1 byte  — выравнивание
}   // = 12 bytes, без padding
```

Конструктор `DiskLoc::new(file_id, offset, len)` с приватным полем `_pad`.

**Отличие от плана:** 12 bytes вместо 8. Причина — `len` нужен полный `u32` диапазон (до 4 GB), потому что VarTree хранит значения произвольного размера. 12-битное поле (до 4096) было бы недостаточно. Конфигурация валидирует `max_file_size <= u32::MAX`.

**Экономия:** 12 bytes на каждый узел, содержащий DiskLoc.

**Файлы:** `armdb/src/disk_loc.rs`

### 2. Tag bit вместо marked: AtomicBool

**Что сделано:** удалено поле `marked: AtomicBool` (1 byte + 7 padding = 8 bytes). Метка логического удаления хранится в младшем бите указателя `tower[0]` (всегда 0 из-за alignment указателей).

```rust
fn is_marked(&self) -> bool {
    self.tower(0).load(Ordering::Acquire) as usize & 1 != 0
}

fn mark(&self) -> bool {
    // AtomicPtr lacks fetch_or, so reinterpret as AtomicUsize.
    let atomic_usize: &AtomicUsize =
        unsafe { &*(self.tower(0) as *const AtomicPtr<Self> as *const AtomicUsize) };
    let old = atomic_usize.fetch_or(1, Ordering::AcqRel);
    old & 1 == 0
}
```

Вспомогательная функция `strip_mark()` в `skiplist/mod.rs` маскирует бит при загрузке указателей tower:

```rust
pub(crate) fn strip_mark<T>(ptr: *mut T) -> *mut T {
    (ptr as usize & !1) as *mut T
}
```

Все загрузки tower-указателей в `SkipList` проходят через `strip_mark()`.

**Соответствие плану:** полностью совпадает с предложением.

**Экономия:** 8 bytes на узел (все три типа).

**Файлы:** `armdb/src/skiplist/node.rs`, `armdb/src/skiplist/mod.rs`, `armdb/src/skiplist/iter.rs`

### 3. VLA tower вместо SmallVec

**Что сделано:** `SmallVec<[AtomicPtr<Self>; 2]>` (40 bytes) заменён на inline-аллокацию переменной длины. Узел аллоцируется одним блоком через `std::alloc::alloc` с tower-массивом сразу после полей структуры:

```rust
fn layout_for(height: u8) -> std::alloc::Layout {
    let tower_bytes = height as usize * size_of::<AtomicPtr<Self>>();
    let total = Self::base_size() + tower_bytes;
    let align = align_of::<Self>().max(align_of::<AtomicPtr<Self>>());
    Layout::from_size_align(total, align).expect("invalid layout")
}
```

**Отличие от плана:** в структуре появилось поле `tower_ptr: *const AtomicPtr<Self>` (+8 bytes), которого не было в исходном предложении. Исходный план предполагал вычисление адреса tower через pointer arithmetic от `&self`. Проблема: Miri/Stacked Borrows — ссылка `&self` имеет provenance только на `size_of::<Self>()` байт, tower-массив расположен за пределами структуры. Чтение через `&self` + смещение — UB по Stacked Borrows.

Решение: хранить raw pointer `tower_ptr`, вычисленный при аллокации из `ptr` (аллокационный указатель имеет provenance на весь блок). Аналогично тому, как `Vec` хранит указатель на свой буфер.

```rust
tower_ptr: *const AtomicPtr<Self>,

fn tower(&self, level: usize) -> &AtomicPtr<Self> {
    debug_assert!(level < self.height as usize);
    unsafe { &*self.tower_ptr.add(level) }
}
```

Кастомные `dealloc_node()` и `reclaim()` в `SkipNode` trait для деаллокации VLA-блока:

```rust
unsafe fn dealloc_node(ptr: *mut Self);
unsafe fn reclaim(ptr: *mut Self, _collector: &seize::Collector);
```

Зависимость `smallvec` удалена из `Cargo.toml`.

**Экономия:** 40 - 8 (tower_ptr) - 8 (средний tower: height=1 -> 8 bytes) = 24 bytes нетто (вместо 32 по плану). Средний height ~1.33 -> средний tower ~10.7 bytes.

**Файлы:** `armdb/src/skiplist/node.rs`, `armdb/Cargo.toml`

### 4. Inline ConstData + SeqLock (только ConstNode)

**Что сделано:** `ConstData<V>` struct удалён полностью. Поля `disk` и `value` встроены непосредственно в `ConstNode` через `UnsafeCell`. Вместо RCU (AtomicPtr + Box + seize retire на каждую запись) используется SeqLock-протокол:

```rust
#[repr(C)]
pub struct ConstNode<K: Key, const V: usize> {
    pub key: K,
    seq: AtomicU64,
    disk: UnsafeCell<DiskLoc>,
    value: UnsafeCell<[u8; V]>,
    height: u8,
    tower_ptr: *const AtomicPtr<Self>,
}
```

SeqLock-протокол чтения:

```rust
loop {
    let s1 = self.seq.load(Acquire);
    if s1 & 1 != 0 { spin_loop(); continue; } // нечётное = writer active
    let disk = unsafe { ptr::read(self.disk.get()) };
    let value = unsafe { ptr::read(self.value.get()) };
    fence(Acquire);  // данные прочитаны до повторной проверки seq
    let s2 = self.seq.load(Relaxed);
    if s1 == s2 { return (disk, value); }
    spin_loop();
}
```

SeqLock-протокол записи (под shard Mutex — один writer):

```rust
self.seq.fetch_add(1, Relaxed);   // odd — writing
fence(Release);                    // видимость перед записью данных
unsafe {
    ptr::write(self.disk.get(), disk);
    ptr::write(self.value.get(), *value);
}
self.seq.fetch_add(1, Release);   // even — done
```

Реализованы специализированные методы: `read_data()`, `read_disk()`, `read_value()`, `write_data()`, `write_disk()`.

**Соответствие плану:** полностью совпадает. Memory ordering для ARM: `Acquire` на обоих чтениях seq + `fence(Acquire)` между данными и вторым seq.

**Эффект:**
- Убирает heap-аллокацию `Box<ConstData>` на каждую запись
- Убирает seize retire для ConstData
- Убирает `AtomicPtr<ConstData>` (8 bytes) и замещает на `seq: AtomicU64` (8 bytes) + inline поля
- Нетто экономия: ~33 bytes (Box overhead + ConstData heap + pointer)

**Ограничение:** только ConstNode (Copy-типы, маленькие значения). TypedNode и VarNode сохраняют RCU + AtomicPtr.

**Файлы:** `armdb/src/skiplist/node.rs`, `armdb/src/const_tree.rs`, `armdb/src/const_map.rs`, `armdb/src/zero_tree.rs`, `armdb/src/zero_map.rs`

## Layout после оптимизации

### ConstNode (K=16, V=16)

```
#[repr(C)]
ConstNode {
    key: [u8; 16],                          // 16 bytes
    seq: AtomicU64,                         //  8 bytes
    disk: UnsafeCell<DiskLoc>,              // 12 bytes
    value: UnsafeCell<[u8; 16]>,            // 16 bytes
    height: u8,                             //  1 byte + padding
    tower_ptr: *const AtomicPtr<Self>,      //  8 bytes
}
// base_size ~ 64 bytes (с учётом alignment padding)
// + tower: height x 8 bytes (среднее 1.33 x 8 ~ 11)
// Итого среднее: ~75 bytes
// Одна аллокация (std::alloc::alloc)
```

### VarNode (K=16)

```
#[repr(C)]
VarNode {
    key: [u8; 16],                          // 16 bytes
    disk: AtomicPtr<DiskLoc>,               //  8 bytes
    height: u8,                             //  1 byte + padding
    tower_ptr: *const AtomicPtr<Self>,      //  8 bytes
}
// base_size ~ 40 bytes (с padding)
// + tower: height x 8 ~ 11
// + Box<DiskLoc> на heap: 12 + ~16 allocator = ~28
// Итого среднее: ~76 bytes (VLA-узел + heap DiskLoc)
```

### TypedNode (K=16, T=64)

```
#[repr(C)]
TypedNode {
    key: [u8; 16],                          // 16 bytes
    data: AtomicPtr<TypedData<T>>,          //  8 bytes
    height: u8,                             //  1 byte + padding
    tower_ptr: *const AtomicPtr<Self>,      //  8 bytes
}
// base_size ~ 40 bytes (с padding)
// + tower: height x 8 ~ 11
// + Box<TypedData<T>> на heap: 12 + 64 + ~16 allocator = ~92
// Но TypedData меньше: DiskLoc теперь 12, не 24
// Итого среднее: ~104 bytes
```

## Результаты

### Экономия по типам (K=16)

| | ConstNode (V=16) | VarNode | TypedNode (T=64) |
|--|--:|--:|--:|
| **До** | ~152 bytes | ~120 bytes | ~148 bytes |
| Упаковка DiskLoc (24 -> 12) | -12 | -12 | -12 |
| Tag bit (-marked) | -8 | -8 | -8 |
| VLA tower (нетто, с tower_ptr) | -24 | -24 | -24 |
| Inline + SeqLock | -33 | -- | -- |
| **После** | **~75 bytes** | **~76 bytes** | **~104 bytes** |
| **Коэффициент** | **~2.0x** | **~1.6x** | **~1.4x** |

### Качественные улучшения

- ConstNode: одна аллокация вместо трёх (node + ConstData + SmallVec spill)
- VarNode: одна аллокация для node, одна для DiskLoc (вместо трёх)
- TypedNode: одна аллокация для node, одна для TypedData (вместо трёх)
- Улучшенная cache locality: tower в том же блоке памяти, что и ключ
- Убран seize retire для ConstData (ConstNode)

## Отклонения от плана

### DiskLoc: 12 bytes вместо 8

Исходный план предполагал упаковку в `u64` с битовыми полями (`len` — 12 бит, до 4096). Реализовано как `#[repr(C)]` struct 12 bytes. Причина: VarTree хранит значения произвольного размера, `len` нужен полный диапазон `u32` (до 4 GB). Это стоило 4 дополнительных байта, но обеспечило безопасные диапазоны для всех полей.

### VLA tower: нужен tower_ptr (+8 bytes)

Исходный план предполагал вычисление адреса tower через `&self` + offset. Miri/Stacked Borrows это запрещает: `&self` имеет provenance только на `size_of::<Self>()`, tower находится за пределами. Решение — хранить raw pointer `tower_ptr` в структуре. Это уменьшило экономию с 32 до 24 bytes.

### VarNode: AtomicU64 трюк отложен

Исходный план предполагал, что с DiskLoc(u64) можно заменить `AtomicPtr<DiskLoc>` на `AtomicU64` в VarNode, убирая heap-аллокацию и seize retire для DiskLoc. Это было бы самой выгодной оптимизацией для VarNode (~40 bytes экономии). Но DiskLoc = 12 bytes, не 8, поэтому в `AtomicU64` не помещается. VarNode по-прежнему использует `AtomicPtr<DiskLoc>` + `Box<DiskLoc>` + seize retire.

Из-за этого реальная экономия VarNode (1.6x) значительно меньше планировавшейся (3.0x).

## Открытые вопросы / будущая работа

1. **VarNode AtomicU64 DiskLoc** — если ограничить `offset` до 32 бит и `len` до 24 бит (16 MB макс. размер значения), DiskLoc помещается в 8 байт. Это позволит заменить `AtomicPtr<DiskLoc>` на `AtomicU64` в VarNode, убрав heap-аллокацию и seize retire. Потенциальная экономия: ~28 bytes на узел VarNode. Требует анализа реальных лимитов `len` для VarTree.

2. **SeqLock для VarNode disk** — альтернативный путь: использовать SeqLock для inline DiskLoc (12 bytes) в VarNode, аналогично ConstNode. Это убирает Box, но добавляет `AtomicU64 seq` (8 bytes) и `UnsafeCell<DiskLoc>` (12 bytes) вместо `AtomicPtr<DiskLoc>` (8 bytes) + Box(12 + 16 alloc) = ~36 bytes. Нетто экономия ~16 bytes.

3. **Loom-тестирование SeqLock** — SeqLock-протокол реализован с корректным ordering для x86 и ARM, но формальная верификация через loom пока не проведена.

4. **tower_ptr elimination** — если Stacked Borrows эволюционирует к Tree Borrows (где `&self` через `addr_of!` сохраняет allocation provenance), поле `tower_ptr` можно будет убрать, вернув 8 bytes.

## Применимость по типам

### Матрица реализованных оптимизаций

| Оптимизация | ConstNode | VarNode | TypedNode |
|-------------|:---------:|:-------:|:---------:|
| Упаковка DiskLoc (24 -> 12) | да | да | да |
| Tag bit | да | да | да |
| VLA tower | да | да | да |
| Inline + SeqLock | да | нет | нет |
| AtomicU64 DiskLoc | -- | отложено | -- |

**ConstNode** получил все 4 оптимизации. Inline + SeqLock применим только к Copy-типам фиксированного размера.

**VarNode** получил 3 из 4 оптимизаций. AtomicU64 трюк отложен из-за того, что DiskLoc = 12 bytes. По-прежнему использует RCU (`AtomicPtr<DiskLoc>` + `Box` + seize).

**TypedNode** получил 3 оптимизации. Inline + SeqLock не применим — `T` может быть произвольного размера и не-Copy (String, Vec). RCU с seize обязателен для безопасного чтения `&T`.
