Re: [boost] [xint] Question about suitability, portability, and "Boostiness"

Subject: Re: [boost] [xint] Question about suitability, portability, and "Boostiness"
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2010-04-13 01:26:27

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 04/13/2010 12:33 AM, Scott McMurray wrote:

>> Right now, the XInt library uses a pointer to a (privately defined)
>> struct. The struct has several items, including a small array of "quick
>> digits" and a pointer to a dynamically allocated array of digit_t types,
>> both for containing the magnitude of the integer.
> 
> The most important optimization for me is the SBO.  If the magnitude
> of the int in question is less than 2**30, it should take no dynamic
> storage at all.  (In addition to space gains, this is a big win for
> exception-safety too.)

SBO = Small B??? Optimization?

That's easily done. It's what the aforementioned "quick digits" are used
for at present. Of course, it means that the space taken up by those
digits will be wasted on every integer that's larger than they can hold.

>> It's an old C trick, apparently legitimized in the C99 standard as the
>> "struct hack". For those not familiar with it, the idea is that I'd
>> allocate a single array of digit_t types, of the required size plus
>> sizeof(new_data_t), then just typecast it as a pointer of type new_data_t.
>>
>> Does anyone know if there's any reason not to do this? Maybe some
>> portability or alignment problem with it?
> 
> I believe the official C way is that the last element is an array
> without a listed length (digits_type digits_[];),

Yes, if you've got a C99-compatible compiler. The trick has been in use
for a lot longer than that though, I first heard about it in the
mid-eighties. Using an array of size 1 allows any C or C++ compiler to
use it.

> so you malloc once for the whole type and use the array being sure
> not to overrun the space you allocated.  I'm not convinced such
> tricks are officially allowed in C++, given that the new/delete model
> doesn't offer any way to use them.

They weren't "officially allowed" in C prior to C99 either, but a lot of
smart people used them anyway. :-) The new/delete model doesn't rule
them out, if you use an array for storage, and the struct you're
overlaying on it doesn't require a constructor or destructor. I think
you could even use a placement-new to allow for those, but that's beyond
what I'd need here.

> Since you just have integral types, why not just allocate new 
> digits_type[allocated+2] and know that index 0 is used and index 1
> is allocated? I doubt anyone would be too concerned about not being 
> able to store 2**37-bit integers.

I considered that too, but a digit_t could be as small as sixteen bits
on some systems (it's defined as half the size of the largest native
integer type the system supports). That could overflow in some rare but
not-too-contrived cases. For example, since it would also have to be
used for the number of copies in the copy-on-write system, I can see
someone making more than 64K copies of a particular number, maybe as a
default number in a container.

I can work around that problem fairly easily if necessary, but the
"struct hack" method is cleaner, if there isn't a good reason to avoid it.
- -- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkvEAH8ACgkQp9x9jeZ9/wRREgCgn0jP40u+vHlOSKOFZovyWpab
n90AnRd1TBMHbE4N2obH4THBdHpMQSFU
=mKCy
-----END PGP SIGNATURE-----