Как оценить сложность решения задачи слияния каналов в Go?

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

Умеете ли вы оценить не только асимптотику, но и цену горутин, блокировок и select, и видите ли ошибки в типовой реализации fan-in. Следом почти всегда просят написать слияние для произвольного числа каналов и объяснить, кто и когда закрывает выходной канал.

Как отвечать

Обозначим: k входных каналов, M сообщений суммарно.

• время: каждое значение один раз читается и один раз пишется в выходной канал, итого O(M) операций с каналами. Каждая операция берёт внутреннюю блокировку канала: это константа, но не бесплатная;
• память: в классическом fan-in на каждый вход своя горутина с небольшим начальным стеком в несколько килобайт, итого O(k) плюс ёмкость буферов;
• select: стоимость одного select растёт с числом веток, рантайм перемешивает их и блокирует все участвующие каналы. Поэтому один select на много каналов хуже горутины на канал. Для динамического k есть reflect.Select, он тоже O(k) на вызов и заметно медленнее.

Каркас правильной реализации: на каждый вход запускается горутина, которая делает for v := range in и пересылает значения в out, sync.WaitGroup считает завершившихся, отдельная горутина после wg.Wait() делает close(out). Для отмены в каждую отправку добавляется select с <-ctx.Done(), иначе при уходе читателя горутины зависнут навсегда.

Если каналы отдают отсортированные потоки и результат тоже должен быть отсортирован, это уже k-way merge: минимальная куча из голов каналов через container/heap, O(M log k) по времени и O(k) по памяти.

Где спотыкаются

Проверяют завершение через len(ch) == 0. У небуферизованного канала len всегда ноль, и цикл выходит после первого же значения. Признак закрытия только один: ok == false при чтении.

Не выключают закрытый канал в select. Чтение из закрытого канала срабатывает мгновенно и бесконечно, получается холостой цикл на 100 % CPU. Закрытому каналу присваивают nil, и ветка перестаёт выбираться.

Забывают про утечку горутин. Без context или канала done отправители блокируются на out <- v, когда потребитель перестал читать, и висят до конца жизни процесса.