Re: Excessive copies of set elements in GMPL

I also add a splaytree to replace the avltree on ARRAY in GMPL and the 
memory usage was reduced even more and the processing time now is 1/2 of 
the original.

See 
https://github.com/mingodad/GLPK/commit/7ffe6eae90e25d23e04b6c2f612daae03f60a8a7

====

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

Memory used: 169.0 Mb (177220286 bytes)
1.76user 0.09system 0:01.85elapsed 100%CPU (0avgtext+0avgdata 
176188maxresident)k

====

On 16/7/20 18:40, Domingo Alvarez Duarte wrote:
> 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