-----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-----