Re: [boost] Yet another bignum type

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2006-11-27 14:53:27

Maarten Kronenburg wrote:
> "Tobias Schwinger"  wrote in message
>>Maarten Kronenburg wrote:
>>>And I would like to use pointers, so runtime polymorphism is required.
>>
>>Why do you need runtime polymorphism to use pointers?
>>
>>Use pointers to a polymorphic base to battle the redundancy you invented
>>by not using a template in the first place?
>> 
>>>What do you need more for derivation?
>>
>>A compelling reason.
>>
>>And while we're at it: I don't see no reason for the allocator not to be a
>>template, either. You also wouldn't need an extra allocated_integer class.
>>Not to mention inconsistency with the STL (yeah, I notice there's an
>>additional reallocate member function in your allocator, but I guess it's
>>better to add it to std::allocator than to require a new, polymorphic one).
> 
> 
> The reason for derivation I already gave, also with the example of usage.

Theorem: An STL allocator can be turned it into an integer_allocator

    template<class STL_Allocator>
    class adapted_stl_allocator : public integer_allocator
    { 
      STL_Allocator & ref_that;
      // Or:
      // typename STL_Allocator::template rebind<unsigned>::other & ref_that;
      // to ensure T is always unsigned if that's what you want
   public:
      adapted_stl_allocator(STL_Allocator & that = STL_Allocator())
        : ref_that(that)
      { }

      ~adapted_stl_allocator()
      { }

      void * allocate( integer::size_type n )
      { return this->ref_that.allocate(n,0L); }

      // ...
    };

Now the expression "new adapted_stl_allocator<Alloc>(obj_alloc)" gives me an integer_allocator. 
Q.E.D. 

So where is the reason for integer_allocator to be part of the interface, again?

However, virtual function might be not the best thing to call from assembly level (because of ABI incompatiblities between different compilers) you might prefer to do a different kind of type erasure to create freestanding functions instead:
    
    namespace detail
    {
        template<class Allocator>
        void* allocate(void * allocator, size_t size, void const * hint = 0L)
        {
            return static_cast<Allocator*>(allocator)->allocate(size,
                static_cast<typename Allocator::const_pointer>(hint) );
        }
    }

Now the expression: "& detail::allocate<Allocator>(& alloc, size)" is an ordinary function pointer. Its type is: "void*(*)(void*,size_t,void const*)" (note that all the type information from the template arguments has been removed and that you have an address you can CALL).

> The STL allocator has a few drawbacks. How do you add two strings with
> different allocators? 

That's a property of std::string - not of the allocator. And there certainly is a way to make strings with different allocators addable without making the allocator polymorphic. In fact, I already presented more advanced techniques earlier in this discussion.

> As they become different template types (and not
> derived), you will get a compile-time error. This is not a problem for
> different char traits (which are impossible to concatenate anyway), but
> adding a differently allocated string could be possible. Another problem:
> when serialization of memory access is needed, how to do that with the STL
> allocator? 

Just implement it? Or better: use Boost.Pool and have a break ;-).

STL allocators are often just handles on static allocators. But since they are held by value they are more flexible and you could also use them to implement e.g. SBO, which is not possible with static allocators (but quite attractive for arbitrary precision integers, I figure).

> For the integer_allocator that is not a problem: just add a mutex
> to the static allocator object.  More allocated integer classes can even
> share the same static allocator object. 

There is no problem and this functionality is provided by Boost.Pool.

> Now I am not saying that the STL
> string or allocator design is wrong, because it is used in different
> contexts, but the priorities for the integer may be a bit different.

Yeah, but memory allocation should stay memory allocation and it might be hard to convince the comittee that another, polymorphic allocator is required...

>>What did you compare it to? The built-in type int? In that case I'd find
>>it very hard to believe that the overhead will be negligible (regardless of
>>the compiler and unless you have unacceptable overhead elsewhere)!
> 
> No, I compared the prefix operator++ of an integer class that is not derived
> with virtual member functions and operators, with one that is. The
> difference should then be the effect of the vtable.

Debug mode of a ten year old compiler, eh? ;-) 

Fact is, dynamic calls come at a much higher cost than addition - and a decent, optimizing C++ compiler will eat away wrapper code around an int (almost - if not) entirely. 

If you dynamically allocate every int you might be right. But you shouldn't, because it is possible to eliminate some dynamic allocation (even for arbitrary precision integers) with SBO and/or expression templates.

<snip>
>>
>>>...
>>>int main()
>>>{ modular_integer<1>::set_modulus( 16 );
>>>  modular_integer<2>::set_modulus( 11 );
>>>  allocated_integer<1>::set_allocator( & global_heap_a );
>>>  allocated_integer<2>::set_allocator( & global_heap_b );
>>>  integer x( 4 );
>>>  modular_integer<1> z( 10 );
>>>  allocated_integer<1> a( 3 );
>>>  integer * p = new allocated_integer<2>( -7 );
>>>  integer * q = new modular_integer<2>( 3 );
>>
>>That mix of tagging plus static functions is weird, at least (not to say
>>scary). I guess I might know what you're up to, though. What about a
>>template parameter that specifies the type of some Singleton for the modulus
>>and a template & ctor parameter for the allocator (a la STL)?
> 
> This is difficult to explain, but I will try it just the same. The integer
> (and its unsigned, modular and allocated variants) are basic types, just
> like for example the string is. 

AFAIK, the type string is just a typedef name for a template specialization...

> Now I agree it is possible to use singleton and object factories etc., 

You are probably misunderstanding me. What I'm talking about is e.g:

    struct my_modulus
    {
        static integer const & value();
    private:
        // whatever
    };

Passed in as template argument:

    modular_integer< my_modulus >

You could also provide a template to allow, e.g:

    modular_integer< integer_constant<123,456,789,012,345,678,901,234> > 

> but should these also be used for a basic type
> like an integer? The integer is very close to the hardware, it is more like
> a driver. A driver is always an abstract class interface with virtual
> functions. 

Yeah, but there are no unsigned drivers that inherit from fully implemented signed ones ;-).

> The integer should also be designed close to the hardware, with
> just the simple language elements. Hope this gives an answer to your
> question.

I don't see how "close to hardware" can be an excuse for design flaws.

How can I e.g. get a modular integer that uses an allocator?

This case is begging for templates but you avoid them at the high cost of a weird and inflexible design. 

Why? Are you using an outdated and broken compiler? Are you afraid that your optimized implementation might not fit in?

If so, update and/or discover the full potential of template-based techniques before jumping to conclusions.
Your interface needs serious work, IMO. It's not meant offensive in any way and I really hope you find the time and energy to pull it off.

Regards,

Tobias