Попарное суммирование

Эта функция попарно складывает массив. Он работает достаточно быстро и кажется дружественным к кешу; Я проверил его на правильность вывода. Он написан на C ++ (ниже в файле есть функция, которая принимает вектор), но также выглядит как действительный C (но я не пробовал это в C). Насколько легко это понять?

double pairwisesum(double *a,unsigned n)
{
  unsigned i,j,b;
  double sums[32],sum=0;
  for (i=0;i+7<n;i+=8)
  {
    b=i^(i+8);
    if (b==8)
      sums[3]=(((a[i]+a[i+1])+(a[i+2]+a[i+3]))+((a[i+4]+a[i+5])+(a[i+6]+a[i+7])));
    else
    {
      sums[3]+=(((a[i]+a[i+1])+(a[i+2]+a[i+3]))+((a[i+4]+a[i+5])+(a[i+6]+a[i+7])));
      for (j=4;b>>(j+1);j++)
        sums[j]+=sums[j-1];
      sums[j]=sums[j-1];
    }
  }
  for (;i<n;i++)
  {
    b=i^(i+1);
    if (b==1)
      sums[0]=a[i];
    else
    {
      sums[0]+=a[i];
      for (j=1;b>>(j+1);j++)
        sums[j]+=sums[j-1];
      sums[j]=sums[j-1];
    }
  }
  for (i=0;i<32;i++)
    if ((n>>i)&1)
      sum+=sums[i];
  return sum;
}

Для сравнения, вот предыдущая версия, которая была медленнее, потому что продолжала пропускать кеш-память, а также засоряла массив:

double pairwisesum(double *a,unsigned n)
// a is clobbered.
{
  unsigned i,j;
  if (n)
  {
    for (i=1;i<n;i*=2)
      for (j=0;j+i<n;j+=2*i)
    a[j]+=a[j+i];
    return a[0];
  }
  else
    return 0;
}

Эта функция попарно складывает массив.

Не уверен, что это значит.

Он работает достаточно быстро и кажется дружественным к кешу; Я проверил его на правильность вывода.

Хорошо, значит, работает.

Он написан на C ++ (ниже в файле есть функция, которая принимает вектор), но также выглядит как действительный C (но я не пробовал это в C).

Нет, это не так.
Это C. Вы только что скомпилировали его с помощью компилятора C ++.

Быть C ++ — это не просто писать код, который может быть скомпилирован компилятором C ++. Это стиль написания кода. Это типичный стиль C. Это просто компилируется под компилятором C ++, но это не C ++.

Этот интерфейс:

double pairwisesum(double *a,unsigned n)

Пара проблем: мы не передаем указатели в C ++ (мы можем, но, как язык, мы решили, что это плохая идея, поскольку он не показывает права собственности). Поэтому мы склонны использовать другие методы (например, ссылки или умные указатели).

В этом случае это не просто указатель: это массив. Проблема здесь в том, что массив распался, поэтому мы больше не можем сказать, что это массив, и просто должны предположить, что вызывающий не сделал что-то глупое. В C ++ нам нравится понимать передаваемый объект, чтобы мы могли его правильно использовать.

В C ++ (до C ++ 17) мы обычно представляем это как итераторы:

 template<typename T>
 double pairwisesum(I begin, I end)
 {
     for(I loop = begin; loop != end; ++loop) {

В C ++ 20 мы, вероятно, представим это диапазоном:

 tempalte<typename R>
 double pairwisesum(R range)
 {
     for (auto const& r: range) {

Обратите внимание на Range в основном поддерживает begin() и end() и взаимозаменяем с View. Если я понял это неправильно, извините: мы все еще привыкаем к этим концепциям, поскольку они являются новинкой для C ++.

Насколько легко это понять?

Я прочитал этот код пару раз и понятия не имею, чего он пытается достичь. Поэтому я не думаю, что это можно читать или понимать без дополнительных объяснений. Некоторые комментарии по поводу происходящего были бы хороши.

Проверка кода

Объявить переменные:

• Как можно ближе к месту использования.

• Объявите по одной переменной в каждой строке.

  unsigned i,j,b;
  double sums[32],sum=0;
  

Чего вы пытаетесь достичь? Вертикальная экономия места — не лучший стиль. Сделайте его максимально понятным для использования.

Я знаю, что многие люди используют i/j для переменных цикла (особенно из C или FORTRAN). Но это объективно плохой выбор. Как только вы начнете добавлять комментарии в свой код, ищите i и j в коде дает слишком много ложных совпадений при попытке найти все варианты использования. Поэтому, если ваш цикл буквально не является очевидным, а переменная цикла используется только в одном месте, не делайте этого. Даже если все вышеперечисленное верно, не делайте этого, потому что код будет меняться со временем, и его выразительное написание сейчас сэкономит время позже.

Вы можете объявить свою переменную в цикле:

  for (i=0;i+7<n;i+=8)

Напишите так:

  for (unsigned loop = 0; loop + 7 < mac; loop += 8) {

Здесь нет никаких правил приоритета, которые вы пытаетесь обойти. Эти дополнительные фигурные скобки просто добавляют шума в код:

      sums[3]=(((a[i]+a[i+1])+(a[i+2]+a[i+3]))+((a[i+4]+a[i+5])+(a[i+6]+a[i+7])));

Почему нет:

      sums[3]=a[i]+a[i+1]+a[i+2]+a[i+3]+a[i+4]+a[i+5]+a[i+6]+a[i+7];

Почему бы не использовать стандартный алгоритм:

      auto start = a + i;
      auto end   = start + 8;
      sums[3]    = std::accumulate(start, end, 0);

Как оказалось, круглые скобки здесь неспроста. Потому что мы имеем дело с двойниками. Скобки сокращают количество ошибок, которые закрадываются в сумму, за счет того, что мы выполняем сложение в определенном порядке.

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

sums[3] = sumValuesBecauseOfSomeReasonIHaveThatReducesErrors(a + i)

inline double sumValuesBecauseOfSomeReasonIHaveThatReducesErrors(double* a) {
    return (((a[0]+a[1])+(a[2]+a[3]))
         +((a[4]+a[5])+(a[6]+a[7])));
}

Это нечитаемо:

      for (j=4;b>>(j+1);j++)

Что вы тестируете в b >> (j+1)? Используем именованную функцию, чтобы прояснить смысл.

      for (unsigned jLoop; insideReachValid(b, jLoop); ++jLoop) {

В качестве примечания: предпочитаю ++j над j++. Для целых чисел разницы нет. Но если вы используете цикл с другими типами, это может иметь незначительное значение, и идея состоит в том, что вы хотите быть оптимальным независимо от типа цикла. Большая часть кода C ++ модифицируется путем простого изменения типа объектов, и вы не хотите менять тип, а затем вернитесь и измените способ его использования.

Всегда добавляйте фигурные скобки вокруг подблоков ‘{} `. Не всегда понятно с отступом (особенно когда он плохо работает), что находится в субблоке. Сделайте это явным, используя фигурные скобки.

      for (unsigned jLoop; insideRacheValud(b, j); ++j) {
          sums[jLoop] += sums[jLoop - 1];
      }

Это должен быть ваш комментарий над кодом.

// This is the original implementation.
// The code has been updated to prevent cache missing and optimize the
// the performance of the operation.
//
// This code is deliberately left here as a comment to provide a reference
// for generating unit tests and validation and to explain what the code
// is actually trying to achieve (as the optimized version is non-trivial to understand).
#if 0
double pairwisesum(double *a,unsigned n)
// a is clobbered.
{
  unsigned i,j;
  if (n)
  {
    for (i=1;i<n;i*=2)
      for (j=0;j+i<n;j+=2*i)
    a[j]+=a[j+i];
    return a[0];
  }
  else
    return 0;
}
#endif