Another performance question

Michel Bardiaux 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
improvement.

> Or, you could get even more general and say that the
> lowest-order N limbs are held statically and any needed above that are
> allocated.
>
> 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
>     than
>     after having done the work!
>
>     HaND,
>     --
>     Michel Bardiaux
>     Peaktime Belgium S.A.  Bd. du Souverain, 191  B-1160 Bruxelles
>     Tel : +32 2 790.29.41
>

--
Michel Bardiaux
Peaktime Belgium S.A.  Bd. du Souverain, 191  B-1160 Bruxelles
Tel : +32 2 790.29.41

```