Насколько хорошо работают молнии на практике, и когда их следует использовать?

Question

Я думаю, что молния - прекрасная идея; он элегантно предоставляет способ для обхода списка или дерева и создания функциональных возможностей для локальных обновлений.

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

Являются ли расходы чрезмерно высокими? И что при каких обстоятельствах было бы разумно использовать молнию?

Answer 1

Я могу предоставить одну надежную точку данных: у нас с Джоном Диасом была статья на семинаре ML ML 2005 года , где мы сравнили стоимость использования застежки-молнии для представления управляющих потоковых диаграмм со стоимостью использования изменяемой запись полей в объективе Caml. Мы были очень приятно удивлены, обнаружив, что производительность нашего компилятора с графами потоков управления на основе zipper на самом деле была немного выше, чем производительность при использовании традиционной структуры данных с изменяемыми записями, связанными указателями. Мы не смогли найти серьезных инструментов анализа, которые бы точно указали нам , почему молния была быстрее, но я подозреваю, что причина заключалась в том, что было меньше поддерживаемых инвариантов и поэтому относительно меньше назначений указателей. Также возможно, что оптимизатор был достаточно умен, чтобы амортизировать некоторые из затрат на выделение, которые несет молния. В любом случае, застежка-молния может использоваться в оптимизирующем компиляторе, и на самом деле есть небольшая производительность преимущество .