API changes have landed: #include "mozilla/StdInt.h" to use <stdint.h> types

[Jeff Walden]

Earlier today I landed patches for bug 704313. With them in place, you can now simply #include "mozilla/StdInt.h" from MFBT and start using the <stdint.h> standard types throughout Mozilla code, on any platform, and things should Just Work. StdInt.h presents exactly the same interface as <stdint.h>, even down to the __STDC_LIMIT_MACROS junk you need to get access to UINT32_MAX and the like in C++. (SpiderMonkey's generated js-config.h defines this unconditionally; it might be worth doing the same in mozilla-config.h. That's a task for someone else who needs it, I think.)

For now, I'd say avoid using StdInt.h if you're defining a cross-file interface, and use it for intra-file things for the moment. There may still be some bumpiness to work out with using it in interfaces, and until we're reasonably sure everything is good, it's probably best to avoid maybe getting burned. (Interfaces probably will be changed with a mass rewrite at some point, so you won't be hurting yourself in the long run.)

Right now the big user of the stdint types is the JS engine, which now includes that file and bases all its own types (uint32 and such) on them through typedefs. However, Gecko itself does have some users -- WOFF decoding, gfx, and a few other places that previously rolled their own <stdint.h> types now use StdInt.h. (This raises one issue for the future: if you're importing new libraries into the tree, you'll have to take into account whether those libraries define stdint.h types or not -- if they do, some workaround will be necessary. Possible options: a downstream patch; getting a #define added upstream that, when set, will cause that code to not define those types; something else, perhaps.)

Sometime after this we'll probably start switching the XPCOM types over to use the new stdint types. This could be a little tricky, but it should be doable. I am not going to take on this task myself. Someone with experience with the big rewriting tools is best equipped to do it. I'll be making the switch, more or less, in the JavaScript engine itself, and to a certain extent in in-tree JSAPI users, though -- there's enough value to us JS hackers that it's worth my time to do that myself.

Anyway: start using stdint types now after an #include "mozilla/StdInt.h". (I recommend putting this at the very start of your file for simplicity, but it should work fine in general after other headers.)

Jeff

[Benoit Jacob]

Really great news. I'll update CheckedInt to use stdint types.

Benoit

2011/12/8 Jeff Walden <jwald...@mit.edu>:

> _______________________________________________
> dev-platform mailing list
> dev-pl...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-platform

[Gervase Markham]

On 08/12/11 23:00, Jeff Walden wrote:
> Anyway: start using stdint types now after an #include
> "mozilla/StdInt.h". (I recommend putting this at the very start of your
> file for simplicity, but it should work fine in general after other
> headers.)

Hi Jeff,

For my own enlightenment: what does all of this work get us? Is it a
code clarity thing, a performance win, or something else?

(I'm not suggesting there's no reason - I just want to be clued in! :-)

Gerv

[Benoit Jacob]

2011/12/9 Gervase Markham <ge...@mozilla.org>:

Using standard types instead of PR ones means:

1. that our code is easier to share with other projects and easier to
read by newcomers / external people.
-> For example CheckedInt has been adopted by WebKit and they had
to manually replace our use of PR types by standard integer types. Now
we will be able to share the exact same code.

2. that templates will not be instantiated more times than necessary,
avoiding executable code bloat. Different types with the same
properties (e.g. int64_t vs PRInt64 vs long long...) might or might
not be treated as the same type in the C++ compiler. If they're not,
then we get redundant copies of templated code. Eliminating redundant
types means that we no longer rely on compiler details, we always
avoid code bloat.

Benoit

[Jeff Walden]

On 12/09/2011 06:47 AM, Gervase Markham wrote:
> For my own enlightenment: what does all of this work get us? Is it a
> code clarity thing, a performance win, or something else?

There's the approachability/clarity bit Benoit mentions. (I'd place less emphasis on reduced template expansions, myself, because inline templates, as most are, should be foldable by a smart compiler, if the types are machine-level-equivalent. I don't know whether any compilers do this.)

The practical benefit to existing developers is that it reduces the number of *incompatible* fixed-size types. Type compatibility is determined at the level of the underlying C type. |unsigned int| and |unsigned long| are not the same type, even if they're machine-level-equal. So if you have |typedef unsigned int uint32;| in one header, and |typedef unsigned long uint32;| in another, you will get problems. If both typedefs show up at once it'll be a compile-time error -- obnoxious but easily diagnosed. When you only get one showing up, problems start showing up at link time. Suppose in C++ you have this definition:

void frob(uint32* u);

And this use:

uint32 u;
frob(&u);

Now suppose the definition sees |typedef unsigned int uint32;| and the use sees |typedef unsigned long uint32;|. This is possible because the typedefs may be in different files, but each file is guarded by the same #include guard -- PROTYPES_H, for example -- and whichever gets included first is what gets used. Because C++ includes argument types in mangled symbols, the two frobs will use different symbols -- one including unsigned long, one including unsigned int. This code will *compile* fine, but when the linker tries to match uses with definitions, it'll complain about an undefined reference to "frob(unsigned long*)", not knowing we were looking for the "frob(unsigned int*)" definition.

The problem is the code *looks* right. If you're not looking out for this issue, it's going to take a long time to debug it. I can easily dig up half a dozen different instances mentioned in bugs or on IRC where people encountered this problem and had to spend time debugging it, usually at some length. One typedef for everyone will in the long run avoid this problem.

The full benefits of this don't pay off until we can switch from using the PR* types, and from using uint32-style types everywhere except in rare interactions with the IPC Chromium headers. The PR* types don't have the same definitions as the <stdint.h> types, nor do the IPC uint32 types have the same definitions as the <stdint.h> types, and there's nothing we can do about it. There will still be some linking errors (mostly on Windows, unfortunately) encountered as people try passing PRUint32* where uint32_t* was expected. But those will go away with further improvements.

Even in the short run, however, this change should eliminate the typedef incompatibility problems for JSAPI users (where we've most hit such incompatibilities). Use uint32_t with the JSAPI -- what the JSAPI headers will soon use -- and things will always work. The same could not be said, before this change, for using uint32.

Jeff

[Jeff Walden]

I also wrote a blog post about this, mostly covering the same ground but perhaps adding detail in some places:

http://whereswalden.com/2011/12/08/party-like-its-1999-stdint-h-comes-to-mozilla/

Jeff

[Gervase Markham]

Thanks for this :-)

Gerv

[Karl Tomlinson]

I have wondered why our code makes so much use of guaranteed width
types, but have followed the trend much of the time.

Now that stdint is proposed to replace integers in prtypes when
guaranteed width is required, I'll ask the question should regular
C types be used in situations where guaranteed width is not
required?

An advantage of regular C types is that it is clear/consistent how
integral promotion will affect the arithmetic. Types with fewer
bits than int get promoted to signed int for arithmetic, which,
for unsigned types, can lead to unexpected consequences from
overflow.
(e.g. https://bugzilla.mozilla.org/show_bug.cgi?id=651309)

Another advantage that I guess results from using plain C int or
unsigned int is that it generates minimal code, assuming int is
a "native" integer type for arithmetic on the processor.

[L. David Baron]

On Tuesday 2011-12-13 15:34 +1300, Karl Tomlinson wrote:
> I have wondered why our code makes so much use of guaranteed width
> types, but have followed the trend much of the time.
>
> Now that stdint is proposed to replace integers in prtypes when
> guaranteed width is required, I'll ask the question should regular
> C types be used in situations where guaranteed width is not
> required?

Speaking of integral types: I think we should also be using size_t
(and occasionally ptrdiff_t) considerably more widely. These types
should be the most likely to correspond to the size of the address
space, which makes them the right thing to use for things like array
sizes/lengths, allocation sizes, and reference counts.

-David

--
𝄞 L. David Baron http://dbaron.org/ 𝄂
𝄢 Mozilla http://www.mozilla.org/ 𝄂

[Jeff Walden]

On 12/12/2011 11:46 PM, L. David Baron wrote:
> Speaking of integral types: I think we should also be using size_t
> (and occasionally ptrdiff_t) considerably more widely. These types
> should be the most likely to correspond to the size of the address
> space, which makes them the right thing to use for things like array
> sizes/lengths, allocation sizes, and reference counts.

These aren't quite the types you mentioned, but note that there are still people babying along architectures where u?intptr_t is not the same as size_t. We probably don't use u?intptr_t that much outside the JS engine, but there are probably places where it would be preferable to use it where we aren't now. They may be fairly few, and I may have some tunnel vision on this point. :-) Just beware that size_t/intptr_t can be tricky things to use pedantically-correctly.

Note that ptrdiff_t (rather, how you generate it) has bad behavior when the pointers being subtracted differ by more than half the address space, because ptrdiff_t is a signed type. The PointerRangeSize method in mfbt is a workaround for this which returns a value in size_t. For this reason I tend to think ptrdiff_t is probably best avoided in many places -- and even beyond those places where it matters that you avoid it, the places where it doesn't matter serve as enough of an example to the places where it should that it seems best to use the safe thing all the time.

Jeff

[Mike Hommey]

On Tue, Dec 13, 2011 at 01:13:34AM -0500, Jeff Walden wrote:
> On 12/12/2011 11:46 PM, L. David Baron wrote:
> >Speaking of integral types: I think we should also be using size_t
> >(and occasionally ptrdiff_t) considerably more widely. These types
> >should be the most likely to correspond to the size of the address
> >space, which makes them the right thing to use for things like array
> >sizes/lengths, allocation sizes, and reference counts.
>
> These aren't quite the types you mentioned, but note that there are still people babying along architectures where u?intptr_t is not the same as size_t.

That would be me, with s390.

> We probably don't use u?intptr_t that much outside the JS engine, but there are probably places where it would be preferable to use it where we aren't now. They may be fairly few, and I may have some tunnel vision on this point. :-) Just beware that size_t/intptr_t can be tricky things to use pedantically-correctly.
>
> Note that ptrdiff_t (rather, how you generate it) has bad behavior when the pointers being subtracted differ by more than half the address space, because ptrdiff_t is a signed type. The PointerRangeSize method in mfbt is a workaround for this which returns a value in size_t. For this reason I tend to think ptrdiff_t is probably best avoided in many places -- and even beyond those places where it matters that you avoid it, the places where it doesn't matter serve as enough of an example to the places where it should that it seems best to use the safe thing all the time.

For all that, we could mandate we use size_t for all cases where
one may want to use u?intptr_t and ptrdiff_t.

Mike

[Benoit Jacob]

2011/12/12 L. David Baron <dba...@dbaron.org>:

> On Tuesday 2011-12-13 15:34 +1300, Karl Tomlinson wrote:

>> I have wondered why our code makes so much use of guaranteed width
>> types, but have followed the trend much of the time.
>>
>> Now that stdint is proposed to replace integers in prtypes when
>> guaranteed width is required, I'll ask the question should regular
>> C types be used in situations where guaranteed width is not
>> required?
>

> Speaking of integral types: I think we should also be using size_t
> (and occasionally ptrdiff_t) considerably more widely. These types
> should be the most likely to correspond to the size of the address
> space, which makes them the right thing to use for things like array
> sizes/lengths, allocation sizes, and reference counts.

I wholeheartedly agree with you and Karl (modulo the little
clarification about size_t != uintptr_t), we should use
"role-specific" rather than "size-specific" types.

This really matters for performance:

A while ago, I wrote to this list to complain that using PRUint32 as
the indexing type for arrays can make things over 10% slower on 64-bit
architectures, see:

http://groups.google.com/group/mozilla.dev.platform/browse_thread/thread/94a564192d4b4f71

I had a specific example in this thread, merge sort, that was 11% slower.

The reason is that on x86_64, pointer arithmetic wants 64-bit offsets,
so using 32-bit integers forces the compiler to add instructions to
fix expand them to 64bit. See the assembly in that thread.

Notice that int is 32bit on x86_64 so it would be wrong too. Really,
only size_t and ptrdiff_t are appropriate for array indexing!

Just to say that it really matters!

Benoit

>
> -David
>
> --
> 𝄞 L. David Baron http://dbaron.org/ 𝄂
> 𝄢 Mozilla http://www.mozilla.org/ 𝄂

[Kyle Huey]

On Tue, Dec 13, 2011 at 8:04 AM, Benoit Jacob <jacob.b...@gmail.com>wrote:

> Just to say that it really matters!
>

If we use size_t all the places where we should be using size_t, does it
matter then? I suspect the answer is no.

- Kyle

[Benoit Jacob]

2011/12/13 Kyle Huey <m...@kylehuey.com>:

Not sure I understand? We currently use PRUint32 in a lot of places
where we should be using size_t. See e.g. nsTArray.h and all the loops
we have that are iterating over nsTArray's using PRUint32 indices.

Benoit

>
> - Kyle

[Kyle Huey]

What I'm asking is if we fix all of these is there value in using
int,long,etc in place of uintN_t?

- Kyle

[Benoit Jacob]

2011/12/13 Kyle Huey <m...@kylehuey.com>:
>
>
> On Tue, Dec 13, 2011 at 8:15 AM, Benoit Jacob <jacob.b...@gmail.com>
> wrote:
>>
>> 2011/12/13 Kyle Huey <m...@kylehuey.com>:
>> > On Tue, Dec 13, 2011 at 8:04 AM, Benoit Jacob <jacob.b...@gmail.com>
>> > wrote:
>> >>
>> >> Just to say that it really matters!
>> >
>> >
>> > If we use size_t all the places where we should be using size_t, does it
>> > matter then?  I suspect the answer is no.
>>
>> Not sure I understand? We currently use PRUint32 in a lot of places
>> where we should be using size_t. See e.g. nsTArray.h and all the loops
>> we have that are iterating over nsTArray's using PRUint32 indices.
>
>
> What I'm asking is if we fix all of these is there value in using
> int,long,etc in place of uintN_t?

Ah, I understand the question now.

I would say that the decision chart to decide which type to use is
something like this, everytime one needs to choose an integer type:

1) Check if there is a role-specific type for what I need? E.g. size_t
for array indices, uintptr_t for pointer arithmetic, etc.
2) Otherwise, check if I need a type-specific type. E.g. 32-bit for
RGBA8888 pixels, etc.
3) Finally, if my use case isn't covered by an existing role-specific
type and exact size doesn't matter, fall back to a 'standard type'
like int, etc.

So yes, I do expect that there will still be use cases for 'int'. For
example, if I want to make a function that will compare two values a
and b and return +1, 0 or -1 depending on whether a>b, a==b or a<b,
then int is probably the sanest return type for it, because we don't
care about the size.

Benoit


>
> - Kyle
>

[Benoit Jacob]

2011/12/13 Benoit Jacob <jacob.b...@gmail.com>:

> 2011/12/13 Kyle Huey <m...@kylehuey.com>:
>>
>>
>> On Tue, Dec 13, 2011 at 8:15 AM, Benoit Jacob <jacob.b...@gmail.com>
>> wrote:
>>>
>>> 2011/12/13 Kyle Huey <m...@kylehuey.com>:
>>> > On Tue, Dec 13, 2011 at 8:04 AM, Benoit Jacob <jacob.b...@gmail.com>
>>> > wrote:
>>> >>
>>> >> Just to say that it really matters!
>>> >
>>> >
>>> > If we use size_t all the places where we should be using size_t, does it
>>> > matter then?  I suspect the answer is no.
>>>
>>> Not sure I understand? We currently use PRUint32 in a lot of places
>>> where we should be using size_t. See e.g. nsTArray.h and all the loops
>>> we have that are iterating over nsTArray's using PRUint32 indices.
>>
>>
>> What I'm asking is if we fix all of these is there value in using
>> int,long,etc in place of uintN_t?
>
> Ah, I understand the question now.
>
> I would say that the decision chart to decide which type to use is
> something like this, everytime one needs to choose an integer type:
>
> 1) Check if there is a role-specific type for what I need? E.g. size_t
> for array indices, uintptr_t for pointer arithmetic, etc.
> 2) Otherwise, check if I need a type-specific type. E.g. 32-bit for
> RGBA8888 pixels, etc.

Er, I meant 'size-specific' of course.

[Chris Peterson]

On 12/12/11 8:46 PM, L. David Baron wrote:
> Speaking of integral types: I think we should also be using size_t
> (and occasionally ptrdiff_t) considerably more widely. These types
> should be the most likely to correspond to the size of the address
> space, which makes them the right thing to use for things like array
> sizes/lengths, allocation sizes, and reference counts.

size_t can be 64-bits, which would bloat objects with size_t member
variables that rarely need to track array or allocation sizes larger
than 4GB.

size_t could also be problematic for reference counts. Since size_t is
unsigned, detecting reference count overflow or underflow with debug
asserts would be more difficult.

FWIW, Google's C++ Style Guide recommends using "naked" signed ints for
most integers:

https://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Integer_Types


chris

[Benoit Jacob]

2011/12/13 Chris Peterson <cpet...@mozilla.com>:

> On 12/12/11 8:46 PM, L. David Baron wrote:
>>
>> Speaking of integral types:  I think we should also be using size_t
>> (and occasionally ptrdiff_t) considerably more widely.  These types
>> should be the most likely to correspond to the size of the address
>> space, which makes them the right thing to use for things like array
>> sizes/lengths, allocation sizes, and reference counts.
>
>
>
> size_t can be 64-bits, which would bloat objects with size_t member
> variables that rarely need to track array or allocation sizes larger than
> 4GB.

First, that only applies to "storage" variables as opposed to local
variables in functions.
Then, one would have to have solid evidence to show that replacing a
size_t by a uint32 is worth it: otherwise that seems like premature
optimization.

>
> size_t could also be problematic for reference counts. Since size_t is
> unsigned, detecting reference count overflow or underflow with debug asserts
> would be more difficult.

Thankfully there's ptrdiff_t for when one needs a signed variant of size_t.

(Likewise, intptr_t vs uintptr_t)

>
> FWIW, Google's C++ Style Guide recommends using "naked" signed ints for most
> integers:
>
> https://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Integer_Types

I interprete this differently: AFAICS it only says that among
char,short,int,long,... they only use int.

In C++, size_t and ptrdiff_t are not built-in types, they're just
typedefs (in std:: namespace). So the google styleguide is not
excluding them.

Benoit



>
>
> chris

[Karl Tomlinson]

Chris Peterson writes:

> On 12/12/11 8:46 PM, L. David Baron wrote:
> size_t could also be problematic for reference counts. Since
> size_t is unsigned, detecting reference count overflow or
> underflow with debug asserts would be more difficult.

Perhaps not an issue in practice, but detecting signed integral
overflow with C++ (as of WG21/N1043 at least) is much harder than
unsigned overflow because the behaviour on signed integral
overflow is undefined.

"If during the evaluation of an expression, the result is not
mathematically defined or not in the range of representable
values for its type, the behavior is undefined, unless such an
expression is a constant expression (5.19), in which case the
program is ill-formed."

[Benoit Jacob]

2011/12/13 Karl Tomlinson <moz...@karlt.net>:

For use cases where we need to check for integer overflow, note that
we have the CheckedInt<T> class template.

Cheers,
Benoit

[Mike Hommey]

On Tue, Dec 13, 2011 at 11:55:17AM -0800, Chris Peterson wrote:
> On 12/12/11 8:46 PM, L. David Baron wrote:
> >Speaking of integral types: I think we should also be using size_t
> >(and occasionally ptrdiff_t) considerably more widely. These types
> >should be the most likely to correspond to the size of the address
> >space, which makes them the right thing to use for things like array
> >sizes/lengths, allocation sizes, and reference counts.
>
>
> size_t can be 64-bits, which would bloat objects with size_t member
> variables that rarely need to track array or allocation sizes larger
> than 4GB.

In practice, there are plenty of cases where even using a 32-bits int
type is going to waste 32-bits anyways. I'm pretty sure we have tons of
those.

Mike

#include <iostream>
struct A {
int i;
void *ptr;
};

struct B {
int i;
};

struct C: public B {
void *j;
};

int main() {
std::cout << sizeof(A) << " " << sizeof(B) << " " << sizeof(C) << "\n";
return 0;
}

[Nicholas Nethercote]

On Tue, Dec 13, 2011 at 2:32 PM, Mike Hommey <m...@glandium.org> wrote:
>>
>> size_t can be 64-bits, which would bloat objects with size_t member
>> variables that rarely need to track array or allocation sizes larger
>> than 4GB.
>

> In practice, there are plenty of cases where even using a 32-bits int
> type is going to waste 32-bits anyways. I'm pretty sure we have tons of
> those.
>

> #include <iostream>
> struct A {
>  int i;
>  void *ptr;
> };

But in a lot of those cases you can easily reorder to avoid the waste.
If you have a size_t you can't.

Nick

[Justin Lebar]

FWIW, Benoit and I played around with some compilers and arrays.

If you have a vanilla

for (T i = 0; i < n; i++) {
do_something_with(arr[i]);
}

loop, then it appears that this is just as fast for T == PRUint32 and
T == size_t on x86-64.

But if you have inside the loop

do_something_with(arr[i*2]);

then gcc and clang are able to optimize the loop better if T ==
size_t. (In the size_t case, the compiler changes the loop index from
i to 2*i, but with PRUint32, it multiplies i by 2 in every step.)

This appears to apply to nsTArrays as well as raw arrays.

On Tue, Dec 13, 2011 at 6:34 PM, Nicholas Nethercote
<n.neth...@gmail.com> wrote:
> On Tue, Dec 13, 2011 at 2:32 PM, Mike Hommey <m...@glandium.org> wrote:
>>>

>>> size_t can be 64-bits, which would bloat objects with size_t member
>>> variables that rarely need to track array or allocation sizes larger
>>> than 4GB.
>>

>> In practice, there are plenty of cases where even using a 32-bits int
>> type is going to waste 32-bits anyways. I'm pretty sure we have tons of
>> those.
>>
>> #include <iostream>
>> struct A {
>>  int i;
>>  void *ptr;
>> };
>
> But in a lot of those cases you can easily reorder to avoid the waste.
>  If you have a size_t you can't.
>
> Nick

[Mike Hommey]

On Wed, Dec 14, 2011 at 01:36:12AM -0500, Justin Lebar wrote:
> FWIW, Benoit and I played around with some compilers and arrays.
>
> If you have a vanilla
>
> for (T i = 0; i < n; i++) {
> do_something_with(arr[i]);
> }
>
> loop, then it appears that this is just as fast for T == PRUint32 and
> T == size_t on x86-64.
>
> But if you have inside the loop
>
> do_something_with(arr[i*2]);
>
> then gcc and clang are able to optimize the loop better if T ==
> size_t. (In the size_t case, the compiler changes the loop index from
> i to 2*i, but with PRUint32, it multiplies i by 2 in every step.)
>
> This appears to apply to nsTArrays as well as raw arrays.

I guess this leads to two additional questions:
Is there a compelling reason why clang and gcc can't do the same
optimization when T == size_t and T == PRUint32 when using i*2?
What does MSVC do?

If the answer to the latter is "the same as gcc and clang", there's not
much we can do, but in the opposite case, gcc and clang could be
improved.

Mike

[David Rajchenbach-Teller]

On 12/13/11 2:53 PM, Benoit Jacob wrote:
> Ah, I understand the question now.
>
> I would say that the decision chart to decide which type to use is
> something like this, everytime one needs to choose an integer type:
>
> 1) Check if there is a role-specific type for what I need? E.g. size_t
> for array indices, uintptr_t for pointer arithmetic, etc.
> 2) Otherwise, check if I need a type-specific type. E.g. 32-bit for
> RGBA8888 pixels, etc.

> 3) Finally, if my use case isn't covered by an existing role-specific
> type and exact size doesn't matter, fall back to a 'standard type'
> like int, etc.

Such a chart should go into our Coding Guidelines.

Cheers,
David

[Neil]

Mike Hommey wrote:

>On Wed, Dec 14, 2011 at 01:36:12AM -0500, Justin Lebar wrote:
>
>
>>FWIW, Benoit and I played around with some compilers and arrays.
>>
>>If you have a vanilla
>>
>> for (T i = 0; i < n; i++) {
>> do_something_with(arr[i]);
>> }
>>
>>loop, then it appears that this is just as fast for T == PRUint32 and T == size_t on x86-64.
>>
>>But if you have inside the loop
>>
>> do_something_with(arr[i*2]);
>>
>>then gcc and clang are able to optimize the loop better if T == size_t. (In the size_t case, the compiler changes the loop index from i to 2*i, but with PRUint32, it multiplies i by 2 in every step.)
>>
>>This appears to apply to nsTArrays as well as raw arrays.
>>
>>
>I guess this leads to two additional questions:
>Is there a compelling reason why clang and gcc can't do the same optimization when T == size_t and T == PRUint32 when using i*2?
>What does MSVC do?
>
>

MSVC generally uses strength reduction on the i*2*sizeof(arr[0]) with
double-register-indirect addressing, although there are some edge cases
with static arrays or optimisation disabled. For instance with
optimisation disabled and char arrays it doubles the second register in
hardware if you use size_t, while with optimisation enabled and string
literals with int indexes then it uses pointer arithmetic instead.

--
Warning: May contain traces of nuts.

[Neil]

Based on a remark by jlebar on IRC I tried it with 2*(size_t)i and it
uses the size_t code paths.

Actually, my methodology was bad. If I use a local variable for arr (I
was using static and extern variables) then when optimisation is enabled
I get hardware multiplication both for int and size_t indices. Only when
the array element reaches 8 bytes does it switch to pointer arithmetic
(although unlike the string literal case above it uses a second loop
variable).

[Justin Lebar]

derf has sagely advice, as usual:

Don't use unsigned integers as loop indices. Signed overflow is
undefined behavior, so the compiler can assume that your signed loop
index doesn't overflow. But the compiler has to correctly handle
unsigned overflow.

Indeed, glandium sees better code for some loops with int than with
unsigned int.

I wonder if Benoit would see better performance if he used ssize_t
instead of size_t in his matrix library.

See also http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

[Neil]

Neil wrote:

> Actually, my methodology was bad. If I use a local variable for arr (I
> was using static and extern variables) then when optimisation is
> enabled I get hardware multiplication both for int and size_t indices.
> Only when the array element reaches 8 bytes does it switch to pointer
> arithmetic (although unlike the string literal case above it uses a
> second loop variable).

Unless you use an unsigned int index, in which case it prefers to use
pointer arithmetic instead of hardware multiplication.

[Benoit Jacob]

2011/12/14 Justin Lebar <justin...@gmail.com>:

> derf has sagely advice, as usual:
>
> Don't use unsigned integers as loop indices. Signed overflow is
> undefined behavior, so the compiler can assume that your signed loop
> index doesn't overflow. But the compiler has to correctly handle
> unsigned overflow.
>
> Indeed, glandium sees better code for some loops with int than with
> unsigned int.
>
> I wonder if Benoit would see better performance if he used ssize_t
> instead of size_t in his matrix library.

I wholeheartedly agree, and my matrix library actually uses ptrdiff_t
instead of size_t for loop indices.

I only used size_t in the above discussion as I wanted to discuss only
one problem at a time (the sizeof) and the signed-vs-unsigned thing is
not 100% consensual everywhere. But since we seem to all agree that
signed is better than unsigned, great.

It's not just a matter of helping the compiler optimize. It's also
important to guard against a common programming mistage:

for(unsigned int stupid = max; stupid >= 0; stupid--) { boom; }

Note that AFAIK ssize_t is POSIX only while ptrdiff_t is available
everywhere, so I prefer the latter.

I would also add in the coding guidelines a general paragraph about
unsigned types. Here's my guiding rule: use signed types by default,
only use unsigned when:
1) you really really want that extra bit of large positive values, or
2) this is not going to be used in any +-/* arithmetic (e.g. bit-fields), or
3) you really want the compiler to be able to optimize x/2 into
x>>1 and you don't want to have to write x>>1 manually; or some other
similar optimization thing.
These are the only 3 reasons I know to use unsigned types.

Cheers,
Benoit

>
> See also http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
>
> On Wed, Dec 14, 2011 at 8:55 AM, Neil <ne...@parkwaycc.co.uk> wrote:

[Neil]

Benoit Jacob wrote:

>I would also add in the coding guidelines a general paragraph about unsigned types. Here's my guiding rule: use signed types by default, only use unsigned when:
>
>

> 1. you really really want that extra bit of large positive values, or
> 2. this is not going to be used in any +-/* arithmetic (e.g.
> bit-fields), or
> 3. you really want the compiler to be able to optimize x/2 into

> x>>1 and you don't want to have to write x>>1 manually; or some
> other similar optimization thing.
>
>These are the only 3 reasons I know to use unsigned types.
>

How about range-checking array indices? With unsigned indices you just
have to write k < l.

[Mike Hommey]

On Wed, Dec 14, 2011 at 09:09:19AM -0500, Justin Lebar wrote:
> derf has sagely advice, as usual:
>
> Don't use unsigned integers as loop indices. Signed overflow is
> undefined behavior, so the compiler can assume that your signed loop
> index doesn't overflow. But the compiler has to correctly handle
> unsigned overflow.
>
> Indeed, glandium sees better code for some loops with int than with
> unsigned int.

But, depending on the compiler, better code can be produced for int over
size_t, or vice-versa. clang does the former, gcc the latter. For both
compilers, size_t and ptrdiff_t/ssize_t generate the same code on my
small testcase.

Conclusion, there's no one true answer to "use 32-bits or 64-bits
integers on 64-bits builds". Signed vs. unsigned is another story.

Mike

[Benoit Jacob]

2011/12/14 Neil <ne...@parkwaycc.co.uk>:

There are 2 arguments here: performance and code complexity.

Performance: typically one wants to only do range-checking in debug
builds (assert) so it doesn't matter much to have to do two
comparisons. If it did matter, you could always do unsigned(k) < l.

Code complexity: you can always do an inline function bool
isIndexInRange(index i) or void assertThatIndexIsInRange(index i) to
make sure that you don't have to write that code more than once.

Benoit

>
>
> --
> Warning: May contain traces of nuts.

[Boris Zbarsky]

On 12/14/11 9:55 AM, Benoit Jacob wrote:
> Performance: typically one wants to only do range-checking in debug
> builds (assert)

Typically one wants to do range checking on every single web API
boundary. Or at least I really hope one does!

-Boris

[Boris Zbarsky]

On 12/14/11 9:09 AM, Justin Lebar wrote:
> Don't use unsigned integers as loop indices.

This only really works if your array length is also signed. Otherwise
you may end up with an index that can't traverse the whole array (and
the compiler will nicely warn you so, with the "comparing signed to
unsigned" warning).

We could do that, of course.

-Boris

[Chris Peterson]

A chart would be what int types to use for which purposes would be
great, especially if it included notes about _why_ other types may be
problematic for that use case (e.g. signed int overflow or bit shifting).

This suggestion might be controversial, but Mozilla typedefs for these
purposes would help with code readability and generation (but make code
_understanding_ more difficult).

For example:

typedef size_t array_index_t;
typedef uint32_t rgba8888_t;



chris

[Jeff Walden]

On 12/14/2011 09:25 AM, Benoit Jacob wrote:
> It's not just a matter of helping the compiler optimize. It's also
> important to guard against a common programming mistage:
>
> for(unsigned int stupid = max; stupid>= 0; stupid--) { boom; }
>
> Note that AFAIK ssize_t is POSIX only while ptrdiff_t is available
> everywhere, so I prefer the latter.
>
> I would also add in the coding guidelines a general paragraph about
> unsigned types. Here's my guiding rule: use signed types by default,
> only use unsigned when:
> 1) you really really want that extra bit of large positive values, or
> 2) this is not going to be used in any +-/* arithmetic (e.g. bit-fields), or
> 3) you really want the compiler to be able to optimize x/2 into
> x>>1 and you don't want to have to write x>>1 manually; or some other
> similar optimization thing.
> These are the only 3 reasons I know to use unsigned types.

When unsigned types match the underlying concept better, they reduce confusion. How does it make sense for an array to have a negative length?

Note that an alternative -- a better one, I think -- to avoiding the >= 0 thinko is to get warnings added to relevant compilers for this case. Oh, wait -- they're pretty much already there, aren't they? So maybe we should actually pay attention to the warnings in our code. :-) That, and make more code build warning-free, and use whatever frobs we design to convert warnings to errors for increasing numbers of portions of the codebase.

Jeff

[Justin Lebar]

> When unsigned types match the underlying concept better, they reduce
> confusion. How does it make sense for an array to have a negative length?

Agreed. But "signed" also means "I promise this won't overflow,"
which is helpful to the compiler.

[Jeff Walden]

On 12/14/2011 04:17 PM, Justin Lebar wrote:
>> When unsigned types match the underlying concept better, they reduce
>> confusion. How does it make sense for an array to have a negative length?
>
> Agreed. But "signed" also means "I promise this won't overflow,"
> which is helpful to the compiler.

If the change demonstrably affects performance, and in the particular situation performance matters a lot, that's one thing. In the general case, clarity trumps, I think.

Jeff

[Brian Smith]

Benoit Jacob wrote:
> Note that AFAIK ssize_t is POSIX only while ptrdiff_t is available
> everywhere, so I prefer the latter.

Unfortunately, C++0x allows pointer subtraction to overflow ptrdiff_t so, at least in language-lawyer-land, ptrdiff_t is useless. In other words, AFAICT, it is perfectly legal for ptrdiff_t to be something silly like int8_t.

Once you get out of language-lawyer-land, I think you can rely on useful properties like malloc() never returning objects larger than numeric_limits<ptrdiff_t>::max() and numeric_limits<size_t>::max() being significantly larger than the 65535+ that the standard guarantees.

Per

[Benoit Jacob]

2011/12/15 Brian Smith <bsm...@mozilla.com>:

> Benoit Jacob wrote:
>> Note that AFAIK ssize_t is POSIX only while ptrdiff_t is available
>> everywhere, so I prefer the latter.
>
> Unfortunately, C++0x allows pointer subtraction to overflow ptrdiff_t so, at least in language-lawyer-land, ptrdiff_t is useless. In other words, AFAICT, it is perfectly legal for ptrdiff_t to be something silly like int8_t.

I don't understand how "allows pointer subtraction to overflow
ptrdiff_t" implies that it is allowed that sizeof(ptrdiff_t) <
sizeof(void*) ?

With sizeof(ptrdiff_t) == sizeof(void*), it is still easy to make
pointer substraction overflow, for example, in the 32bit case:

0x00000000 - 0xffffffff

overflows because the minimum representable 32bit signed value is -0x80000000.

Benoit

[Brian Smith]

Benoit Jacob wrote:
> I don't understand how "allows pointer subtraction to overflow
> ptrdiff_t" implies that it is allowed that sizeof(ptrdiff_t) <
> sizeof(void*) ?

It doesn't imply it. But, there's nothing in any standard that says sizeof(ptrdiff_t) must be >= sizeof(void*), right?

- Brian

[Brian Smith]

Let me explain this more concretely. Let's say that the compiler refuses to allow you to malloc more than 65535 bytes at a time. Then, the compiler would be free to assume that the range of any value of type ptrdiff_t is 65535 to +65535. That means it could do things like assume that, for ptrdiff_t x, x < (1 << 18) == true for all x, even on a 32-bit system or 64-bit system.

What happens when you replace the default malloc() with your own that could return a 2GB array? Undefined behavior--in particular, the compiler could still assume that x < (1 << 18) for all x, even when the potential difference between two pointers in an array returned from your custom malloc is larger than that, AFAICT.

This is one of a few reasons why it isn't a good idea to use ptrdiff_t.

- Brian

[Benoit Jacob]

2011/12/15 Brian Smith <bsm...@mozilla.com>:

> Benoit Jacob wrote:
>> I don't understand how "allows pointer subtraction to overflow
>> ptrdiff_t" implies that it is allowed that sizeof(ptrdiff_t) <
>> sizeof(void*) ?
>
> It doesn't imply it. But, there's nothing in any standard that says sizeof(ptrdiff_t) must be >= sizeof(void*), right?

I think we somehow got confused again between ptrdiff_t and intptr_t :)

Indeed sizeof(ptrdiff_t) can be smaller than sizeof(void*). What is
required is that sizeof(ptrdiff_t) == sizeof(size_t) and that be large
enough to store any array offset, so, on an architecture where pointer
arithmetic can use 32bit offsets, you know that ptrdiff_t is at least
32bit.

Meanwhile, it is guaranteed that sizeof(intptr_t) == sizeof(void*),
but that is a different type.

Examples of platforms where sizeof(intptr_t) != sizeof(ptrdiff_t)
include ibm s390, IIUC. You can have a 64bit address space but arrays
limited to 32bit sizes, for example.

Benoit



>
> - Brian

[Benoit Jacob]

2011/12/15 Brian Smith <bsm...@mozilla.com>:

> Brian Smith wrote:
>> > I don't understand how "allows pointer subtraction to overflow
>> > ptrdiff_t" implies that it is allowed that sizeof(ptrdiff_t) <
>> > sizeof(void*) ?
>>
>> It doesn't imply it. But, there's nothing in any standard that says
>> sizeof(ptrdiff_t) must be >= sizeof(void*), right?
>

> Let me explain this more concretely. Let's say that the compiler refuses to allow you to malloc more than 65535 bytes at a time. Then, the compiler would be free to assume that the range of any value of type ptrdiff_t is 65535 to +65535.

I don't know about that. My understanding is that there is only 2 guarantees:
- that sizeof(ptrdiff_t) == sizeof(size_t)
- that size_t can represent any array index

But I was not aware of a guarantee that ptrdiff_t can represent any
array index or difference between indices.

If that were true, on a full 64bit arch with 64bit array indices,
ptrdiff_t would require more than 64bits...

Cheers,
Benoit

[Brian Smith]

Benoit Jacob wrote:
> What is required is that sizeof(ptrdiff_t) == sizeof(size_t)

That isn't required, AFAICT.

> and that be large enough to store any array offset,

I do not think even this is guaranteed, unless there is something that guarantees that numeric_limits<ptrdiff_t>::max() >= numeric_limits<size_t>::max().

- Brian

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf

[Benoit Jacob]

2011/12/15 Brian Smith <bsm...@mozilla.com>:

> Benoit Jacob wrote:
>> What is required is that sizeof(ptrdiff_t) == sizeof(size_t)
>
> That isn't required, AFAICT.
>
>> and that be large enough to store any array offset,
>
> I do not think even this is guaranteed, unless there is something that guarantees that numeric_limits<ptrdiff_t>::max() >= numeric_limits<size_t>::max().

I was unclear here: I was referring to size_t, not ptrdiff_t. See my last email.

For this reason, when I propose to use ptrdiff_t for array indices,
implicitly I propose to divide by 2 the maximum array size i.e. we
wouldn't let nsTArray grow bigger than half the max size accepted by
malloc.

Benoit