Re: [boost] [xint] Fourth release, requesting preliminary review again

Subject: Re: [boost] [xint] Fourth release, requesting preliminary review again
From: Jeffrey Lee Hellrung, Jr. (jhellrung_at_[hidden])
Date: 2010-06-03 17:28:47

On 6/3/2010 9:53 AM, Chad Nelson wrote:
> On 06/03/2010 09:40 AM, Marius Stoica wrote:
[...]
>>>> It's just a compile-time option like the other ones.
>>>
>>> Not entirely, due to those two extra functions. And logically it's a
>>> distinct type.
>>
>> The more i think about it i think you should go for a policy based design.
>> Rigth now there is the obvious problem that you don't have a
>> nothrow_fixed_integer.
>
> I don't see that as a problem. The fixed_integer class is a convenience,
> because one fellow here requested it; it does nothing that
> nothrow_integer can't do just as well and nearly as easily.
>
>> Maby you can do something like this :
>>
>> integer_t<
>> 	throws<false>,
>> 	size<128>, // 0 means unlimited
>>   	thread_safe<false>>  myint;
>>
>> You could also have some other policies
>>    -overflow policy( become nan, overflow to negative)
>>    -signed/unsigned policy
>
> I'm not sure that's really an improvement. The current design separates
> throwing and nonthrowing for a reason; take a look at some of the
> function implementations and you'll see why. Combining those would mean,
> at the very least, an extra if statement in every function.

If by "an extra if statement" you mean an extra compile-time dispatch, 
then yes, but there wouldn't (or shouldn't, if done correctly) be any 
runtime overhead.  I can see Marius' point of unifying all the integer 
classes under a single templated class xint::integer_t, but I imagine it 
will require quite a bit of refactoring.  Whether to do this or not, and 
actually doing it if it should be done, is not the tallest nail right 
now (or is it?).

>>> That might save a few bytes of memory, but it would make the
>>> entire library slower, because it would have to check to see
>>> whether to use the data_t object or not before every operation.
>>> Memory isn't so precious that I'd consider that a good trade-off.
>>
>> Doesn't seem to bad to me, the advantages quite serious
>> -if you have a lot of small ints you save a lot of memory( i think an data_t
>> would be more than 3x larger)
>
> If you have a lot of small ints, you're better off storing them as ints
> and constructing large integer types from them if and when necessary.
> The library is explicitly designed for storing and manipulating *large*
> integers, things that are too big for the built-in types. I'd rather not
> dilute that by trying to make it all things to all people.

It would be nice to have the performance (or some significant fraction 
thereof) of small integers initially, and have it "nicely transition" 
into arbitrary precision integers automatically.  Manipulations with 
small integers right now are probably dominated by memory management. 
Again, this behavior might be most appropriate using another policy (the 
maximum size of an immediate integer before moving it out to 
dynamically-allocated remote memory).  Again, likely not the tallest 
nail; I would put it on the "to be considered in the future" list.

> Not part of the library's design goals. The expense of dynamic memory
> allocation is dwarfed by the time it takes to process numbers of any
> reasonable size.

Agreed.

>> For that you will need to
>>
>> -add a few instructions to every function(not very much)
>> -check a flag (not very costly xoring and comparing are the cheapest ops and it
>> will have good branch prediction )
>> -add another pointer(probably the most serious issue, but you already have a 3
>> pointer indirection -  maby you can make it so you can keep that ? )
>
> The fact that it takes any at all means that it would slow the library
> down further. Just adding support for user-selected allocators slowed it
> down by 2.3 to 2.5 percent, something I am not very happy about. I'd
> need a *very* compelling reason to slow it any further.

Wait...adding support for custom allocators slowed things down over raw 
new/delete???  That doesn't sound right, though the 2~3% hit might be 
quality of compiler...

You can dispatch (select) between immediate and remote representations 
via a single function call through a function pointer, so you'll pay a 
minimum of that, plus any additional logic you need to switch between 
representations (which can probably be immediate -> remote most of the 
time).  I don't think small-object-optimization should be written off 
right away, but yeah, I can see where it doesn't fit into your immediate 
design goals.

I'll have to review this incantation of the library when I get some free 
time.

- Jeff