logo标签列表

为什么我的程序运行缓慢？我如何提高其效率？

c++performance
6
我有一个程序可以执行块嵌套循环连接（链接文本）。基本上，它会从文件中读取内容（比如10GB的文件），将其放入缓冲区1（例如400MB），并将其放入哈希表中。现在读取第二个文件（比如10GB的文件）的内容到缓冲区2（例如100MB），并查看缓冲区2中的元素是否存在于哈希表中。输出结果并不重要。我只关心程序的效率。在这个程序中，我需要从两个文件中每次读取8个字节，因此我使用long long int。问题是我的程序非常低效。如何使它高效？
// 我使用g++ -o hash hash.c -std=c++0x进行编译
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdint.h>
#include <math.h>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

typedef std::unordered_map<unsigned long long int, unsigned long long int> Mymap; 
int main()
{

uint64_t block_size1 = (400*1024*1024)/sizeof(long long int);  //block size of Table A - division operator used to make the block size 1 mb - refer line 26,27 malloc statements.
uint64_t block_size2 = (100*1024*1024)/sizeof(long long int);   //block size of table B

int i=0,j=0, k=0;
uint64_t x,z,l=0;
unsigned long long int *buffer1 = (unsigned long long int *)malloc(block_size1 * sizeof(long long int));
unsigned long long int *buffer2 = (unsigned long long int *)malloc(block_size2 * sizeof(long long int));

Mymap c1 ;                                                          // Hash table
//Mymap::iterator it;

FILE *file1 = fopen64("10G1.bin","rb");  // Input is a binary file of 10 GB
FILE *file2 = fopen64("10G2.bin","rb");

printf("size of buffer1 : %llu \n", block_size1 * sizeof(long long int));
printf("size of buffer2 : %llu \n", block_size2 * sizeof(long long int));


while(!feof(file1))
        {
        k++;
        printf("Iterations completed : %d \n",k);
        fread(buffer1, sizeof(long long int), block_size1, file1);                          // Reading the contents into the memory block from first file

        for ( x=0;x< block_size1;x++)
            c1.insert(Mymap::value_type(buffer1[x], x));                                    // inserting values into the hash table

//      std::cout << "The size of the hash table is" << c1.size() * sizeof(Mymap::value_type) << "\n" << endl;

/*      // display contents of the hash table 
            for (Mymap::const_iterator it = c1.begin();it != c1.end(); ++it) 
            std::cout << " [" << it->first << ", " << it->second << "]"; 
            std::cout << std::endl; 
*/

                while(!feof(file2))
                {   
                    i++;                                                                    // Counting the number of iterations    
//                  printf("%d\n",i);

                    fread(buffer2, sizeof(long long int), block_size2, file2);              // Reading the contents into the memory block from second file

                    for ( z=0;z< block_size2;z++)
                        c1.find(buffer2[z]);                                                // finding the element in hash table

//                      if((c1.find(buffer2[z]) != c1.end()) == true)                       //To check the correctness of the code
//                          l++;
//                  printf("The number of elements equal are : %llu\n",l);                  // If input files have exactly same contents "l" should print out the block_size2
//                  l=0;                    
                }
                rewind(file2);
                c1.clear();                                         //clear the contents of the hash table
    }

    free(buffer1);
    free(buffer2);  
    fclose(file1);
    fclose(file2);
}

更新：

是否可能使用C++流读取器直接从文件中读取一个块（例如400 MB）并将其直接放入哈希表中？我认为这可以进一步减少开销。

3
当你将这标记为C和C++时，你并没有开玩笑。 - Kevin
@Hans：我只是担心我的编程风格不够好，我同时使用HDD和SSD。 - 0x0
@Andi：它运行大约一个小时。 - 0x0
哦，我没看到你多次读取了第二个文件。你程序的瓶颈肯定是硬盘，所以你应该考虑一个更好的算法。 - AndiDog
你的 while(!feof(..)) 循环不正确，feof 只有在读取函数在文件末尾失败后才会设置描述符。 - wilx
显示剩余8条评论
6个回答
3
如果您正在使用fread，那么请尝试使用setvbuf()。标准库文件I/O调用使用的默认缓冲区非常小（通常为4kB数量级）。当快速处理大量数据时，您将会受到I/O限制，并且获取许多小缓冲区的开销可能会成为一个显著的瓶颈。将其设置为较大的大小（例如64kB或256kB），您可以降低开销并可能看到显着的改进-尝试几个值以查看您可以获得最好的收益，因为您会获得递减的回报。
看起来很有趣。我会尝试并回复结果。 - 0x0
2
您的程序运行时间为(l1 x bs1 x l2 x bs2)，其中l1是第一个文件中的行数，bs1是第一个缓冲区的块大小，l2是第二个文件中的行数，bs2是第二个缓冲区的块大小，因为您有四个嵌套循环。由于您的块大小是恒定的，您可以说您的顺序是O(n x 400 x m x 400)或O(1600mn)，或在最坏情况下为O(1600n2)，这实际上最终变成了O(n2)。
如果您采取以下类似的做法，您可以拥有O(n)算法（伪代码如下）：
map = new Map();
duplicate = new List();
unique = new List();

for each line in file1
   map.put(line, true)
end for

for each line in file2
   if(map.get(line))
       duplicate.add(line)
   else
       unique.add(line)
   fi
end for

现在，duplicate将包含重复项列表，unique将包含唯一项列表。
在您原来的算法中，您不必为第一个文件中的每一行遍历第二个文件。因此，实际上您失去了哈希的好处（它给您提供了O(1)的查找时间）。当然，在这种情况下的权衡是，您必须将整个10GB存储在内存中，这可能并没有什么帮助。通常，在这些情况下，权衡是在运行时间和内存之间进行的。
可能有更好的方法来做到这一点。我需要再考虑一下。如果没有，我相信有人会想出更好的主意 :)
更新
如果您可以找到一种很好的方法来对从第一个文件中读取的行进行哈希，以便获得唯一值（即，行和哈希值之间的1对1映射），那么您可以减少内存使用率。基本上，您会这样做：
for each line in file1
   map.put(hash(line), true)
end for

for each line in file2
   if(map.get(hash(line)))
       duplicate.add(line)
   else
       unique.add(line)
   fi
end for

这里的哈希函数是执行哈希的函数。这样，您就不必将所有行存储在内存中，只需存储它们的哈希值即可。这可能会对您有所帮助。即使如此，在最坏的情况下（比较两个相同或完全不同的文件），您仍然可能会在重复或唯一列表中占用10GB的内存。如果您只存储唯一或重复项的计数而不是它们本身，则可以通过损失一些信息来解决这个问题。
@Sunil 是的，没错（除非你存储了哈希值，这样可以减少内存成本）。正如我所提到的，这通常是一种权衡。速度与内存之间的权衡。在你的解决方案中，你牺牲了速度来使用很少的内存。在我的（原始）解决方案中，我的运行时间很短，但内存使用率更高。对于大型数据集，嵌套循环通常具有非常高的运行时间。 - Vivin Paliath
1

long long int *ptr = mmap() 你的文件，然后将它们分块使用memcmp()进行比较。一旦发现差异，就向后退回一个块并进行更详细的比较。（在这种情况下，更详细的意思是比较long long int。）

如果你预计经常会发现差异，那么不要费心使用memcmp()，只需编写自己的循环来比较long long ints。

0

了解它的唯一方法是通过gprof进行分析。创建您当前实现的基准，然后系统地尝试其他修改并重新运行基准测试。

0

我敢打赌，如果你一次读取更大的块，你会获得更好的性能。使用fread()函数并且每次处理多个块。

当然，但我只想使用8个字节。如果我使用ifstream()而不是fread()，会不会更快呢？我试图表达的主要观点是我的读取函数和映射函数非常慢，我希望能得到改进建议。谢谢。 - 0x0
如果您调用fread的次数较少，则可以消除每次调用时设置和拆卸的开销。由于您要这样做很多次，因此它将产生重大影响。 10 gb / 8 bytes = 可以消除1.25亿次调用的开销。 - Jay
0
我看到的问题是你多次读取第二个文件，速度非常慢。
让这个过程更快的最佳方法是预先对文件进行排序，然后执行Sort-merge join。在我的经验中，排序几乎总是值得的。
我知道，但这就是块嵌套循环连接算法的全部意义所在。 - 0x0
我想说的是，除非你别无选择，否则不要使用块嵌套循环连接。嵌套循环连接是一种最后的算法类型。我不了解你的数据，但通常有一种方法可以对数据进行排序，以便您可以使用更合理的连接算法。 - Jeff Walker
我明白你在说什么。问题不是找到另一个高效的算法，而是使用块嵌套循环连接并编写这个程序，以便它有效地工作。 - 0x0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接