Another performance question
mbardiaux at peaktime.be
Mon May 3 15:41:17 CEST 2004
DTAshley at aol.com wrote:
> I personally wouldn't approach the problem that way.
> First, if you are going to represent rational time values (and they will
> all be rational--some fraction of a second), then figure out what those
> denominators can be, and choose a denominator that includes all of those
> prime factors in the required multiplicity, i.e. LCM (a, b, c, etc.).
> Then, just represent time as large integers in those units. For
> example, if you know that 90,000 of a second, 44100 of a second, and
> microseconds are all common, then find LCM(90000, 44100, 1000000) and
> use that as a basis. Then, all times are integers, not rational numbers.
Murphy's law applies here, ensuring a high probability some other
frequency will become important in the future :-)
> Second, if I were to optimize the GMP (using integer arithmetic as an
> example), I would do it in a more general way than reusing a pointer as
> an integer. Why don't you make a preprocessor constant that specifies
> the number of limbs to use before you have to "overflow" to allocation
> and deallocation.
You're absolutely right, of course. But I did not pretend my design was
already optimal, it was just a very rough sketch of the general idea.
*Real* development work would of course lead quite naturally to this
> Or, you could get even more general and say that the
> lowest-order N limbs are held statically and any needed above that are
> It would look something like this:
> #define GMP_N_LIMBS_COMMON_INTS (4)
> /* Customized per application, speeds things up in some applications by
> ** eliminating allocation and deallocation when the integers are
> "small" in an
> ** application dependent sense of "small".
> struct GMP_Int
> int nlimbs;
> int low_limbs[GMP_N_LIMBS_COMMON_INTS];
> int *high_limbs;
> So, instead of reusing the integer pointer to perhaps hold an integer,
> make the scheme more general where the notion of a "small" integer is
> application-dependent and results in huge performance gains when only
> integers of that size and below are manipulated. The performance gains
> come from no allocation and deallocation.
> I understand all the implications of what I'm suggesting, and there is a
> bit more complexity than what I've suggested above.
> But, for many applications of the GMP, this approach would pay back heavily.
> Good idea in spirit. I would just suggest generalizing to have an
> application-dependent notion of "small".
I agree with all that of course, except I dont understand what one gains
by using the low_limbs *and* the high_limbs. Using only one *or* the
other would simplify things a lot, no?
> Best regards, Dave.
> In a message dated 4/30/2004 4:44:27 AM Eastern Daylight Time,
> mbardiaux at peaktime.be writes:
> I am using mpq's to represent time values with arbitrary precision so
> that arithmetic is lossless (e.g. in MPEG video files, one has to add
> 1/90000 of second; in audio, 1/44100 is common).
> I end up with a vast majority of numbers with very small limb sets, so
> that the malloc/free overhead dominates. What would be the impact,
> risks, etc of having flags (1 in mpz, 2 in mpq) telling that a limb is
> *not* a pointer but a number making by itself a 1-integer limb?
> Note well, I am not asking that somebody else do it. If it seems
> possible, I might have a go, but I would prefer to be flamed before
> after having done the work!
> Michel Bardiaux
> Peaktime Belgium S.A. Bd. du Souverain, 191 B-1160 Bruxelles
> Tel : +32 2 790.29.41
Peaktime Belgium S.A. Bd. du Souverain, 191 B-1160 Bruxelles
Tel : +32 2 790.29.41
More information about the gmp-discuss