On Fri, 2020-07-24 at 13:04 -0500, Michael Hennebry wrote: > On Fri, 24 Jul 2020, Andrew Makhorin wrote: > > > The issue can be illustrated by the following example: > > > > for (i = 0; i < 1000000; i++) > > for (j = 0; j < 1000000; j++) > > for (k = 0; k < 1000000; k++) > > if (j == i+1 && j == j+2) > > foo(i, j, k); > > > > Would you expect the C compiler to optimize this fragment in order > > not > > to perform obvious excessive computations? > > My recollection is that gcc does make that > kind of optimization for linear constraints. > At the very least, most optimizing compilers > would hoist the j==i+1 test ouside the k loop. > That might be just enough to allow it to run in a practical amount of > time: > a few trillion cycles plus whatever foo requires.
Yes, recent versions of gcc include very smart optimization features, and probably in the example above gcc would be able to eliminate loops on j and k. In MathProg (AMPL) as well as in RDBMS the situation is a bit easier, however, the problem has the same nature, and solving it even in a limited number of practical cases is an extremely non-trivial task. I know many cases when a simple reformulation of a sql statement significantly reduced the processing time, though modern RDBMS'es provide very powerful features to optimize access to data tables. (Usually formulae given in textbooks are inappropriate to be used in real computer programs.) > > That said, the coder can, as noted, > provide equivalent code that requires no optimization. >
