文字列の一般的なパッケージ方式のメモリレイアウト(1):メタデータと文字列の内容、全体として分離しますか?
(Discramer:許可なしに転載しないでください.転載するなら先に連絡してください.
著者:RednaxelaFX->rednaxelafx.itey.com)
文字列の一般的なパッケージ方式のメモリレイアウトシリーズ:
[url=http://rednaxelafx.iteye.com/blog/1969833」(0):手に持っているのは何ですか?
[size=medium]1、メタデータ、文字列の内容:全体ですか?それとも分離ですか?[/size]
[url=を引く]http://rednaxelafx.iteye.com/blog/1969833前の[/url]を見て、今回は文字列のメタデータと文字列の内容が全体ですか?それとも分離ですか?
文字列に共通するメタデータは、オプションであり、例えば、
*文字列の内容を指すポインタ/参照
全体式であればこの情報は不要ですが、分離式では文字列の実際の内容を指すポインタが必要です.
*文字列の長さ
おそらく、文字数(ASCIIコードのstd:string)、コードunit個数(Java、.NET、JavaScriptなどの文字列をsequence of UTF-16 code unitsと表現する)、文字列の実際のバイト数(例えば、[url==http://msdn.microsoft.com/en-us/library/windows/desktop/ms221069.aspx」BSTR[url]).それぞれ用途があり、それぞれ長所と短所がある.
文字列が'\0'で終わることが要求され、文字列内に'\0'が含まれてはいけない場合、文字列長はオプションのメタデータである.さもなくば必要です.
*オフセット量
あるストリングスタイプが他のストリングスのサブストリングを表してもよく、またブザーを共有すると、オフセット量を記録することができます.オフセット量は、下付きでも良いし、ポインタでもいいし、システムによっては、オブジェクトの頭だけを実行できるか、またはオブジェクトの内部を指すポインタも許される.
*文字列のハッシュ値
単なるキャッシュ特性の最適化で、ハッシュ・コンテナのキーとしてのstringの性能を向上させます.
*文字列コード
これは、複数の符号化された文字コンテンツを使用することができる文字列実装にのみ存在し、例えばRuby 1.9またはより高いバージョンの[url=http://ruby-doc.org/core-2.0.0/String.html」String[/url]類.固定符号化しか使用できない文字列タイプはこの情報を必要としません.Javaと.NETの内部構築文字列など、すでにタイプに含まれています.
上記のメタデータはいずれもオプションですので、いらないで、一番「裸」にしてもいいです.陳の大きな大文字の[url=http://blog.csdn.net/solstice/article/details/12613275」面接問題のC++文字列で使える[url=https://github.com/chenshuo/recipes/blob/master/string/StringTrivial.h」char*メンバーを一つだけカプセル化しました.
もしある文字列タイプが上記のオプションのメタデータを持っているなら、「全体式」と「分離式」の違いがあります.
名前の通り、前者はメタデータと文字列の内容がくっついて一つの全体とします.後者は、少なくとも一部のメタデータと文字列の内容が分離され、一つの文字列のインスタンスは複数のオブジェクトの組み合わせで構成される.
「全体式」は、例えば32ビットx 86上、NET 4.0のSystem.Stringのメモリレイアウトはこうです.
フォロワー
ここで、文字列のメタデータ部分と実際のコンテンツは明らかに2つのブロックに分割される.
*メタデータは2つのフィールド、1つは実際のコンテンツを指すvalueフィールド、もう1つはキャッシュされたハッシュ値のhashフィールドです.固定長さのjava.lang.Stringの例があります.
*実際の文字列メモリには他のchar[]オブジェクトがあります.この配列オブジェクトは文字列の長さのメタデータを含んでいます.
前に述べたRuby 1.8.7のSymbolはさらに分離されました.でもそれは特例です.
明らかに、全体式は分離式よりコンパクトで、メモリの占有量が少なく、データの局所性が高い.なぜ分離式を使うのですか?
少なくとも以下のいくつかの可能性があります.
[b]1)分離式は、全体式よりも少ない「特殊タイプ」です.[/b]
いくつかのクラスのオブジェクト指向言語に基づいて、例えばOracle/Sun JDK 6によって実現されるJavaは、配列が唯一の可変長のオブジェクトタイプである(注1).言い換えれば、他のオブジェクトだけが、そのタイプを決定すれば、オブジェクトのサイズが分かります.配列光は、タイプがまだ足りないと判断し、配列のインスタンスに長さ情報を保存し、種類と長さを組み合わせてオブジェクトサイズを決定する必要がある.
このような実装では、他の本来の意味は可変長のタイプであり、上述の例のjava.lang.Stringのように、オブジェクトサイズ自体が固定されており、可変長の部分はchar[]によって実現される.java.util.rayList、HashMapなどもそうです.
配列に依存しなくても、例えばjava.util.Linked Listによって実現されるチェーンテーブルのような、チェーン構造によって可変長タイプを実現することができる.
長いオブジェクトで長く包装された配列は、多くのプログラミング言語のオブジェクトの実現ニーズを満たすことができます.また、「可変長さ」を配列という特殊なタイプに限定しているため、このようなデザインは「清潔だ」と考える人もいます.
C++のように柔軟な言語であっても、内部に構築されたnew演算子だけでオブジェクトを作成する場合(newを積載しない、placment newを使わない、allocatorをカスタマイズしない)は、配列だけが可変長さであり、種類のインスタンスサイズはsizef演算子がコンパイル期間で得た結果と同じである(注2)を選択します.C++のこのサブセットを使ってプログラムを書くと、長いデータ構造を実現するためにもよく使われる配列(またはstd::vectorで、その中にも動的に割り当てられた配列に依存します.)
このサブセットの外で、C++は割り当て行為をカスタマイズすることができます.オブジェクトにsizofの値よりも実際のメモリ空間を割り当てることで、特殊な可変長データ構造を自制することができます.このようなデザインは「不潔」と考える人もいます.私は大丈夫です.…
上に展示されているCLRv 4によって実現されるSystem.Stringタイプは配列以外のもう一つの特殊なタイプでなければなりません.VMには専用のサポートが必要です.配列のサポートコードと似ていますが、完全ではないので、特殊な実装を多く書かなければなりません.サボるにはこの道を選ばないです.しかし、性能が高いなら、とにかくstringに特化して実現しなければなりません.特殊なタイプを作ってもいいです.(JVMを見て…)
Java側にもjava.lang.Stringを特殊なタイプにする研究があり、収益がいいです.次の一連の論文を参考にしてもいいです.
[url=http://ssw.jku.at/Research/Papers/Wimmer08PhD/Wimmer08PhD.pdf」Automatic Object Inlining in a Java Virtual Machine[/url]
[url=http://www.ssw.uni-linz.ac.at/Research/Papers/Haeubl08Master/Haeubl08Master.pdf」Optimized Strings for the Java Hot Spot VM[/url]
[url=http://www.christianwimmer.at/Publications/Haeubl10a/Haeubl10a.pdf」Compect and Efficient Strings for Java[/url]
Oracle JDK 7から、いずれにしてもjava.lang.Stringはサブストリングの共有を捨てて、いつか論文で述べた特化で実現できるかもしれません.JDK 9?ほほほ.
注1:Oracle JDK 7または以上のバージョンのHotSpot VMでは、java.lag.lassの例も可変長タイプになりましたので、上記の文字は特にバージョンを限定しました.
注2:C+14ドラフトの[url=http://isocpp.org/files/papers/N3639.html」runtime-sized array[url]も対象例のメンバーとしては使えません.
[b]2)分離式はより柔軟性が高い[/b]
全体的なアプローチは、通常は「文字列の内容を指すポインタ」というメタデータではなく、文字列の内容が文字列オブジェクトの固定オフセットから始まる必要があります.このようにコンパクトでコンパクトで、柔軟な変化をするのは難しいです.
(「通常」は「絶対」ではないですよ.)
分離式には通常、「文字列の内容を指すポインタ」というメタデータがあり、機能的にいくつかの機能を実現することができます.
*文字列の実際の内容のソースを外部から自由に指定してください.グローバルデータエリア、スタック、積み上げに関係なく.http://www.cppblog.com/vczh/]vzch大[/url]の[url=http://gac.codeplex.com/SourceControl/latest#Common/Source/String.h」vl::Object String[/url]はこの可能性を許す
*複数の文字列のインスタンスに一つのバfferを共有させます.これはサブストリング共有のシーンを含みます.
など.
著者:RednaxelaFX->rednaxelafx.itey.com)
文字列の一般的なパッケージ方式のメモリレイアウトシリーズ:
[url=http://rednaxelafx.iteye.com/blog/1969833」(0):手に持っているのは何ですか?
[size=medium]1、メタデータ、文字列の内容:全体ですか?それとも分離ですか?[/size]
[url=を引く]http://rednaxelafx.iteye.com/blog/1969833前の[/url]を見て、今回は文字列のメタデータと文字列の内容が全体ですか?それとも分離ですか?
文字列に共通するメタデータは、オプションであり、例えば、
*文字列の内容を指すポインタ/参照
全体式であればこの情報は不要ですが、分離式では文字列の実際の内容を指すポインタが必要です.
*文字列の長さ
おそらく、文字数(ASCIIコードのstd:string)、コードunit個数(Java、.NET、JavaScriptなどの文字列をsequence of UTF-16 code unitsと表現する)、文字列の実際のバイト数(例えば、[url==http://msdn.microsoft.com/en-us/library/windows/desktop/ms221069.aspx」BSTR[url]).それぞれ用途があり、それぞれ長所と短所がある.
文字列が'\0'で終わることが要求され、文字列内に'\0'が含まれてはいけない場合、文字列長はオプションのメタデータである.さもなくば必要です.
*オフセット量
あるストリングスタイプが他のストリングスのサブストリングを表してもよく、またブザーを共有すると、オフセット量を記録することができます.オフセット量は、下付きでも良いし、ポインタでもいいし、システムによっては、オブジェクトの頭だけを実行できるか、またはオブジェクトの内部を指すポインタも許される.
*文字列のハッシュ値
単なるキャッシュ特性の最適化で、ハッシュ・コンテナのキーとしてのstringの性能を向上させます.
*文字列コード
これは、複数の符号化された文字コンテンツを使用することができる文字列実装にのみ存在し、例えばRuby 1.9またはより高いバージョンの[url=http://ruby-doc.org/core-2.0.0/String.html」String[/url]類.固定符号化しか使用できない文字列タイプはこの情報を必要としません.Javaと.NETの内部構築文字列など、すでにタイプに含まれています.
上記のメタデータはいずれもオプションですので、いらないで、一番「裸」にしてもいいです.陳の大きな大文字の[url=http://blog.csdn.net/solstice/article/details/12613275」面接問題のC++文字列で使える[url=https://github.com/chenshuo/recipes/blob/master/string/StringTrivial.h」char*メンバーを一つだけカプセル化しました.
もしある文字列タイプが上記のオプションのメタデータを持っているなら、「全体式」と「分離式」の違いがあります.
名前の通り、前者はメタデータと文字列の内容がくっついて一つの全体とします.後者は、少なくとも一部のメタデータと文字列の内容が分離され、一つの文字列のインスタンスは複数のオブジェクトの組み合わせで構成される.
「全体式」は、例えば32ビットx 86上、NET 4.0のSystem.Stringのメモリレイアウトはこうです.
フォロワー
System.String (C# ) / StringObject (C++ )
(-4) [ m_SyncBlockValue ] \ ObjHeader: sync block index
--> (+0) [ m_pMethTab ] / Object: MethodTable pointer
(+4) [ m_stringLength = 0x00000006 ] // length, in code unit count
(+8) [ m_firstChar = 0x0066 ('f') ] // string contents starts here
(+10) [ 0x006F ('o') ]
(+12) [ 0x006F ('o') ]
(+14) [ 0x0062 ('b') ]
(+16) [ 0x0061 ('a') ]
(+18) [ 0x0072 ('r') ]
(+20) [ 0x0000 ] (null-terminate)
(+22) [ (padding) 0x0000 ][/code]
m_SyncBlockValue m_pMethTab .NET , ;m_stringLength , m_firstChar , '\0' , 4 2 padding。
System.String 。
“ ” 。 64 [url=http://hg.openjdk.java.net/jdk7u/jdk7u/jdk/file/b5326675e374/src/share/classes/java/lang/String.java]Oracle JDK7u40/OpenJDK 7u[/url] java.lang.String ( ):
"foobar"
[code="">24 :
java.lang.String (Java ) / oopDesc (C++ )
--> (+0) [ _mark ] 32 :
(+8) [ _metadata ] char[] (Java ) / typeArrayOopDesc (C++ )
(+12) [ value ] --> (+0) [ _mark ]
(+16) [ hash = 0x00000000 ] (+8) [ _metadata ]
(+20) [ (padding) 0x00000000 ] (+12) [ _length = 0x00000006 ]
(+16) [ 0x0066 ('f') ]
(+18) [ 0x006F ('o') ]
(+20) [ 0x006F ('o') ]
(+22) [ 0x0062 ('b') ]
(+24) [ 0x0061 ('a') ]
(+26) [ 0x0072 ('r') ]
(+28) [ (padding) 0x00000000 ]
(私のところではhttp://www.valleytalk.org/2011/07/28/java-%E7%A8%8B%E5%BA%8F%E7%9A%84%E7%BC%96%E8%AF%91%EF%BC%8C%E5%8A%A0%E8%BD%BD-%E 5%92%8 C-E 6%89%A 7%E 8%A 8 C/'以前作ったプレゼンテーションの中にもっと綺麗な絵があります.参照してください.ここで、文字列のメタデータ部分と実際のコンテンツは明らかに2つのブロックに分割される.
*メタデータは2つのフィールド、1つは実際のコンテンツを指すvalueフィールド、もう1つはキャッシュされたハッシュ値のhashフィールドです.固定長さのjava.lang.Stringの例があります.
*実際の文字列メモリには他のchar[]オブジェクトがあります.この配列オブジェクトは文字列の長さのメタデータを含んでいます.
前に述べたRuby 1.8.7のSymbolはさらに分離されました.でもそれは特例です.
明らかに、全体式は分離式よりコンパクトで、メモリの占有量が少なく、データの局所性が高い.なぜ分離式を使うのですか?
少なくとも以下のいくつかの可能性があります.
[b]1)分離式は、全体式よりも少ない「特殊タイプ」です.[/b]
いくつかのクラスのオブジェクト指向言語に基づいて、例えばOracle/Sun JDK 6によって実現されるJavaは、配列が唯一の可変長のオブジェクトタイプである(注1).言い換えれば、他のオブジェクトだけが、そのタイプを決定すれば、オブジェクトのサイズが分かります.配列光は、タイプがまだ足りないと判断し、配列のインスタンスに長さ情報を保存し、種類と長さを組み合わせてオブジェクトサイズを決定する必要がある.
このような実装では、他の本来の意味は可変長のタイプであり、上述の例のjava.lang.Stringのように、オブジェクトサイズ自体が固定されており、可変長の部分はchar[]によって実現される.java.util.rayList、HashMapなどもそうです.
配列に依存しなくても、例えばjava.util.Linked Listによって実現されるチェーンテーブルのような、チェーン構造によって可変長タイプを実現することができる.
長いオブジェクトで長く包装された配列は、多くのプログラミング言語のオブジェクトの実現ニーズを満たすことができます.また、「可変長さ」を配列という特殊なタイプに限定しているため、このようなデザインは「清潔だ」と考える人もいます.
C++のように柔軟な言語であっても、内部に構築されたnew演算子だけでオブジェクトを作成する場合(newを積載しない、placment newを使わない、allocatorをカスタマイズしない)は、配列だけが可変長さであり、種類のインスタンスサイズはsizef演算子がコンパイル期間で得た結果と同じである(注2)を選択します.C++のこのサブセットを使ってプログラムを書くと、長いデータ構造を実現するためにもよく使われる配列(またはstd::vectorで、その中にも動的に割り当てられた配列に依存します.)
このサブセットの外で、C++は割り当て行為をカスタマイズすることができます.オブジェクトにsizofの値よりも実際のメモリ空間を割り当てることで、特殊な可変長データ構造を自制することができます.このようなデザインは「不潔」と考える人もいます.私は大丈夫です.…
上に展示されているCLRv 4によって実現されるSystem.Stringタイプは配列以外のもう一つの特殊なタイプでなければなりません.VMには専用のサポートが必要です.配列のサポートコードと似ていますが、完全ではないので、特殊な実装を多く書かなければなりません.サボるにはこの道を選ばないです.しかし、性能が高いなら、とにかくstringに特化して実現しなければなりません.特殊なタイプを作ってもいいです.(JVMを見て…)
Java側にもjava.lang.Stringを特殊なタイプにする研究があり、収益がいいです.次の一連の論文を参考にしてもいいです.
[url=http://ssw.jku.at/Research/Papers/Wimmer08PhD/Wimmer08PhD.pdf」Automatic Object Inlining in a Java Virtual Machine[/url]
[url=http://www.ssw.uni-linz.ac.at/Research/Papers/Haeubl08Master/Haeubl08Master.pdf」Optimized Strings for the Java Hot Spot VM[/url]
[url=http://www.christianwimmer.at/Publications/Haeubl10a/Haeubl10a.pdf」Compect and Efficient Strings for Java[/url]
Oracle JDK 7から、いずれにしてもjava.lang.Stringはサブストリングの共有を捨てて、いつか論文で述べた特化で実現できるかもしれません.JDK 9?ほほほ.
注1:Oracle JDK 7または以上のバージョンのHotSpot VMでは、java.lag.lassの例も可変長タイプになりましたので、上記の文字は特にバージョンを限定しました.
注2:C+14ドラフトの[url=http://isocpp.org/files/papers/N3639.html」runtime-sized array[url]も対象例のメンバーとしては使えません.
[b]2)分離式はより柔軟性が高い[/b]
全体的なアプローチは、通常は「文字列の内容を指すポインタ」というメタデータではなく、文字列の内容が文字列オブジェクトの固定オフセットから始まる必要があります.このようにコンパクトでコンパクトで、柔軟な変化をするのは難しいです.
(「通常」は「絶対」ではないですよ.)
分離式には通常、「文字列の内容を指すポインタ」というメタデータがあり、機能的にいくつかの機能を実現することができます.
*文字列の実際の内容のソースを外部から自由に指定してください.グローバルデータエリア、スタック、積み上げに関係なく.http://www.cppblog.com/vczh/]vzch大[/url]の[url=http://gac.codeplex.com/SourceControl/latest#Common/Source/String.h」vl::Object String[/url]はこの可能性を許す
*複数の文字列のインスタンスに一つのバfferを共有させます.これはサブストリング共有のシーンを含みます.
など.