December 28, 2008
> 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
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
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
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
== 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
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
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
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
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
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.