Оптимизация компилятора ломает ленивый итератор
Я написал собственный контейнер с его собственным итератором. Из-за особенностей контейнера итератор должен оцениваться лениво. Ради вопроса, релевантная часть кода является оператором разыменования итератора, который реализован таким образом.
template<typename T>
struct Container
{
vector<T> m_Inner;
// This should calculate the appropriate value.
// In this example is taken from a vec but in
//the real use-case is calculated on request
T Value(int N)
{ m_Inner.at(N); }
}
template<typename T>
struct Lazy_Iterator
{
mutable pair<int, T> m_Current;
int Index
Container<T>* C
Lazy_Iterator(const Container& Cont, int N):
m_Current{Index, T{}}, Index{N}, C{&Cont}
{ }
pair<int, T>&
operator*() const // __attribute__((noinline)) (this cures the symptom)
{
m_Current.first = Index; /// Optimized out
m_Current.second = C->Value(Index); /// Optimized out
return m_Current;
}
}
Поскольку сам итератор является шаблоном, его функции могут быть свободно встроены компилятором.
Когда я компилирую код без оптимизации, возвращаемое значение обновляется, как и ожидалось. Когда в некоторых случаях я использую оптимизацию компилятора релиза (-O2 в GCC 4.9), компилятор оптимизирует строки, которые я пометил как оптимизированные, даже если член m_Current помечен как изменяемый. Как следствие, возвращаемое значение не соответствует значению, на которое должен указывать итератор.
Это ожидаемое поведение? Знаете ли вы какой-либо переносимый способ указать, что содержимое этой функции должно оцениваться, даже если оно помечено как const?
Я надеюсь, что вопрос достаточно исчерпывающий, чтобы быть полезным. Пожалуйста, посоветуйте, если в этом случае может помочь более подробная информация.
Редактировать:
Чтобы ответить на один комментарий, это потенциальное использование, взятое из небольшой тестовой программы:
Container<double> myC;
Lazy_Iterator<double> It{myC, 0}
cout << "Creation: " << it->first << " , " << it->second << endl;
auto it2 = it;
cout << "Copy: "<< it2->first << " , " << it2->second << endl;
cout << "Pre-increment: " << (it++)->first << " , " << it->second << endl;
cout << "Post-increment: " << (++it)->first << " , " << it->second << endl;
cout << "Pre-decrement: " << (it--)->first << " , " << it->second << endl;
cout << "Post-decrement: " << (--it)->first << " , " << it->second << endl;
cout << "Iterator addition: " << (it+2)->first << " , " << (it+2)->second << endl;
cout << "Iterator subtraction: "<< (it-2)->first << " , " << (it-2)->second << endl;
reverse_iterator<Lazy_Iterator> rit{it};
cout << "Reverse Iterator: " << rit->first << " , " << rit->second << endl;
auto rit2 = rit;
cout << "Reverse Iterator copy: " << rit2->first << " , " << rit2->second << endl;
cout << "Rev Pre-increment: " << (rit++)->first << " , " << rit->second << endl;
cout << "Rev Post-increment: " << (++rit)->first << " , " << rit->second << endl;
cout << "Rev Pre-decrement: " << (rit--)->first << " , " << rit->second << endl;
cout << "Rev Post-decrement: " << (--rit)->first << " , " << rit->second << endl;
cout << "Rev Iterator addition: " << (rit+2)->first << " , " << (rit+2)->second << endl;
cout << "Rev Iterator subtraction: "<< (rit-2)->first << " , " << (rit-2)->second << endl;
Результаты теста являются ожидаемыми для всех тестов, кроме двух последних строк
Последние две строки теста ломаются, когда оптимизация включена.
Система на самом деле работает хорошо и не так опаснее, чем любой другой итератор. Конечно, произойдет сбой, если контейнер будет удален из-под его носа, и, вероятно, безопаснее использовать возвращаемое значение при копировании, а не просто хранить ссылку, но это не по теме
4 ответа
Существует проблема с разницей между физическим итератором reverse_iterator
(что возвращается .base()
) и логическое значение, на которое оно указывает: они однозначно. reverse_iterator
может сделать return *(--internal_iterator);
на разыменование, которое оставляет вас с висячей ссылкой на внутренности разрушенного локального временного функции.
После очередного прочтения стандарта я узнал, что у него есть дополнительные требования, чтобы избежать такого сценария, читайте в примечании.
Также я обнаружил, что стандартная библиотека GCC 4.9 несовместима. Он использует временный. Итак, я думаю, что это ошибка GCC.
Изменить: Стандартная цитата
24.5.1.3.4 оператор * [reverse.iter.op.star]
reference operator*() const;
1 Эффекты:
deref_tmp = current; --deref_tmp; return *deref_tmp;
2 [Примечание: эта операция должна использовать вспомогательную переменную-член, а не временную переменную, чтобы избежать возврата ссылки, которая сохраняется в течение времени жизни связанного с ней итератора. (См. 24.2.) - Конец примечания]
Последующее чтение: Отчет о дефектах библиотеки 198.
И похоже, что это возвращается к старому поведению.
Позднее редактирование: P0031 был выбран в C++17 Working Draft. Это заявляет, что reverse_iterator
использует временный, не член для хранения промежуточного значения.
"Оптимизировано, хотя m_Current
член помечен как изменяемый
Это говорит мне о том, что вы полагаете, что оптимизатор заботится о mutable
, Это не так. const
а также mutable
были лишены более ранней фазы компиляции.
Почему тогда оптимизатор удаляет два оператора, если они встроены? Я подозреваю, что после встраивания, оптимизатор может доказать, что две записи являются бездействующими, либо как m_Current
переменная должна содержать правильное значение уже, или потому что последующее использование m_Current
делает это спорным. Тривиально следующий случай делает те, кто пишет no-op:
Lazy_Iterator LI = foo(); // Theoretically writes
*LI = bar(); // Overwrites the previous value.
При условии, что вы должны опубликовать скомпилированный фрагмент, который воспроизводит эту проблему (на самом деле я не смог воспроизвести его с помощью GCC 4.9). Я думаю, что у вас неопределенное поведение, которое запускается O2 (O2 позволяет оптимизировать, что может нарушить неопределенное поведение). Вы должны иметь указатель на
Container<T>
внутри итератора.
В любом случае, имейте в виду, что ленивый итератор нарушает контракт итераторов std, я думаю, что лучшей альтернативой является создание обычного контейнера с ленивыми значениями, вы могли бы таким образом пропустить создание собственного контейнера и итератора вообще;) (см. Образец прокси),
После очень прибыльного раунда обсуждений ответ Revolver_Ocelot показал мне, что нужно смотреть дальше на реализацию reverse_iterators. Согласно его цитате из стандартов:
24.5.1.3.4 оператор * [reverse.iter.op.star]
reference operator*() const;
1 Эффекты:
deref_tmp = current; --deref_tmp; return *deref_tmp;
2 [Примечание: эта операция должна использовать вспомогательную переменную-член, а не временную переменную, чтобы избежать возврата ссылки, которая сохраняется в течение времени жизни связанного с ней итератора. (См. 24.2.) - Конец примечания]
Заглянем внутрь заголовка stl_iterator.c стандартной библиотеки, реализованной в GCC 4.9 в Debian 8:
/**
* @return A reference to the value at @c --current
*
* This requires that @c --current is dereferenceable.
*
* @warning This implementation requires that for an iterator of the
* underlying iterator type, @c x, a reference obtained by
* @c *x remains valid after @c x has been modified or
* destroyed. This is a bug: http://gcc.gnu.org/PR51823
*/
reference
operator*() const
{
_Iterator __tmp = current;
return *--__tmp;
}
Обратите внимание на предупреждение:
Предупреждение: эта реализация требует, чтобы для итератора базового типа итератора, @c x, ссылка, полученная с помощью @c *x, оставалась действительной после того, как @cx был изменен или уничтожен. Это ошибка: http://gcc.gnu.org/PR51823