Factorize/FactDollar are much slower than FactArg

[tueda]

I am trying to switch from FactArg to FactDollar to avoid the curse of MaxTermSize. The major problem is that FactDollar is really much slower than FactArg.

I put a test program at https://gist.githubusercontent.com/tueda/5f83e562854158b5a62f/raw/test1.frm. The file contains two expressions F1 and F2. The timing I obtained for F1 was

~~~factarg : .01 sec
~~~#factdollar : 7.74 sec
~~~factdollar : 7.81 sec
~~~factorize : 7.75 sec

and the timing for F2 was

~~~factarg : .01 sec
~~~#factdollar : 350.05 sec
~~~factdollar : 350.31 sec
~~~factorize : 356.11 sec

Maybe the recent improvements do not apply for them?

[vermaseren]

Hi Takahiro,

This is a bit strange. The ArgFact eventually calls poly_factorize_argument which calls poly_factorize
and factdollar calls poly_factorize_dollar which calls poly_factorize. This would mean that the work
should sit in the stuff around it (getting content out etc.). These are the routines ArgFactorize and
DollarFactorize. The main difference is that ArgFactorize maintains a cache, but since that is the first
one you call, the cache should be empty.
Clearly needs some investigations.

Jos

On 28 aug. 2015, at 18:45, Takahiro Ueda notifications@github.com wrote:

I am trying to switch from FactArg to FactDollar to avoid the curse of MaxTermSize. The major problem is that FactDollar is really much slower than FactArg.

I put a test program at https://gist.githubusercontent.com/tueda/5f83e562854158b5a62f/raw/test1.frm https://gist.githubusercontent.com/tueda/5f83e562854158b5a62f/raw/test1.frm. The file contains two expressions F1 and F2. The timing I obtained for F1 was

~~~#factdollar : 7.74 sec
~~~factdollar : 7.81 sec
~~~factorize : 7.75 sec
and the timing for F2 was

~~~factarg : .01 sec
~~~#factdollar : 350.05 sec
~~~factdollar : 350.31 sec
~~~factorize : 356.11 sec
Maybe the recent improvements do not apply for them?

—
Reply to this email directly or view it on GitHub https://github.com/vermaseren/form/issues/42.

[vermaseren]

Hi Takahiro,

I understand it now.
The difference is the content.
In FactArg the content is taken out properly: ie numerical content and symbol content.
In FactDollar there is the option (STEP2) to take out the numerical content, but the symbolic
content is never taken out.
Apparently the poly_factorize assumes the expression to be contentfree.
This needs a little bit of work.

Jos

On 28 aug. 2015, at 18:45, Takahiro Ueda notifications@github.com wrote:

I am trying to switch from FactArg to FactDollar to avoid the curse of MaxTermSize. The major problem is that FactDollar is really much slower than FactArg.

I put a test program at https://gist.githubusercontent.com/tueda/5f83e562854158b5a62f/raw/test1.frm https://gist.githubusercontent.com/tueda/5f83e562854158b5a62f/raw/test1.frm. The file contains two expressions F1 and F2. The timing I obtained for F1 was

~~~#factdollar : 7.74 sec
~~~factdollar : 7.81 sec
~~~factorize : 7.75 sec
and the timing for F2 was

~~~factarg : .01 sec
~~~#factdollar : 350.05 sec
~~~factdollar : 350.31 sec
~~~factorize : 356.11 sec
Maybe the recent improvements do not apply for them?

—
Reply to this email directly or view it on GitHub https://github.com/vermaseren/form/issues/42.

[tueda]

Hi Jos,

OK. For now I'm fine with a workaround like

#$c = content_($x);
#$x = div_($x,$c);
#factdollar $c
#factdollar $x

which is fast as FactArg. Thanks.

[vermaseren]

Hi Takahiro,

I managed to fix up the dollars. In the end the proper routines were there, but were not called/
had wrong commentary, etc.
The expressions are much harder, because that plays completely inside the .cc routines.
We better discuss that, so that either you or Ben fix that up.

Cheers

Jos

On 29 aug. 2015, at 19:39, Takahiro Ueda notifications@github.com wrote:

Hi Jos,

OK. For now I'm fine with a workaround like

#$c = content_($x);
#$x = div_($x,$c);
#factdollar $c
#factdollar $x
which is fast as FactArg. Thanks.

—
Reply to this email directly or view it on GitHub #42 (comment).

[tueda]

Hi Jos,

It broke GCD:

S x;
L F = gcd_(
  (1+x),
  2*(1+x),
  3*(1+x)
);
P;
.end

which now gives

Negative power in SymbolNormalize
   F =
      1;

[tueda]

#FactDollar is also broken.

S x,y;
#$a = x^4-y^4;
#factdollar $a
.end

*** glibc detected *** form: double free or corruption (fasttop): 0x0000000001b824c0 ***
...
Aborted (core dumped)

valgrind output:

...
FORM 4.1 (Aug 31 2015) 64-bits                   Run: Tue Sep  1 13:24:06 2015
    S x,y;
    #$a = x^4-y^4;
    #factdollar $a
==23638== Invalid read of size 4
==23638==    at 0x44EA00: DollarFactorize (dollar.c:2932)
==23638==    by 0x51ECE1: DoFactDollar (pre.c:6239)
==23638==    by 0x510152: PreProInstruction (pre.c:1065)
==23638==    by 0x50F89C: PreProcessor (pre.c:857)
==23638==    by 0x5728D4: main (startup.c:1519)
==23638==  Address 0x5825960 is 0 bytes inside a block of size 72 free'd
==23638==    at 0x4A06430: free (vg_replace_malloc.c:446)
==23638==    by 0x599EFA: M_free (tools.c:2326)
==23638==    by 0x44E9D0: DollarFactorize (dollar.c:2930)
==23638==    by 0x51ECE1: DoFactDollar (pre.c:6239)
==23638==    by 0x510152: PreProInstruction (pre.c:1065)
==23638==    by 0x50F89C: PreProcessor (pre.c:857)
==23638==    by 0x5728D4: main (startup.c:1519)
==23638==
...

[tueda]

Status update: $-variables now seem to be OK (5fbce8e).

[tueda]

Oh, the above gcd_ issue (#42 (comment)) was not fixed.

[tueda]

Hi, good news is the above example now works thanks to 5f9b827, and it seems that somehow "incomplete gcd" has been fixed:

S n1,...,n4;
L F1 = (1+n1)*(1+n2)*n1*n2*n3;
L F2 = (1+n2)*n1*n2*n3*n4;
L F3 = (1+n4)*n1*n2*n3*n4^2;
L F = gcd_(F1,F2,F3);
P F;
.end

The result was

FORM 4.1 (Aug 18 2015) 64-bits

   F =
      1;

But now

FORM 4.1 (Sep  1 2015) 64-bits

   F =
      n1*n2*n3;

Bad news is that another part (#FactDollar) is broken...

#procedure PrintFactorizedDollar(dollar)
  #write "(%$)%", `dollar'[1]
  #do i=2,``dollar'[0]'
    #write "*(%$)%", `dollar'[`i']
  #enddo
  #write ""
#endprocedure

S x,y;
#$a = (1-x)*(1+y);
#$b = (1-x)*(1-y);
#factdollar $a
#factdollar $b
#call PrintFactorizedDollar($a)
#call PrintFactorizedDollar($b)
.end

gives

FORM 4.1 (Sep  1 2015) 64-bits

    #call PrintFactorizedDollar($a)
(1+y-x-x*y)
    #call PrintFactorizedDollar($b)
PrintFactorizedDollar Line 3 ==> PrintFactorizedDollar Line 3 ==> write instruc
tion: $b has not been factorized

which had been

FORM 4.1 (Aug 18 2015) 64-bits

    #call PrintFactorizedDollar($a)
(-1)*(-1+x)*(1+y)
    #call PrintFactorizedDollar($b)
(-1+y)*(-1+x)

[tueda]

I don't understand code around dollar.c:3055. If the input is $a = (1+x)*(1-y), here buf3 contains two factors y-1 and x+1. But this code seems to treat -1 in y-1 as a numeric factor in the content, setting nfactors to 1 and increase factorsincontent to 2 at the end. I guess nfactors should be 2 and factorsincontet should be 1...???

[vermaseren]

Hi Takahiro,

This is indeed where things did go wrong. But checking now, I did repair in my sources, but must
have made (it was in the middle of the night and I had gotten out of bed because I could not sleep
and saw your mail and found the bug and thought I had properly pushed it) a mistake.
The idea there is that:
The factors are sequences of terms, zero terminated.
The sequence of factors is terminated by a second zero.
Hence the part in the STEP2 is supposed to get an expression that contains only -1 and add it
to the content. Then later it will check in the content whether there are more factors -1.
The error was that in the part outside STEP2 it should skip a whole sequence and not just a
single term. You will see that in the new push.
With that it should work. (at least it does that here).

Jos

On 2 sep. 2015, at 20:28, Takahiro Ueda notifications@github.com wrote:

I don't understand code around dollar.c:3055

form/sources/dollar.c

Line 3055 in 5fbce8e

if ( *term == 4 && term[4] == 0 && term[3] == -3 && term[2] == 1

. If the input is $a = (1+x)*(1-y), here buf3 contains two factors y-1 and x+1. But this code seems to treat -1 in y-1 as a numeric factor in the content, setting nfactors to 1 and increase factorsincontent to 2 at the end. I guess nfactors should be 2 and factorsincontet should be 1...???

—
Reply to this email directly or view it on GitHub #42 (comment).

[tueda]

Thanks. I've added test cases for the examples in this issue. (ParFORM freezes for #factdollar, but probably it is a different thing.) For now I will close this issue, and will open an issue for slow Factorize separately.