View mode: basic / threaded / horizontal-split · Log in · Help
December 28, 2008
Re: 128 bit signed and unsigned integer types
> Does anyone have a use for these?

I use sum area tables in my research and currently restrict the problem  
size to avoid overflow issues, so a longer integer type would be useful.
December 28, 2008
Re: 128 bit signed and unsigned integer types
Walter Bright wrote:
> You know, the unimplemented 128 bit integer types.
> Does anyone have a use for these?

In distributed systems, *a lot*.

1. In network programming, IPv6 addresses are becoming very common
(nobody should ever think about writing a network-enabled application
without native IPv6 support nowadays). IPv6 addresses are 128-bit. No
arithmetic is needed, just copy, comparison and bitwise, masking and
bitshift operations.

2. Also, UUIDs[1] and other similar universal identification schemes are
very common, we use them all the time in distributed systems. They are
128-bit numbers, only copy, comparison and bitwise operations are needed.

3. In cryptography, also very common in distributed systems, it is
common to have symmetric ciphers with key sizes of 128 and 256-bits. We
currently have to break the cypher blocks in peaces and move a lot of
the complexity up to the algorithm level in order to process such data
in 32 or 64-bit registers and variables. It would be great if
cryptographers could trust compilers to do this in the lower level
(properly using SSE registers and so).

In all these cases, bigints are completely inadequate. I currently have
to use (for the first two cases) a struct with operators implemented in
asm (with different versions for x86 and x64) for efficient manipulation
of these numbers. All this in C and C++.


[1] http://en.wikipedia.org/wiki/Universally_Unique_Identifier
December 28, 2008
Re: 128 bit signed and unsigned integer types
Andrei Alexandrescu wrote:
> If 128-bit built-in integer can't be made more efficient by moving them 
> in the core, then the question is really "do you need 128-bit literals?" 
> because that's all the built-in feature would bring over a library.

The literals would be an issue, otherwise you get into the std::string 
problem where:

s + "abc"

works, but:

"abc" + "def"

does not.

If it's not built-in, you also lose the constant folding and math 
identity stuff.
December 28, 2008
Re: 128 bit signed and unsigned integer types
Don wrote:
> Otherwise, it's hard to imagine many cases where 64 bits are inadequate 
> but 128 bits are enough.

Counting the federal deficit comes to mind.
December 28, 2008
Re: 128 bit signed and unsigned integer types
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
> Walter Bright wrote:
> > John Reimer wrote:
> >> Hello Walter,
> >>
> >>> You know, the unimplemented 128 bit integer types.
> >>>
> >>> Does anyone have a use for these?
> >>>
> >>
> >>
> >> Was that "cent" and "ucent"?
> >
> > yes.
> >
> >> Would any of these map well to SSE Instructions on Intel CPU's?
> >
> > Not a chance :-(
> Then it looks like we better leave large fixed-size integers to a library.
> Andrei

Something that I still don't think has been made very clear in this discussion
that I'm very curious about:  How efficient would these large fixed-size ints be
(on 32-bit hardware)?  Would they be almost as fast as 64-bit, almost as slow as
bigints, or somewhere roughly in the middle?  Obviously on 64-bit hardware they
can be made fast, but if that's the only place they can be made fast, then I think
it's more important that DMD support 64-bit hardware first.
December 28, 2008
Re: 128 bit signed and unsigned integer types
dsimcha wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
>> Walter Bright wrote:
>>> John Reimer wrote:
>>>> Hello Walter,
>>>>
>>>>> You know, the unimplemented 128 bit integer types.
>>>>>
>>>>> Does anyone have a use for these?
>>>>>
>>>>
>>>> Was that "cent" and "ucent"?
>>> yes.
>>>
>>>> Would any of these map well to SSE Instructions on Intel CPU's?
>>> Not a chance :-(
>> Then it looks like we better leave large fixed-size integers to a library.
>> Andrei
> 
> Something that I still don't think has been made very clear in this discussion
> that I'm very curious about:  How efficient would these large fixed-size ints be
> (on 32-bit hardware)?  Would they be almost as fast as 64-bit, almost as slow as
> bigints, or somewhere roughly in the middle?  Obviously on 64-bit hardware they
> can be made fast, but if that's the only place they can be made fast, then I think
> it's more important that DMD support 64-bit hardware first.

Assume we define a FixedInt(uint bits) structure. That would contain the 
value in-situ so there is no dynamic allocation, no indirection, and 
full-blown copying. For built-in sizes, FixedInt will alias itself away, 
for example:

template FixedInt(uint n) if (n == 8) { alias byte FixedInt; }
template FixedInt(uint n) if (n == 16) { alias short FixedInt; }
template FixedInt(uint n) if (n == 32) { alias int FixedInt; }
template FixedInt(uint n) if (n == 64) { alias long FixedInt; }

That's nice because it allows you to use FixedInt with a parameterized 
size throughout, yet still take advantage of builtin optimizations 
whenever applicable.

For the larger sizes and operations my guess would be that FixedInt will 
be close to what can be achieved via built-ins.


Andrei
December 28, 2008
Re: 128 bit signed and unsigned integer types
I could use them for a certain neural network implementation I'm working on 
if they are fast for boolean operations.

"Walter Bright" <newshound1@digitalmars.com> wrote in message 
news:gj6vrj$2lj4$1@digitalmars.com...
> You know, the unimplemented 128 bit integer types.
>
> Does anyone have a use for these?
December 28, 2008
Re: 128 bit signed and unsigned integer types
Andrei Alexandrescu wrote:
> dsimcha wrote:
>> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s
>> article
>>> Walter Bright wrote:
>>>> John Reimer wrote:
>>>>> Hello Walter,
>>>>>
>>>>>> You know, the unimplemented 128 bit integer types.
>>>>>>
>>>>>> Does anyone have a use for these?
>>>>>>
>>>>>
>>>>> Was that "cent" and "ucent"?
>>>> yes.
>>>>
>>>>> Would any of these map well to SSE Instructions on Intel CPU's?
>>>> Not a chance :-(
>>> Then it looks like we better leave large fixed-size integers to a
>>> library.
>>> Andrei
>>
>> Something that I still don't think has been made very clear in this
>> discussion
>> that I'm very curious about: How efficient would these large
>> fixed-size ints be
>> (on 32-bit hardware)? Would they be almost as fast as 64-bit, almost
>> as slow as
>> bigints, or somewhere roughly in the middle? Obviously on 64-bit
>> hardware they
>> can be made fast, but if that's the only place they can be made fast,
>> then I think
>> it's more important that DMD support 64-bit hardware first.
>
> Assume we define a FixedInt(uint bits) structure. That would contain the
> value in-situ so there is no dynamic allocation, no indirection, and
> full-blown copying. For built-in sizes, FixedInt will alias itself away,
> for example:
>
> template FixedInt(uint n) if (n == 8) { alias byte FixedInt; }
> template FixedInt(uint n) if (n == 16) { alias short FixedInt; }
> template FixedInt(uint n) if (n == 32) { alias int FixedInt; }
> template FixedInt(uint n) if (n == 64) { alias long FixedInt; }
>
> That's nice because it allows you to use FixedInt with a parameterized
> size throughout, yet still take advantage of builtin optimizations
> whenever applicable.
>
> For the larger sizes and operations my guess would be that FixedInt will
> be close to what can be achieved via built-ins.
>
>
> Andrei

is it possible to make int/long/short/etc internal to the compiler and 
use the above FixedInt in the language? there shouldn't be any 
performance differences between an old-style int and the above 
FixedInt!(32), for instance.
this way all the different types are reduced to one built-in type that 
looks like a template. similar to the way C++ uses the template syntax 
for casts like static_cast<type>(var) even though it's usually 
implemented inside the compiler.

also, this approch can be expanded to eliminate also size_t (which to me 
seems ugly).
libs could perhaps extend the same interface and add a BigInt as well.
December 29, 2008
Re: 128 bit signed and unsigned integer types
Yigal Chripun wrote:
> Andrei Alexandrescu wrote:
>> dsimcha wrote:
>>> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s
>>> article
>>>> Walter Bright wrote:
>>>>> John Reimer wrote:
>>>>>> Hello Walter,
>>>>>>
>>>>>>> You know, the unimplemented 128 bit integer types.
>>>>>>>
>>>>>>> Does anyone have a use for these?
>>>>>>>
>>>>>>
>>>>>> Was that "cent" and "ucent"?
>>>>> yes.
>>>>>
>>>>>> Would any of these map well to SSE Instructions on Intel CPU's?
>>>>> Not a chance :-(
>>>> Then it looks like we better leave large fixed-size integers to a
>>>> library.
>>>> Andrei
>>>
>>> Something that I still don't think has been made very clear in this
>>> discussion
>>> that I'm very curious about: How efficient would these large
>>> fixed-size ints be
>>> (on 32-bit hardware)? Would they be almost as fast as 64-bit, almost
>>> as slow as
>>> bigints, or somewhere roughly in the middle? Obviously on 64-bit
>>> hardware they
>>> can be made fast, but if that's the only place they can be made fast,
>>> then I think
>>> it's more important that DMD support 64-bit hardware first.
>>
>> Assume we define a FixedInt(uint bits) structure. That would contain the
>> value in-situ so there is no dynamic allocation, no indirection, and
>> full-blown copying. For built-in sizes, FixedInt will alias itself away,
>> for example:
>>
>> template FixedInt(uint n) if (n == 8) { alias byte FixedInt; }
>> template FixedInt(uint n) if (n == 16) { alias short FixedInt; }
>> template FixedInt(uint n) if (n == 32) { alias int FixedInt; }
>> template FixedInt(uint n) if (n == 64) { alias long FixedInt; }
>>
>> That's nice because it allows you to use FixedInt with a parameterized
>> size throughout, yet still take advantage of builtin optimizations
>> whenever applicable.
>>
>> For the larger sizes and operations my guess would be that FixedInt will
>> be close to what can be achieved via built-ins.
>>
>>
>> Andrei
> 
> is it possible to make int/long/short/etc internal to the compiler and 
> use the above FixedInt in the language? there shouldn't be any 
> performance differences between an old-style int and the above 
> FixedInt!(32), for instance.
> this way all the different types are reduced to one built-in type that 
> looks like a template. similar to the way C++ uses the template syntax 
> for casts like static_cast<type>(var) even though it's usually 
> implemented inside the compiler.

Well it's possible but probably too verbose for many. I mean, if I had 
only FixedInt, I'd first define int, short et al as aliases :o).

Andrei
December 29, 2008
Re: 128 bit signed and unsigned integer types
On Sun, 28 Dec 2008 17:17:03 -0200, Miles wrote:

> Walter Bright wrote:
>> You know, the unimplemented 128 bit integer types. Does anyone have a
>> use for these?
> 
> In distributed systems, *a lot*.
> 
> 1. In network programming, IPv6 addresses are becoming very common
> (nobody should ever think about writing a network-enabled application
> without native IPv6 support nowadays). IPv6 addresses are 128-bit. No
> arithmetic is needed, just copy, comparison and bitwise, masking and
> bitshift operations.
> 
> 2. Also, UUIDs[1] and other similar universal identification schemes are
> very common, we use them all the time in distributed systems. They are
> 128-bit numbers, only copy, comparison and bitwise operations are
> needed.
> 
> 3. In cryptography, also very common in distributed systems, it is
> common to have symmetric ciphers with key sizes of 128 and 256-bits. We
> currently have to break the cypher blocks in peaces and move a lot of
> the complexity up to the algorithm level in order to process such data
> in 32 or 64-bit registers and variables. It would be great if
> cryptographers could trust compilers to do this in the lower level
> (properly using SSE registers and so).
> 
> In all these cases, bigints are completely inadequate. I currently have
> to use (for the first two cases) a struct with operators implemented in
> asm (with different versions for x86 and x64) for efficient manipulation
> of these numbers. All this in C and C++.
> 
> 
> [1] http://en.wikipedia.org/wiki/Universally_Unique_Identifier

Good point.
1 2 3 4 5
Top | Discussion index | About this forum | D home