27

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

簡単な例を挙げれば、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])のようなもの)

20
  • 1
    とりあえず、本家の記事へのリンクを提示してもらえるとありがたいですが。
    – kmugitani
    Commented 2015年1月22日 0:38
  • 1
    @kotatsu n1256.pdf6.2.5 Types 20 の部分ですね。 これ自体はC99のドラフトですが、ネットからリンクできるソースとして使えると思います。
    – BLUEPIXY
    Commented 2015年1月22日 0:44
  • 2
    逆に、連続でないような実装を禁止する文言を見つけることができないのですが、どの部分からそのように判断されたのでしょうか? 6.2.5の20からは、Tの配列が連続したTの列であること、Tの配列の配列が連続したTの配列の列であることを示していますが、Tの配列の配列が連続したTの列であることは示していなように思います。
    – snak
    Commented 2015年1月22日 0:55
  • 4
    今回のケースはテストコードは意味が無いです。というのも、規格として「多次元配列は連続領域でなければならない」と記載されていないのであれば、多次元配列の実装方法はコンパイラ任せだからです。ここの実装が変われば、多次元配列におけるsizeofの実装も変わります。コンパイラが変われば結果が変わるということもあり得ます。
    – kotatsu
    Commented 2015年1月22日 2:09
  • 1
    @kotatsu 直接記述されていなくても、仕様内の記述から演繹的に導き出せるかどうか、というのが今回の質問(の前半部分)だと思うので、直接書いていないから実装依存であるというのは乱暴すぎるのではないかと思います。現実には、仕様に則っていないコンパイラも沢山あるので、拘っても仕方のないことなのかもしれませんが。
    – snak
    Commented 2015年1月22日 3:05

5 件の回答 5

11

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

  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により保証がないと当初考えていました。ただ、改めて確認すると問題無いように思えたので、こちらの主張は取り下げます。

12
  • 上記の"the total number of bytes in the array"が、パディングを含めたバイト数であったとしても、この記述には違反していないように読めるのですが、いかがでしょうか?
    – snak
    Commented 2015年1月22日 4:52
  • @snak 該当文面だけの解釈ではその通りですし、structではパディングを含むバイトサイズを返します。私の解釈のポイントは「多次元配列に対するsizeof演算子の仕様から演繹的に解釈すると、配列型では要素以外のパディングの存在が許容されない」という点です。また、6.5.3.4/p6例示は恒に成り立つべきであるという仮定もあります。(これは主張の増補材料としてですが)
    – yohjp
    Commented 2015年1月22日 5:04
  • 1
    ありがとうございます。まだ釈然としないので、ちょっと質問を変えます。short[7]を、shortのフィールドを7個持ち最後に2バイトのパディングがある(フィールド間にはパディングがない)構造体と同じメモリレイアウトで実装することが禁止されている、と考える根拠は何でしょうか?(sizeof short[7]は16を返すとします)6.5.3.4 p6の例に反するということ以外の根拠を自分では見つけられずにいます。
    – snak
    Commented 2015年1月22日 5:35
  • 1
    @snal 正直なところ、"パディング有レイアウトが禁止と考える根拠"は、1)6.5.3.4/p2文面で配列へのパディング言及がない一方で構造体にはその明記があること、2)多次元配列(T[2][7])の要素(T)を連続配置してもアライメント上の問題は起きえないこと、3)以上より処理系で冗長なオブジェクト表現(with padding)を選択する合理的理由が思いつかないこと、という程度です。
    – yohjp
    Commented 2015年1月22日 6:02
  • 1
    Strict Aliasing Ruleに関する懸念は、short a[2][2] = { 0, 1, 2, 3 }; short *p = &a[0][0] + 3; *p = 10; short n = a[1][1];のようなコードを書いた時に、n10ではなくて3になるような最適化をコンパイラがすることが許されるか、というような話ですね。しかし、この場合には、そのような最適化を許すようなルールはない、という話だと思います。
    – snak
    Commented 2015年1月22日 9:46
4

タグがCなのでオフトピ気味になりますが、C++だと、配列のサイズが要素のサイズ×要素数とあるので、配列の後ろにパディングが付かないことになりますね。

5.3.3 Sizeof p6 より引用:

When applied to an array, the result is the total number of bytes in the array. This implies that the size of an array of n elements is n times the size of an element.

ISO/IEC 14882:2003, 2011, 2014 で、上記の存在を確認しました。

1

あえて仕様を当たらず。

一般に配列a、型typeについて、

  1. &a[N]a + Nと常に同義である。
  2. a + N の結果は常に&a[0] + sizeof(*a) * N(ポインタ型を考慮しない単純加算)と一致する。
  3. sizeof(type[M])は常にsizeof(type) * Mと一致する。

ことが保証されていれば、連続していると言えると思います。
(そしてそれぞれ保証されているはず)

つまり

short array[2][7];
があったとき

  1. &array[1] = array + 1
  2. array + 1 = &array[0] + sizeof(*array) * 1 (ポインタ型を考慮しない単純加算)
  3. sizeof(*array) = sizeof(short[7]) = sizeof(short) * 7

ゆえに
&array[1] = &array[0] + sizeof(short) * 7 (ポインタ型を考慮しない単純加算)

この式は領域が連続していることを示していると思うわけです。

すなわち、メモリ内配置は

array[0][0]
array[0][1]
array[0][2]
array[0][3]
array[0][4]
array[0][5]
array[0][6]
array[1][0]
array[1][1]
array[1][2]
array[1][3]
array[1][4]
array[1][5]
array[1][6]

と連続しており、array[0][6]とarray[1][0]の間にパディングは存在し得ないということです。

2
  • 論点としては「3.sizeof(type[M])は常にsizeof(type) * Mと一致」が仕様上保証されるか?という点でしょうね。仕様文面からこのことが直接読み取れれば、仰る通りのシンプルな証明で済むのですけど…
    – yohjp
    Commented 2015年1月23日 4:56
  • @yohjp そうですね。質問に対する@kotatsuさんのコメントでは1.~3.が保証されてても不連続の可能性はある、と主張されているように見えたので、それに対する反論としてこの回答を書き始めた気がします。まあ、仕様を追求しなくても1.~3.は周知の事実だよねという、なんというか、厳密さよりもわかりやすさを優先した感覚的な回答もありかなぁとも思ったり思わなかったり。(単に私が仕様の解釈論争はあんまり好きじゃないだけという噂も)
    – Ripple
    Commented 2015年1月23日 15:13
1

仮に多次元配列を1次元配列として扱えない処理系が存在するなら、それらの処理系ではcallocやmemset等を独自に拡張する必要があります。
規格がそういった処理系も考慮しているなら、独自拡張しなくても済む仕様になってるはず。

0

追記:yohjpさんとsnakさんの回答・コメントより、配列の配列も配列なんだから連続だ、ということが腑に落ちましたので下記回答は撤回します。

コメント等の情報も加味して回答します。
私の回答としては「不連続かもしれない」です。

前提の配列は以下。

short array[2][7];

※結果は妄想であって、各種コンパイラが用意できるはずもなく、検証はしていないです。

1. パディング入れるよ、多次元配列も連続領域だよコンパイラ

sizeof(array) == 32
2*7*sizeof(short) == 28

2. パディング入れるよ、多次元配列は連続領域じゃないよコンパイラ

sizeof(array) == 32
2*7*sizeof(short) == 28

3. パディング入れないよ、多次元配列も連続領域だよコンパイラ

sizeof(array) == 28
2*7*sizeof(short) == 28

4. パディング入れないよ、多次元配列は連続領域じゃないよコンパイラ

sizeof(array) == 28
2*7*sizeof(short) == 28

パディングなしの場合、sizeof(short[7])の評価は常に14で、それはarray[0][0]のアドレスが0x1000array[1][0]のアドレスが0x2000となっていても変わらないため、連続領域かそうでないかは区別が付かないと思いますがいかがでしょうか。

sizeofとパディングについて私が何か根本的に間違ってますか・・・?

2
  • @yohjpさんの解答にあるように、2次元配列を1次元配列の1次元配列と考えると、2次元配列中の1次元配列同士は連続して配置される必要があります。その前提ですと、4は仕様違反です。1に関しては、それが許されるのかどうか疑問です(例えば、array[0][6]を指すポインタをインクリメントすると、パディング部分を飛ばしてarray[1][0]を指すようになるということですよね?)これらを前提として、2と3を区別するために、sizeof(array)2*7*sizeof(array[0][0])を比較すればいいのではないか、というのが、質問の3番目であると理解しています。
    – snak
    Commented 2015年1月22日 5:16
  • あーなるほど。配列の配列も配列なので連続しているべき、ということですね。2.と4.は本来ないはずだ、と。
    – kotatsu
    Commented 2015年1月22日 5:23

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。