C: избежать переполнения при работе с большими числами

Question

Я реализовал несколько алгоритмов сортировки (для сортировки целых чисел) в C, осторожно используя uint64_t для хранения всего, что имеет отношение к размеру данных (таким образом, также счетчики и прочее), поскольку алгоритмы также должны быть проверены с наборами данных из нескольких гига целых чисел.

Алгоритмы должны быть хорошими, и не должно быть никаких проблем с количеством выделенных данных: данные хранятся в файлах, и мы загружаем только небольшие порции за раз, все работает нормально, даже когда мы забиваем буферы в памяти для любой размер.

Тесты с наборами данных до 4 Гигабайт (таким образом, 16 ГБ данных) работают нормально (сортировка 4Gint заняла 2228 секунд, ~ 37 минут), но когда мы превышаем это значение (то есть: 8 Gints), алгоритм кажется не остановка (она работает уже около 16 часов).

Боюсь, что проблема может быть связана с переполнением целых чисел, возможно, счетчик в цикле хранится в 32-битной переменной, или, может быть, мы вызываем некоторые функции, которые работают с 32-битными целыми числами.
Что еще это может быть?

Есть ли простой способ проверить, не происходит ли целочисленное переполнение во время выполнения?

Answer 1

Это зависит от компилятора, но если вы используете 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

Answer 2

Взгляните на -ftrapv и -fwrapv:

-ftrapv

Эта опция генерирует ловушки для переполнения со знаком при сложении, вычитании,операции умножения.

-fwrapv

Эта опция указывает компилятору предположить, что знаковое арифметическое переполнение сложения, вычитания и умножения оборачивается с использованием представления с двойным дополнением.Этот флаг включает некоторые оптимизации и отключает другие.Эта опция включена по умолчанию для внешнего интерфейса Java, как того требует спецификация языка Java.

См. Также Целочисленное переполнение в C: стандарты и компиляторы и Полезные флаги GCC для C .

Answer 3

clang теперь поддерживает динамические проверки переполнения для целых чисел со знаком и без знака. См. Ключ -fsanitize = integer . Пока это только один компилятор C ++ с полностью поддерживаемой динамической проверкой переполнения для целей отладки.

Answer 4

Если вы используете компилятор Microsoft, есть опции для генерации кода, который вызывает исключение SEH, когда целочисленное преобразование обрезает ненулевые биты. В местах, где это действительно необходимо, используйте битовое И для удаления старших бит перед выполнением преобразования.

Answer 5

Единственный надежный способ - это обернуть операции над этими целыми числами в функции, выполняющие проверку нарушения границ.Это, конечно, замедлит целочисленные операции, но если ваш код утверждает или останавливает нарушение границы с значимым сообщением об ошибке, это в значительной степени поможет вам определить, где проблема.

Что касается вашегоОсобая проблема, имейте в виду, что сортировка по общему случаю - это O (nlogn), поэтому причина, по которой алгоритм занимает намного больше времени, может быть связана с тем, что увеличение времени не является линейным по отношению к размеру набора данных.Поскольку также не упоминалось, сколько физической памяти находится в блоке и как много ее используется для вашего алгоритма, возможно, на странице возникла ошибка на диске с большим набором данных, что потенциально может замедлить процесс сканирования.