Для вектора вектора вектора с использованием указателей стиля C, но не с использованием итераторов

Question

Я написал небольшой фрагмент кода, который я использую для накопления значений вектора, который быстрее, чем std :: accumulate, потому что он позволяет функции векторизация. Основной предпосылкой для функции является то, что вектор больше не используется после накопления. Код выглядит следующим образом:

template <typename floatType> 
template <typename Iterator> 
double Numeric_class<floatType>::AmDestructiveAccumulate(Iterator A, size_t length) 
{ 
    if (length == 1) 
    { 
     return A[0]; 
    } 

    Iterator temp_; 
    while (length > 1) 
    { 
     if (length & 1) // odd 
     { 
      A[0] += A[length - 1]; // We add the last value which would otherwise be lost. 
      length >>= 1; 
      temp_ = A+length; 
      for (int i = 0; i < length; i++) 
      { 
       A[i] += temp_[i]; 
      } 
     } 
     else // even 
     { 
      length >>= 1; 
      temp_ = A+length; 
      for (int i = 0; i < length; i++) 
      { 
       A[i] += temp_[i]; 
      } 
     } 
    } 
    return A[0]; 
} 

функция в основном разделяет вектор в двух половинках и принимает парную сумму два половинок. После этого он разбивает суммарную первую половину на два одинаковых диапазона и снова суммирует вверх и так далее.

Я использовал эту функцию с std::vector<double> data. Если я называю это A, то data.data(). Сказки векторизации располагаются так, как ожидалось, и я также получаю значительное увеличение скорости выполнения. Если я использую data.begin(), векторизация не выполняется. Я скомпилировал код с помощью VC2015 с полной оптимизацией. Есть ли причина, по которой было бы незаконно векторизовать версию итератора кода, или VC просто не делает этого, хотя это будет законным.

Answer 1

Основной проблемой будет A[i] += temp_[i];. Обратите внимание, что A и temp являются псевдонимами друг друга, но ваш выбор времени выполнения [i] означает, что это только теоретическое. Теперь, что означает [i]? Если A является указателем, это просто сокращение для *(A+i), но когда A является итератором, это вызов функции.

Эффективная векторизация требует, чтобы компилятор обнаружил, что запись в A[i] не влияет на последующие чтения с temp[i], что является нетривиальным наблюдением. Нет никакой зависимости от цикла, но оптимизатор должен быть в состоянии это доказать.