Re: Excessive copies of set elements in GMPL

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