Re: Excessive copies of set elements in GMPL

[Domingo Alvarez Duarte]

Hello Andrew !

Thank you for reply !

After doing some experimentation I think I found an easy way to 
eliminate unnecessary set copies here is a commit on 
https://github.com/mingodad/GLPK/commit/6f3da6ab31ca8d710f706f60635e5b17cf2ded40, 
also see bellow, glpsol now uses 1/3 of the memory and is slight faster:

====

set S := {1..1000000};
param d { i in S} := if ((i mod 2) == 0) then 0.0000000123 else 
12345.0000000001;
display card(S);
display sum {i in S} d[i];
display card(S)*2;
display card(S)*3;
display sum {i in S : (i mod 2) == 0} d[i];
display sum {i in S : (i mod 2) <> 0} d[i];
end;

====

/usr/bin/time ./glpsol -m sum-test.mod #without refcount
GLPSOL: GLPK LP/MIP Solver, v4.65
...

Memory used: 645.0 Mb (676328774 bytes)
3.68user 0.23system 0:03.91elapsed 100%CPU (0avgtext+0avgdata 
664568maxresident)k

====

/usr/bin/time ./glpsol -m sum-test.mod #with refcount
GLPSOL: GLPK LP/MIP Solver, v4.65
...

Memory used: 215.4 Mb (225829958 bytes)
3.06user 0.08system 0:03.14elapsed 100%CPU (0avgtext+0avgdata 
223772maxresident)k

====

diff --git a/src/mpl/mpl.h b/src/mpl/mpl.h
index ddd3154..262a783 100644
--- a/src/mpl/mpl.h
+++ b/src/mpl/mpl.h
@@ -1358,6 +1358,8 @@ struct ARRAY
          the array is 0-dimensional */
       int size;
       /* size of the array, i.e. number of its members */
+      int refcount;
+      /* reference counting to allow reuse without copy */
       MEMBER *head;
       /* the first array member; NULL means the array is empty */
       MEMBER *tail;
diff --git a/src/mpl/mpl3.c b/src/mpl/mpl3.c
index 2489db2..036ef8c 100644
--- a/src/mpl/mpl3.c
+++ b/src/mpl/mpl3.c
@@ -1002,6 +1002,7 @@ MEMBER *add_tuple
       xassert(set != NULL);
       xassert(set->type == A_NONE);
       xassert(set->dim == tuple_dimen(mpl, tuple));
+      xassert(set->refcount == 1);
       memb = add_member(mpl, set, tuple);
       memb->value.none = NULL;
       return memb;
@@ -1038,6 +1039,10 @@ ELEMSET *copy_elemset
       xassert(set != NULL);
       xassert(set->type == A_NONE);
       xassert(set->dim > 0);
+      if(set->size) {
+          ++set->refcount;
+          return set;
+      }
       copy = create_elemset(mpl, set->dim);
       for (memb = set->head; memb != NULL; memb = memb->next)
          add_tuple(mpl, copy, copy_tuple(mpl, memb->tuple));
@@ -1170,6 +1175,7 @@ ELEMSET *set_union
       xassert(X != NULL);
       xassert(X->type == A_NONE);
       xassert(X->dim > 0);
+      xassert(X->refcount == 1); /* only add to recently/owned created 
sets */
       xassert(Y != NULL);
       xassert(Y->type == A_NONE);
       xassert(Y->dim > 0);
@@ -1626,6 +1632,7 @@ ARRAY *create_array(MPL *mpl, int type, int dim)
       array->type = type;
       array->dim = dim;
       array->size = 0;
+      array->refcount = 1;
       array->head = NULL;
       array->tail = NULL;
       array->tree = NULL;
@@ -1742,6 +1749,7 @@ void delete_array
 )
 {     MEMBER *memb;
       xassert(array != NULL);
+      if(--array->refcount) return; /* someone is still using this array */
       /* delete all existing array members */
       while (array->head != NULL)
       {  memb = array->head;

====

Cheers !

On 16/7/20 14:06, Andrew Makhorin wrote:
> > Trying to improve GLPK/GMPL
> It is a non-trivial task.
>
> The MathProg translator included in glpk was implemented in a
> non-efficient way, because there was no intention to process models
> of huge size (so this allowed essentially reducing implementation
> efforts).
>
> The key idea to translate MathProg (or AMPL) models much more
> efficiently is to avoid using "direct" representation of sets and
> arrays and implement all operations in a way similar to one used
> in relational database management systems.
>
> > I can see that GMPL model generation is
> > making an excessive number of set element copies (see bellow).
> Please note that most of the copies might be temporary quantities
> that exist (allocated in the memory) only during evaluation of the
> (sub)expressions involving these quantities.
>
>
> Best regards,
>
> Andrew Makhorin