Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI26 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Как располагается в памяти связный список: Техническое углубление
Этот вопрос требует понимания низкоуровневого расположения данных в памяти. Расскажу о том, как Node'ы размещаются в RAM и почему это важно для производительности.
1. Базовое расположение в памяти
Виртуальное адресное пространство процесса:
┌─────────────────────────────────────────┐
│ HIGH MEMORY (высокие адреса) │
│ ┌──────────────────────────────────┐ │
│ │ Stack (локальные переменные) │ │
│ └──────────────────────────────────┘ │
│ ↑ │
│ (растёт вверх) │
│ │
│ (пустое место) │
│ │
│ (растёт вниз) │
│ ↓ │
│ ┌──────────────────────────────────┐ │
│ │ Heap (динамическое выделение) │ │
│ │ ← LinkedList Node'ы выделяются │ │
│ └──────────────────────────────────┘ │
│ │
│ ┌──────────────────────────────────┐ │
│ │ Data/BSS (статические данные) │ │
│ └──────────────────────────────────┘ │
│ │
│ ┌──────────────────────────────────┐ │
│ │ Code (инструкции программы) │ │
│ └──────────────────────────────────┘ │
│ LOW MEMORY (низкие адреса) │
└─────────────────────────────────────────┘
2. LinkedList Node в памяти
Структура одного Node:
// Представим Node так
struct LinkedListNode<T> {
value: T, // Данные (размер зависит от T)
next: *mut Node<T>, // Указатель на следующий (8 байт на 64-bit)
prev: *mut Node<T>, // Указатель на предыдущий (8 байт) для двусвязного
}
// Если T = String (примерно 24 байта в Dart)
// sizeof(LinkedListNode<String>) = 24 + 8 + 8 = 40 байт
Как это выглядит в памяти:
┌─────────────────────────────────┐
│ Heap (динамическая память) │
├─────────────────────────────────┤
│ │
│ Node A @ 0x10000 │ ← First Node
│ ┌─────────────────────────┐ │
│ │ value: "Hello" │ │
│ ├─────────────────────────┤ │
│ │ next: 0x10028 │ ← указывает сюда
│ ├─────────────────────────┤ │
│ │ prev: null │ │
│ └─────────────────────────┘ │
│ │
│ (может быть пусто) │
│ │
│ Node B @ 0x10028 │ ← Second Node
│ ┌─────────────────────────┐ │
│ │ value: "World" │ │
│ ├─────────────────────────┤ │
│ │ next: 0x10050 │ ← указывает сюда
│ ├─────────────────────────┤ │
│ │ prev: 0x10000 │ ← указывает обратно на A
│ └─────────────────────────┘ │
│ │
│ (может быть пусто) │
│ │
│ Node C @ 0x10050 │ ← Third Node
│ ┌─────────────────────────┐ │
│ │ value: "Flutter" │ │
│ ├─────────────────────────┤ │
│ │ next: null │ ← конец
│ ├─────────────────────────┤ │
│ │ prev: 0x10028 │ ← указывает обратно на B
│ └─────────────────────────┘ │
│ │
└─────────────────────────────────┘
Адреса могут быть НЕ подряд!
0x10000 → 0x10028 → 0x10050
3. Выделение памяти
Когда создаёшь Node, вызывается allocate:
// Это происходит под капотом
var node = LinkedListNode('Hello');
// Внутри Dart runtime:
// 1. malloc/new выделяет блок памяти размером 40 байт
// 2. Инициализируются поля (value, next, prev)
// 3. Возвращается указатель на этот блок
// 4. Указатель сохраняется в переменной node
Фрагментация памяти:
Первая программа (Array):
┌────────────────────────────────────┐
│ [0x1000] [0x1008] [0x1010] [0x1018] │
│ A B C D │
└────────────────────────────────────┘
Мемория компактная
Вторая программа (LinkedList):
┌─────────────────────────────────────────┐
│ 0x1000: Node A 0x2000: Node B 0x3000: C│
│ (выделено) (выделено) (выделено) │
│ 0x1028: пусто │
│ 0x2028: пусто │
│ 0x3028: пусто │
└─────────────────────────────────────────┘
Фрагментирована - пусто везде!
4. Cache Locality (кэш процессора)
Проблема: процессору нужны соседние данные
Процессор имеет кэши разных уровней:
┌─────────────────────┐
│ L1 Cache (64KB) │ ← очень быстро (1-2 цикла)
├─────────────────────┤
│ L2 Cache (256KB) │ ← быстро (4-10 циклов)
├─────────────────────┤
│ L3 Cache (8MB) │ ← средне (40-75 циклов)
├─────────────────────┤
│ RAM (16GB) │ ← медленно (200+ циклов)
└─────────────────────┘
Когда обращаешься к Array[0], процессор кэширует
отпущусть и Array[0..63] в L1 cache.
Это очень быстро!
Когда обращаешься к LinkedListNode->next,
процессор должен идти в RAM по адресу,
который может быть далеко.
Это медленно!
5. Page Faults (ошибки страниц)
Как ОС управляет памятью:
Виртуальная память разделена на страницы (обычно 4KB)
┌──────────────────────────────────┐
│ Виртуальное адресное пространство │
├──────────────────────────────────┤
│ Page 0: 0x0000 - 0x0FFF │ ← в физической памяти
│ Page 1: 0x1000 - 0x1FFF │ ← в физической памяти
│ Page 2: 0x2000 - 0x2FFF │ ← на диске (swap)
│ Page 3: 0x3000 - 0x3FFF │ ← на диске (swap)
└──────────────────────────────────┘
Когда обращаешься к Node в Page 2:
1. Page Fault! (исключение процессора)
2. ОС загружает Page 2 с диска в RAM (~100мс)
3. Программа возобновляется
Это ужасно медленно!
6. Размер Node и overhead
В Dart LinkedListEntry:
┌─────────────────────────────────────┐
│ LinkedListEntry<String> │
│ ┌────────────────────────────────┐ │
│ │ _element: String (24 bytes) │ │ ← Ваши данные
│ │ _previousLink: (8 bytes) │ │ ← prev pointer
│ │ _nextLink: (8 bytes) │ │ ← next pointer
│ │ _list: LinkedList (8 bytes) │ │ ← ссылка на список
│ └────────────────────────────────┘ │
│ Total: ~48 байт на String │
└─────────────────────────────────────┘
// Сравнение
// List<String>: ~56 байт на 1000 элементов (компактно)
// LinkedList<StringEntry>: ~48,000 байт на 1000 элементов
// = В 857 раз больше!
7. Обход связного списка
Время обхода по шагам:
var list = LinkedList<Node>();
// Добавили 1000 элементов
// Обход:
for (var node in list) { // Очень медленно!
// Для каждого элемента:
// 1. Читаем текущий Node из памяти
// 2. Берём next pointer
// 3. Идём в совсем другое место памяти
// 4. Читаем следующий Node
// 5. Cache miss! Переполнение кэша!
print(node);
}
// Time: ~100-200мс на 1000 элементов
// Сравнение с Array:
for (var item in items) { // Очень быстро!
// Элементы рядом в памяти
// Кэш работает эффективно
print(item);
}
// Time: ~1-5мс на 1000 элементов
8. Операции вставки/удаления
Вставка в начало LinkedList:
До:
head → Node A → Node B → Node C → null
Вставляем новый Node X в начало:
1. Выделяем память для Node X (40 байт где-то в heap)
→ Может быть в совсем другом месте!
2. Node X.next = head (0x1000) → указываем на A
3. head = Node X (0x4000) → новая голова
После:
head → Node X (0x4000) → Node A (0x1000) → Node B → Node C
Операция: O(1)
Проблема: Новый Node не рядом с остальными!
Кэш: Все испорчен!
Вставка в конец Array:
До:
[A][B][C][_][_][_] (capacity=6, size=3)
Вставляем D:
[A][B][C][D][_][_] (capacity=6, size=4)
Операция: O(1)
Преимущество: Данные подряд, кэш счастлив!
Если capacity исчерпан (size == capacity):
Перавыделяем, копируем (O(n) один раз),
но потом опять быстро добавляем.
9. Memory Allocator поведение
Часто используемый allocator (jemalloc, mimalloc):
Когда запрашиваешь 40 байт:
1. Allocator проверяет free list
2. Если есть блок 40+ байт - используем
3. Если нет - запрашиваем у ОС новую страницу (4KB)
4. Разбиваем страницу на малые блоки
5. Даём вам один из них
Проблема: Node'ы часто находятся в разных страницах!
10. Практическое сравнение производительности
import 'dart:collection';
import 'package:benchmark_harness/benchmark_harness.dart';
class LinkedListBench extends BenchmarkBase {
LinkedListBench() : super('LinkedList iteration');
static void main() => LinkedListBench().report();
@override
void run() {
var list = LinkedList<TestEntry>();
for (int i = 0; i < 10000; i++) {
list.add(TestEntry(i));
}
var sum = 0;
for (var entry in list) {
sum += entry.value;
}
}
}
class ListBench extends BenchmarkBase {
ListBench() : super('List iteration');
static void main() => ListBench().report();
@override
void run() {
var list = List<int>.generate(10000, (i) => i);
var sum = 0;
for (var value in list) {
sum += value;
}
}
}
// Результаты (примерные):
// LinkedList iteration: 50мс
// List iteration: 1мс
// LinkedList медленнее в 50 раз!
11. Визуализация памяти
Array в памяти:
┌──────────────────────────────────────┐
│ [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] │ ← Подряд
├──────────────────────────────────────┤
│ Кэш загружает часто [1-8] │
│ Очень быстро! │
└──────────────────────────────────────┘
LinkedList в памяти:
┌──────────────────────────────────────────────────────┐
│ Heap (разброс по памяти) │
├──────────────────────────────────────────────────────┤
│ [1] @ 0x1000 → next @ 0x5000 │
│ │
│ [2] @ 0x5000 → next @ 0x2000 │
│ │
│ [3] @ 0x2000 → next @ 0x7000 │
│ │
│ Page faults везде! │
│ Кэш бесполезен │
└──────────────────────────────────────────────────────┘
12. Когда LinkedList имеет смысл
// ✅ Очередь (Queue): часто удаляешь с начала, добавляешь в конец
class Queue<T> {
LinkedList<Node<T>> _list = LinkedList();
void enqueue(T value) {
_list.add(Node(value)); // O(1) вставка в конец
}
T? dequeue() {
if (_list.isEmpty) return null;
final first = _list.first;
final value = first.value;
first.unlink(); // O(1) удаление из начала
return value;
}
}
// ❌ Обход всех данных: используй List
for (var item in linkedList) { // Медленно!
process(item);
}
// Лучше:
for (var item in list) { // Быстро!
process(item);
}
Вывод
Как располагается LinkedList в памяти:
- Фрагментировано — Node'ы в разных местах Heap
- Неэффективно для кэша — нет locality
- Больше памяти — overhead на указатели
- Page faults — медленные обращения к памяти
- O(1) операции — компенсируют, но редко стоит
В практике:
- List лучше для 99% случаев
- LinkedList только для специфических операций (Queue)
- На мобильных устройствах разница ещё заметнее
- Профилируй перед выбором структуры
Память — это не бесконечный ресурс, и современные процессоры требуют уважения к расположению данных!