Re: GLPSOL in webassemby faster than native ?

Hello Michael !

You answer is pointing correctly the issue on this thread, and that is 
the difference between libc/qsort and musl/qsort, I found it adding 
"printf" inside "src/intopt/gmigen::glp_gmi_gen" and compared 
native/wasm output and seeing the difference looked in the source of 
emscripten and found they are using musl/qsort then I've added it to my 
repository and I'm sing it instead of libc/qsort, at least this way 
we'll have a stable result on every platform (till we found a way to 
better fix this issue).

But in reality it seems that musl/qsort results in "stable sort" but 
actually for hashi.mod and tiling.mod the order of the "tie-breaker" 
results in a lot shorter solving time.

Probably a review of "glp_gmi_gen" function and others that use qsort 
with this insight can reveal a better/stable approach to calculate cuts 
(or other tasks around qsort).

====
int glp_gmi_gen(glp_prob *P, glp_prob *pool, int max_cuts)
{
...
       /* sort the list by descending fractionality */
       glp_qsort(&var[1], nv, sizeof(struct var), fcmp);
       /* try to generate cuts by one for each variable in the list, but
        * not more than max_cuts cuts */
       nnn = 0;
       for (t = 1; t <= nv; t++)
       {  len = glp_gmi_cut(P, var[t].j, ind, val, phi);
          if (len < 1)
             goto skip;
          /* if the cut inequality seems to be badly scaled, reject it
           * to avoid numerical difficulties */
          for (k = 1; k <= len; k++)
          {  if (fabs(val[k]) < GLP_GMI_GEN_TOL)
                goto skip;
             if (fabs(val[k]) > GLP_GMI_GEN_TOL2)
                goto skip;
          }
          /* add the cut to the cut pool for further consideration */
          i = glp_add_rows(pool, 1);
          glp_set_row_bnds(pool, i, GLP_LO, val[0], 0);
          glp_set_mat_row(pool, i, len, ind, val);
          /* one cut has been generated */
          /*printf("nnn %d : %d : %d : %d : %g : %g : %g\n", i, len, t, 
var[t].j, var[t].f, val[k], fabs(val[k]));*/
          nnn++;
          if (nnn == max_cuts)
             break;
skip:    ;
       }
}
====
Cheers !

On 1/10/20 19:29, Michael Hennebry wrote:
> On Thu, 1 Oct 2020, Heinrich Schuchardt wrote:
>
>> On 9/30/20 10:02 PM, Michael Hennebry wrote:
>>> On Tue, 29 Sep 2020, Domingo Alvarez Duarte wrote:
>>>
>>>> I found why GLPK in wasm was faster with "--cuts" option than native,
>>>> it was due wasm using qsort from muslc that is a "stable sort", I've
>>>> added it to my GLPK repository and running all models in the
>>>> "examples" folder only "color.mod" produces a different solution (that
>>>> seems to be valid anyway).
>>
>> My expectation is that all sort algorithms produce the same result if
>> you supply a sort key that is different for all elements.
>
> In the case of ties, tie-breaking matters.
> For a stable sort, the tie-breaker is the original position.
>