The "effective type" rules in the C standard are designed to allow compilers to reorder certain operations on disjoint objects in such a way as to maximize performance. Unfortunately, the language used to describe them is rather cryptic and ambiguous, and fails to make clear what compilers are and are not allowed to do. Further, even when understood, they only enable compilers to make a fraction of the useful optimizations they could make in most programs without adversely affecting the semantics, and yet may sometimes require programmers to awkwardly jump through hoops to prevent compilers from make unwanted "optimizations" that would break their code.
I would propose that rather than speaking of the effective types of objects sitting in memory, it would be far more useful to express rules in terms of sequencing behavior. Since performing multiple unsequenced accesses to an object will invoke Undefined Behavior unless none of the accesses modify the object in question, defining the cases in which accesses are sequenced will effectively define the cases where aliasing is permissible or impermissible, but will do so in a way would convey much more effectively than the current Standard what optimizations a compiler may or may not do.
The basic essence of the rules would be that even in cases where the Standard would describe an execution order for an abstract machine which stores objects in memory, the abstract machine would in general be allowed to read objects from memory in advance of when their values were used, and delay writing them to memory after their values were set, provided that if an object or portion thereof is read by operation R and there exists an operation W such that:
1. Operation W was a write to that portion of the object.
2. All write operations to that portion of the object, other than W, are either sequenced before W or after R.
Then operation R will yield the value written by W.
BASIC SEQUENCING GUARANTEES
To start with, in the absence of any specifications to the contrary, writes and reads made to the same object using identical type/member paths shall be sequenced relative to each other in the order they
occur. Further, if an expression reads some objects and writes some objects, any operation which is sequenced before any of the reads shall be sequenced before all of the writes, and any operation which is sequenced after any of the writes will be sequenced after all of the reads(*). The operations performed in the true or false bodies of an "if()" or "if/else" statement are sequenced after any reads syntactically required to resolve the condition, even if the effects of both branches of the conditional test would be identical. Likewise for operations in other conditional or looping structures except that Basic Guarantees do not cause operations after a loop which have no data dependencies on anything within the loop to be sequenced after it.
(*)Note that this means that an expression like *q=*p ^ 1; will have
defined behavior if both pointers are of the same type and identify the
same object, or if they identify disjoint objects, but will invoke
Undefined Behavior if they alias in any other fashion, since the read
and write would be unsequenced in that case. Note also that the
sequencing rules apply even when the value obtained by one of the reads
can't change the result. For example, give "x=y*z;", a compiler may not
move the write to x before any operation preceding the read of z, even
if "y" is known to be zero.
If a variable of pointer type has a "restrict" qualifier applied to it, then accesses made using that
pointer or other pointer based upon it (per C99 terminology) will, collectively, be unsequenced
relative to anything else in the universe except at the moment the pointer is created and the moment it is destroyed, unless the pointer is also qualified "volatile", in which case such accesses shall also be sequenced relative to other "volatile" accesses but not to ordinary accesses; all pointers with the same base shall honor the same sequencing relations relative to each other as they would absent the qualifier. Once the pointer is destroyed, all operations on the object identified thereby using the pointer will forevermore be unsequenced with regard to anything else in the universe unless the pointer was volatile, in which case such operations will be forevermore unsequenced with regard to non-volatile variables.
All accesses to lvalues of volatile type are fully sequenced relative
to other lvalue accesses of volatile types, but the minimal sequencing guarantees say nothing about sequencing relative to non-volatile accesses.
Functions like malloc(), calloc(), strdup(), etc. would be sequenced before any operations which
dereference the pointer acquired thereby; functions like "realloc()" and "free()" would be
sequenced after any operations which dereference the pointers released thereby.
ADDITIONAL IMPLICIT GUARANTEES
Certain directives would allow programs to specify that additional sequencing guarantees beyond those above should be applied by default when using objects of various types; further, the lack of any directives related to aliasing would imply certain default behaviors including saying that all character-type accesses to things that could be of allocated duration have both happens-before and happens-after relationships with accesses to all other types, and all writes to things that could be of allocated duration have happens-before and happens-after relationships with all other writes of all types, and happens-after (though not happens-before) relationships with reads of all types.
EXPLICIT GUARANTEES
Execution of a __FULL_ALIASING_BARRIER() directive will cause all operations which precede the directive to be sequenced before all operations which follow it. Over-use of this directive may adversely affect performance, but it may be required for some kinds of systems programming (e.g. prior to and following code that alters memory mappings, to ensure that any pending writes get deferred past the mapping change, and no reads get moved before it).
DEFINITIONS:
The "outer lvalue" refers to object
returned by the last pointer indirection, if any, applied in the
evaluation of an lvalue, or else the type of the object before any subscripting or member-access operators, if no
pointer indirections were performed.
The "type/member path" to be
the type of an outer lvalue, along with whatever subscripting or
member-access operators are applied to it. A member/access path is compatible with another if the outer-lvalue type of one is the type of a step along the access path for the other, and if the access paths beyond that point are equivalent. Note that compatibility is not an equivalence relation, because a type may have multiple access paths to the same member; the trailing portions of those
access paths would be compatible with the base type, but would not be compatible with each
other.
Given
struct foo { int x, y; };
union bar { int ints[8]; int fourpair[4][2]; int biquad[2][4]; struct foo foos[4]; } union bar *moo;
foo *zoo;
The
outer lvalue type for "moo[4].foos[2].y" would be "union bar", since
that's the result of the indirection applied by [4]. Note that the
access to foos[2] is not an indirection, since foo is a pointer rather
than an array. The type/access path for that expression would be
"(union bar).foos[2].y". Note also that while "moo[4].fourpair[2][1]"
and "moo[4].biquad[1][1]" would identify the same integer (which would
likely be the same integer as "moo[4].foos[2].y"), they would have
different access paths to it.
The outer lvalue type for "zoo->y" would be "struct foo", and the access path would be "(struct foo).y". Note that because the type of "moos[4].foos[2]" is "struct foo", the type/access path of "zoo->y" would be compatible with that of the earlier expression.
TEST DIV
Friday, November 27, 2015
Thursday, September 10, 2015
Proposa for new term: Optionally-Strictly-Conforming Program
The C Standard presently defines two levels of standards-conformance for programs:
If any C implementation exists that can make a program yield desired behavior while complying with the Standard, the program is "conforming".
If no possible C implementation could comply with the the Standard but fail to process the program so as to yield desired behavior, the program is "strictly conforming".
Unfortunately, the first definition is absurdly loose [even a program consisting of nothing but
two underscores and a newline could be made conforming if one wrote a compiler which, given
such a program, would produce desired behavior], but the second is so strict that it is impossible to express many algorithms using code which is strictly conforming without making the code inefficient, unreadable, or both.
I would suggest a new standard of conformance, and a couple of new vocabulary terms to go with it. A program would be said to be "optionally strictly conforming" if it complies with both of the following arguments:
- It must be possible for a Standard-compliant C implementation to exist that could process the program so as to yield desired behavior.
- All possible C implementations which comply with the Standard must either process it the program so as to yield desired behavior, or reject it outright by yielding at least one diagnostic message as a consequence of the program's assertion of requirements the compiler cannot meet.
At present there is no mechanism for programs to assert their requirements, but I would propose that the Standard define a mechanism by which assertions be added, and do so in a way that could be supported by existing C compilers with nothing other than the addition of suitable header files. Toward that end, I would propose adding two more new terms to the lexicon to extend the terms "Undefined Behavior" and "Implementation-Defined" behavior:
- A program invokes Testably-Specified Behavior if it invokes an action that would be Implementation-Defined Behavior, but has made assertions regarding that action's behavior and the compiler has not rejected them. For example, if a source file asserts that a conversion from an out-of-range int32_t to int16_t will be performed a mod-65536 two's-complement reduction, then the effects of code performing such conversion would no longer be Implementation-Defined within that source file [at present, nothing would forbid an implementation from documenting that such conversions will yield -32768 or +32767 when a program is invoked with a command line argument of "ovs", and two's-complement reduction elsewhere, nor would there be any mechanism by which a program which had not particularly prepared for such behavior to test for it, so a strictly-conforming program can't use any Implementation-Defined behaviors, no matter how consistent existing implementations happen to be].
- A program involves Testably-Constrained Behavior if it invokes an action that would be Undefined Behavior, except that the program has made assertions regarding that action's behavior and the compiler has not rejected them. For example, if a source file asserts that the use of a relational operator may return zero or one in arbitrary fashion, and a compiler does not reject such an assertion, then such comparisons within that source file would no longer invoke Undefined Behavior but would instead be required to meet the indicated requirements.
If any C implementation exists that can make a program yield desired behavior while complying with the Standard, the program is "conforming".
If no possible C implementation could comply with the the Standard but fail to process the program so as to yield desired behavior, the program is "strictly conforming".
Unfortunately, the first definition is absurdly loose [even a program consisting of nothing but
two underscores and a newline could be made conforming if one wrote a compiler which, given
such a program, would produce desired behavior], but the second is so strict that it is impossible to express many algorithms using code which is strictly conforming without making the code inefficient, unreadable, or both.
I would suggest a new standard of conformance, and a couple of new vocabulary terms to go with it. A program would be said to be "optionally strictly conforming" if it complies with both of the following arguments:
- It must be possible for a Standard-compliant C implementation to exist that could process the program so as to yield desired behavior.
- All possible C implementations which comply with the Standard must either process it the program so as to yield desired behavior, or reject it outright by yielding at least one diagnostic message as a consequence of the program's assertion of requirements the compiler cannot meet.
At present there is no mechanism for programs to assert their requirements, but I would propose that the Standard define a mechanism by which assertions be added, and do so in a way that could be supported by existing C compilers with nothing other than the addition of suitable header files. Toward that end, I would propose adding two more new terms to the lexicon to extend the terms "Undefined Behavior" and "Implementation-Defined" behavior:
- A program invokes Testably-Specified Behavior if it invokes an action that would be Implementation-Defined Behavior, but has made assertions regarding that action's behavior and the compiler has not rejected them. For example, if a source file asserts that a conversion from an out-of-range int32_t to int16_t will be performed a mod-65536 two's-complement reduction, then the effects of code performing such conversion would no longer be Implementation-Defined within that source file [at present, nothing would forbid an implementation from documenting that such conversions will yield -32768 or +32767 when a program is invoked with a command line argument of "ovs", and two's-complement reduction elsewhere, nor would there be any mechanism by which a program which had not particularly prepared for such behavior to test for it, so a strictly-conforming program can't use any Implementation-Defined behaviors, no matter how consistent existing implementations happen to be].
- A program involves Testably-Constrained Behavior if it invokes an action that would be Undefined Behavior, except that the program has made assertions regarding that action's behavior and the compiler has not rejected them. For example, if a source file asserts that the use of a relational operator may return zero or one in arbitrary fashion, and a compiler does not reject such an assertion, then such comparisons within that source file would no longer invoke Undefined Behavior but would instead be required to meet the indicated requirements.
Saturday, August 1, 2015
A call for Testably-Constrained Behaviors and Testably-Specified Behaviors (draft)
When the C standard was written, rules stating that certain operations invoked Undefined Behavior weren't intended to discourage implementations from defining and documenting useful behaviors for them, but instead said that implementations could implement any behavior (useful or otherwise) they considered most practical. Although the Standard would allow implementations to do anything whatsoever, many implementations have historically been able to offer some guarantees about their behaviors, and in many cases code that can rely upon such guarantees can be written much more cleanly and efficiently than code which has to confine itself to behaviors specified by the Standard.
In recognition of this, many compilers offer options to make them honor behavioral guarantees which the Standard does not require, but which some code relies upon. Unfortunately, there is at present no standard way of specifying such options, nor is there any way to ensure that failure to specify required options will not result in a program which compiles cleanly but whose behavior doesn't match the code.
Further, there are a number of operations to which the standard ascribes "Implementation-Defined" behavior, and where the vast majority of implementations behave identically, but where nothing would forbid an implementation from doing something completely contrary to that common practice [but allowable by the Standard], and no means exists by which a program could refuse compilation on such implementations.
I would propose, therefore, that most uses of the terms "Undefined Behavior" and "Implementation-Defined Behavior" be changed to "Testably-Constrained Behavior" and "Testably-Specified Behaviors", as defined below:
An action invokes "Testably-Constrained Behavior" if implementations are required to report, as defined below, whether or not they make various guarantees with regard to the consequences, and are required to honor any guarantees they makes, but are not required to report that they guarantee anything.
An action invokes "Testably-Specified Behavior" if implementations are required to provide and report at least some guarantees with regard to the consequences, and honor any guarantees they make. The specific minimum guarantees are described separately for each such behavior.
The goal in either case is that a standardized means be defined by which programs could assert their requirements and refuse compilation on implementations that could not satisfy them. For every form of Testably-Constrained Behavior, one of the allowable options would be "Undefined Behavior" [compiler makes no guarantees]; another option in many cases where most platforms would have one clear and obvious "literal" meaning for an operation, even though the effects might often be unpredictable and outside the jurisdiction of the standard, would be "Literal operation on platform". As an example of the latter, if a compiler specified that division by zero would invoke "literal operation on platform" [note that only compilers for platforms which have a division instruction could specify that], the code generated for "int x=5/0;", if executed, would be required to attempt to divide five by zero using the divide instruction, but would be under no obligation to configure trap vectors to ensure meaningful behavior.
An additional term, useful for describing the behavior of various overflow and integer-type coercions is "Partially-Indeterminate Value". A partially-indeterminate value of an n-bit type may behave as any integer--not necessarily a representable one--which is congruent to some particular value of that type, mod 2^n. If a system with a 16-bit "int", for example, were to specify that overflow yields a Partially-Indeterminate Value, then 32767+1 could arbitrarily behave as 32768, or -32768, or 98304, 163840, or any value which is congruent to -32768 mod 65536. If the system further specifies that storing an out-of-range value into an "int" variable will store a Partially-Indeterminate Value, then each attempt to read the integer could potentially yield a different result, provided that all such results are congruent mod 65536. Note that such a rule would allow a compiler to legitimately assume that it could regard the value of "j" after "j=i+1;" as being larger than "i" [since "j" will either be a defined value larger than "i", or a Partially-Indeterminate Value which may arbitrarily compare larger or smaller than "i"], but it would not allow the compiler to assume that the statement could not be reached with "i" holding 32767.
I would propose, as a baseline implementation, a header stdtcsb.h containing macro definitions that could be used by code to test implementation support for required features and behaviors. Almost any existing compiler which includes support for specific behaviors meeting a program's needs could be upgraded to support this new standard merely by supplying a suitable stdtcsb.h file and, for compilers that allow command-line control over options that are not testable in code, having makefiles that set such options also predefine vendor-specified macros to indicate that they have done so.
A baseline means by which the Standard could allow code to make use of actions whose behavior is not presently not mandated by the Standard, but whose behavior in the intended implementation would meet requirements, would be to define for each form of action that could invoke Undefined Behavior or Implementation-Defined Behavior an identifier which would behave as a compile-time constant bitmask identifying all of the possible consequences that could occur as a result of the action, along with macro or directive __STDC_REQUIRE_TCSB(x, y) which would at minimum refuse compilation if the possible behaviors indicated by "x" included some not allowed by "y". Beyond the fact that the macro/directive would be more concise than using `#if` with `#error` directives, it would also allow compilers to adapt their behavior to suit programs' requirements. A desirable feature of this approach is that almost any existing compiler whose natural behavior would satisfy a program's needs could be made compatible with code demanding such features by adding a suitable stdtcsb.h file and having any make files which specify options controlling compiler behavior also predefine macros to notify the stdtcsb.h file of them.
A lot of code, including high-performance audiovisual CODECs, is subject to two requirements:
1. When given valid input, produce valid output.
2. When given invalid input, do not launch nuclear missiles.
In recognition of this, many compilers offer options to make them honor behavioral guarantees which the Standard does not require, but which some code relies upon. Unfortunately, there is at present no standard way of specifying such options, nor is there any way to ensure that failure to specify required options will not result in a program which compiles cleanly but whose behavior doesn't match the code.
Further, there are a number of operations to which the standard ascribes "Implementation-Defined" behavior, and where the vast majority of implementations behave identically, but where nothing would forbid an implementation from doing something completely contrary to that common practice [but allowable by the Standard], and no means exists by which a program could refuse compilation on such implementations.
I would propose, therefore, that most uses of the terms "Undefined Behavior" and "Implementation-Defined Behavior" be changed to "Testably-Constrained Behavior" and "Testably-Specified Behaviors", as defined below:
An action invokes "Testably-Constrained Behavior" if implementations are required to report, as defined below, whether or not they make various guarantees with regard to the consequences, and are required to honor any guarantees they makes, but are not required to report that they guarantee anything.
An action invokes "Testably-Specified Behavior" if implementations are required to provide and report at least some guarantees with regard to the consequences, and honor any guarantees they make. The specific minimum guarantees are described separately for each such behavior.
The goal in either case is that a standardized means be defined by which programs could assert their requirements and refuse compilation on implementations that could not satisfy them. For every form of Testably-Constrained Behavior, one of the allowable options would be "Undefined Behavior" [compiler makes no guarantees]; another option in many cases where most platforms would have one clear and obvious "literal" meaning for an operation, even though the effects might often be unpredictable and outside the jurisdiction of the standard, would be "Literal operation on platform". As an example of the latter, if a compiler specified that division by zero would invoke "literal operation on platform" [note that only compilers for platforms which have a division instruction could specify that], the code generated for "int x=5/0;", if executed, would be required to attempt to divide five by zero using the divide instruction, but would be under no obligation to configure trap vectors to ensure meaningful behavior.
An additional term, useful for describing the behavior of various overflow and integer-type coercions is "Partially-Indeterminate Value". A partially-indeterminate value of an n-bit type may behave as any integer--not necessarily a representable one--which is congruent to some particular value of that type, mod 2^n. If a system with a 16-bit "int", for example, were to specify that overflow yields a Partially-Indeterminate Value, then 32767+1 could arbitrarily behave as 32768, or -32768, or 98304, 163840, or any value which is congruent to -32768 mod 65536. If the system further specifies that storing an out-of-range value into an "int" variable will store a Partially-Indeterminate Value, then each attempt to read the integer could potentially yield a different result, provided that all such results are congruent mod 65536. Note that such a rule would allow a compiler to legitimately assume that it could regard the value of "j" after "j=i+1;" as being larger than "i" [since "j" will either be a defined value larger than "i", or a Partially-Indeterminate Value which may arbitrarily compare larger or smaller than "i"], but it would not allow the compiler to assume that the statement could not be reached with "i" holding 32767.
I would propose, as a baseline implementation, a header stdtcsb.h containing macro definitions that could be used by code to test implementation support for required features and behaviors. Almost any existing compiler which includes support for specific behaviors meeting a program's needs could be upgraded to support this new standard merely by supplying a suitable stdtcsb.h file and, for compilers that allow command-line control over options that are not testable in code, having makefiles that set such options also predefine vendor-specified macros to indicate that they have done so.
A baseline means by which the Standard could allow code to make use of actions whose behavior is not presently not mandated by the Standard, but whose behavior in the intended implementation would meet requirements, would be to define for each form of action that could invoke Undefined Behavior or Implementation-Defined Behavior an identifier which would behave as a compile-time constant bitmask identifying all of the possible consequences that could occur as a result of the action, along with macro or directive __STDC_REQUIRE_TCSB(x, y) which would at minimum refuse compilation if the possible behaviors indicated by "x" included some not allowed by "y". Beyond the fact that the macro/directive would be more concise than using `#if` with `#error` directives, it would also allow compilers to adapt their behavior to suit programs' requirements. A desirable feature of this approach is that almost any existing compiler whose natural behavior would satisfy a program's needs could be made compatible with code demanding such features by adding a suitable stdtcsb.h file and having any make files which specify options controlling compiler behavior also predefine macros to notify the stdtcsb.h file of them.
A lot of code, including high-performance audiovisual CODECs, is subject to two requirements:
1. When given valid input, produce valid output.
2. When given invalid input, do not launch nuclear missiles.
Thursday, July 30, 2015
Propsal for new names of integer types
Propsal for new names of integer types:
Although the C standard presently defines integer types whose size is unaffected by the size of int (e.g. uint16_t), the behavior of such types is very much dependent upon the size of int. For example, in the function
int32_t comp(uint32_t x, int16_t y) { return x > y; }
machines where int is larger than 32 bits will define uint32_t as a type which will get promoted to a larger signed int, while machines where int is 32 bits or smaller will define uint32_t as a type which will not get promoted except when necessary to balance something of a larger type.
I would propose naming new types wrapN_t and unumN_t with the semantics that if type wrapN_t is defined, its behavior must be essentially equivalent to how a uintN_t would behave on a system where int was no larger than N bits, and if type unumN_t is defined, its behavior must be essentially equivalent to how a uintN_t would behave on a system where int is 2N bits or larger. Systems which presently define various uintN_t types could define the larger uwrapN_t and the smaller unumN_t types as aliases for uintN_t. Having code which relies upon promotion behavior use such types in preference to uintN_t would make the intention of the code clearer and would also make it easier to migrate such code to machines with different size integers. Had the above function used type uwrap32_t or unum32_t instead of uint32_t, the intended meaning would have been unambiguous.
To facilitate migration of code using uwrapN_t to platforms with larger integer types, I would propose the following rules for platforms making them available for types smaller than int:
1. When promoting values to int, the system must keep track of what type they would have been if the size of "int" were equal to that of the smallest supported uwrapN_t type.
2. If one operand of an operator requiring balancing is a uwrapN_t type and the other would have been a type that would have been no larger if int were N bits, then the other operand will be coerced to uwrapN_t, as will be the result of such expression, and behavior shall be equivalent to performing the computation with the uwrapN_t [a system may promote uwrapN_t to int, perform the computation, and then cast the result back, if and only if its behavior in case of any possible overflows would be consistent with having performed the operation directly on the uwrapN_t].
3. Types uintN_t and uwrapN_t must have identical representations, and uwrapN_t and uintN_t shall be considered equivalent in function declarations; it shall be legal for a function declaration to specify any type equivalent to uintN_t and its definition to specify uwrapN_t, or vice versa, even if they are different types.
4. For purposes of the Strict Aliasing Rule, a uwrapN_t shall be equivalent to a uintN_t.
To facilitate migration of code using unumN_t to platforms having smaller integer types, I would propose the following rules for platforms making them available for types whose values are not all representable as "int":
1. When Usual Arithmetic Promotions would apply, a variable of type unumN_t must be promoted to a signed integer type which is capable of representing any value it might hold.
2. If a variable or directly-cast expression of type unumN_t is passed to a variadic function, it shall be equivalent to `uintN_t`.
3. If an expression containing `uNum_t` is passed to a variadic function, and if the promotion required by #1 would cause the result to be a type incompatible from what would have resulted without the promotion, a compiler must reject the code. A compiler may accept the code if the type is changed but it can ensure compatible behavior.
4. Types uintN_t and unumN_t must have identical representations, and unumN_t and uintN_t shall be considered equivalent in function declarations; it shall be legal for a function declaration to specify any type equivalent to uintN_t and its definition to specify unumN_t, even if they are different types.
5. For purposes of the Strict Aliasing Rule, a unumN_t shall be equivalent to a uintN_t.
Additional proposed types to facilitate optimization
At present, operations on signed integer types smaller than int are subject to different rules from those on larger types, rules which presently impede optimizations. Further, the guaranteed semantics of unsigned types often limit optimization opportunities even in cases where programmers have no need of those guarantees. I would therefore suggest that for types intN_t and uintN_t there be additional defined types xuintN_t, ointN_t, and ouintN_t, whose defined behaviors would be consistent with those of intN_t and uintN_t, but subject to the following constraints:
The extensible types:
1. Values and variables of type xuintN_t would be similar to `uintN_t` except that a compiler would be allowed to retain an arbitrary number of additional bits. If a value of X is stored to e.g. an xuint16_t, each read of that value could yield X & (65535 | arbitrary_value), with a potentially different arbitrary value used for each read.
2. Writing to any of the constituent char or unsigned char values of an extensible-type variable would clear any "extra" bits associated therewith.
3. It shall be legal for a function declaration to specify any type equivalent to uintN_t and its definition to specify xuintN_t, even if they are different types, but the reverse is not true; compilers may flag an error if a declaration specifies xuintN_t and the definition specifies anything other than xuintN_t or ouintN_t, even if the types are otherwise compatible, and must flag an error if it cannot ensure that the function will not receive a value outside the range of its defined type. Note that systems which declare `xuintN_t` as a synonym for `uintN_t` will implicitly meet this requirement.
4. For purposes of the Strict Aliasing Rule, types uintN_t and xuintN_t would generally be equivalent, with the proviso that writing as a non-x (and non-o) type must cause any "extra bits" to be cleared, and reading as a non-x (and non-o) type must cause any extra bits to be ignored. Note that systems which declare ointN_t and ouintN_t as a synonyms for intN_t and uintN_t will implicitly meet this requirement.
The optimizer-friendly types:
1. Variables and values of type ointN_t or ouintN_t behave like intN_t and uintN_t with values that are within the range of the latter types, but coercion of out-of-range values to `ointN_t` or `ouintN_t` would be exempt from the normal rules applicable to out-of-range coercions to `intN_t` and `uintN_t`.
2. It is recommended that coercion of out-of-range value to an ointN_t or ouintN_t yield a Partially-Indeterminate Value as described below; such semantics should allow nearly all of the useful optimization opportunities that would be afforded by Undefined Behavior, without requiring that code expend effort to avoid such behavior in cases where a Partially-Indeterminate Value would satisfy program requirements.
3. It shall be legal for a function declaration to specify any type equivalent to uintN_t or xuintN_t and its definition to specify ouintN_t, even if they are different types, but the reverse is not true; compilers may flag an error if a declaration specifies ouintN_t and the definition specifies anything other than ouintN_t, even if the types are otherwise compatible, and must flag an error if it cannot ensure that the function will not receive a value outside the range of its defined type. Note that systems which declare ointN_t and ouintN_t as a synonyms for intN_t and uintN_t will implicitly meet this requirement.
4. For purposes of the Strict Aliasing Rule, types uintN_t and xuintN_t would generally be equivalent, with the proviso that writing as a non-o (and non-x) type must cause any "extra bits" to be cleared, and reading as a non-o (and non-x) type must cause any extra bits to be ignored. Note that systems which declare ointN_t and ouintN_t as a synonyms for intN_t and uintN_t will implicitly meet this requirement.
Partially-Indeterminate Value:
A compiler shall be allowed to behave as though each value has a "hidden" bit indicating whether it represents a Partially-Indeterminate Value. If a value of an N-bit type holds a partially-indeterminate value, then each rvalue conversion may independently behave as any positive or negative mathematical integer which is congruent to the original mod 2^n, without regard for whether that number would be representable in any data type, and without regard for whether the type is signed or unsigned. If a partially-indeterminate value of a particular type is coerced to a longer type, the value of any additional bits in the result shall be Unspecified; if the longer type can accommodate Partially-Indeterminate Values, the result will be a Partially-Indeterminate Value of that longer type.
For example, consider "ouint8_t x=258; ouint16_t y=x; uint32_t z1=y,z2=y;"
x will be a Partially-Indeterminate Value congruent to 2 mod 256.
y will be a Partially-Indeterminate Value congruent to K*256+2 mod 65536, for some value K
z1 will be equal L1*65536+K*256+2 mod 4294967296, for the above value K and some arbitrary value L1.
z2 will be equal L2*65536+K*256+2 mod 4294967296, for the above value K and some arbitrary value L2not necessarily equal to L1.
Note that under these rules, Partially-Indeterminate Values are highly "contagious", thus facilitating many kinds of optimization, but their behavior is sufficiently constrained that code need not waste time on checks to avoid operations that would yield Partially-Indeterminate Value any possible result from such operations would be acceptable. As a simple example, if a platform specified that integer overflow would yield Partially-Indeterminate Value, compilers would be able to assume that any integer i will be less than i+1, but code like "uint16_t x,y,z; ... x=y*z;" would have fully-defined behavior for all values of y and z even on a 32-bit system [the computation y*z might yield Partially-Indeterminate Value, but the assignment to x would throw away all indeterminate bits].
Although the C standard presently defines integer types whose size is unaffected by the size of int (e.g. uint16_t), the behavior of such types is very much dependent upon the size of int. For example, in the function
int32_t comp(uint32_t x, int16_t y) { return x > y; }
machines where int is larger than 32 bits will define uint32_t as a type which will get promoted to a larger signed int, while machines where int is 32 bits or smaller will define uint32_t as a type which will not get promoted except when necessary to balance something of a larger type.
I would propose naming new types wrapN_t and unumN_t with the semantics that if type wrapN_t is defined, its behavior must be essentially equivalent to how a uintN_t would behave on a system where int was no larger than N bits, and if type unumN_t is defined, its behavior must be essentially equivalent to how a uintN_t would behave on a system where int is 2N bits or larger. Systems which presently define various uintN_t types could define the larger uwrapN_t and the smaller unumN_t types as aliases for uintN_t. Having code which relies upon promotion behavior use such types in preference to uintN_t would make the intention of the code clearer and would also make it easier to migrate such code to machines with different size integers. Had the above function used type uwrap32_t or unum32_t instead of uint32_t, the intended meaning would have been unambiguous.
To facilitate migration of code using uwrapN_t to platforms with larger integer types, I would propose the following rules for platforms making them available for types smaller than int:
1. When promoting values to int, the system must keep track of what type they would have been if the size of "int" were equal to that of the smallest supported uwrapN_t type.
2. If one operand of an operator requiring balancing is a uwrapN_t type and the other would have been a type that would have been no larger if int were N bits, then the other operand will be coerced to uwrapN_t, as will be the result of such expression, and behavior shall be equivalent to performing the computation with the uwrapN_t [a system may promote uwrapN_t to int, perform the computation, and then cast the result back, if and only if its behavior in case of any possible overflows would be consistent with having performed the operation directly on the uwrapN_t].
3. Types uintN_t and uwrapN_t must have identical representations, and uwrapN_t and uintN_t shall be considered equivalent in function declarations; it shall be legal for a function declaration to specify any type equivalent to uintN_t and its definition to specify uwrapN_t, or vice versa, even if they are different types.
4. For purposes of the Strict Aliasing Rule, a uwrapN_t shall be equivalent to a uintN_t.
To facilitate migration of code using unumN_t to platforms having smaller integer types, I would propose the following rules for platforms making them available for types whose values are not all representable as "int":
1. When Usual Arithmetic Promotions would apply, a variable of type unumN_t must be promoted to a signed integer type which is capable of representing any value it might hold.
2. If a variable or directly-cast expression of type unumN_t is passed to a variadic function, it shall be equivalent to `uintN_t`.
3. If an expression containing `uNum_t` is passed to a variadic function, and if the promotion required by #1 would cause the result to be a type incompatible from what would have resulted without the promotion, a compiler must reject the code. A compiler may accept the code if the type is changed but it can ensure compatible behavior.
4. Types uintN_t and unumN_t must have identical representations, and unumN_t and uintN_t shall be considered equivalent in function declarations; it shall be legal for a function declaration to specify any type equivalent to uintN_t and its definition to specify unumN_t, even if they are different types.
5. For purposes of the Strict Aliasing Rule, a unumN_t shall be equivalent to a uintN_t.
Additional proposed types to facilitate optimization
At present, operations on signed integer types smaller than int are subject to different rules from those on larger types, rules which presently impede optimizations. Further, the guaranteed semantics of unsigned types often limit optimization opportunities even in cases where programmers have no need of those guarantees. I would therefore suggest that for types intN_t and uintN_t there be additional defined types xuintN_t, ointN_t, and ouintN_t, whose defined behaviors would be consistent with those of intN_t and uintN_t, but subject to the following constraints:
The extensible types:
1. Values and variables of type xuintN_t would be similar to `uintN_t` except that a compiler would be allowed to retain an arbitrary number of additional bits. If a value of X is stored to e.g. an xuint16_t, each read of that value could yield X & (65535 | arbitrary_value), with a potentially different arbitrary value used for each read.
2. Writing to any of the constituent char or unsigned char values of an extensible-type variable would clear any "extra" bits associated therewith.
3. It shall be legal for a function declaration to specify any type equivalent to uintN_t and its definition to specify xuintN_t, even if they are different types, but the reverse is not true; compilers may flag an error if a declaration specifies xuintN_t and the definition specifies anything other than xuintN_t or ouintN_t, even if the types are otherwise compatible, and must flag an error if it cannot ensure that the function will not receive a value outside the range of its defined type. Note that systems which declare `xuintN_t` as a synonym for `uintN_t` will implicitly meet this requirement.
4. For purposes of the Strict Aliasing Rule, types uintN_t and xuintN_t would generally be equivalent, with the proviso that writing as a non-x (and non-o) type must cause any "extra bits" to be cleared, and reading as a non-x (and non-o) type must cause any extra bits to be ignored. Note that systems which declare ointN_t and ouintN_t as a synonyms for intN_t and uintN_t will implicitly meet this requirement.
The optimizer-friendly types:
1. Variables and values of type ointN_t or ouintN_t behave like intN_t and uintN_t with values that are within the range of the latter types, but coercion of out-of-range values to `ointN_t` or `ouintN_t` would be exempt from the normal rules applicable to out-of-range coercions to `intN_t` and `uintN_t`.
2. It is recommended that coercion of out-of-range value to an ointN_t or ouintN_t yield a Partially-Indeterminate Value as described below; such semantics should allow nearly all of the useful optimization opportunities that would be afforded by Undefined Behavior, without requiring that code expend effort to avoid such behavior in cases where a Partially-Indeterminate Value would satisfy program requirements.
3. It shall be legal for a function declaration to specify any type equivalent to uintN_t or xuintN_t and its definition to specify ouintN_t, even if they are different types, but the reverse is not true; compilers may flag an error if a declaration specifies ouintN_t and the definition specifies anything other than ouintN_t, even if the types are otherwise compatible, and must flag an error if it cannot ensure that the function will not receive a value outside the range of its defined type. Note that systems which declare ointN_t and ouintN_t as a synonyms for intN_t and uintN_t will implicitly meet this requirement.
4. For purposes of the Strict Aliasing Rule, types uintN_t and xuintN_t would generally be equivalent, with the proviso that writing as a non-o (and non-x) type must cause any "extra bits" to be cleared, and reading as a non-o (and non-x) type must cause any extra bits to be ignored. Note that systems which declare ointN_t and ouintN_t as a synonyms for intN_t and uintN_t will implicitly meet this requirement.
Partially-Indeterminate Value:
A compiler shall be allowed to behave as though each value has a "hidden" bit indicating whether it represents a Partially-Indeterminate Value. If a value of an N-bit type holds a partially-indeterminate value, then each rvalue conversion may independently behave as any positive or negative mathematical integer which is congruent to the original mod 2^n, without regard for whether that number would be representable in any data type, and without regard for whether the type is signed or unsigned. If a partially-indeterminate value of a particular type is coerced to a longer type, the value of any additional bits in the result shall be Unspecified; if the longer type can accommodate Partially-Indeterminate Values, the result will be a Partially-Indeterminate Value of that longer type.
For example, consider "ouint8_t x=258; ouint16_t y=x; uint32_t z1=y,z2=y;"
x will be a Partially-Indeterminate Value congruent to 2 mod 256.
y will be a Partially-Indeterminate Value congruent to K*256+2 mod 65536, for some value K
z1 will be equal L1*65536+K*256+2 mod 4294967296, for the above value K and some arbitrary value L1.
z2 will be equal L2*65536+K*256+2 mod 4294967296, for the above value K and some arbitrary value L2not necessarily equal to L1.
Note that under these rules, Partially-Indeterminate Values are highly "contagious", thus facilitating many kinds of optimization, but their behavior is sufficiently constrained that code need not waste time on checks to avoid operations that would yield Partially-Indeterminate Value any possible result from such operations would be acceptable. As a simple example, if a platform specified that integer overflow would yield Partially-Indeterminate Value, compilers would be able to assume that any integer i will be less than i+1, but code like "uint16_t x,y,z; ... x=y*z;" would have fully-defined behavior for all values of y and z even on a 32-bit system [the computation y*z might yield Partially-Indeterminate Value, but the assignment to x would throw away all indeterminate bits].
Monday, November 17, 2014
New integer types and promotion rules:
New types:
__ring(1) etc. up to __ring(64)
Ring types would be specified to behave like abstract algebraic ring of integers congruent size 2^n; such types would behave similarly to the way unsigned types of the same size would behave, except for the following:
1. They would be exempt from integer promotions. Applying binary operators to a ring of any size and an integer or whole-number type of any size would cause the integer to be converted to the ring type, and would yield a result of the original ring type. Operations involving two different ring types would be forbidden, except for "&" which would yield a result of the *smaller* ring type.
2. Compilers would be required to allow rings of any size up to the implementation's maximum size, regardless of whether the requested size coincides with any multiple of the machine's word size, and include whatever bit-masking operations are required to yield semantically-correct results. It would be perfectly acceptable for a compiler to allocate a 32-bit storage word for a __ring(3), but all computations on such rings must yield a result in the range 0-7.
__whole(1) up to __whole(63)
Whole-number types would be specified to behave like integer types capable of holding values from 0 to 2^n-1; any such types smaller than __int would have computations on them performed using using intermediate values of type __int. As with ring types, the compiler would be free to allocate as much or as little space to each number as it sees fit.
__signed(2) up to __signed(64)
Signed-number types would hold values from (2^(n-1)) to (2^(n-1))-1; any such types smaller than __int would have computations on them performed using using intermediate values of type __int. As with ring types, the compiler would be free to allocate as little or as much space to each number as it sees fit.
Overflow rules:
If a numeric overflow occurs, or an attempt is made to store a value into a storage location (other than a ring) which is too small to hold it, the generated code may cause an immediate trap, or may "store" the value, with the constraint that any future attempt to reading the storage location may arbitrarily trap or yield any number which would be correct modulo 2^(n-1), where n is the specified size of the storage location.
Note that Overflow would no longer constitute "undefined behavior"; among the consequences of this, compilers would no longer be allowed to assume that values upon which computations will be performed cannot cause overflow, but would still be allowed to assume that computations will not yield a result that would be arithmetically impossible. For example, given:
int64_t test(int64_t x)
{
int temp=(x > 3037000500);
int64_t y =x*x;
if (temp) return 1;
if (y > -3) return 2; return y;
}
Under C14 rules, a compiler would be allowed to unconditionally set "temp" to zero, since the only way its value would be non-zero would be if the multiplication was going to overflow and allow the compiler to do whatever it felt like. Under the proposed rules, such treatment would be forbidden. The test for "y > -3" would be another story, however; a compiler would be allowed to assume that because the arithmetically-accurately-computed square of any number cannot be negative, there is no way y can be negative and thus no need to test for it. If an overflow occurs, it would thus be possible for the method to return a negative number.
New types:
__ring(1) etc. up to __ring(64)
Ring types would be specified to behave like abstract algebraic ring of integers congruent size 2^n; such types would behave similarly to the way unsigned types of the same size would behave, except for the following:
1. They would be exempt from integer promotions. Applying binary operators to a ring of any size and an integer or whole-number type of any size would cause the integer to be converted to the ring type, and would yield a result of the original ring type. Operations involving two different ring types would be forbidden, except for "&" which would yield a result of the *smaller* ring type.
2. Compilers would be required to allow rings of any size up to the implementation's maximum size, regardless of whether the requested size coincides with any multiple of the machine's word size, and include whatever bit-masking operations are required to yield semantically-correct results. It would be perfectly acceptable for a compiler to allocate a 32-bit storage word for a __ring(3), but all computations on such rings must yield a result in the range 0-7.
__whole(1) up to __whole(63)
Whole-number types would be specified to behave like integer types capable of holding values from 0 to 2^n-1; any such types smaller than __int would have computations on them performed using using intermediate values of type __int. As with ring types, the compiler would be free to allocate as much or as little space to each number as it sees fit.
__signed(2) up to __signed(64)
Signed-number types would hold values from (2^(n-1)) to (2^(n-1))-1; any such types smaller than __int would have computations on them performed using using intermediate values of type __int. As with ring types, the compiler would be free to allocate as little or as much space to each number as it sees fit.
Overflow rules:
If a numeric overflow occurs, or an attempt is made to store a value into a storage location (other than a ring) which is too small to hold it, the generated code may cause an immediate trap, or may "store" the value, with the constraint that any future attempt to reading the storage location may arbitrarily trap or yield any number which would be correct modulo 2^(n-1), where n is the specified size of the storage location.
Note that Overflow would no longer constitute "undefined behavior"; among the consequences of this, compilers would no longer be allowed to assume that values upon which computations will be performed cannot cause overflow, but would still be allowed to assume that computations will not yield a result that would be arithmetically impossible. For example, given:
int64_t test(int64_t x)
{
int temp=(x > 3037000500);
int64_t y =x*x;
if (temp) return 1;
if (y > -3) return 2; return y;
}
Under C14 rules, a compiler would be allowed to unconditionally set "temp" to zero, since the only way its value would be non-zero would be if the multiplication was going to overflow and allow the compiler to do whatever it felt like. Under the proposed rules, such treatment would be forbidden. The test for "y > -3" would be another story, however; a compiler would be allowed to assume that because the arithmetically-accurately-computed square of any number cannot be negative, there is no way y can be negative and thus no need to test for it. If an overflow occurs, it would thus be possible for the method to return a negative number.
8086 segmentation--One of the great underappreciated ideas of the 1980's
One of the most widely "noted" features of the 8086 architecture is its unusual addressing scheme. Rather than using a 16-bit linear address and relying upon external hardware to access more than 64K of storage, the 8086 forms physical addresses by taking a 16-bit segment register, shifting it left 4 bits, and adding that to a 16-bit displacement to yield a 20-bit address which can access a 1MB address space. This design was widely criticized at the time, but in it worked better than any alternatives that existed at the time other than a linear 32-bit address space (which would of course required a 32-bit architecture). Further, if one compares the IBM PC with the Macintosh, one observes that while PC code often limited things to 64K, the Macintosh (which used a 68000) had a lot of 32K limits. Even if a processor has 32-bit linear addressing, 32-bit pointers take more space than using 16-bit offsets.
The 8086 architecture was hardly perfect, but the problems for which people blame the segmented architecture were not problems with the concept, but rather were small issues with its implementation. The segmented architecture would have been great but for the fact that there was only one "general-purpose" segment register. Even though the processor had four registers which could be used for address generation (BX, BP, SI, and DI), and had a segment register dedicated for use with one of them (SS was dedicated BP), there was only one segment register which did not generally have a fixed place it was expected to point (ES). Consequently, code that tried to use more than one arbitrarily-placed object at a time would have to reload ES every time it accessed a different object, largely negating the benefits of having multiple address-related registers. Code which was written with segmentation in mind--especially if it was written in assembly language, could work around this limitation various ways (e.g. by using buffers that were placed near the code, and could thus be accessed using the CS register). Having even one more segment register (so that SI and DI could access different things while DS continued to access the "main" data segment) would have been a huge improvement.
The other thing that would have improved the usability of segment registers would have been if programming languages were to better recognize different kinds of pointers. I dislike Microsoft's "memory models", and would have preferred that common practice classify pointers into categories:
-- 16 bit pointer to something in main data segment (which MS supports)
-- 16 bit pointer to something known to be on stack (not supported)
-- 16 bit pointer to start of paragraph-aligned object (not supported)
-- 32 bit pointer to anything
Having calloc round all allocations to multiples of 16 bytes might seem like it would waste space, but it really wouldn't waste much if memory-allocation-list entries were kept in the slack space. Further, it would reduce the size of every reference to a calloc'ed object by two bytes; since every such object will have at least one reference to it, and will often have more, that could easily become a major win.
Interestingly, today's .NET and Java frameworks would both work very nicely on a system that combined 32-bit segment registers with 32-bit offsets, even if the system did nothing more complicated than what the 8086 did (but with 32-bit values). Such a system could easily accesss 64GB rather than 4GB, while retaining the use of 32-bit object references; the only "penalty" would be that object sizes would be rounded up to the next multiple of 16 rather than the next multiple of 4 or 8. If one wanted to reduce that penalty while allowing more than 64GB of storage, one could have the top 4 or so bits of the segment register select a region of memory while the remaining bits are shifted by a region-specific factor and added to the offset. Objects up to e.g. 256 bytes could be allocated in an area which is 4-byte aligned; those up to 5105 bytes could be allocated in an area which is 16-byte aligned; those up to 80K in an area that's 256-byte aligned, and huge objects in an area that's 4096-byte aligned. Using 15 of the 16 segment regions, one could accommodate all of the following
-- Small objects totalling up to 8 gigabytes (segment 0xxx...)
-- Medium objects totalling up to 16 gigabytes (segment 10xx...)
-- Large objects totaling up to 128 gigabytes (segment 110x...)
-- Huge objects totaling up to one terabyte (segment 1110...)
-- Additional address space of 256 million segments remaining for other purposes (the stack, OS buffers, etc.)
All while using 32-bit object references. Small objects would have the same level of overhead they do in 32-bit .NET; larger objects would have slightly more overhead due to alignment, but no more 5%. Pointers (as opposed to offset registers) would be 8 bytes rather than four, but since code in Java and .NET mainly persists object references rather than pointers, the cost of expanding pointers to 64 bits would be far less than the cost of expanding object references likewise.
Note that the thresholds between object sizes could be adjusted if need be based upon program requirements; the garbage-collector could even perform such rebalancing during program execution. While there are some programs which would truly need 64-bit object references, I would expect that the extremely vast majority of programs could get by with 32-bit object references using a scheme like the above.
The 8086 architecture was hardly perfect, but the problems for which people blame the segmented architecture were not problems with the concept, but rather were small issues with its implementation. The segmented architecture would have been great but for the fact that there was only one "general-purpose" segment register. Even though the processor had four registers which could be used for address generation (BX, BP, SI, and DI), and had a segment register dedicated for use with one of them (SS was dedicated BP), there was only one segment register which did not generally have a fixed place it was expected to point (ES). Consequently, code that tried to use more than one arbitrarily-placed object at a time would have to reload ES every time it accessed a different object, largely negating the benefits of having multiple address-related registers. Code which was written with segmentation in mind--especially if it was written in assembly language, could work around this limitation various ways (e.g. by using buffers that were placed near the code, and could thus be accessed using the CS register). Having even one more segment register (so that SI and DI could access different things while DS continued to access the "main" data segment) would have been a huge improvement.
The other thing that would have improved the usability of segment registers would have been if programming languages were to better recognize different kinds of pointers. I dislike Microsoft's "memory models", and would have preferred that common practice classify pointers into categories:
-- 16 bit pointer to something in main data segment (which MS supports)
-- 16 bit pointer to something known to be on stack (not supported)
-- 16 bit pointer to start of paragraph-aligned object (not supported)
-- 32 bit pointer to anything
Having calloc round all allocations to multiples of 16 bytes might seem like it would waste space, but it really wouldn't waste much if memory-allocation-list entries were kept in the slack space. Further, it would reduce the size of every reference to a calloc'ed object by two bytes; since every such object will have at least one reference to it, and will often have more, that could easily become a major win.
Interestingly, today's .NET and Java frameworks would both work very nicely on a system that combined 32-bit segment registers with 32-bit offsets, even if the system did nothing more complicated than what the 8086 did (but with 32-bit values). Such a system could easily accesss 64GB rather than 4GB, while retaining the use of 32-bit object references; the only "penalty" would be that object sizes would be rounded up to the next multiple of 16 rather than the next multiple of 4 or 8. If one wanted to reduce that penalty while allowing more than 64GB of storage, one could have the top 4 or so bits of the segment register select a region of memory while the remaining bits are shifted by a region-specific factor and added to the offset. Objects up to e.g. 256 bytes could be allocated in an area which is 4-byte aligned; those up to 5105 bytes could be allocated in an area which is 16-byte aligned; those up to 80K in an area that's 256-byte aligned, and huge objects in an area that's 4096-byte aligned. Using 15 of the 16 segment regions, one could accommodate all of the following
-- Small objects totalling up to 8 gigabytes (segment 0xxx...)
-- Medium objects totalling up to 16 gigabytes (segment 10xx...)
-- Large objects totaling up to 128 gigabytes (segment 110x...)
-- Huge objects totaling up to one terabyte (segment 1110...)
-- Additional address space of 256 million segments remaining for other purposes (the stack, OS buffers, etc.)
All while using 32-bit object references. Small objects would have the same level of overhead they do in 32-bit .NET; larger objects would have slightly more overhead due to alignment, but no more 5%. Pointers (as opposed to offset registers) would be 8 bytes rather than four, but since code in Java and .NET mainly persists object references rather than pointers, the cost of expanding pointers to 64 bits would be far less than the cost of expanding object references likewise.
Note that the thresholds between object sizes could be adjusted if need be based upon program requirements; the garbage-collector could even perform such rebalancing during program execution. While there are some programs which would truly need 64-bit object references, I would expect that the extremely vast majority of programs could get by with 32-bit object references using a scheme like the above.
Language philosophy
When designing a language, what goal should drive decisions about when the compiler should automatically apply certain transformations to code (such as adding typecasts) and when it should require that the programmer specify what is desired?
I would posit that a transform should be considered helpful if the meaning of the code with the transform applied would almost certainly match what the programmer intended. It should be considered harmful in cases where it causes the compiler to accept code whose resultant meaning is likely to be something other than what was intended.
I would posit that a transform should be considered helpful if the meaning of the code with the transform applied would almost certainly match what the programmer intended. It should be considered harmful in cases where it causes the compiler to accept code whose resultant meaning is likely to be something other than what was intended.
Subscribe to:
Posts (Atom)