Без дополнительной информации, я думаю, что вы имеете дело с алгоритмом Шлемиэля Художника: (Оригинал) (Википедия) . Их невероятно легко впитать в обработку строк. Позвольте привести пример.
Я хочу прочитать каждую строку в файле, как-то обработать каждую строку, пройти через некоторую промежуточную обработку. Затем я хочу собрать результаты и, возможно, записать их обратно на диск. Вот способ сделать это. Я совершаю одну огромную ошибку, которую легко упустить:
// proc.cpp
class Foo
{
public:
std::string chew_on(std::string const& line_to_chew_on) {...}
...
};
Foo processor;
std::string buffer;
// Read/process
FILE *input=fopen(..., "r");
char linebuffer[1000+1];
for (char *line=fgets(linebuffer, 1000, input); line;
line=fgets(linebuffer, 1000, input) )
{
buffer=buffer+processor.chew_on(line); //(1)
}
fclose(input);
// Write
FILE *output=fopen(...,"w");
fwrite(buffer.data(), 1, buffer.size(), output);
fclose(output);
Проблема, которую на первый взгляд легко упустить, заключается в том, что при каждом запуске строки (1) копируется все содержимое buffer. Если имеется 1000 строк по 100 символов в каждой, вы тратите время на копирование 100 + 200 + 300 + 400 + .... + 100 000 = 5 050 000 байт-копий, чтобы выполнить это. Увеличить до 10000 строк? 500500000. Эта банка краски становится все дальше и дальше.
В этом конкретном примере исправить легко. Строка (1) должна гласить:
buffer.append(processor.chew_on(line)); // (2)
или эквивалентно: (спасибо Мэтью М.):
buffer += processor.chew_on(line);
Это помогает, потому что (обычно) std::string не нужно делать полную копию buffer для выполнения функции append, тогда как в (1) мы настаиваем на том, чтобы была сделана копия .
В целом, предположим, (а) процесс, который вы выполняете, сохраняет состояние, (б) вы часто ссылаетесь на все или большую его часть, и (в) это состояние растет со временем. Тогда есть большая вероятность того, что вы написали алгоритм времени Θ (n 2 ), который будет точно соответствовать типу поведения, о котором вы говорите.
Редактировать
Конечно, стандартный ответ на вопрос "почему мой код работает медленно?" это «запустить профиль.» Для этого есть ряд инструментов и методов. Некоторые опции включают в себя:
callgrind /
kcachegrind (в соответствии с предложением
David Schwartz )
Случайная пауза (в соответствии с предложением
Mike Dunlavey )
Профилировщик GNU,
gprof
Профилировщик покрытия теста GNU,
gcov
oprofile
У них всех есть свои сильные стороны. «Случайная пауза», вероятно, является самой простой для реализации, хотя может быть трудно интерпретировать результаты. «gprof» и «gcov» практически бесполезны в многопоточных программах. Callgrind тщательный, но медленный, и иногда может играть странные трюки в многопоточных программах. oprofile работает быстро, хорошо работает с многопоточными программами, но может быть сложным в использовании и может пропускать некоторые вещи.
Однако, если вы пытаетесь профилировать однопотоковую программу и разрабатываете с помощью цепочки инструментов GNU, gprof может быть отличным вариантом. Возьми мой proc.cpp, выше. В целях демонстрации я собираюсь профилировать неоптимизированный пробег. Сначала я перестраиваю свою программу для профилирования (добавляя -pg к этапам компиляции и компоновки):
$ g++ -O0 -g -pg -o proc.o -c proc.cpp
$ g++ -pg -o proc proc.o
Я запускаю программу один раз, чтобы создать информацию о профилировании:
./proc
В дополнение к тому, что он обычно делает, этот прогон создаст файл с именем 'gmon.out' в текущем каталоге. Теперь я запускаю gprof для интерпретации результата:
$ gprof ./proc
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
100.50 0.01 0.01 234937 0.00 0.00 std::basic_string<...> std::operator+<...>(...)
0.00 0.01 0.00 234937 0.00 0.00 Foo::chew_on(std::string const&)
0.00 0.01 0.00 1 0.00 10.05 do_processing(std::string const&, std::string const&)
...
Да, действительно, 100,5% времени моей программы тратится на std::string operator+. Ну, хорошо, до некоторой ошибки выборки. (Я запускаю это на виртуальной машине ... кажется, что время захвата gprof выключено. Моей программе потребовалось гораздо больше времени, чем 0,01 накопительных секунды ...)
Для моего очень простого примера gcov немного менее поучителен. Но вот что происходит, чтобы показать. Сначала скомпилируйте и запустите gcov:
$ g++ -O0 -fprofile-arcs -ftest-coverage -o proc proc.cpp
$ ./proc
$ gcov ./proc
...
Это создает группу файлов, оканчивающихся на .gcno, .gcda, .gcov в текущем каталоге. Файлы в .gcov говорят нам, сколько раз каждая строка кода была выполнена во время выполнения. Итак, в моем примере мой proc.cpp.gcov выглядит так:
-: 0:Source:proc.cpp
-: 0:Graph:proc.gcno
-: 0:Data:proc.gcda
-: 0:Runs:1
-: 0:Programs:1
-: 1:#include
-: 2:#include
-: 4:class Foo
-: 5:{
-: 6: public:
234937: 7: std::string chew_on(std::string const& line_to_chew_on) {return line_to_chew_on;}
-: 8:};
-: 9:
-: 10:
-: 11:
1: 12:int do_processing(std::string const& infile, std::string const& outfile)
-: 13:{
-: 14: Foo processor;
2: 15: std::string buffer;
-: 16:
-: 17: // Read/process
1: 18: FILE *input=fopen(infile.c_str(), "r");
-: 19: char linebuffer[1000+1];
234938: 20: for (char *line=fgets(linebuffer, 1000, input); line;
-: 21: line=fgets(linebuffer, 1000, input) )
-: 22: {
234937: 23: buffer=buffer+processor.chew_on(line); //(1)
-: 24: }
1: 25: fclose(input);
-: 26:
-: 27: // Write
1: 28: FILE *output=fopen(outfile.c_str(),"w");
1: 29: fwrite(buffer.data(), 1, buffer.size(), output);
1: 30: fclose(output);
1: 31:}
-: 32:
1: 33:int main()
-: 34:{
1: 35: do_processing("/usr/share/dict/words","outfile");
-: 36:}
Итак, из этого я должен сделать вывод, что std :: string :: operator + в строке 23 (которая выполняется 234 937 раз) является потенциальной причиной медлительности моей программы.
КакКроме того, callgrind / kcachegrind работает с многопоточными программами и может предоставить гораздо больше информации.Для этой программы я запускаю:
g++ -O0 -o proc proc.cpp
valgrind --tool=callgrind ./proc # this takes forever to run
kcachegrind callgrind.out.*
И нахожу следующий вывод, показывающий, что мои циклы действительно поглощают много-много копий памяти (99,4% времени выполнения, потраченного на __memcpy_ssse3_back),что я вижу, все происходит где-то ниже строки 23 в моем источнике: 