Re: scm_i_fraction_reduce thread safety

[Kevin Ryde]

Bill Schottstaedt <address@hidden> writes:
>
> I'd vote for a lock,

I guess everywhere inspecting the parts of a fraction would need to
acquire and release such a lock.  Perhaps a macro that did that and
delivered out the parts could stop it being too awful when coding.

> if it's really an issue.

Unfortunately I believe it is, in the new-style free-running
concurrent posix threads.  It'll be one of those threading things that
might almost never actually cause a problem, but alas is not right.

> On the need for reduction, I wonder how much of that
> notoriety is due to Knuth -- his discussion of this
> was in a slightly artificial context, and I've been
> intending for a long time to check some "real-world"
> situation.

I guess +, -, *, / will keep increasing num and/or den (though perhaps
with some cancellation in the num for + and -), unless steps are taken
at some point.

> (I think it's less of a problem than calling gcd all the time).

The claim in gmp (without anything actual to cite :-), is that because
gcd is O(N^2) it's better to do a couple of smaller one's sooner than
to allow a product to accumulate and do a big one later.

Of course if one knows or suspects not much cancellation will be
possible in a given algorithm, then all theories about automated
reductions go out the window.  A general purpose fraction type is
probably not the tool for the job in that case.


Carl Witty <address@hidden> writes:
>
> I think that one way to avoid arbitrarily-bad behavior is to reduce only
> if the numerator or denominator is "sufficiently large" (I think this is
> at most a constant factor worse than always reducing).

mpz_t allocated memory could be counted towards the mtrigger, to
provoke a gc when big numbers are using up memory.  That's probably a
good idea anyway.  The gc could nose around and attempt to reduce
likely looking big fractions.