Почему это так медленнее в C ++?

Question

Я преобразовал этот простой метод из C # в C ++. Он читает таблицу путей и заполняет список списков целых чисел (или вектора векторов целых чисел).

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

0 12 5 16 n

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

//Parses the text path vector into the engine
void Level::PopulatePathVectors(string pathTable)
{
    // Read the file line by line.
    ifstream myFile(pathTable);

        for (unsigned int i = 0; i < nodes.size(); i++)
        {
            pathLookupVectors.push_back(vector<vector<int>>());

            for (unsigned int j = 0; j < nodes.size(); j++)
            {
                string line;

                if (getline(myFile, line)) //Enter if a line is read successfully
                {
                    stringstream ss(line);
                    istream_iterator<int> begin(ss), end;
                    pathLookupVectors[i].push_back(vector<int>(begin, end));
                }
            }
        }
    myFile.close();
}

Вот версия C #:

private void PopulatePathLists(string pathList)
{
    // Read the file and display it line by line.
    StreamReader streamReader = new StreamReader(pathList);

    for (int i = 0; i < nodes.Count; i++)
    {
        pathLookupLists.Add(new List<List<int>>());

        for (int j = 0; j < nodes.Count; j++)
        {
            string str = streamReader.ReadLine();
            pathLookupLists[i].Add(new List<int>());

            //For every string (list of ints) - put each one into these lists
            int count = 0;
            string tempString = "";

            while (str[count].ToString() != "n") //While character does not equal null terminator
            {
                if (str[count].ToString() == " ") //Character equals space, set the temp string 
                                                  //as the node index, and move on
                {
                    pathLookupLists[i][j].Add(Convert.ToInt32(tempString));
                    tempString = "";
                }
                else //If characters are adjacent, put them together
                {
                    tempString = tempString + str[count];
                }
                count++;
            }
        }
    }
    streamReader.Close();
}

Извините, это так конкретно, но я в тупике.

РЕДАКТИРОВАТЬ - Многие люди сказали, что они проверили этот код, и для них это занимает всего несколько секунд. Все, что я знаю, это то, что если я закомментирую вызов этой функции, программа загружается за считанные секунды. С вызовом функции это занимает 5 минут. Почти точно. Я действительно в тупике. В чем может быть проблема?

Вот PathTable , который он использует.

РЕДАКТИРОВАТЬ - я пытался запустить функцию в программе самостоятельно, и это заняло несколько секунд, но я боюсь, что не знаю достаточно, чтобы узнать, как решить эту проблему. Очевидно, это не код. Что бы это могло быть? Я проверил, где он вызывается, чтобы увидеть, было ли несколько вызовов, но нет. Он находится в конструкторе уровня игры и вызывается только один раз.

РЕДАКТИРОВАТЬ - Я понимаю, что код не лучший, каким он может быть, но здесь дело не в этом. Он работает быстро сам по себе - около 3 секунд, и это хорошо для меня. Проблема, которую я пытаюсь решить, состоит в том, почему это занимает намного больше времени внутри проекта.

РЕДАКТИРОВАТЬ - я закомментировал весь код игры, кроме основного игрового цикла. Я поместил метод в раздел инициализации кода, который запускается один раз при запуске. Если не считать нескольких методов настройки окна, то теперь это почти то же самое, что и программа, в которой используется ТОЛЬКО метод, только ОЧЕНЬ требуется около 5 минут для запуска. Теперь я знаю, что это не имеет ничего общего с зависимостями pathLookupVectors. Кроме того, я знаю, что это не проблема с памятью, когда компьютер начинает запись на жесткий диск, потому что, пока медленная программа откладывает выполнение метода, я могу открыть другой экземпляр Visual Studio и одновременно запустить программу с одним методом, которая завершает работу в секундах Я понимаю, что проблема может быть в некоторых основных настройках, но у меня нет опыта, поэтому извиняюсь, если причина в том, что это вызывает разочарование. Я до сих пор не понимаю, почему так долго.

Answer 1

Я профилировал код с Very Sleepy ( Visual C ++ 2010, 32-битная Windows XP). Я не знаю, насколько похожи были мои входные данные, но все равно вот результаты:

39% времени было проведено в basic_istream :: operator >>

12% basic_iostream :: basic_iostream

9% оператор +

8% _Mutex :: Mutex

5% getline

5% basic_stringbuf :: _ Init

4% локаль :: _ Locimp :: _ Addfac

4% вектор :: резерв

4% basic_string :: assign

Оператор удаления 3%

2% basic_Streambuf :: basic_streambuf

1% Wcsxfrm

5% другие функции

Некоторые вещи, похоже, происходят из встроенных вызовов, поэтому трудно сказать, откуда они на самом деле. Но вы все еще можете получить идею. Единственная вещь, которая должна делать ввод / вывод, это getline, которая занимает всего 5%. Остальное - накладные расходы от потоковых и строковых операций. C ++ потоки медленны, как ад.

Answer 2

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

Полагаю, вы можете воспроизводить эту проблему производительности каждый раз, когда запускаете свой код, правильно? Тогда я хотел бы предложить вам сделать следующие тесты:

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

• Чтобы проверить, тратится ли дополнительное время на эту подозрительную функцию, вы можете добавить операторы printf в начале и конце функции, которые включают временные метки. Если это не консольное приложение, а приложение с графическим интерфейсом, и printfs никуда не денутся, запишите файл журнала. Если вы работаете в Windows, вы можете использовать OutputDebugString и использовать отладчик для захвата printfs. Если вы работаете в Linux, вы можете записать в системный журнал, используя syslog .

• Используйте профилировщик исходного кода, чтобы определить, на что тратится все это время. Если разница между вызовом этой функции или нет составляет несколько минут, то профилировщик наверняка даст понять, что происходит. Если вы работаете в Windows, то Very Sleepy - хороший выбор, и если вы работаете в Linux, вы можете использовать OProfile .

Обновление : Итак, вы говорите, что сборка релиза быстрая. Вероятно, это означает, что библиотечные функции, которые вы используете в этой функции, имеют медленную реализацию отладки. STL, как известно, так и есть.

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

• отключить оптимизации только для файлов, которые вы хотите отлаживать (убедитесь, что оптимизации остаются включенными, по крайней мере, для файла, который имеет медленную функцию). Чтобы отключить оптимизации для файла, выберите файл в обозревателе решений, щелкните правой кнопкой мыши, выберите «Свойства», затем перейдите в «Свойства конфигурации» | C / C ++ / «Оптимизация». Посмотрите, как все элементы на этой странице установлены для сборки Debug, и скопируйте все эти элементы в вашу сборку Release. Повторите для всех файлов, которые вы хотите быть доступными для отладчика.

• включить создание информации об отладке (файл pdb). Для этого выберите проект в верхней части обозревателя решений, щелкните правой кнопкой мыши и выберите «Свойства». Затем перейдите в Configuration Properties | Linker | Debugging и скопируйте все настройки из сборки Debug в сборку Release.

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

Как только вы закончите отладку, вам, конечно, придется сбросить все эти настройки обратно.

Надеюсь, это поможет.

Answer 3

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

Простой и быстрый эквивалентный код будет следующим:

int result;
stringstream ss(line);
while ( ss >> result ) //reads all ints untill it encounters non-int
{
    pathLookupVectors[i][j].push_back(result);
}

В C ++ такой цикл также идиоматичен. Или вместо этого ручного цикла вы можете написать: std::copy ¹ :

std::copy(std::istream_iterator<int>( ss ), 
          std::istream_iterator<int>(), 
          std::back_inserter(pathLookupVectors[i][j]));

^{1. Это взято из комментария Дэвида.}

Или даже лучше, если вы сделаете это, когда у вас push_back сам вектор:

 if (getline(myFile, line)) //enter if a line is read successfully
 {
   stringstream ss(line);
   std::istream_iterator<int> begin(ss), end;
   pathLookupVectors[i].push_back(vector<int>(begin, end));
 }

Готово!

Answer 4

Вот несколько вещей, которые я не видел ни у кого. Они несколько расплывчаты, но неспособность воспроизвести вещи затрудняет детализацию всего этого.

Профилирование бедного человека.

Пока код работает, просто продолжайте его прерывать. Обычно вы будете видеть один и тот же кадр стека снова и снова.

Начните комментировать вещи. Если вы закомментируете ваше разбиение, и оно завершается мгновенно, тогда довольно ясно, с чего начать.

Часть кода зависит, но вы можете прочитать весь файл в память, а затем выполнить анализ, чтобы создать очевидное разделение на то, где он тратит свое время. Если оба заканчивают быстро независимо друг от друга, то это, вероятно, взаимодействие.

Буферизация.

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

Хотя это не похоже на то, что вы пишете здесь, ваша основная программа может использовать больше памяти. Вполне возможно, что после того, как вы достигнете полной воды, ОС начнет передавать часть памяти на диск. Вы будете трэшить, когда читаете построчно, пока идет пейджинг.

Обычно я настраиваю простой интерфейс итератора, чтобы убедиться, что все работает. Затем напишите декоратор, чтобы прочитать 500 строк за раз. Стандартные потоки также имеют некоторые встроенные параметры буферизации, которые могут быть лучше использовать. Я догадываюсь, что их буферизованные настройки по умолчанию довольно консервативны.

Резерв.

std::vector::push_back работает лучше всего, когда вы также используете std::vector::reserve. Если вы можете сделать большую часть памяти доступной, прежде чем войти в тесный цикл, вы выиграете. Тебе даже не нужно точно знать, сколько, просто угадай.

Вы также можете превзойти производительность std::vector::resize с этим, потому что std::vector::resize использует alloc и std::vector::push_back будет использовать realloc

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

Тем не менее push_back может работать быстрее, если вы используете с ним резерв.

Расщепление строки.

Я никогда не видел решения итератора C ++, которое было бы эффективным, когда дело доходит до работы с файлами gb +. Я не пробовал это определенно, все же. Я догадываюсь, почему они обычно делают небольшие ассигнования.

Вот ссылка на то, что я обычно использую.

Разделить массив символов на два массива символов

Рекомендации по std::vector::reserve применяются здесь.

Я предпочитаю boost::lexical_cast потоковую реализацию из соображений обслуживания, хотя я не могу сказать, что она более или менее эффективна, чем потоковая реализация. Я скажу, что очень редко можно увидеть правильную проверку ошибок при использовании потока.

STL shenanigans.

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

На некоторых платформах при использовании потоковых операций по умолчанию включена некоторая странная безопасность потоков. Так что я видел, как незначительное использование std :: cout полностью разрушало производительность алгоритма. Здесь у вас ничего нет, но если вы ведете запись в другом потоке, это может вызвать проблемы. Я вижу 8% _Mutex::Mutex в другом комментарии, который может говорить о его существовании.

Вероятно, что у вырожденной реализации STL может даже возникнуть вышеуказанная проблема с операциями лексического анализа.

На некоторых контейнерах имеются странные характеристики производительности.У меня никогда не было проблем с вектором, но я действительно понятия не имею, что istream_iterator использует внутри.В прошлом я проследил через алгоритм неправильного поведения, чтобы найти вызов std::list::size, выполняющий полный обход списка, например, с помощью GCC.Я не знаю, являются ли более новые версии менее бессмысленными.

Об обычной глупой глупости SECURE_CRT следует тупо позаботиться.Интересно, это то, что, по мнению Microsoft, мы хотим тратить на это время?

Answer 5

Я не совсем уверен, что здесь происходит, но я вижу несколько способов, которыми вы можете оптимизировать свой код. Если это не поможет вам, возможно, происходит что-то еще.

---

Насколько велики твои струны? Когда вы передаете их в своей версии C ++, вы делаете копии, потому что вы «передаете по значению». Попробуйте передать его по постоянной ссылке:

void Level::PopulatePathVectors(const string &pathTable)

Это передает объект по ссылке, что означает, что он не делает копию. Затем это обычно делают const, чтобы гарантировать, что он не изменяется в вашей функции.

---

Используйте .append или += для расширения tempString. Я полагаю, что вы создаете новый строковый объект, а затем заменяете старый на +, тогда как += и .append собираются изменить текущий на месте:

tempString.append(line[count]);

---

Вы также можете немного повысить производительность, объявив переменные сверху и затем переназначив их. Это предотвратит их воссоздание каждый раз. Например, поставьте string line; перед циклом for, потому что он все равно будет перезаписан.

Есть несколько мест, где вы можете сделать это, например, с tempString.

Answer 6

И List.Add, и vector::push_back время от времени перераспределяют память по мере роста контейнера. Вектор C ++ хранит подвекторы по значению, поэтому все их данные (которые в вашем случае кажутся огромными) копируются снова и снова. В отличие от этого, список C # хранит подсписки по ссылкам, поэтому данные подсписков не копируются во время перераспределения.

Типичная векторная реализация удваивает свою емкость во время перераспределения. Так что если у вас есть 1 миллион строк, то субвекторы будут скопированы log (2 100 000) ≈ 10 раз.

Семантика перемещения , введенная в C ++ 11, должна устранить этот эффект. До этого попробуйте vector< shared_ptr< vector<int> > >, list< vector<int> > или, если вы заранее знаете размер в будущем, используйте vector::reserve(), чтобы избежать перераспределения.

Answer 7

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

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

_{1.Установлено в вашем последнем редактировании.}

Answer 8

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

Answer 9

Не проверял код, но сколько ints он обычно загружает?Подумайте, что происходит, когда каждый из ваших vectors достигает своего capacity.A vector растет неэффективно - O (n) я считаю.В C # List такого поведения нет.

Подумайте об использовании std::deque, std::list или какого-либо другого контейнера с лучшим поведением роста.См. статью для получения дополнительной информации.