Another performance question

[Michel Bardiaux]

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