Оптимизация компилятора ломает ленивый итератор

Я написал собственный контейнер с его собственным итератором. Из-за особенностей контейнера итератор должен оцениваться лениво. Ради вопроса, релевантная часть кода является оператором разыменования итератора, который реализован таким образом.

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

Другие вопросы по тегам