Re: [boost] Infinite precision integer draft

From: Jarrad Waterloo (jwaterloo_at_[hidden])
Date: 2006-05-31 09:55:12

Sorry for confusing us both! When I say heap I was referring to memory
allocated dynamically via the POSIX methods or C++ new/delete. Although the
majority of my background has been in a Win32 environment when I deal with
standard C++ and boost the word Microsoft doesn't enter into my vocabulary.

I was working/speaking under the mistaken assumption that each instance of
integer has its own allocator by type as in the standard library or at
runtime as many but not all wish it. As such I thought integer_allocator was
an interface or close to one and there was a separate class that implements
that interface or abstract class that had the code for the dynamic memory
allocations. I totally missed the following sentences in the spec.

> The abstract class integer allocator provides the interface to provide a
> user-defined derived allocator class for class integer. Classes derived
> from this class can only be used as static allocators for other classes
> derived from class integer.
> Makes the static allocator active for all integer memory allocations.

What I was hoping to be able to do was something like this?
integer<stack_allocator<T> > or integer(stack_allocator<T>) or integer<T>
where T is the minimum number of bits, minimum number of bytes or minimum
number of longs (bits may be better as the internal implementation may very
from processor to processor). The implementation is simple because the size
of the stack_allocator or stack_integer is allocated at compile time on the
stack. As allocate will just return the already allocated memory and
deallocate will do nothing.
The demand for this is the need/preference for large finite precision
numbers. Currently C++ provides the ability to work with small finite
numbers and integer provides infinite precision numbers. This addition would
fill in the gap between the two with many of the strength and advantages of
both worlds without negating the need to be able to go to either extreme.
Your code is capable of filling this gap it just needs the ability to limit
itself to stack operations on a per instance basis. This request is similar
to the differences between std::bitset<T> and boost::bitset. Sure
boost::bitset can do everything std::bitset can do but users will still use
std::bitset for efficiency when they know the size up front since it is
created on the stack and the other is dynamically allocated. Users just want
the two to have a common base class which can't currently be done as that
will change the std. However as yours is a new library, I was hoping it
would handle this need and do it correctly from the beginning.

With the current design how would one do this? Deriving from
integer_allocator is straight forward but what must one do to a derived
integer to use this new allocator? If you do concur that this is a need
wouldn't it be good to go ahead and provide an implementation of
stack_integer and stack_integer_allocator that can do this so users don't
have to keep reinventing the wheel. Further could there be any changes to
the allocator architecture to make things easier not from its interface
standpoint but from from how it is used and stored to get better reuse
especially with all this talk on unsigned integer and modulus integer. I
would hate to see stack variants for all three.

-----Original Message-----
From: Maarten Kronenburg [mailto:M.Kronenburg_at_[hidden]] 
Sent: Tuesday, May 30, 2006 3:46 PM
To: Jarrad Waterloo
Subject: Re: Infinite precision integer draft

Jarrad,
Thanks for your reply.
The default integer_allocator used by integer
use the standard POSIX malloc, realloc and free
functions. You are right that I should add
this remark to the spec document.
The making of a heap_allocator is trivial,
using HeapCreate and HeapDestroy,
and HeapAlloc, HeapReAlloc and HeapFree.
But this only works on Win32 systems,
so this cannot be added to the spec.
Your stack_integer_allocator<size_t>,
how would that allocate, reallocate
and deallocate look like?
Do you have such an implementation ?
Or a literature reference where I can find it ?
When I have an implementation, then I feel
safe to add it to the spec.
Regards, Maarten.

----- Original Message ----- 
From: "Jarrad Waterloo" <jwaterloo_at_[hidden]>
To: "'Maarten Kronenburg'" <M.Kronenburg_at_[hidden]>;
<boost_at_[hidden]>
Sent: Tuesday, May 30, 2006 5:12 PM
Subject: RE: Infinite precision integer draft

> Thanks for the welcome of all the other enhancements, especially in the
area
> of conversion, to make your integer library easy to use for everyone.
>
> Further, don't get discouraged as your colleagues discuss the meaning of
0,
> life and the universe while people who actually would use it already
> understand what 0 means because we have been without, 0, this library for
so
> long.
>
> 'Feed a mouse a cookie and he will ask for a glass of milk.'
>
> > Creating integers with variable size on the stack,
> > that is in any case something that I will not
> > specify, but users that want to use these tricks
> > can just override the integer_allocator.
>
> Currently you have an integer class which takes an integer_allocator base
> class. Even though the spec doesn't mention this or I glossed over reading
> it but you probably are going to provide a heap_integer_allocator class
that
> could be named whatever but exists as the default integer_allocator for
the
> integer class. This way users can just start using the library right away
> instead creating there own allocator the first time they use this library.
>
> What I was suggesting was not a change to the integer, integer_allocator
> base class or the currently unnamed heap_integer_allocator! Rather the
> addition of a stack_integer_allocator<size_t> : public integer_allocator.
>
> The reasons for the library to provide this instead of the end user is as
> follows:
> 1) Performance, stack based allocations are faster than heap based and in
> some field domains one will know the upper limit on size. This generates
the
> need for multiple people wanting to do this especially when performance
> matters.
> 2) Standardization, if you foresee that many people are going to need this
> functionality than your library becomes easier because you can go ahead
and
> provide the class instead of a large unsigned integer of people having to
> reinvent the wheel and create the exact same class themselves.
> 3) Maintain ease of use as complexity increases, in just this one area
this
> library could suffer from the opposite problem of the standard library.
The
> standard library algorithms was all passing 2 iterators around which
allows
> for maximum flexibility for more complicated scenarios but lacked the
> overrides like boost Range where you could pass the collection and the
> algorithm uses begin and end for the more common and simple scenarios.
> Integer library does the opposite which is mostly good, it provides the
heap
> allocator for the most common and general use but as complexity increases
> and someone needs stack based allocator the user is left in the lurch and
> have to right there own, over and over again from user to user. I just
> believe this library would be more feature complete if it would just go
> ahead and provide the both implementations up front.
> 4) Architectural consistency, this library is designed to behave like
> existing integer types that can be created both on the stack and on the
> heap.
>
>
>
>
>