Make FactInt compatible with HPC-GAP.

[rbehrends]

This pull request tries to make FactInt work with HPC-GAP. We make tables immutable so that they can be read from any thread and in HPC-GAP, also make the cache thread-local.

A thread-local cache is preferred over a shared cache with locks, as the cache can become a serialization bottleneck for a frequently used operation.

Note: I assume that tables in tables/*.g are not changed after creation. If that assumption is false, we need to fix the PR accordingly.

Resolves #2

[codecov[bot]]

Codecov Report

Merging #19 into master will increase coverage by 0.59%. The diff coverage is 94.63%.

@@            Coverage Diff             @@
##           master      #19      +/-   ##
==========================================
+ Coverage   98.48%   99.08%   +0.59%     
==========================================
  Files          21       21              
  Lines       18077    19875    +1798     
==========================================
+ Hits        17804    19693    +1889     
+ Misses        273      182      -91

Impacted Files	Coverage Δ
tables/brent/brfac10	100% <ø> (ø)	:arrow_up:
tables/brent/brfac12	100% <ø> (ø)	:arrow_up:
tables/3k2k.g	100% <100%> (ø)	:arrow_up:
tables/akbk.g	100% <100%> (ø)	:arrow_up:
tables/brent/brfac11	100% <100%> (ø)	:arrow_up:
lib/general.gi	88.19% <77.77%> (+8.32%)	:arrow_up:
tables/brent/brfac2	100% <0%> (ø)	:arrow_up:
tables/brent/brfac5	100% <0%> (ø)	:arrow_up:
tables/brent/brfac3	100% <0%> (ø)	:arrow_up:
tables/brent/brfac7	100% <0%> (ø)	:arrow_up:
... and 4 more

[Stefan-Kohl]

The assumption that the tables in tables/*.g are not changed after creation is correct. Actually these tables are only possibly changed when preparing a new release of the package. -- But isn't it necessary to treat the files in tables/brent/ in just the same way (I mean, making the lists immutable)?

[fingolfin]

I think @Stefan-Kohl is right and tables/brent also needs to be dealt with. I have updated the PR accordingly.

In particular I modified WriteBrentFactorsFiles to insert MakeImmutable comments, and then run FetchBrentFactors (after updating that to use the latest URL for the input data). I also had to use SizeScreen([80]) before that to reduce the diffs, but there still are a lot, some just due to different formatting, but there also seem to be many new factors and even new files. Indeed, the last time the data in tables/brent was updated was 2011-06-14, but factors.gz was last updated 2011-09-16, so that doesn't seem implausible...

I've also changed a few other global variables in the final commit. @rbehrends could you please take a look at those changes?

[rbehrends]

I've been testing it more aggressively in HPC-GAP and ran into some more problems:

gap> TaskResult(RunTask(IntegerFactorization,2^63+1));
fail
gap> TaskResult(RunTask(IntegerFactorization,2^63+1));
[ 3, 3, 3, 19, 43, 5419, 77158673929 ]
gap> TaskResult(RunTask(IntegerFactorization,2^63+1));
<protected object in shared region 0x115724480 (id: 4498790896)>

The initial fail seems to be the result of a read guard error that is being caught by the task system, namely:

gap> t := RunTask(IntegerFactorization, 2^63+1); 
<protected 'task descriptor' object (id: 4723126832)>
gap> TaskSuccess(t);
false
gap> TaskError(t);
"Error, Attempt to read object 4834878480 of type empty plain list without hav\
in\\\ng read access"

The protected object in the last invocation is a list with the correct result, but is located in a shared region, and I don't know how that ended up there. I'll need to dig into the code later today to find out where this comes from.

And Print(IntegerFactorization) shows the FactInt version, so it is indeed this package producing the results.

[Stefan-Kohl]

@fingolfin Thank you very much for updating the factors database! -- If it is now up-to-date, then the following issue can be closed: https://github.com/gap-packages/FactInt/issues/14

[fingolfin]

@Stefan-Kohl no, it is not up-to-date as discussed in #14, it just updates to the latest version of the data available from its old location, which was just slightly newer than what was in FactInt (by a few month). But doing that was the easiest way to make the required changes. But I can also write a sed script to insert the MakeImmutable calls w/o otherwise modifying the brent tables at all.

[fingolfin]

@rbehrends I updated this PR again, and fixed at least one of the Task issues by storing immutable results in FACTINT_CACHE (this should als fix a potential bug where client code could have modified the content of the cache). But the first call to your Task example still gives an error, but now a different one:

gap> t := RunTask(IntegerFactorization, 2^63+1);
<protected 'task descriptor' object (id: 4784978944)>
gap> TaskSuccess(t);
false
gap> TaskError(t);
"Error, Panic: READ cannot close input, this should not happen"

Among the things I changed is a call to ReadPackage which I replaced by a call to Read; both call the kernel function READ in the end.

When factorizing that number, FactInt decides to look at a Brent table (which is exactly the right thing to do, of course); it then determines that this table is not yet loaded, so it loads it. And that seems to blow up at the end.

[fingolfin]

@rbehrends maybe this is part of the problem:

UInt CloseInput ( void )
{
    /* refuse to close the initial input file                              */
    if (IO()->InputStackPointer <= 1)
        return 0;

The logic for this is that normally, the initial input is stdin, and you don't want to close that here. But in the task, there is no initial input, until we open the file to be read. And when closing it, well, things break.

Perhaps the above check should simply be removed...

[Stefan-Kohl]

@fingolfin Wouldn't it be more elegant to place one call to 'MakeImmutable' where the Brent factors files are read in general.gi, rather than adding calls to 'MakeImmutable' to every single data file?

[rbehrends]

I've committed a change to the HPC-GAP PR that adds separate CloseInput() logic for HPC-GAP. In HPC-GAP, the main thread will still use the same check, but any spawned threads will allow the IO input stack become empty. This seems to fix this particular issue.

Testing with random integers now also seems to work.

[fingolfin]

@Stefan-Kohl that wouldn't work, because the data would already be put into the cache before it is immutable, and so other threads could access it before we have a chance to call MakeImmutable. So while there are indeed other ways we can handle this, including some where we call MakeImmutable only in one place, in all scenarios we need to modify the brent table files.

[Stefan-Kohl]

@fingolfin I see. -- Would it also not be possible to put locks around, such that other threads cannot interfere?

[fingolfin]

That would be possible, but then you'd get a lot of overhead for using locks that you almost never need; using an atomic list is superior to that.

[Stefan-Kohl]

Is someone still working on this pull request -- or can I 'Rebase and merge'?

[fingolfin]

@Stefan-Kohl I think it's fine to merge this now; if we need more changes in the future, we can simply make another PR. Thank you.