Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Limitations and workarounds to expressions defining size of an array

Reply
Thread Tools

Limitations and workarounds to expressions defining size of an array

 
 
Eric Sosman
Guest
Posts: n/a
 
      09-05-2012
On 9/5/2012 5:39 PM, Francois Grieu wrote:
> [...]
> Questions: In C11, what liberties do we have?
> In particular,
> - can we define the size of a static array (non-VLA)
> using a static const long ?


Sure:

static const long scl = 42;
static int array[sizeof scl];

But for the question I think you're really asking, the
answer is No. First read 6.7.6.2p4 to learn that an array
with a dimension that is not an integer constant expression
is a VLA. Then read 6.6p6 to find out how an ICE is formed;
note that `static const long' does not match any of the allowed
operands. Hence an expression using the value of an SCL is
not an ICE, and an array declared with such an expression as
its dimension is a VLA.

> - can we use a static const long freely in an
> expression that defines another static const long ?


No. 6.6p7-9.

> - can we use floating point arithmetic in expressions defining
> a static const long ?


Yes. 6.6p8.

> - can we use exp() and log() in such expressions ?


No. 6.6p6-9.

6.6p10 offers a loophole: "An implementation may accept
other forms of constant expressions," so for any particular
compiler some of the Noes may turn to Yesses. But you wrote
"freely," which I'm interpreting as "works on all C11 compilers,"
and with that understanding the Noes have it.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d
"The speed at which the system fails is usually not important."
 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      09-05-2012
On 9/5/2012 5:30 PM, army1987 wrote:
> On Wed, 05 Sep 2012 17:23:04 -0400, James Kuyper wrote:
>
>> In
>> particular, your "WTF?" left me wondering whether you thought the
>> optimization was invalid.

>
> I don't. But 1) I was surprised that strspn() was optimized away, and 2)
> I seemed to remember seeing a compiler optimizing away printf() some time
> ago, so I expected that if a compiler would do the former it would do the
> latter too.


Pre-computation of strspn() surprised me, too. But compilers
have been handling certain special cases of printf() for a long
time. More than fifteen years ago, a colleague told me of writing
the transformation

printf("%s\n", ptr); /* as written */
to
puts(ptr); /* as compiled */

.... with the usual justification: "One of the SPEC benchmarks used
the printf() a lot, and we got a speed increase by eliminating the
format interpretation." <Checks> A fairly elderly gcc does this,
even at the default optimization level.

--
Eric Sosman
(E-Mail Removed)d
"The speed at which the system fails is usually not important."
 
Reply With Quote
 
 
 
 
James Kuyper
Guest
Posts: n/a
 
      09-05-2012
On 09/05/2012 05:30 PM, army1987 wrote:
> On Wed, 05 Sep 2012 17:23:04 -0400, James Kuyper wrote:
>
>> In
>> particular, your "WTF?" left me wondering whether you thought the
>> optimization was invalid.

>
> I don't. But 1) I was surprised that strspn() was optimized away, and 2)
> I seemed to remember seeing a compiler optimizing away printf() some time
> ago, so I expected that if a compiler would do the former it would do the
> latter too.


What this particular format string causes printf() to do is relatively
simple. The whole thing could have been optimized all the way down to
fputs("3", stdout). However, in general printf() is far more complicated
than strspn(), which might explain why the strspn() call got evaluated
at compile time, while the printf() call did not.

In particular, printf()'s behavior depends upon the current locale,
while strspn()'s does not. In this simple program, it's easy to confirm
that there's no possibility of setlocale() being called. However, the
need to check for that possibility might have discouraged any attempt to
pre-evaluate the printf() call.
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      09-07-2012
Francois Grieu <(E-Mail Removed)> writes:

> I'm trying to figure out the exact limitations that (possibly:
> various versions of ISO/IEC 9899) C puts to expressions defining
> the size of a plain array at compile time, and how to workaround
> that. [.. rearranging ..] Can I
> - use floating point at all ?


Not portably.

> - if yes: use sqrt, log, exp ?


No.

> - or at least, use intermediate values (other than
> macro identifiers) to clarify things and remain below
> the "4095 characters in a logical source line" limit?


Note that "logical source lines" occur in translation phase 2,
whereas macro expansion is done in phase 4 (and is done in terms
of tokens, not characters). The 4095 character limit affects
macro definitions, not macro expansions.

> I can think of enum as intermediates, [snip] but they have
> rather silly range limitations.


Yes, generally expressions using macro expansion are better
than using enum constants.

> An application would be, given EXPECTED, to define at compile
> time an array with EXPECTED + 12*sqrt(EXPECTED) elements, or
> some even more complex formula, [snip example]
>
> I think the above works for any EXPECTED>=900 up to
> some large value like ULONG_MAX-ULONG_MAX/19 and then some,
> and errs on the safe side, with at worse 5% wasted memory;
> but this is
> - unclear at best;
> - painful to extend to lower bounds or less wasted memory;
> - hard to generalize to more complex formula involving
> for example log or exp.


If you need to do something like this, generally a good way of
approaching it is to divide the input space up into ranges and
find a good integer approximation in each range. There can be
interplay between the ranges and the approximations chosen. For
example, using ceil( 12 * sqrt( x ) ) as the desired target (and
must never be less than that, or less than one), the target
function could be approximated using

#define SQ12(n) SQ12_((n))
#define SQ12_(n) ( \
n < 2 ? 12*n + (n==0) : \
n < 3 ? 17 : \
n < 4 ? 21 : \
n < 16 ? SQx(12*n/8,144*n) : \
n < 1055 ? SQx(12*n/13,144*n) : \
n < 26866 ? SQx(12*n/80,144*n) : \
n < 361166 ? SQx(12*n/331,144*n) : \
n < 3321166 ? SQx(12*n/1093,144*n): \
n < 22000000 ? SQx(12*n/2992,144*n) : \
n < 160000000 ? 12 * SQx(n/6543,n) : \
n < 1200000000 ? 12 * SQx(n/12500,n) : \
12 * SQx(n/45000,n) \
)

#define SQx( k, n ) SQx_((k),(n))
#define SQx_( k, n ) (1+SQ3_(k,n))
#define SQ3_( k, n ) SQ2_(SQ1_(k,n),n)
#define SQ2_( k, n ) SQ1_(SQ1_(k,n),n)
#define SQ1_( k, n ) ((k+n/k)/2)

#define EXPECTED 6999999

int HERE = SQ12( EXPECTED );

Obviously the ranges and specific constants were chosen by
experimentation. Naturally there is a tradeoff between the
complexity involved and the accuracy desired (and also what
input domain needs to be covered). The particular definition
above works over all 32 bit inputs, and has good accuracy (off
by at most one up to n = 20000000, and within a factor of
1.005 above that). Of course it is possible to find simpler
formulations or more accurate ones; the point is to pick an
approximation that suits the needs of the problem to be solved
-- dividing into ranges and using various approximations in
the various ranges is general and flexible, understandable,
and also fairly cheap in terms of expanded token count.

Incidentally, the sample code above generates an expansion
(the line with HERE in it) of about 3000 characters.

(Ben's suggestion is also good. For anyone interested I think
it's worth looking at the similarities and differences of the
two approaches.)
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      09-07-2012
Eric Sosman <(E-Mail Removed)> writes:

> On 9/4/2012 7:51 PM, Keith Thompson wrote:
>> "BartC" <(E-Mail Removed)> writes:
>>> "Kaz Kylheku" <(E-Mail Removed)> wrote in message
>>> news:(E-Mail Removed)...
>>>> On 2012-09-04, Francois Grieu <(E-Mail Removed)> wrote:
>>>>> Can I
>>>>> - use floating point at all ?
>>>>> - if yes: use sqrt, log, exp ?
>>>>
>>>> No. Constant expressions cannot contain funtion calls.
>>>
>>> Yet, an expression such as sqrt(9.0) seems to be reduced to 3.0 on the
>>> first two compilers I tried.

>>
>> Yes, I'm sure that's a common optimization.
>>
>> But the phrase "constant expression" is defined by the standard in
>> terms of what it can contain; it doesn't merely mean "an expression
>> that a sufficiently clever compiler can evaluate at compile time".
>>
>>> It's not much of a stretch to allow that to be used as an array
>>> dimension, the main stumbling block being that 3.0 is not integral,
>>> while adding an (int) cast makes it look like a runtime expression.

>>
>> But where do you draw the line between constant and non-constant
>> expressions? The authors of the standard already decided exactly
>> where to draw that line. Moving it in the direction of treating
>> more expressions as constant risks imposing requirements that some
>> compilers may not be able to meet.

>
> The Standard draws a line and says "All C compilers accept
> everything on this side of the line as constants." But the line
> is permeable: "An implementation may accept other forms of constant
> expressions" (6.6p10). The upshot:
>
> 1) A C compiler must accept `static int x[2+1];', because
> `2+1' is on the hither side of the line,
>
> 2) A C compiler may reject `static int x[strlen("abc")];'
> because `strlen("abc")' is on the thither side, but
>
> 3) A C compiler may accept `static int x[strlen("abc")];'
> under the "other forms" allowance, and need not even
> issue a diagnostic.
>
> Cases (2) and (3) illustrate why "It works with my compiler"
> does not define the language.


The principle is right, the specific example is wrong.
Expressions that contain a function call and that must
be constant expressions are constraint violations and
must have a diagnostic issued, regardless of whether
an implementation chooses to regard them as constant
expressions.
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      09-07-2012
Keith Thompson <(E-Mail Removed)> writes:

> "BartC" <(E-Mail Removed)> writes:
>> "Kaz Kylheku" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed)...
>>> On 2012-09-04, Francois Grieu <(E-Mail Removed)> wrote:
>>>> Can I
>>>> - use floating point at all ?
>>>> - if yes: use sqrt, log, exp ?
>>>
>>> No. Constant expressions cannot contain funtion calls.

>>
>> Yet, an expression such as sqrt(9.0) seems to be reduced to 3.0 on the
>> first two compilers I tried. [snip]

>
> But where do you draw the line between constant and non-constant
> expressions? The authors of the standard already decided exactly
> where to draw that line. [snip]


More specifically, they have drawn two lines, one representing
a minimum set of what are constant expressions, and one
representing which constructs are always out of bounds for
constant expressions -- kind of a lower bound and an upper
bound. And function calls are over the "not allowed" line.
 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      09-07-2012
"Tim Rentsch" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Keith Thompson <(E-Mail Removed)> writes:


>> But where do you draw the line between constant and non-constant
>> expressions? The authors of the standard already decided exactly
>> where to draw that line. [snip]

>
> More specifically, they have drawn two lines, one representing
> a minimum set of what are constant expressions, and one
> representing which constructs are always out of bounds for
> constant expressions -- kind of a lower bound and an upper
> bound. And function calls are over the "not allowed" line.


Perhaps it's about time then that the built-in mathematical functions were
classed as operators, not as arbitrary functions.

Compilers already do that for optimising, but aren't allowed to do that when
the code depends on it (expressions defining array bounds for example,
because it would break on another compiler.)

There are some numeric implications (eg. an array bound could vary slightly
between compilers and machines) but there already are many issues with
floating point anyway. And in examples like the OP's, it wouldn't really
matter.

--
Bartc

 
Reply With Quote
 
army1987
Guest
Posts: n/a
 
      09-07-2012
On Tue, 04 Sep 2012 19:14:10 +0200, Francois Grieu wrote:

> An application would be, given EXPECTED, to define at compile time an
> array with EXPECTED + 12*sqrt(EXPECTED) elements, or some even more
> complex formula, as required by


I would do this:

#define EXPECTED 15000 /* When changing this, please also change
ARRAY_SIZE accordingly. */
#define ARRAY_SIZE 16470 /* ceil(EXPECTED + 12*sqrt(EXPECTED)) */



--
[ T H I S S P A C E I S F O R R E N T ]
Troppo poca cultura ci rende ignoranti, troppa ci rende folli.
-- fathermckenzie di it.cultura.linguistica.italiano
<http://xkcd.com/397/>
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      09-07-2012
Tim Rentsch <(E-Mail Removed)> writes:
[...]
> Expressions that contain a function call and that must
> be constant expressions are constraint violations and
> must have a diagnostic issued, regardless of whether
> an implementation chooses to regard them as constant
> expressions.


I'm not convinced that's correct.

N1370 6.6p10 says

An implementation may accept other forms of constant expressions.

To take one example of a context requiring a constant expression,
6.8.4.2p3 says:

The expression of each case label shall be an integer constant
expression and no two of the case constant expressions in the
same switch statement shall have the same value after conversion.

If an implementation accepts `foo()` as a constant expression, then
using `foo()` in a case label doens't violate that constraint, because
it's a constant expression *for that implementation*.

This is different than the general permission to provide extensions
given by 4p6:

A conforming implementation may have extensions (including
additional library functions), provided they do not alter the
behavior of any strictly conforming program.

which does (I think!) require a diagnostic for any code that would
violate a constraint in the absence of the extension.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      09-07-2012
"BartC" <(E-Mail Removed)> writes:
> "Tim Rentsch" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> Keith Thompson <(E-Mail Removed)> writes:

>
>>> But where do you draw the line between constant and non-constant
>>> expressions? The authors of the standard already decided exactly
>>> where to draw that line. [snip]

>>
>> More specifically, they have drawn two lines, one representing
>> a minimum set of what are constant expressions, and one
>> representing which constructs are always out of bounds for
>> constant expressions -- kind of a lower bound and an upper
>> bound. And function calls are over the "not allowed" line.

>
> Perhaps it's about time then that the built-in mathematical functions were
> classed as operators, not as arbitrary functions.
>
> Compilers already do that for optimising, but aren't allowed to do that when
> the code depends on it (expressions defining array bounds for example,
> because it would break on another compiler.)
>
> There are some numeric implications (eg. an array bound could vary slightly
> between compilers and machines) but there already are many issues with
> floating point anyway. And in examples like the OP's, it wouldn't really
> matter.


Sorry, but I don't think that's a good idea. Consider, for example, a
cross compiler where the host and target systems have differing
floating-point precision. (Compilers need to handle this for
floating-point constant, but not for any more complicated expression.)

I think you're understating the problems caused by floating-point
rounding errors. It could be implementation-defined (or unspecified)
a given switch statement is legal, depending on whether the
expressions in two case labels evaluate to the same integer value.

And how often do you really need to use a floating-point function in a
constant expression? I don't think it's worth the additional complexity.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
total array size limitations? glennklockwood C Programming 10 03-16-2009 08:49 AM
service-policy output on a 3560 doesn't work, any workarounds ? hm klette Cisco 2 10-21-2005 09:36 AM
ASP.NET restricts server forms to one per page... workarounds... ??? nzanella@gmail.com ASP .Net 3 01-14-2005 04:54 PM
defining or not defining destructors johny smith C++ 8 07-02-2004 08:51 AM
g++: class size or file size limitations: NONTRIVIAL BUG Neil Zanella C++ 4 10-09-2003 01:49 PM



Advertisments