32ビット整数がオーバーフローする場合、64ビット長の構造体ではなく、40ビット構造体を使用することは可能ですか？

質問

例えば32ビット整数がオーバーフローしている場合、アップグレードではなく int を long の範囲だけが必要な場合，40ビット型を使うことができるのでしょうか？ ⁴⁰ の範囲のみを必要とする場合、40 ビットの型を使用することはできますか？

もしそうなら、どのように？

数十億を相手にしなければならないので、スペースの制約の方が大きいです。

どのように解決するのですか？

はい、でも...

それは確かに 可能 を使用しないプログラムでは）通常、無意味です。 億円 を使用しないプログラムでは)無意味です。

#include <stdint.h> // don't want to rely on something like long long
struct bad_idea
{
    uint64_t var : 40;
};

ここで var は確かに40ビットの幅を持ちますが、その代償として を犠牲にして、40ビットの幅を持つことになります。 の代償として、生成されるコードの効率は低下し ("much" は非常に間違っていることが判明しました。測定されたオーバーヘッドはわずか 1 ～ 2% で、以下のタイミングを参照してください)、通常は無駄になります。同じ構造にパックしたい別の 24 ビット値 (または 8 ビットと 16 ビットの値) が必要でない限り、アライメントは得られるかもしれないものを放棄することになります。

いずれにせよ、何十億ものこれらの値がない限り、メモリ消費における効果的な違いは顕著ではありません (しかし、ビット フィールドを管理するために必要な余分なコードは顕著になります!)。

注意してください。

この質問は、その間に更新されました。 億円 残りの 24 ビットに何か別のものを格納するか、40 ビットの値をそれぞれ 8 またはその倍数の構造体に格納するなどして）構造体のアライメントとパディングによって得られる利点を失わないような措置を取ることが前提です。

3 バイトの保存 10 億回 は、必要とするメモリ ページが明らかに少なくなるため、キャッシュおよび TLB のミス、そして何よりもページフォルト (1 つのページフォルトで何千万もの命令の重み付け) の発生が少なくなるため、価値があります。

上記のスニペットは残りの 24 ビットを使用しませんが (単に 40 ビットを使用する部分を示しているだけです)、メモリを保持するという意味でこのアプローチを本当に有用にするには、次のようなものが必要になるでしょう。

struct using_gaps
{
    uint64_t var           : 40;
    uint64_t useful_uint16 : 16;
    uint64_t char_or_bool  : 8;  
};

構造体のサイズとアライメントは64ビット整数と同じになるので、例えばこのような構造体の配列を10億個作っても（コンパイラ固有の拡張を使わなくても）何も無駄にはなりません。8 ビットの値を使用しない場合は、48 ビットと 16 ビットの値を使用することもできます（より大きなオーバーフローのマージンが得られます）。

または、ユーザビリティを犠牲にして、8 つの 40 ビット値を構造体に入れることもできます（40 と 64 の最小公倍数は 320 = 8*40 です）。もちろん、構造体の配列の要素にアクセスするコードは、次のようになります。 大いに より複雑になります（しかし、おそらく operator[] を実装し、線形配列の機能を回復させ、構造の複雑さを隠すことができるかもしれません）。

更新しました。

ビットフィールド（およびビットフィールド参照による演算子のオーバーロード）がどのようなオーバーヘッドをもたらすかを確認するために、簡単なテストスイートを書きました。コードは（長さの関係で）次の場所に掲載しました。 gcc.godbolt.org 私の Win7-64 マシンからのテスト出力は次のとおりです。

Running test for array size = 1048576
what       alloc   seq(w)  seq(r)  rand(w)  rand(r)  free
-----------------------------------------------------------
uint32_t    0      2       1       35       35       1
uint64_t    0      3       3       35       35       1
bad40_t     0      5       3       35       35       1
packed40_t  0      7       4       48       49       1


Running test for array size = 16777216
what        alloc  seq(w)  seq(r)  rand(w)  rand(r)  free
-----------------------------------------------------------
uint32_t    0      38      14      560      555      8
uint64_t    0      81      22      565      554      17
bad40_t     0      85      25      565      561      16
packed40_t  0      151     75      765      774      16


Running test for array size = 134217728
what        alloc  seq(w)  seq(r)  rand(w)  rand(r)  free
-----------------------------------------------------------
uint32_t    0      312     100     4480     4441     65
uint64_t    0      648     172     4482     4490     130
bad40_t     0      682     193     4573     4492     130
packed40_t  0      1164    552     6181     6176     130

このことからわかるのは、ビットフィールドの余分なオーバーヘッドは無視できますが、キャッシュに適した方法で直線的にデータにアクセスする場合、便宜上ビットフィールド参照で演算子をオーバーロードすると、かなり大幅に（約3倍）増加するということです。一方、ランダムアクセスでは、それはほとんど問題になりません。

これらのタイミングは、ビットフィールドよりも全体的にまだ高速であるため、単に 64 ビット整数を使用する方が良いことを示唆しています (より多くのメモリに触れるにもかかわらず)。物理RAMを使い切ると、かなり違ってくるかもしれません(テストしてませんが)。