Member Avatar for Nemes

Hello,

I am running a lightly random-based heuristic search with a problem, and I encounter something quite peculiar.

When I run the program using no compiler optimization, I obtain results that are consistently worse than when I use compiler optimization (-O3 parameter using gcc). What I mean by "results" is the actual solution (the goal being to find the solution with the lowest possible cost). I am not concerned with memory used and CPU time spent, which should be the only two things optimization should affect.

I am running both versions of the search on the same OS, same machine, same eveything, except for the optimization parameter. I have run both versions of the search several times, and the results are always consistently better for the optimized version.

I am wondering if it makes sense that optimizating with a compiler change the outcome of the solutions. I was under the impression that the results of a program should be identical. Is it possible optimization affects the random number generator?

Thank you for your help,
Marc

  • 4 Contributors
  • 3 Replies
  • 136 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by Salem

Dani AI

Generated

Different outputs between -O0 and -O3 almost always means the program depends on behavior the compiler is allowed to change. For a randomized heuristic like describes, the usual culprits are undefined or unspecified behavior, subtle floating‑point differences, or non‑determinism (PRNG usage or races). This echoes the instincts of , and but focuses on concrete checks that find the problem quickly.

Try these targeted diagnostics and fixes:

  • Make the run deterministic first: seed the PRNG explicitly (for example, srand(12345)) and dump the first N random values from both builds to see whether the RNG stream differs.
  • Build with strong diagnostics: enable warnings and run with sanitizers (for example -Wall -Wextra -fsanitize=undefined,address,thread) or valgrind to catch uninitialized reads, buffer overruns and undefined behavior.
  • Test aliasing/optimization assumptions: recompile with -fno-strict-aliasing and with -fno-fast-math to see if results change; those options often expose strict‑aliasing or FP-reordering bugs.
  • Check for concurrency/race conditions: if the search is multi‑threaded or uses a shared RNG, run ThreadSanitizer or serialize RNG access.
  • Pin down floating-point causes: different register spills or SSE vs x87 behavior can alter rounding; try forcing a consistent FP model (e.g. disable fast-math or use -mfpmath=sse -msse2) to see if the outcome stabilizes.
  • Instrument and bisect: add lightweight logging to record the algorithm state at key steps, then compare optimized vs unoptimized logs to find the exact point of divergence. Compiling selective files or functions without optimization (or using compiler pragmas) helps isolate the faulty section.

A common pattern is an uninitialized local or an expression that relies on unspecified evaluation order; optimization just changes the garbage values or reorders operations so one build happens to produce better search paths. Applying the diagnostics above will usually reveal the exact source so correctness can be fixed while keeping the performance benefit of optimization.

Recommended Answers

All 3 Replies

Member Avatar for Narue

>I am wondering if it makes sense that optimizating
>with a compiler change the outcome of the solutions.
Well, it doesn't make sense, but I can see it happening if your code makes some kind of weird assumption about itself that ends up being optimized into something different. I can't think of a good example that might happen though. Optimizers shouldn't normally affect the output of a program.

Member Avatar for Duoas

They shouldn't, but sometimes they do. This is because a great deal of optimization is based on heuristic rules, which you can break in quite a number of different ways.

According to Microsoft, you should always get your program working and thoroughly tested before enabling optimizations, and then test it yet again. If you do find discrepancies, you can compile using an "optimized debug" build for tracking down the differences, then use pragmas to selectively disable optimizations where it makes a difference.

I would like to think that the code you are using was designed to be compiled as optimized code, but it is more likely that whoever programmed it originally just got lucky.

Without knowing more about your code, or what you are doing, it is impossible for me to point you in the right direction.

Member Avatar for Salem

> I am wondering if it makes sense that optimizating with a compiler change the
> outcome of the solutions.
Sure it can, if there are bugs or unwarranted assumptions in your code, all sorts of things can break. At -O3, your code needs to be pretty darn perfect to produce consistent results.

Just because you managed to produce an expected result at -O0 should NOT in any way be construed as meaning "bug free". You've reached base camp 1, not scaled Everest.

Here's one classic example of how assumptions can bite you and produce different results for pretty obscure reasons.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.