2次元配列は不連続か?

投稿者: Anonymous

本家の方でちょっと議論になったのですが、英語には弱く知識も不十分ということもあって英語での議論では相手の主張がよく納得ができなかったのでこちらで質問させて頂きたいと思います。

簡単な例を挙げれば、short array[n][m];という配列がある時、

short *p = &array[0][0];
for(int i = 0;i < n*m; ++i)
    *p++ = 1;

は、

for(int i = 0; i < n; ++i)
    for(int j = 0; j < m; ++j)
        array[i][m] = 1;


同じ挙動をすることが保証されているか?
言い換えれば、2次の配列はその最小要素(つまりshort int)が連続していることが保証されているか?
ということです。

標準では、「配列はその要素は連続しており隙間はない」とされていますが、
その方の主張によると、
「1次元配列は確かにそうであるが、2次元配列は必ずしもそうではない。」
例えばshort a[2][7];のような副配列を考える時、
Cでは2次元配列は配列の配列であり、その意味で要素としてshort [7];は隙間なく連続しているが、
副配列であるshort [7];の最後には調整パディングが付与されているかもしれない。
そのような場合2次元配列全体としてみると連続していない。
(つまり先述の例のような場合の動作は保証されない)

確かに副配列の最後にパディングが存在しても標準の言と矛盾しないとは思いますが、
そもそもそのような(配列でパディングが付与される)ことがあるのかどうかも疑問です。
(構造体でメンバー間でパディングがある場合があることは承知しています、しかし配列の最後にパディングが付与されsizeof(short[7])8*sizeof(short)になるとは思えません。)
例えば、short a[4];short b[5];もアラインメントの問題なくアクセスできます、
そのような手段がある(つまり最小構成要素であるshortにアクセスできる)中でshort a[14](連続している)を解釈上short a[2][7];(不連続である?)と内部の表現が違うというのは納得できません。
そのようなパディングがそもそも必要無いと思うし、
もしそのようなパディングが存在するような内部イメージを持つならアドレス演算を複雑にするだけだと思います。(Cの理念に反する?)

また、対象としている配列が

sizeof(array) == n*m*sizeof(array[0][0])

が真である場合にはそのようなパディングが存在しない、
なので、この場合連続であるといってもよく、先述の例の動作は保証される。
と思ったのですが、
「それでも動作は保証されない。境界制約のルールに違反する。」
と言われました。
私の理解としては、short *p = &array[0][0]; のようなことは最小構成要素が同じshortであり、連続している場合(つまりメモリのサイズが同じでパディングを有していないと考えられる場合)問題無いと思えます。(逆に最小構成要素が異なる場合、例えばchar *int *に変換してintでアクセスすることは問題がある。)

私の理解が間違っているとしたら何が間違っているのでしょうか?
このようなこと(連続か不連続か)をハッキリさせるような文言が標準にありますか?


長くて要点がはっきりしない部分もあると思うのでまとめを追加します。

Q:多次元配列は不連続か?(不連続の意味合いの説明はもういいと思うので略)
A:
標準に記載がない以上、連続かも知れないし、不連続かもしれない。
不連続かも知れないので不連続だとして扱う必要がある。
(つまりサンプルコードの動作は保証されないものとしなければならない)

Q:では、連続すると判断ができた場合のサンプルコードの動作は保証されるか?
A:(私の理解では保証される)

Q:自分のシステム+コンパイラで連続する(あるいは不連続)と判断するためにどのようなコードを書けばよいか?
A:(私の理解ではsizeof(array) == n*m*sizeof(array[0][0])のようなもの)

解決

私の解釈では以下の通りです。

  1. 2次元配列要素の連続性保証は直接明言されないが、演繹的には連続したメモリ配置であるといえる。
  2. ただし、2次元配列上での1次元配列的な要素走査(*p++)は、その動作保証がなされない。
  3. 以上より、質問文中のサンプルプログラムは同じ挙動を示す。(そうならないC言語処理系は合理的に存在し得ないという態度)

以降の解釈はWG14/N1256 ISO/IEC 9899:TC3(C99言語仕様)に基づきます。


  1. 2次元配列要素の連続性保証は直接明言されないが、演繹的には連続したメモリ配置であるといえる。

6.2.5/p20により、1次元配列(short [7])ではその要素(short)の連続性が明らかに保証されます。2次元配列(short [2][7])の要素は1次元配列型(short [7])であり、この1次元配列型の連続性が明らかに保証されます。2次元配列(short [2][7])の全要素の連続性が保証されるか否かは、その配列要素型short [7]同士の”間”にパディングバイトが存在しえるかという問題に帰着できます。

20 Any number of derived types can be constructed from the object, function, and incomplete types, as follows:

  • An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. […]
  • […]

6.5.3.4/p2-3にはsizeof演算子は「オペランド式の型が占めるバイトサイズを返す」「オペランドが配列型の場合は、配列が占める総バイトサイズを返す」とあります。

2 The sizeof operator yields the size (in bytes) of its operand, which may be an expression or the parenthesized name of a type. The size is determined from the type of the operand. The result is an integer. If the type of the operand is a variable length array type, the operand is evaluated; otherwise, the operand is not evaluated and the result is an integer constant.

3 […] When applied to an operand that has array type, the result is the total number of bytes in the array. When applied to an operand that has structure or union type, the result is the total number of bytes in such an object, including internal and trailing padding.

short array[2][7];では、sizeof(array[0][0])short型サイズ(例えば2)、sizeof(array[0])sizeof(short[7])つまりshort型×2sizeof(array)sizeof(short[2][7])つまりsizeof(short[7])x2short型×2×7となるべきです。先ほど懸念したパディングがどこかに存在すると仮定した場合、この制約を満たすことができなくなるため、パディングバイトはその存在が許されないと考えます。(下図参照)

// 要素short型が*連続配置*された配列short[7]
+---+---+-//-+---+
| s | s | .. | s |  sizeof(short)*7 == sizeof(short[7])
+---+---+-//-+---+

// 要素(short[7])型が*連続配置*された配列short[2][7]
+------+------+
| s[7] | s[7] |  sizeof(short[7])*2 == sizeof(short[2][7])
+------+------+

これらより、配列要素数の計算式が期待通り動作すると保証されています。(6.5.3.4/p6は例示にすぎず、原理主義的立場では仕様(normative)ではありませんが、前掲解釈を増補するものとみなせます。)

6 EXAMPLE 2 Another use of the sizeof operator is to compute the number of elements in an array:
sizeof array / sizeof array[0]


補足:@snakさんに指摘頂いた、配列実装のメモリレイアウトとして「末尾パディングはあり得ないのか?」という点について、英語版StackOverflowに質問”Can an array have trailing padding?“がありました。付いていた回答の主張は、私の解釈と同じで「そうする理由が存在しない」という点です。また、6.5.9/p6 ==演算子セマンティクスを根拠として提示されていました。

6 Two pointers compare equal if and only if both are null pointers, […] or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space. 94)

脚注94) Two objects may be adjacent in memory because they are adjacent elements of a larger array or adjacent members of a structure with no padding between them, or because the implementation chose to place them so, even though they are unrelated. If prior invalid pointer operations (such as accesses outside array bounds) produced undefined behavior, subsequent comparisons also produce undefined behavior.


2点目については、C99仕様の6.5/p7、いわゆるStrict Aliasing Ruleにより保証がないと当初考えていました。ただ、改めて確認すると問題無いように思えたので、こちらの主張は取り下げます。

回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *