Re: [boost] Proposed templated integer_sort

From: Steven Ross (spreadsort_at_[hidden])
Date: 2008-07-09 10:30:08

On Wed, Jul 9, 2008 at 12:42 AM, Daryle Walker <darylew_at_[hidden]> wrote:

> On Jul 8, 2008, at 5:01 PM, Steven Ross wrote:
>
>  On Tue, Jul 8, 2008 at 9:25 AM, Phil Endecott <
>> spam_from_boost_dev_at_[hidden]> wrote:
>>
>>  Steven Ross wrote:
>>>
>>>  [SNIP]
>
>>  - Does it work with uint64_t?  I see some variables declared as 'long',
>>>
>>>> which often can't store a uint64_t.
>>>>>
>>>>>
>>>> There exists the problem of how to identify and deal with negatives.  I
>>>> try
>>>> to avoid forcing any particular return data type
>>>>
>>>>
>>> Why not just use Iterator::value_type (or whatever it's called; or some
>>> iterator_traits thing) everywhere?
>>>
>>>  They are already divided
>>>
>>>> by 512, so an unsigned should fit inside a signed data type without
>>>> trouble.
>>>>
>>>>
>>> Dividing a 64-bit value by 512 does not make it small enough to fit in a
>>> 32-bit long.  (Have I misunderstood you?)
>>>
>>>
>> I was suggesting using an int64_t, which will hold a 64-bit value, so yes,
>> there was a misunderstanding.
>> The problem is that I need to use the return type of the user's >> method,
>> and with the same code supporting any-size data and both signed and
>> unsigned
>> integers, I need a data type that can support all the different
>> possibilities.
>> Is there some way I can grab the return type of the user's >> method and
>> use
>> it directly?
>> Otherwise, I think int64_t should work as long as it's fast until people
>> start using 128-bit values.
>>
>
> Why not use boost::uintmax_t?

All these type problems can be resolved by using a trick from the standard
library.  I call >> on the first element inside the integer_sort call, and
then template the rest of the calls on the type of the returned class.  This
extra call is made exactly once, and Spreadsort isn't used on less than 4000
elements, so the runtime overhead is constant and trivial.
I've also added a 1% speed improvement, based upon something I learned from
investigating Phil's testcase, and verified across my test suite.  It's not
much, but they add up.  Spreadsort is not done being optimized.
I'm not done implementing Phil's suggestions, but the latest version is
attached.