Неизменяемость и потокобезопасность – это не одно и то же
При разработке компилятора мы постоянно сталкиваемся со следующей задачей: создать эффективную неизменяемую таблицу соответствия (lookup table) имен и «символов». По сути, это основная задача, которую должен решать компилятор; кто-то пишет «x = y + z;» и прежде чем выполнять дополнительный анализ, нужно определить, что означает «x», «y» и «z». Очевидным решением этой задачи является однократное определение для некоторой области видимости всех соответствий имя-символ, сохранение этого результата в таблице соответствия и использование ее в будущем анализе.
Эта таблица соответствия может быть неизменяемой, поскольку после заполнения никакие символы в нее добавляться не будут, и она будет использоваться исключительно для поиска. Простым и распространенным способом решения этой задачи является использование подхода, который я называю «мороженое»: структура данных является полностью изменяемой до тех пор, пока она не заморожена, после чего при любой попытке изменения будет сгенерировано исключение. Такой подход значительно отличается от неизменяемости на основе «повторно-используемых структур данных», которую мы когда-то обсуждали, когда данные текущего объекта используются повторно при создании нового экземпляра, на основе существующего.
Например, вы можете написать очень простую хэш-таблицу, с поддержкой «заморозки». Что-то типа такого:
abstract class Symbol
{
public string Name { get; protected set; }
}
sealed class SymbolTable
{
private bool frozen = false;
private class BucketListNode
{
public Symbol Symbol { get; set; }
public BucketListNode Next { get; set; }
public BucketListNode Prev { get; set; }
}
private BucketListNode[] buckets = new BucketListNode[17];
private int GetBucket(string s)
{
return Math.Abs(s.GetHashCode()) % buckets.Length;
}
public void Add(Symbol symbol)
{
// Проверка символа на null, что имя не пустое, на отсутствие дубликатов и т.п. опущена.
if (this.frozen)
throw new InvalidOperationException();
int bucket = GetBucket(symbol.Name);
var node = new BucketListNode();
node.Symbol = symbol;
node.Prev = null;
node.Next = buckets[bucket];
if (node.Next != null)
node.Next.Prev = node;
buckets[bucket] = node;
}
public void Freeze()
{
this.frozen = true;
}
public Symbol Lookup(string name)
{
// Обработка ошибок опущена
int bucket = GetBucket(name);
for (var node = buckets[bucket]; node != null; node = node.Next)
{
if (node.Symbol.Name == name)
return node.Symbol;
}
return null;
}
}
Все очень просто. У нас есть массив из семнадцати двусвязных списков. И мы балансируем таблицу, выбирая, в какой из семнадцати списков добавить новый элемент путем получения хэш-значения символа.
Конечно, существуют другие более эффективные пути решения. Мы можем сортировать список символов и использовать двоичный поиск. Мы можем увеличивать количество массивов, если выяснится, что в таблице будет храниться тысячи символов. Но ради простоты, давайте предположим, что мы решили остановиться на приведенном выше решении с фиксированным количеством сегментов (buckets).
Одним из наиболее известных преимуществ неизменяемых структур данных является «потокобезопасность» (threadsafe). Поскольку данные никогда не изменяются, то вы никогда не столкнетесь ситуацией, когда операция записи будет прервана на половине из-за переключения контекста, что приведет к чтению рассогласованной структуры данных из другого потока. Однако это заблуждение полагать, что если вы не можете изменить содержимое структуры данных, то ее реализация является потокобезопасной!
Давайте ради примера предположим, что мы выполняем анализ использования нашей маленькой таблицы в реальных приложениях и понимаем, что следующий код является типовым кодом наших пользователей:
x.Foo();
x.Bar();
x.Blah();
y.Abc();
y.Def();
y.Ghi();
Таким образом, поиск одного и того же идентификатора происходит множество раз в одной и той же таблице символов. И мы можем решить добавить небольшую оптимизацию в наш метод поиска:
for (var node = buckets[bucket]; node != null; node = node.Next)
{
if (node.Symbol.Name == name)
{
MoveToFront(bucket, node);
return node.Symbol;
}
}
...
private void MoveToFront(int bucket, BucketListNode node)
{
if (buckets[bucket] == node)
return;
node.Prev.Next = node.Next;
if (node.Next != null)
node.Next.Prev = node.Prev;
node.Prev = null;
node.Next = buckets[bucket];
node.Next.Prev = node;
buckets[bucket] = node;
}
По сути, мы превратили нашу хэш-таблицу из простого массива двусвязных списков, в массив наиболее часто используемых списков. Это может привести к повышению производительности при увеличении размера списков, и при использовании одинаковых идентификаторов близко в коде. (И это реальный выигрыш для движка VBScript, в котором таблицы соответствия используют похожую оптимизацию.)
Но вы поняли, что мы только что сделали? Теперь чтение таблицы иногда приводит к изменению внутренней структуры, а это изменение не является потокобезопасным! И хотя пользователь не может логически изменить замороженную таблицу, мы не гарантируем, что чтение является потокобезопасным.
На практике, большинство структур данных не изменяют своего содержимого при чтении, однако, если это не указано в документации, то вы не можете на это рассчитывать. Например, в документации класса Dictionary указано, что он является потокобезопасным для нескольких читателей одновременно, если при этом нет ни одного писателя (конечно, сами итераторы не являются потокобезопасными объектами, поскольку они постоянно изменяются; но сама итерируемая коллекция является потокобезопасной). И пока автор класса ничего подобного не гарантирует, вы не должны рассчитывать, что некоторая операция является потокобезопасной, даже если объект используется только для чтения.