Re: Excessive copies of set elements in GMPL

[Domingo Alvarez Duarte]

Hello Andrew !

Thank you for pointing out better ways to write gmpl code !

And here is the results with it still show that GLPK with my 
modifications is faster and uses less memory, although in this minimal 
example it's negligible.

And I agree with you that implement optimizations in the translator 
would not be easy but we can do some simple changes and get better 
performance like the changes I made.

Any way thanks for all comments/suggestions so far and I hope they'll 
contribute to a better GLPK/GMPL !

====

/usr/bin/time glpsol -m test-nested-sets.mod

GLPSOL: GLPK LP/MIP Solver, v4.65
Parameter(s) specified in the command line:
 -m test-nested-sets.mod
Reading model section from test-nested-sets.mod...
test-nested-sets.mod:13: warning: unexpected end of file; missing end 
statement inserted
13 lines were read
A count: 100
B count: 200
C count: 300
D count: 100
Display statement at line 13
D:
   (1,2,4)
   (2,3,5)
   (3,4,6)
   (4,5,7)
...
Memory used: 0.3 Mb (316229 bytes)
1.27user 0.00system 0:01.28elapsed 99%CPU (0avgtext+0avgdata 
3400maxresident)k


/usr/bin/time myglpsol -m test-nested-sets.mod

GLPSOL: GLPK LP/MIP Solver, v4.65
Parameter(s) specified in the command line:
 -m test-nested-sets.mod
Reading model section from test-nested-sets.mod...
test-nested-sets.mod:13: warning: unexpected end of file; missing end 
statement inserted
13 lines were read
A count: 100
B count: 200
C count: 300
D count: 100
Display statement at line 13
D:
   (1,2,4)
   (2,3,5)
   (3,4,6)
   (4,5,7)
...

Memory used: 0.1 Mb (131501 bytes)
0.54user 0.00system 0:00.54elapsed 100%CPU (0avgtext+0avgdata 
3004maxresident)k

====

set A := {1..100};
set B := {1..200};
set C := {1..300};

#set D := { (a,b,c) in A cross B cross C : b=a+1 and c=b+2 };
set D := setof{a in A, b in B, c in C: b=a+1 and c=b+2} (a,b,c);

printf "A count: %d\n", card(A);
printf "B count: %d\n", card(B);
printf "C count: %d\n", card(C);
printf "D count: %d\n", card(D);

display D;

====

Cheers !

On 24/7/20 13:45, Andrew Makhorin wrote:
> On Fri, 2020-07-24 at 09:12 +0200, Domingo Alvarez Duarte wrote:
> > And here is the output of the the script bellow:
> >
> > Memory usage:
> >
> > ubuntu glpsol package : 1,422,160 KB => 4.20s elapsed
> >
> > glpk with my changes: 429,000 KB => 1.37s elapsed
> As I explained in my previous message, the MathProg translator performs
>   all computations directly as specified by corresponding expressions,
> i.e. *no code optimization* is used.
>
> In most cases the user may perform some "optimization" replacing
> non-efficient expressions by more efficient ones. For example,
>
>    set D := { (a,b,c) in A cross B cross C : b=a+1 and c=b+2 };
>
> can be replaced by
>
>    set D := setof{a in A, b in B, c in C: b=a+1 and c=b+2} (a,b,c);
>
> in order not to compute "A cross B cross C".
>
> I agree that the translator could be more smart to recognize such
> cases, but necessary analysis in a general case is a non-trivial thing,
> and there was no attempt to implement anything of this kind.
>
> 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?
>
>
> Andrew Makhorin