Another performance question

DTAshley at DTAshley at
Fri Apr 30 18:40:45 CEST 2004

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.

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.  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:

    /* 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 

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".

Best regards, Dave.

In a message dated 4/30/2004 4:44:27 AM Eastern Daylight Time, 
mbardiaux at 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!

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

gmp-discuss mailing list
gmp-discuss at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /list-archives/gmp-discuss/attachments/20040430/6e90033f/attachment.htm

More information about the gmp-discuss mailing list