=head1 Block allocation of memory.

The idea is that we pre-allocate equally-sized chunks of memory for
later allocation. We store the chunks in a vector from which they get
popped on use and pushed back on object deletion.

This does not only greatly speed up allocation, it also prevents memory
fragmentation to a large extent.

=head2 Synopsis

   struct Type : balloc<class Type,
                        int NewInit = 100,
                        void* (*Alloc) (size_t) = &::operator new,
                        void (*Dealloc) (void *) = &::operator delete,
                        void (*NDealloc) (void *, size_t) = NullNDealloc>
   {
   }

=over

=item Type

The type of elements you want allocated. This is always the inheriting
class's/struct's name.

=item NewInit

The number of elements that should be newly allocated if you use up
the last pre-allocated element.

=item Alloc

An C<operator new> of your choice that takes a C<size_t>.

=item Dealloc

An C<operator delete> of your choice that takes a C<void *>.

=item NDealloc

An C<operator delete> of your choice that takes a C<void *> and a C<size_t>.
Useful if your deallocation routine needs to know the size of the object.

=back


=head2 Usage

   struct mystruct : balloc<mystruct>
   {
     char twentybytes[20];
     int tenintegers[10];
   };

   int
   main ()
   {
     // optional: you can pre-allocate an arbitrary number of mystructs
     // or stick with the default of 100
     mystruct::initialise (200); // pre-allocate 200 mystructs
   
     mystruct *ms = new mystruct; // just as always. internally, nothing
                                  // gets allocated, except if you are
                                  // trying to allocate more objects than
                                  // were allocated by initialise
   
     delete ms; // give back the memory chunk to the pool
   
     mystruct::finalise (); // if you like, you can return the memory to
                            // the system on shutdown. this is neither
                            // needed nor recommended, though, because
                            // the system already does that itself.
   }

=head3 Further usages

   struct mystruct : balloc<mystruct,
                            200,
                            &myallocator::operator new,
                            &myallocator::operator delete>
   {
   }

=head4 Explanation

=over

=item 200

in this case is the number of blocks that should additionally be
allocated if we run out of them (defaults to 100).

=item The last two arguments

can be provided if you have a custom allocation routine (for instance if
you want to check if malloc actually allocated memory or if you ran out
of memory).

=back

   struct mystruct : balloc<mystruct,
                            200,
                            &myallocator::operator new,
                            NullDealloc,
                            &myallocator::operator delete>
   {
   }

=head4 Explanation

This example shows a way of using an overloaded C<operator delete (void *, size_t)>.
This is useful if you use C<g_slice_free1> do deallocate memory previously
allocated by C<g_slice_alloc0> in a custom C<operator new>.

Note that you do not have to give C<NullDealloc> as third argument, but it is
shorter to write than "&::operator delete", so it is provided for convenience.


=head2 Performance

The following was my result of the benchmark using test/balloc.t:

=over

=item huge struct balloc

0.19363 seconds

=item huge struct system malloc

18.3853 seconds

=item tiny struct balloc

0.0725439 seconds

=item tiny struct system malloc

0.303035 seconds

=item myuser balloc

1.62715 seconds

=item myuser system malloc

3.47373 seconds

=back

=head3 Observation

=over

=item - The 60KB hugestruct allocation is sped up by 9495%.

=item - The single-byte tinystruct allocation is sped up by 417%.

=item - The real-world myuser allocation is sped up by 213%.

=back

=head3 Conclusion

=over

=item - Large structs

The block allocator yields most when used on huge structures.

=item - Real world

In the real world (as shown by the myuser struct actually used in ermyth),
the difference is not as large due to construction and destruction.

=back


Another benchmark I did was looking at the CPU time distribution:

With balloc, allocating hugestruct (60KB):

   real         0m0.208s
   user         0m0.176s
   system       0m0.024s

With system malloc, allocating the same struct:

   real         0m18.646s
   user         0m2.308s
   system       0m15.969s

=head3 Observation

=over

=item - With balloc, system time (mostly allocation) is 11% of the total runtime

=item - With malloc, system time is 86% of the total runtime.

=back

=head3 Conclusion

=over

=item - Memory allocation is slow

(anything new?)

=item - With balloc, memory allocation is almost nil

The actual 0.024 seconds of system time were probably the pre-allocation,
meaning that with balloc, system time goes to zero leaving you precious
CPU time for real work.

=back


=head2 Rules

There are a few rules for your own protection that you should follow.

=over

=item Keep NewInit low

If you give NewInit (the second argument) very high values, allocation of
objects will slow down if you use up your last pre-allocated element.

=item Keep the initial number of chunks low

You should do tests and counts if possible to determine the amount of
chunks required in normal operation. Be aware that in the current version
of Ermyth, the block allocator does not do garbage collection. This means
that once chunks have been allocated, they remain allocated until
C<mystruct::finalise ()> is called.

=item Only call finalise () on program end

The above could make you like to do C<mystruct::finalise ()> every so often
to free unused memory. B<Do not do that>, as it will free used chunks as well.

=back