I've implemented some sorting algorithms (to sort integers) in C, carefully using uint64_t
to store anything which has got to do with the data size (thus also counters and stuff), since the algorithms should be tested also with data sets of several giga of integers.
The algorithms should be fine, and there should be no problems about the amount of data allocated: data is stored on files, and we only load little chunks per time, everything works fine even when we choke the in-memory buffers to any size.
Tests with datasets up to 4 giga ints (thus 16GB of data) work fine (sorting 4Gint took 2228 seconds, ~37 minutes), but when we go above that (ie: 8 Gints) the algorithm doesn't seem to halt (it's been running for about 16 hours now).
I'm afraid the problem could be due to integer overflow, maybe a counter in a loop is stored on a 32 bits variable, or maybe we're calling some functions that works with 32 bits integers.
What else could it be?
Is there any easy way to check whether an integer overflow occurs at runtime?
look into bignum arithmetic libraries. they'll be a bit slower than standard C arithmetic but at least you won't get overflow. also many standard math functions (exp etc) will set errno to ERANGE in case of overflow. Usually, it is prevented by thinking carefully when writing code.
In C programming language, a computation of unsigned integer values can never overflow, this means that UINT_MAX + 1 yields zero. More precise, according to the C standard unsigned integer operations do wrap around, the C Standard, 6.2.
This is compiler-specific, but if you're using gcc then you can compile with -ftrapv
to issue SIGABRT
when signed integral overflow occurs.
For example:
/* 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;
}
When I run this code locally, the output is
Overflow detected
Aborted
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With