Коротко: системный подход + набор инструментов. Ниже — последовательность действий и конкретные приёмы/команды, которые помогут локализовать причину недетерминизма в «решателе».
1) Подтвердите и охарактеризуйте недетерминизм
- Запустите программу много раз и соберите контрольные суммы выходного файла:
- for i in {1..100}; do ./solver in.bin; cp in.bin out$i.bin; sha256sum out$i.bin >> sums.txt; done
- Посмотрите, сколько уникальных сумм — если >1, поведение недетерминично.
- Выделите две разные версии результата (outA, outB) и сделайте бинарный дифф:
- cmp -l outA outB (покажет смещённые байты и значения)
- hexdump -C outA > a.txt; hexdump -C outB > b.txt; diff -u a.txt b.txt
- diffoscope outA outB (если установлен — удобно для сложных форматов)
2) Попытайтесь локализовать, какие поля/блоки файла меняются
- Если формат известен, напишите скрипт/утилиту, чтобы распарсить файл и вывести значимые поля (флоаты, векторы, записи). Сравните поля между двумя запусками — это сразу сузит место ошибки.
- Если формат неясен, используйте hexdump и посмотрите, какие диапазоны изменяются (в начале/в середине/в конце файла).
3) Устраните «внешние» источники недетерминизма (простые фиксы)
- Отключите ASLR: sudo sysctl -w kernel.randomize_va_space=0
- Зафиксируйте CPU и NUMA: taskset -c 0 ./solver in.bin
- Ограничьте число потоков (если используются OpenMP/TBB/потоки):
- export OMP_NUM_THREADS=1; export OMP_PROC_BIND=close
- Для Intel TBB / MKL см. KMP_AFFINITY, MKL_NUM_THREADS
- Зафиксируйте локаль/переменные окружения:
- export LANG=C; unset LC_ALL
- Отключите динамические источники энтропии (getrandom) — см. ниже про перехват.
Если после этих мер поведение стало детерминированным — причина скорее в планировщике/параллельности/сопроцессах.
4) Проверка конкурентного доступа (data races)
- Если программа многопоточная, самая частая причина недетерминизма — гонки данных.
- Компиляция с ThreadSanitizer:
- g++ -fsanitize=thread -g -O1 ... и запуск — TSan выявит гонки.
- Запуск под Valgrind Helgrind/DRD:
- valgrind --tool=helgrind ./solver in.bin
- Если у вас нет исходников — попробуйте динамический анализ с Helgrind на собранном бинарнике (работает, но медленнее).
5) Проверка неинициализированной памяти и UB
- Неинициализированные поля структур, которые пишутся в файл, часто дают «рандомные» байты.
- Memcheck (Valgrind) для выявления чтения неинициализированной памяти:
- valgrind --tool=memcheck --track-origins=yes ./solver in.bin
- Если можете пересобрать — используйте Sanitizers:
- -fsanitize=address,undefined -g -O1
- Для неинициализированных значений: MemorySanitizer (clang): -fsanitize=memory (требует clang и специфич. сборки).
- Подсказка: если отличия в файле — «мусор» в padding полях struct, это 99% неинициализированные данные. Догма: всегда обнулять буферы перед записью (memset).
6) ФПО и численный недетерминизм
- Ассоциативность операций с плавающей точкой + многопоточность дают разные суммирования и небольшие числовые расхождения, которые могут накапливаться.
- Проверить:
- Запустить с одним потоком (OMP_NUM_THREADS=1) — если исчезает, проблема в суммировании/распараллеливании.
- Отключить быстрые оптимизации компилятора: -fno-fast-math; при сборке включить -ffloat-store или использовать более строгие флаги.
- Зафиксировать режим округления и исключения: feclearexcept/fesetround при необходимости.
- Для детальной проверки — сравнивать численные поля с плавающей точкой и их относительные отклонения.
7) Источники случайности (PRNG, getrandom, time)
- Проверьте, используются ли rand()/srand(), random(), std::mt19937 с нефиксированным seed, getrandom(), /dev/urandom, время (time(), gettimeofday()).
- Если исходники отсутствуют, попробуйте перехватить вызовы раннего уровня:
- strace -e trace=desc,process,network,clock_gettime,stat ./solver in.bin (посмотреть обращения к /dev/urandom, time и т.д.)
- Можно LD_PRELOAD написать маленькую библиотеку, которая переопределяет getrandom/srand/time и возвращает фиксированные значения.
- Если причиной является нефиксированный seed — проще всего обеспечить фиксированный seed.
8) Сравнение поведения при разных оптимизациях/компиляторах
- Если у вас исходники, перекомпилируйте с -O0 -g и с разными флагами (-O2, -O3, -march), посмотрите, меняется ли поведение. Если при -O0 поведение детерминированно, вероятна проблема UB (компилятор оптимизирует, проявляется UB).
- Включите -fsanitize=undefined, это часто выявляет UB (например, сдвиг больше размера, деление на 0, signed overflow).
9) Логирование и «бисекция» по этапам вычислений
- Если файл записи структурирован и вы можете модифицировать код (или собрать fork), добавьте логирование контрольных сумм промежуточных результатов (часть данных до/после ключевых этапов). Это позволяет найти, на каком шаге появляются различия.
- Если исходников нет, попробуйте запускать программу над различными подмножествами входных данных (сделать input crop) чтобы локализовать место проблемы.
10) Инструменты для глубокого анализа
- strace/ltrace — увидите системные вызовы (случайные устройства, время, mmap).
- perf record/annotate — для поиска «шумных» участков (информативно, но не обязательно для ошибок).
- DynamoRIO / PIN — можно записывать все обращения к памяти; это продвинутый путь (лог огромный), но позволяет детектировать, где память влияет на выход.
11) Если проблема в структуре, пишущей в файл
- Частая ошибка: напрямую fwrite(&struct, sizeof struct, 1, f) — и в struct есть padding/неинициализированные поля. Решения:
- Перед записью memset(&s, 0, sizeof s); затем заполнить поля.
- Явно записывать поля по отдельности/в порядке и с контролем endian.
- Использовать сериализацию, которая не включает padding.
12) Если у вас нет исходников (только бинарник)
- Сначала попробуйте внешние меры (ASLR, taskset, фиксировать окружение, перехват getrandom, запускаать однопоточно).
- Используйте strace + cmp/hexdump, чтобы понять источник отличий.
- Если требуется — отладка через gdb: запуск нескольких снэпшотов, сравнение регистров/памяти на ключевых точках (трудоёмко).
- Можно попробовать динамический инструмент вроде Valgrind (работает с бинарниками) или Helgrind.
Краткий план действий (приоритет):
1. Сформируйте статистику — сколько разных выходов и где отличаются (hexdump/cmp).
2. Попробуйте простые внешние фиксы: ASLR off, taskset, OMP_NUM_THREADS=1, LANG=C.
3. Запустите под valgrind memcheck и helgrind (если возможно).
4. Если есть исходники — перекомпилируйте с Sanitizers и с разными оптимизациями.
5. Запишите промежуточные контрольные суммы или добавьте логирование, чтобы локализовать этап, где данные расходятся.
6. Если поля файла выглядят как «мусор» — проверьте неинициализированные поля/padding.
Если хотите, могу помочь практическим образом:
- Подсказать точные команды вашей ОС или показать пример LD_PRELOAD-«фиксатора» для getrandom/srand.
- Проанализировать два бинарных файла — пришлите вырезы hexdump или diff, и я помогу интерпретировать, что именно меняется.