c++ - 内存/速度问题的一般策略

Question

我有一个 c++ 代码，它运行大约 200 个 ASCII 文件，进行一些基本的数据处理，并输出一个包含(基本上)所有数据的单个 ASCII 文件。

该程序一开始运行得非常快，然后在中途急剧减慢，也许逐渐减慢一点，然后在其余部分以相当慢的速度进行。 IE。它在大约 5 秒内完成前 ~80 个文件，在大约 50 秒内完成~200 个文件。每个文件基本相同。

我正在寻找有关如何追踪问题或内存泄漏的建议。

---

更多细节:起初我会在我的程序开始时使用 fopen(FILE *outputFile, "w") ，在结束时使用 fclose() 。前 40 个文件大约需要 4 秒；然后约 1.5 分钟即可处理约 200 个文件。

我认为输出文件可能会阻塞内存，所以我将代码更改为 fopen(outputFile, "a") 每次迭代(即每次我打开一个新文件时)，以及每次关闭输入时的 fclose()文件...如上所述，这将性能提高到大约 50 秒。

这个“修复”会如此显着但并非完全有效，这似乎很奇怪。

此外，我没有动态分配任何内存(没有调用“新建”或“删除”或“免费”或其他)......所以我什至不确定我怎么能 内存泄漏。

任何帮助将不胜感激!谢谢!

---

代码:

vector<string> dirCon;
// Uses boost::filesystem to store every file in directory
bool retVal = FileSystem::getDirectoryContents(HOME_DIR+HISTORY_DIR, &dirCon, 2);

int counter = 0;
for(int i = 0; i < dirCon.size(); i++) { 
    // Create output file
    FILE *outFile;
    string outputFileName = HOME_DIR ... ;
    // open file as append "a"
    bool ifRet = initFile(outFile, outputFileName.c_str(), "a");
    if(!ifRet) {
        fprintf(stderr, "ERROR ... ");
        return false;
    }       

    // Get the topmost directory name
    size_t loc = dirCon.at(i).find_last_of("/");
    string dirName = dirCon.at(i).substr(loc+1, (dirCon.at(i).size()-(loc+1)));

    // Get the top directory content
    vector<string> subDirCon;
    bool subRetVal = FileSystem::getDirectoryContents(dirCon.at(i), &subDirCon);
    if(!subRetVal) { fprintf(stderr, "ERROR\n"); return false; }

    // Go through each file in directory, look for the one that matches
    for(int j = 0; j < subDirCon.size(); j++) {

        // Get filename
        loc = subDirCon.at(j).find_last_of("/");
        string fileName = subDirCon.at(j).substr(loc+1, (subDirCon.at(j).size()-(loc+1)));

        // If filename matches desired station, process and store
        if( fileName == string(dirName ...) ) {
            // Open File
            FILE *inFile;
            if(!initFile(inFile, subDirCon.at(j).c_str(), "r")) { 
                fprintf(stderr, "ERROR: ... !\n");
                break;
            }

            // Parse file line-by-line
            char str[TB_CHARLIMIT_LARGE];
            const char *delim = ",";
            while(true) {
                vector<string> splitString;
                fgets(str, TB_CHARLIMIT_LARGE, inFile);

                if(feof(inFile)) { break; }     // break at end of file
                removeEndLine(str);

                // If non-comment line, parse
                if(str[0] != COMCHAR){
                    string strString(str);
                    // remove end line char
                    strString.erase(std::remove(strString.begin(), strString.end(), '\n'), strString.end());
                    strcpy(str, strString.c_str());

                    char *temp = strtok(str,delim);
                    char *lastTemp;
                    while(temp != NULL) {
                        splitString.push_back(string(temp));
                        temp = strtok(NULL,delim);
                    }
                    if(splitString.size() > 0) { 
                        DateTime dtTemp(splitString.at(0));  
                        goodLines++;

                        /*  ... process splitString, use dtTemp ... */

                        // Output to file
                        fprintf(outFile, "%s\n", strFromStrVec(splitString).c_str());
                    }
                }
            } //while
            fclose(inFile); 
        }
    } //j
    cout << "GoodLines = " << goodLines << endl;

    fclose(outFile);
} // i

bool getDirectoryContents(const string dirName, vector<string> *conts) {
    path p(dirName);
    try {
        // Confirm Exists
        if(!exists(p)) {
            fprintf(stderr, "ERROR: '%s' does not exist!\n", dirName.c_str());
            return false;
        }

        // Confirm Directory
        if(!is_directory(p)) {
            return false;
        }

        conts->clear();

        // Store paths to sort later
        typedef vector<path> vec;
        vec v;

        copy(directory_iterator(p), directory_iterator(), back_inserter(v));

        sort(v.begin(), v.end()); 

        for(vec::const_iterator it(v.begin()), it_end(v.end()); it != it_end; ++it) {
            conts->push_back(it->string());
        }


    } catch(const filesystem_error& ex) {
        fprintf(stderr, "ERROR: '%s'!\n", ex.what());
        return false;
    }   

    return true;
}

Answer 1

如果没有更多信息，我猜你正在处理的是 Schlemiel the Painter 的算法:(Original) (Wikipedia) .他们非常容易陷入字符串处理。让我举个例子。

我想读取文件中的每一行，以某种方式处理每一行，然后通过一些中间处理运行它。然后我想收集结果，并可能将其写回磁盘。这是一种方法。我犯了一个很容易被忽略的大错误:

// 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 字节拷贝来运行它。增加到 10,000 行？ 500,500,000。那个油漆 jar 离我们越来越远了。

在此特定示例中，修复很简单。 (1) 行应为:

    buffer.append(processor.chew_on(line)); // (2)

或等效地:(感谢 Matthieu M.):

    buffer += processor.chew_on(line);

这会有所帮助，因为(通常)std::string 不需要制作 buffer 的完整拷贝来执行 append 函数，而在 (1) 中，我们坚持要进行复制。

更一般地说，假设 (a) 您正在进行的处理保持状态，(b) 您经常引用所有或大部分状态，以及 (c) 该状态随时间增长。那么很有可能您已经编写了 Θ(n²) 时间算法，该算法将完全表现出您正在谈论的行为类型。

---

编辑

当然，“为什么我的代码很慢？”的常见答案是“运行配置文件”。有许多工具和技术可用于执行此操作。一些选项包括:

callgrind/kcachegrind (如 David Schwartz 所建议)

Random Pausing (如 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 ./procFlat 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&)...

Yes indeed, 100.5% of my program's time is spent in std::string operator+. Well, ok, up to some sampling error. (I'm running this in a VM ... it seems that the timing being captured by gprof is off. My program took much longer than 0.01 cumulative seconds to run...)

For my very simple example, gcov is a little less instructive. But here's what it happens to show. First, compile and run for 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:}

So from this, I'm going to have to conclude that the std::string::operator+ at line 23 (which is executed 234,937 times) is a potential cause of my program's slowness.

As an aside, callgrind/kcachegrind work with multithreaded programs, and can provide much, much more information. For this program I run:

g++ -O0 -o proc proc.cpp
valgrind --tool=callgrind ./proc  # this takes forever to run
kcachegrind callgrind.out.*

我发现以下输出，表明真正耗尽我的周期的是大量内存拷贝(99.4% 的执行时间花在 __memcpy_ssse3_back 上)，我可以看到这一切都发生在某处在我的来源第 23 行下方: