Hello Caio !
Thank you for reply !
I just used your proposed macro and it seems that the performance seems
to be the same as before, see the commit here
https://github.com/mingodad/GLPK/commit/519a803f9c7cda7b278c04ea205435f38c654fca
.
I also updated the online version here https://meimporta.eu/myglpk-ext/ .
Just in case you are interested I have done several changes to GLPK on
this fork https://github.com/mingodad/GLPK (mainly on GMPL/glpsol).
Cheers !
On 17/12/21 12:50, Caio Giuliani wrote:
Hello,
I was just reading the source code and found it by chance.
Signed integer overflow is known to be Undefined Behavior (UB) in the
C standard.
You must simply avoid it. Trying to observe its effects is wrong.
Though I found it by chance, some tools (such as static analysers and
compiler's ub sanitizer) could help, but I have no experience with them.
If the code is taking much longer, you could try substituting the test
with a macro such as
#define addition_overflows(u, v) ((u > 0 && v > INT_MAX - u) || (u <
0 && v < INT_MIN - u))
but it would have no effect if the compiler is already inlining the
function.
Best,
Caio
Em sex., 17 de dez. de 2021 às 08:22, Domingo Alvarez Duarte
<[email protected] <mailto:[email protected]>> escreveu:
Hello Caio !
How have you come to find this problem ?
Looking through compiler warnings ?
Trying to solve a specific problem ?
Using your proposed overflow function and testing the all models
in the "examples" folder I didn't found any difference on the
results other than it takes a bit longer to solve then (before the
compiler was effectively eliminating the "overflow" function).
Cheers !
On 15/12/21 16:37, Domingo Alvarez Duarte wrote:
Hello Caio !
Thank you for your discovery !
I can confirm what you've found, here is small C program to test it:
====
#include <stdio.h>
#include <limits.h>
static int overflow2(int u, int v)
{ /* check for integer overflow on computing u + v */
if (u > 0 && v > INT_MAX - u) return 1;
if (u < 0 && v < INT_MIN - u) return 1;
return 0;
}
static int overflow(int u, int v)
{ /* check for integer overflow on computing u + v */
if (u > 0 && v > 0 && u + v < 0) return 1;
if (u < 0 && v < 0 && u + v > 0) return 1;
return 0;
}
int main() {
int max_u = 10;
for(int u= 0, v = 0; u< max_u; ++u, ++v)
printf("== %d : %d : %d : %d\n", u, v, overflow(u,v),
overflow2(u,v));
for(int u= 0, v = INT_MAX-max_u; u < max_u; ++u, ++v)
printf(":::: %d : %d : %d : %d\n", u, v, overflow(u,v),
overflow2(u,v));
return 0;
}
====
Output without optimization:
====
gcc -o overflow overflow.c
./overflow
== 0 : 0 : 0 : 0
== 1 : 1 : 0 : 0
== 2 : 2 : 0 : 0
== 3 : 3 : 0 : 0
== 4 : 4 : 0 : 0
== 5 : 5 : 0 : 0
== 6 : 6 : 0 : 0
== 7 : 7 : 0 : 0
== 8 : 8 : 0 : 0
== 9 : 9 : 0 : 0
:::: 0 : 2147483637 : 0 : 0
:::: 1 : 2147483638 : 0 : 0
:::: 2 : 2147483639 : 0 : 0
:::: 3 : 2147483640 : 0 : 0
:::: 4 : 2147483641 : 0 : 0
:::: 5 : 2147483642 : 0 : 0
:::: 6 : 2147483643 : 1 : 1
:::: 7 : 2147483644 : 1 : 1
:::: 8 : 2147483645 : 1 : 1
:::: 9 : 2147483646 : 1 : 1
====
Output without optimization:
====
gcc -O2 -o overflow2 overflow.c
./overflow2
== 0 : 0 : 0 : 0
== 1 : 1 : 0 : 0
== 2 : 2 : 0 : 0
== 3 : 3 : 0 : 0
== 4 : 4 : 0 : 0
== 5 : 5 : 0 : 0
== 6 : 6 : 0 : 0
== 7 : 7 : 0 : 0
== 8 : 8 : 0 : 0
== 9 : 9 : 0 : 0
:::: 0 : 2147483637 : 0 : 0
:::: 1 : 2147483638 : 0 : 0
:::: 2 : 2147483639 : 0 : 0
:::: 3 : 2147483640 : 0 : 0
:::: 4 : 2147483641 : 0 : 0
:::: 5 : 2147483642 : 0 : 0
:::: 6 : 2147483643 : 0 : 1 <<< always 0
:::: 7 : 2147483644 : 0 : 1 <<< always 0
:::: 8 : 2147483645 : 0 : 1 <<< always 0
:::: 9 : 2147483646 : 0 : 1 <<< always 0
====
Cheers !
On 15/12/21 16:01, Caio Giuliani wrote:
Greetings,
Files src/misc/okalg.c and src/api/mcfrelax.c define the
following function:
static int overflow(int u, int v)
{ /* check for integer overflow on computing u + v */
if (u > 0 && v > 0 && u + v < 0) return 1;
if (u < 0 && v < 0 && u + v > 0) return 1;
return 0;
}
It contains integer overflow, which is undefined behavior by the
C standard.
As I tested, both GCC 11.1.0 and clang 13.0.0 make this function
always return 0 from optimization level O1 onwards.
Particularly function glp_mincost_relax4 appears to have
received ad-hoc patches on the places this function is used.
I propose, instead, the following:
#include <limits.h>
static int overflow(int u, int v)
{ /* check for integer overflow on computing u + v */
return (u > 0 && v > INT_MAX - u) return 1;
if (u < 0 && v < INT_MIN - u) return 1;
return 0;
}
Best regards,
--
Caio Merlini Giuliani
Operations Research Analyst
WPLEX Software Ltda
www.wplex.com.br <http://www.wplex.com.br>
--
Caio Merlini Giuliani
Operations Research Analyst
WPLEX Software Ltda
www.wplex.com.br <http://www.wplex.com.br>
