C:在处理大数字时避免溢出

我已经在C中实现了一些sortingalgorithm(对整数进行sorting),仔细地使用uint64_t来存储与数据大小有关的任何东西(因此还有计数器和东西),因为algorithm也应该用几个数据集千兆整数。

algorithm应该没问题,分配的数据量应该没有问题:数据存储在文件中,而且每次只加载很less的块,即使我们将内存中的缓冲区缩小到任意大小,一切都可以正常工作。

testing数据集高达4千兆(因此16GB的数据)工作正常(sorting4Gint花了2228秒,〜37分钟),但是当我们高于那个(即:8 Gints)algorithm似乎并没有停止现在已经运行了大约16个小时)。

恐怕问题可能是由于整数溢出,也许一个循环中的计数器存储在一个32位的variables,或者我们可能调用一些函数,使用32位整数。
还有什么呢?

有没有简单的方法来检查运行时是否发生整数溢出?

这是编译器特定的,但是如果你使用的是gcc,那么你可以使用-ftrapv进行编译来在有符号整数溢出发生时发布SIGABRT

例如:

 /* compile with gcc -ftrapv <filename> */ #include <signal.h> #include <stdio.h> #include <limits.h> void signalHandler(int sig) { printf("Overflow detected\n"); } int main() { signal(SIGABRT, &signalHandler); int largeInt = INT_MAX; int normalInt = 42; int overflowInt = largeInt + normalInt; /* should cause overflow */ /* if compiling with -ftrapv, we shouldn't get here */ return 0; } 

当我在本地运行这个代码时,输​​出是

 Overflow detected Aborted 

看看-ftrapv-fwrapv

-ftrapv

这个选项在加法,减法,乘法运算中产生有符号溢出的陷阱。

-fwrapv

该选项指示编译器假设使用二进制补码表示法的加法,减法和乘法的有符号算术溢出循环。 该标志启用一些优化并禁用其他。 按照Java语言规范的要求,Java前端默认启用此选项。

C:标准和编译器中的整数溢出 ,以及C中有用的GCC标志 。

如果您使用的是Microsoft的编译器,那么有一些选项可用于在整数转换切断非零位时生成触发SEH异常的代码。 在实际需要的地方,在转换之前使用按位“与”来删除高位。

现在支持动态溢出检查有符号和无符号整数。 请参阅-fsanitize =整数切换。 目前,只有一个C ++编译器具有完全支持的用于调试目的的动态溢出检查。

唯一可靠的方法是将这些整数的操作封装到执行边界违例检查的函数中。 这当然会减慢整数运算的速度,但是如果你的代码断言或停止了一个有意义的错误信息的边界违规,那么这对于帮助你确定问题的位置将会有很大的帮助。

至于你的特定问题,请记住一般情况下的排序是O(nlogn),所以算法花费的时间更长的原因可能是由于时间的增加对于数据集的大小不是线性的。 因为也没有提到盒子里有多少物理内存,有多少物理内存用于你的算法,所以可能会出现页面错误,导致数据集较大,从而有可能减慢抓取的速度。