运行实验的好方法是C 中算法的内存使用情况

Question

我具有在C 中实现的算法A和算法B。从理论上讲，A使用的空间比B更多，事实证明，在实践中也是如此。我想生成一些不错的图表来说明这一点。两种算法都会收到一个输入n，我希望我的实验对于不同的n有所不同，因此该图的X轴必须像n = 10^6, 2*10^6, ...

之类的东西。

通常，当涉及到时间或缓存失误之类的数据时，我最喜欢设置实验的方法如下。在C 文件中，我有这样实现的算法：

#include <iostream>
using namespace std;
int counters[1000];
void init_statistics(){
   //use some library for example papi (http://icl.cs.utk.edu/papi/software/)
  //to start counting, store the results in the counters array
}
void stop_statistics(){
   //this is just to stop counting
}
int algA(int n){
//algorithm code
int result = ...
return result;
}
void main(int argc, const char * argv[]){
   int n = atoi(argv[1]);
   init_statistics(); //function that initializes the statistic counters
   int res = algA(n);
   end_statistics(); //function that ends the statistics counters
   cout<<res<<counter[0]<<counter[1]<<....<<endl;
}

然后，我将创建一个用于不同n调用result = subprocess.check_output(['./algB',...])的Python脚本。之后，在Python中解析结果字符串，并以合适的格式打印。例如，如果我将R用于图，我可以将数据打印到外部文件，每个计数器都由t分开。

这对我来说很好，但是现在是我第一次需要有关算法使用的空间的数据，我不确定如何计算这个空间。一种方法是使用Valgrind，这是Valgrind的可能输出：

==15447== Memcheck, a memory error detector
==15447== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==15447== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==15447== Command: ./algB 1.txt 2.txt
==15447== 
==15447== 
==15447== HEAP SUMMARY:
==15447==     in use at exit: 72,704 bytes in 1 blocks
==15447==   total heap usage: 39 allocs, 38 frees, 471,174,306 bytes allocated
==15447== 
==15447== LEAK SUMMARY:
==15447==    definitely lost: 0 bytes in 0 blocks
==15447==    indirectly lost: 0 bytes in 0 blocks
==15447==      possibly lost: 0 bytes in 0 blocks
==15447==    still reachable: 72,704 bytes in 1 blocks
==15447==         suppressed: 0 bytes in 0 blocks
==15447== Rerun with --leak-check=full to see details of leaked memory
==15447== 
==15447== For counts of detected and suppressed errors, rerun with: -v
==15447== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

有趣的数字是471,174,306 bytes。但是，Valgrind会大大减慢执行时间，同时不仅返回此数字，而且还返回此大字符串。而且我不确定如何解析它，因为出于某种原因，如果使用Python，我称result = subprocess.check_output(['valgrind','./algB',...])，result字符串仅将输出存储在./algB中，并且完全忽略了Valgrind的返回。

谢谢Advace！

Answer 1

memcheck是查找内存泄漏的工具，您应该使用massif(Valgrind中的另一个工具(进行内存分配分析。