09.03.2026 06:50
gandjustas 1 6100 Источник

Три года назад я опубликовал статью Сортировка слиянием — не так просто, как кажется, в которой решал задачу с собеседования, как построчно отсортировать огромный текстовый файл, который заведомо не влезает в оперативную память.

Напомню требования:

  • Формат строки: число, точка, пробел, далее любые символы до конца строки.

  • Порядок сортировки: сначала сортируем текстовой части строки, потом по числу если текстовые части совпадают.

  • Кодировка: UTF-8.

  • Размер файла: 100гб — гарантированно больше объема ОП.

  • Должно отработать менее чем за час на HDD.

Прошлая версия, которую я написал еще на .NET 7, справлялась за 32 минуты на моем компьютере. Большую часть времени занимало чтение-запись файлов, поэтому так применялись сжатие, параллельная обработка сортировки и ввода-вывода, а таже низкоуровневые манипуляции с массивом байт для уменьшения аллокаций.

Что еще можно оптимизировать

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

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

Для решения такой проблемы в .NET 9 добавили Alternate Dictionary Lookup. Несмотря на то, что это одна из важнейших фич для оптимизации задач, связанных с вводом-выводом и парсингом, у нее даже своей статьи документации нет. Теперь мы можем искать по словарю, используя не тип ключа, а другой тип, для которого реализован IAlternateEqualityComparer<TAlternate,TKey>.

С использованием такого Dictionary мы можем воспользоваться классами из пространства имен System.IO.Pipelines. Она была добавлена еще в .NET 2.1 и чтение файла построчно в ней получается проще и эффективнее чем с FileStream.

Baseline для тестов

Как и в прошлый раз я буду для замеров сортировать файл в 10ГБ, в 10 раз меньше чем нужный нам. Все операции ввода-вывода происходят на диске Toshiba P300 7200 об\мин.

Старый вариант на .NET 7 сортирует файл за 4:00 или 3:10 если работает кэш файловой системы.

Для новой версии сначала сделаю код, который просто копирует файл построчно

static async Task Sort(FileInfo source, FileInfo? destination, CancellationToken ct)
{
    if (destination is null)
    {
        var file = source.FullName;
        destination = new FileInfo(Path.ChangeExtension(file, ".sorted" + Path.GetExtension(file)));
    }
    var reader = PipeReader.Create(source.OpenRead());
    var writer = PipeWriter.Create(destination.OpenWrite());

    await CopyLines(reader, writer, ct);
    await reader.CompleteAsync();
    await writer.CompleteAsync();
}

static async Task CopyLines(PipeReader reader, PipeWriter writer, CancellationToken ct)
{
    var encoding = System.Text.Encoding.UTF8;
    var newLine = encoding.GetBytes(Environment.NewLine);

    while (true)
    {
        var result = await reader.ReadAsync(ct);
        var buffer = result.Buffer;
        SequenceReader<byte> sequenceReader = new(buffer);
        while (!sequenceReader.End)
        {
            while (sequenceReader.TryReadTo(out ReadOnlySpan<byte> line, newLine))
            {
                writer.Write(line);
                writer.Write(newLine);
            }

            buffer = buffer.Slice(sequenceReader.Position);
            sequenceReader.Advance(buffer.Length);
        }

        reader.AdvanceTo(buffer.Start, buffer.End);
        await writer.FlushAsync(ct);
        if (result.IsCompleted) break;
    }
}

Результат: 2:05 если кэша файловой системы нет и 0:56 если ОС кэширует файл

Код по ссылке https://github.com/gandjustas/HugeFileSort/tree/3d7e01eb04a335441f65393d10ff3ed5481ca0c2

Сортировка в памяти

Для тестов я использую файл, строки в котором взяты из книги «Война и Мир» Толстого. Исходный файл занимает всего 2 мегабайта. Dictionary<string, List<long>> , где ключами будут все строки из исходного файла, точно влезет в оперативную память. Поэтому напишу сначала код, который формирует такой Dictionary, а потом записывает его в выходной файл

Функция Sort

static async Task Sort(FileInfo source, FileInfo? destination, CancellationToken ct)
{
    if (destination is null)
    {
        var file = source.FullName;
        destination = new FileInfo(Path.ChangeExtension(file, ".sorted" + Path.GetExtension(file)));
    }
    var reader = PipeReader.Create(source.OpenRead());

    var encoding = System.Text.Encoding.UTF8;
    var newLine = encoding.GetBytes(Environment.NewLine);
    StringToUtf8BytesComparer comparer = new(encoding, Random.Shared.Next());
    var dict = await ReadDictionary<long>(reader, newLine, comparer, ct);
    
    var sorted = dict
        .AsParallel()
        .Select(x => { x.Value.Sort(); return (x.Key, x.Value); })
        .OrderBy(p => p.Key);

    var writer = PipeWriter.Create(destination.OpenWrite());
    foreach (var (line, values) in sorted)
    {
        foreach (var value in values)
        {
            writer.Write(value, "d");
            writer.Write(". ", encoding);
            writer.Write(line, encoding);
            writer.Write(newLine);
        }
        await writer.FlushAsync(ct);
    }
    await reader.CompleteAsync();
    await writer.CompleteAsync();
}

Вся магиях в функции ReadDictionary

static async Task<IReadOnlyDictionary<string, List<T>>> ReadDictionary<T>(
  PipeReader reader, 
  byte[] newLine, 
  IEqualityComparer<string> comparer, 
  CancellationToken ct) 
where T : struct, INumberBase<T>
{
    Dictionary<string, List<T>> d = new(comparer);
    var l = d.GetAlternateLookup<ReadOnlySpan<byte>>();
    await ProcessLines(reader, newLine, line =>
    {
        var dotPos = line.IndexOf((byte)'.');
        var x = T.Parse(line[..dotPos], null);
        line = line[(dotPos + 2)..];

        ref var list = ref CollectionsMarshal.GetValueRefOrAddDefault(l, line, out bool exist);
        if (!exist)
        {
            list = [x];
        }
        else
        {
            list!.Add(x);
        }

    }, ct);

    return d;
}

  • Функция ProcessLines инкапсулирует обход файла по строкам.

  • GetAlternateLookup<ReadOnlySpan<byte>>() возвращает нам структуру, которая позволяет искать по Dictionary<string, V> используя ключ типа ReadOnlySpan<byte>.

  • CollectionsMarshal.GetValueRefOrAddDefault позволяет в одной операции найти существующий элемент или добавить новый, чтобы два раз не выполнять поиск. Это является небезопасным методом, поэтому вызов такой многословынй.

Чтобы эта магия работала надо создавать Dictionary со специальным comparer_ом

class StringToUtf8BytesComparer(Encoding enc, int seed = 0) 
  : IEqualityComparer<string>, 
    IAlternateEqualityComparer<ReadOnlySpan<byte>, string>
{
    public string Create(ReadOnlySpan<byte> alternate)
    {
        return enc.GetString(alternate);
    }

    public bool Equals(ReadOnlySpan<byte> alternate, string other)
    {
        Span<byte> buffer = stackalloc byte[enc.GetByteCount(other)];
        enc.GetBytes(other, buffer);
        return alternate.SequenceCompareTo(buffer) == 0;
    }

    public bool Equals(string? x, string? y)
    {
        return string.Equals(x, y);
    }

    public int GetHashCode(ReadOnlySpan<byte> alternate)
    {
        return (int)System.IO.Hashing.XxHash32.HashToUInt32(alternate, seed);
    }

    public int GetHashCode([DisallowNull] string obj)
    {
        Span<byte> buffer = stackalloc byte[enc.GetByteCount(obj)];
        enc.GetBytes(obj, buffer);
        return (int)System.IO.Hashing.XxHash32.HashToUInt32(buffer, seed);
    }
}

  • Нужно реализовать IAlternateEqualityComparer с тем типом, значения которого вы хотите искать, в моем случае ReadOnlySpan<byte>.

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

  • Я использовал System.IO.Hashing.XxHash32 для хэша, чтобы работало быстро.

С кэшем сортировка отрабатывает за 1:42, из которых 0:56 это запись. Объем памяти при работе не превышает 800мб.

На 100ГБ файле (10 раз скопированный по 10ГБ) получилось 00:30:52. Объем памяти в пике - 8гб.

Код по ссылке https://github.com/gandjustas/HugeFileSort/tree/6a3dc422d429e2e9dbb2bfeeb3e9ff0816025c59

Уникальные строки

Получивший код хоть и может отсортировать 100ГБ менее чем за час, но он не выполняет сортировку слияние и работает только потому, что в файле на 100ГБ уникальных строк получилось менее 0,01%.

Чтобы сделать более пессимистичный пример напишу генератор файла со случайными данными.

static async Task Generate(FileInfo file, int size, CancellationToken ct)
{
    var encoding = System.Text.Encoding.UTF8;
    var newLine = encoding.GetBytes(Environment.NewLine);
    var random = Random.Shared;
    var buffer = new char[1024];
    long written = 0;
    
    var writer = PipeWriter.Create(file.Create());
    while (written < size * 1024L* 1024L)
    {
        writer.Write(random.Next(), "d");        
        writer.Write(". ", encoding);        
        writer.Write(RandomString(random, random.Next(buffer.Length), buffer), encoding);
        writer.Write(newLine);
        if(writer.UnflushedBytes > size)
        {
            written += writer.UnflushedBytes;
            await writer.FlushAsync(ct);
        }
    }

    await writer.CompleteAsync();
}

static ReadOnlySpan<char> RandomString(Random random, int length, Span<char> span)
{
    const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    for (int i = 0; i < length; i++)
    {
        span[i] = chars[random.Next(chars.Length)];
    }
    return span[..length];
}

На фале в 10Гб сгенерированном таким алгоритмом сортировка кодом выше работает за 02:28 с кэшированием и 04:09 без него. В пике съедает 27 ГБ оперативной памяти.

Код по ссылке https://github.com/gandjustas/HugeFileSort/tree/857f52185b734570eb15d12f5ee3a201291a8007

Оптимизация памяти

27 ГБ памяти на 10 ГБ файле возникает потому, что мы используем string в качестве ключей dictionary. То есть при чтении каждая строка в UTF8, в которой тратится 1 байт на символ, превращается в массив char, каждый из которых тратит 2 байта на символ, чем удваивает потребление.

Комментарии (1)


  1. mayorovp
    09.03.2026 07:14
    #29638778

    Код копирования файла с двумя циклами крайне странный, он работает только по той причине, что внешний цикл никогда не выполняется второй раз.

    while (!sequenceReader.End)
{
    // …
    buffer = buffer.Slice(sequenceReader.Position);
    sequenceReader.Advance(buffer.Length);
}

    Проблема 1: позиция в sequenceReader накапливается от итерации к итерации, а вы каждый раз режете buffer. Второй раз от буфера был бы отрезан в том числе и тот кусок, который уже был отрезан в первый раз.

    Проблема 2: sequenceReader.Advance(buffer.Length); немедленно потребляет все оставшиеся байты в sequenceReader, делая вторую итерацию невозможной.

    Но главная проблема - зачем вообще это написано? Первый цикл уже вычитал все полные строки из буфера, больше из него прочитать невозможно. И sequenceReader сам по себе прекрасно отслеживает что было обработано, а что нет. Зачем тут вообще отдельная работа с буфером?

    Вот как-то так должно быть:

            var result = await reader.ReadAsync(ct);
        SequenceReader<byte> sequenceReader = new(result.Buffer);

        while (sequenceReader.TryReadTo(out ReadOnlySpan<byte> line, newLine))
        {
            writer.Write(line);
            writer.Write(newLine);
        }

        reader.AdvanceTo(sequenceReader.Position, sequenceReader.Sequence.End);
        await writer.FlushAsync(ct);
        if (result.IsCompleted) break;