gmpxx and allocation
marc.glisse at inria.fr
Tue Mar 6 01:07:04 CET 2012
just showing some numbers on a very silly example:
With gmp-5.0.4, it takes 1.10s.
With gmp-5.1, it takes 0.77s.
With a pool of objects, it takes 0.26s.
With a small object optimization, it takes 0.11s.
* gmp-5.1 uses fewer temporaries than 5.0 (just one less here, I didn't
take a particularly favorable case). It does in-place operations as much
as possible, which saves some allocations. gmp doesn't always like that,
and sometimes this will result in a copy (say in mpz_mul). I doubt there
is ever a significant loss compared to 5.0. If needed (for instance if we
use a pool that makes creating temporaries very cheap), we could specify
for each operation whether it likes being in-place (mpz_neg, mpz_add) or
not (mpz_sqrt, mpz_mul).
It is becoming hard to use even fewer temporaries. One possibility is
resurrecting the ternary operators (calling mpz_addmul); it uses a
temporary internally, but that's infinitely cheaper than a temporary at
the C++ level. Another possibility is merging temporaries inside an
expression: z=a*b+c*d+e*f is currently computed as tmp1=e*f, tmp2=c*d,
z=a*b, z+=tmp2, z+=tmp1. It could be done as tmp=c*d, z=a*b, z+=tmp,
tmp=e*f, z+=tmp, but that requires checking that z doesn't alias e or f
(and it is quite a bit of work). Using alloca for C++ temporaries would be
inconvenient (though probably not that hard), and it doesn't feel like the
* For the pool of objects experiment, I have a linked list (could be
vectors, but a list is more compatible with garbage collection) of
initialized mpz_t objects, mpz_class contains just a mpz_ptr, when I
construct a mpz_class I pop an element from the list (or create a new one
if it is empty) and the destructor puts it back in the list. So mpz_init
is only called 3 times for the whole program above.
With a pool, objects are never destructed (unless you explicitly purge the
pool). Making this thread-safe is complicated: if there is a single pool,
we need to synchronize access to it, which is slow and if we have one pool
per thread, we need some working TLS and a way to clear the pool at thread
exit, all doable in C++11 but not implemented in g++ yet. Since an
mpz_class just contains an mpz_ptr, it is not possible to have
mpq_class::get_num and get_den return references to an mpz_class as they
currently do. They would have to return either a copy, or a mpz_class that
doesn't own its mpz_t (we would need to store somewhere the information
that the destructor should do nothing), or some proxy (there are traces of
a mpz_classref in the ChangeLog), but none of those would be
source-compatible with the current get_num.
Note that it would be possible to keep the current mp*_class and only use
a pool internally for the temporary objects created during the evaluation
of complex expressions.
This optimization and the previous one should have no benefit for
optimally-written code, where the user takes care to create temporaries
himself and reuses them (the pool even slows things down a little bit).
* For the small object optimization, I used flint's fmpz_t. It computes
with integers as long as numbers fit in a pointer minus a few bits and
only uses gmp when they don't (and in that case uses a pool approach).
Note that this is a classical technique (some standard libraries use it
for std::string, integers in guile (scheme) are implemented that way),
flint was just the first one I found for this test. If done properly, one
can get a speed within a small factor of builtin operations as long as the
numbers fit (although it is hard to convince the compiler to generate
optimal code without writing the whole function in asm).
The benefits are entirely limited to those small numbers. As soon as
numbers don't fit anymore, it just slows things down a little bit. With
64-bit numbers (that don't fit), the runtime increases to 0.44s whereas
all the others remain the same (flint's pool implementation is different
from mine, so the difference between .44s and .26s should not be
interpreted directly as the overhead of small object optimization).
Depending on how things are handled, pointers may be mangled which can
hurt garbage collection (or they may not, or it may not).
This technique subsumes lazy allocation (which in some sense is a small
object optimization where "small" means 0). Lazy allocation is
particularly interesting in C++11. First, it allows a constexpr noexcept 0
(ok, maybe not so useful). But mostly, it lets move construction skip an
unneeded mpz_init/mpz_free pair which makes it fast and noexcept.
There will probably be a bigint type in the next C++ standard library, and
it is likely that all implementations will use a small number
optimization. The standard might even make lazy initialization mandatory
(if it requires noexcept on the default and move constructors).
I don't think any of this will make it into gmpxx, it looks better suited
to different C++ wrappers (I didn't even mention reference counting), but
it seemed interesting to post it and see if people had any comments.
More information about the gmp-discuss