[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: scm_i_fraction_reduce thread safety
From: |
Kevin Ryde |
Subject: |
Re: scm_i_fraction_reduce thread safety |
Date: |
Sat, 13 Dec 2003 09:23:40 +1000 |
User-agent: |
Gnus/5.1003 (Gnus v5.10.3) Emacs/21.3 (gnu/linux) |
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.