Как хорошо застежки-молнии работают на практике, и когда они должны использоваться?
Я думаю, что застежка-молния является красивой идеей; это изящно позволяет обходить список или дерево и делать то, что, кажется, локальные обновления функциональным способом.
Асимптотически, затраты, кажется, разумны. Но пересечение структуры данных требует выделения памяти при каждом повторении, где нормальный список или обход дерева являются просто преследованием указателя. Это кажется дорогим (исправьте меня, если я неправ).
Действительно ли стоимость является чрезмерной? И что, при каких обстоятельствах было бы разумно использовать застежку-молнию?
1 ответ
Я могу привести один надежный момент: у нас с Джоном Диасом была статья на семинаре ML 2005 , в которой мы сравнивали стоимость использования застежки-молнии для представления графов потока управления со стоимостью использования изменяемых поля записи в Objective Caml. Мы были очень приятно удивлены, обнаружив, что производительность нашего компилятора с графами потока управления на основе застежки-молнии на самом деле была немного лучше, чем производительность при использовании традиционной структуры данных с изменяемыми записями, связанными указателями. Мы не смогли найти серьезных инструментов анализа, чтобы точно сказать , почему застежка-молния была быстрее, но я подозреваю, что причина заключалась в том, что было меньше инвариантов, которые нужно было поддерживать, и поэтому относительно меньше назначений указателей. Также возможно, что оптимизатор был достаточно умен, чтобы компенсировать некоторые затраты на размещение, понесенные застежкой-молнией. В любом случае застежка-молния может использоваться в оптимизирующем компиляторе, и на самом деле это дает небольшое преимущество в производительности .