Производительность странного алгоритма

Ответ 1

Большинство людей, работающих с гипотезой, похоже, что в библиотеки есть какой-то магический номер, который закодирован в библиотеки, что приводит к фазовому переходу в производительности около 999-1000 (за исключением LSerni, который делает предварительное наблюдение, что может быть многократная магия числа).

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

Затем я запустил свой код, чтобы проверить, могу ли я дублировать результаты на моем процессоре Intel Core i5 с процессором M480, Linux 4.8.0-34, используя g++ 6.2.0-5ubuntu2 в качестве моего компилятора с оптимизацией -O3.

Конечно, есть волшебное падение с 999 до 1000 (и еще около 1600):

Обратите внимание, что мой набор данных trans-1000 не так чист, как ваш: это может быть потому, что я играю с несколькими другими вещами в фоновом режиме на своей машине, тогда как у вас была более спокойная среда тестирования.

Мой следующий вопрос: был ли этот волшебный номер 1000 стабильным между средами?

Поэтому я попытался запустить код на процессоре Intel (R) Xeon (R) CPU E5-2680 v3, Linux 2.6.32-642.6.1.el6.x86_64, используя g++ 4.9.2. И, что не удивительно, магическое число было другим, происходящим в 975-976:

Это говорит нам, что, если было волшебное число, оно изменилось между версиями. Это уменьшает мою уверенность в теории магических чисел по нескольким причинам. (a) Оно изменяется. (b) 1000 + 24 байта накладных расходов - хороший кандидат на магию. 975 + 49 байт меньше. (c) Первая среда имеет лучшее программное обеспечение на более медленном процессоре, но первая среда показывает, что я считаю худшей производительностью: до тех пор, пока 1000 не ускорят работу. Это похоже на регресс.

Я попробовал другой тест: запуск программы с различными случайными входными данными. Это дает следующий результат:

Существенной точкой в ​​приведенном выше графике является то, что падение 999-1000 не является таким особенным. Похоже, что многие капли перед ним: медленное снижение скорости, за которым следует резкое улучшение. Также стоит отметить, что многие предыдущие капли не выравниваются.

Это показало мне, что это зависящее от ввода поведение и что существует корреляция между прогонами. Поэтому я задавался вопросом, что произойдет, если я уменьшу корреляцию между прогонами, рандомизировав их порядок. Это дало:

Что-то еще происходит около 999-1000:

Позвольте увеличить масштаб еще больше:

Выполнение этого на более быстром компьютере с более старым программным обеспечением дает аналогичный результат:

Увеличенный:

Так как рандомизация порядка, в котором строки из разных длин считаются существенно устраненными медленным нарастанием между прогонами (вышеупомянутая корреляция), это говорит о том, что явление, которое вы видите, требует своего рода глобального состояния. Поэтому строка/вектор С++ не может быть объяснением. Поэтому malloc, "ОС" или архитектурные ограничения должны быть объяснением.

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

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

Другим аргументом против эффекта кеширования является следующее. Обе машины имеют кэши L1 и L2 объемом 32 КБ и 256 КБ, поэтому их производительность кэша должна быть одинаковой. Моя медленная машина имеет кэш-память L3 3,072 КБ. Если вы принимаете страницу размером 4 КБ на выделение, 1000 узлов выделяют 4 000 КБ, что близко к размеру кеша. Тем не менее, быстрая машина имеет кэш-память L3 30,720 КБ и показывает разрыв на уровне 975. Если бы это явление было кеширующим эффектом, вы ожидали бы, что это произойдет, если что-нибудь случится позже. Поэтому я уверен, что кэширование здесь не работает.

Единственным оставшимся виновником является malloc.

Почему это происходит? Я не уверен. Но, как программист, мне все равно, как следует.

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

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

Далее следует исходный код. Обратите внимание, что код изменяет вашу версию char indexToNext на int indexToNext, исправляя возможные проблемы с переполнением целых чисел. Тестирование interjay suggestion, что мы избегаем создания копий строки, фактически приводило к худшей производительности.

#include <string>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>

struct profiler
{
  std::string name;
  std::chrono::high_resolution_clock::time_point p;
  profiler(std::string const &n) :
      name(n), p(std::chrono::high_resolution_clock::now()) { }
  ~profiler()
  {
      using dura = std::chrono::duration<double>;
      auto d = std::chrono::high_resolution_clock::now() - p;
      std::cout //<< name << ": "
          << std::chrono::duration_cast<dura>(d).count()
          << std::endl;
  }
};

#define PROFILE_BLOCK(pbn) profiler _pfinstance(pbn)

struct node {
  char value = ' ';
  std::vector<node*> children;
  ~node(){
    for (node* child: children)
      delete child;
  }
};

int numberOfUniqueSubstrings(const std::string aString, node*& root)
{
    root = new node();
    int substrings = 0;
    for (int i = 0; i < aString.size(); ++i)
    {
        node* currentNode = root;
        int indexToNext = i;
        for (int j = 0; j < currentNode->children.size(); ++j)
        {
            if (currentNode->children[j]->value == aString[indexToNext])
            {
                currentNode = currentNode->children[j];
                j = -1;
                indexToNext++;
            }
        }
        for (int j = indexToNext; j < aString.size(); ++j)
        {
            node* theNewNode  = new node;
            theNewNode->value = aString[j];
            currentNode->children.push_back(theNewNode);
            currentNode = theNewNode;
            substrings++;
        }
    }
    return substrings;
}


int main(int argc, char **argv){
  const int MAX_LEN = 1300;

  if(argc==1){
    std::cerr<<"Syntax: "<<argv[0]<<"<SEED> [LENGTH]"<<std::endl;
    std::cerr<<"Seed of -1 implies all lengths should be explore and input randomized from time."<<std::endl;
    std::cerr<<"Positive seed sets the seed and explores a single input of LENGTH"<<std::endl;
    return -1;
  }

  int seed = std::stoi(argv[1]);

  if(seed==-1)
    srand(time(NULL));
  else
    srand(seed);

  //Generate a random string of the appropriate length
  std::string a;
  for(int fill=0;fill<MAX_LEN;fill++)
      a.push_back('a'+rand()%26);

  //Generate a list of lengths of strings to experiment with
  std::vector<int> lengths_to_try;
  if(seed==-1){
    for(int i=1;i<MAX_LEN;i++)
      lengths_to_try.push_back(i);
  } else {  
    lengths_to_try.push_back(std::stoi(argv[2]));
  }

  //Enable this line to randomly sort the strings
  std::random_shuffle(lengths_to_try.begin(),lengths_to_try.end());

  for(auto len: lengths_to_try){
    std::string test(a.begin(),a.begin()+len);

    std::cout<<len<<" ";
    {
      PROFILE_BLOCK("Some time");
      node *n;
      int c = numberOfUniqueSubstrings(test,n);
      delete n;
    }
  }
}

substr является "константой"

Оригинальный код OP включал следующее:

for (int i = 0; i < aString.size(); ++i)
{
  string tmp = aString.substr(i, aString.size());

Операция substr занимает O(n) время в длине строки. В ответе ниже, утверждается, что эта операция O(n) приводит к низкой производительности исходного кода OP.

Я не согласен с этой оценкой. Из-за операций кеширования и SIMD процессоры могут считывать и копировать данные в блоках до 64 байтов (или более!). В связи с этим затраты на распределение памяти могут доминировать в стоимости копирования строки. Таким образом, для размеров входного сигнала OP операция substr действует скорее как дорогая константа, чем дополнительный цикл.

Это можно продемонстрировать путем тестирования путем компиляции кода с помощью, например, g++ temp.cpp -O3 --std=c++14 -g и профилирование с помощью, например, sudo operf ./a.out -1. Результирующий профиль использования времени выглядит следующим образом:

25.24%  a.out    a.out                [.] _ZN4nodeD2Ev        #Node destruction                                                                           
24.77%  a.out    libc-2.24.so         [.] _int_malloc                                                                                    
13.93%  a.out    libc-2.24.so         [.] malloc_consolidate                                                                            
11.06%  a.out    libc-2.24.so         [.] _int_free                                                                                      
 7.39%  a.out    libc-2.24.so         [.] malloc                                                                                        
 5.62%  a.out    libc-2.24.so         [.] free                                                                                          
 3.92%  a.out    a.out                [.] _ZNSt6vectorIP4nodeSaIS1_EE19_M_emplace_back_auxIJRKS1_EEEvDpOT_                              
 2.68%  a.out    a.out                [.]
 8.07%  OTHER STUFF

Из чего видно, что управление памятью доминирует во время выполнения.

Ответ 2

for (int i = 0; i < aString.size(); ++i)
{
    string tmp = aString.substr(i, aString.size());

Это уже делает ваш алгоритм O (n ^ 2) или хуже. Вызов substr создает в среднем подстроку размера n/2, поэтому она принимает O (n), и вы называете ее n раз.

Кажется, вам действительно не нужна строка tmp, поскольку вы только читали ее. Вместо этого прочитайте исходную строку, но соответственно измените свою индексацию.

Цикл for (int j = indexToNext; j < tmp.size(); ++j), вероятно, также даст вашему алгоритму O (n ^ 2) общее время (я говорю "возможно", потому что он зависит от вычисленного значения indexToNext, но от тестирования со случайными строками он, кажется, удерживается правда). Он запускает O (n) раз и каждый раз занимает до O (n) итераций.

Ответ 3

Я подозреваю malloc больше, чем string или vector. Весьма возможно, что он обрабатывает < 1000 байтов и > 1000 байтов по-разному. Коалесцирование освобожденных блоков может быть дорогостоящим. Он может воздерживаться от попыток объединить более крупные блоки (т.е. Поддерживая их в пулах). Но это действительно просто догадка. Почему бы вам не попробовать профайлер и получить реальные данные? gprof прост в использовании.

В этой статье есть интересные сведения о glibc malloc. Если это то, что под капотом вашей программы, различия между типами бинов, описанных там, могут быть на работе. Действительно, куски освобождаются до "несортированного бункера", который иногда реорганизован. Это возможно, что шипы являются этими реорганизациями, чтобы предотвратить рост кучи. Если эта теория верна, то сглаживание может быть результатом роста арены кучи до размера, при котором реорганизация не так дорого.

Но опять же, это все догадки, которые можно разрешить, запустив профайлер, чтобы увидеть, где время идет с < 1000 vs > 1000.