Luaにおける文字列タイプのソースコード実装
8474 ワード
概要
Luaは完全に8ビット符号化を採用し、Lua文字列の文字は任意の数値符号化を有し、数値0を含むことができる.すなわち、任意のバイナリデータを1つの文字列に格納することができる.Luaの文字列は可変値(immutable values)です.変更すると、実質的に新しい文字列が作成されます.前述の「Luaにおけるデータ型のソースコード実装」によれば、Luaでは、文字列は自動メモリ管理メカニズムによって管理されるオブジェクトであり、連合体TStringによって文字列値の格納が実現される.以下、Lua 5.2.1のソースコードから文字列の実装を見て、Luaで文字列を使用する際の注意点をまとめます.
ソース実装
まず、文字列に対応するデータ構造TStringを見てみましょう.そのソースコードは以下の通りです(lobject.h).
この連合体の定義には、いくつかの点が説明に値します.
I、連合体TStringのメンバーL_Umaxalign dummyは、最大長のCタイプとの位置合わせを保証するために使用され、以下のように定義されています(llimits.h).
他の回収可能なオブジェクト(tableなど)の実装では、この連合体メンバーも見られます.これは、メモリの位置合わせによって、CPUがメモリにアクセスする速度を速めることを目的としています.
II、連合体のメンバーtsvこそ文字列を実現するために本当に使われている.メンバーCommonHeaderはGCに使用され、マクロ形式ですべての回収可能オブジェクトで定義されます.コードは以下の通りです(lobject.h).
このマクロに対応する構造体の形式は以下の通りである(lobject.h):
構造体Gcheaderは、一般的なリサイクル可能オブジェクトunion GCObjectの定義で役立ちます.
III、lu_byte extraは短い文字列に対して、この文字列が保留字であるかどうかを記録するために使用され、長い文字列に対して、Hash値を不活性に求めるために使用することができる.unsigned int hashメンバーは文字列に対応するHash値である(Luaが文字列のHash値をどのように計算するかは後述する).size_t lenは文字列の長さを表すために使用されます.
IV,上の構造体は1つの文字列の構造を記述しただけであり,真の文字列データ保存は構造体の後に続く保存である.
Lua 5.2.1以前は、文字列の長さと短い文字列を区別することなく、すべての文字列が1つのグローバルなHashテーブルに保存されていたが、Lua仮想マシンにとって、同じ文字列には1つのデータしかない.Lua 5から.2.1から、短い文字列(現在の定義は長さが40以下)をグローバルHashテーブルに配置するだけで、長い文字列は独立して生成され、Hash値を計算する際にランダムシードを導入することで、Hash Dos--攻撃者が同じHash値の異なる文字列を非常に多く構築することを防止し、Luaが外部から文字列を押し込んでグローバルな文字列Hashテーブルに入る効率を低下させる.次はLua 5.2.1では、対応するコードがlstringである新しい文字列を生成する.c中:
(1)文字列長がLUAI_より大きい場合MAXSHORTLEN(デフォルトは40)は、長い文字列であり、文字列インタフェースを作成する関数createstrobjを直接呼び出します(もちろん、文字列の長さはメンバーsize_t lenに保存する必要がありますが、そうでなければ直接戻ります).コードは以下の通りです(lstring.c).
入力された文字列が構造体TStringメモリのすぐ後ろに具体的に格納されていることがわかり、108行に注意して、文字列は「0」でC言語文字列と互換性があります.
(2)文字列が短い文字列の場合、まず文字列のHash値を計算し、対応するチェーンテーブル(短い文字列のグローバルHashテーブルで、リンク法の方法を使用している.つまり、すべての衝突した要素を同じチェーンテーブルに置く)を見つけ、現在作成する文字列がHashテーブルに存在するかどうかを検索し、すでに存在する場合は、この文字列を直接返す.そうでない場合、関数newshrstrが呼び出され、関数newshrstrは上のcreatestrobj関数を呼び出して新しい文字列を作成し、新しく作成した文字列をHashテーブルに配置します.コードは次の通りです(lstring.c).
グローバル文字列Hashテーブルは、仮想マシングローバルステータスメンバーstrtに保存されます(lstate.h):
タイプstringtableは構造体であり、以下のように定義されています(lstate.h).
メンバーGCObject*hashはポインタ配列であり、配列内の各メンバーは実質的にTStringを指す(TStringにはマクロCommonHeaderが含まれていることに注意し、マクロ内のnextメンバーはHashテーブルに分散したチェーンテーブルを構築することができる).nuseは配列hashですでに使用されている要素の数である.sizeは、現在の配列hashのサイズです.
関数newshrstrに新しい文字列を挿入する前にnuse値がsizeより大きいかどうかを判断します.大きい場合は、Hashテーブルのサイズが拡張する必要がないことを示します.Hashテーブルのサイズを元の2倍に拡張します.対応するコードは以下の通りです(lstring.c).
gcの場合は、nuseがsize/2よりも小さいかどうか(Lua 5.1ではnuseとsize/4を比較)を判断し、もしそうならresizeというstringtableの大きさを元の半分に改めます.対応するコードは以下の通りである(lgc.c):
文字列の比較では、まずタイプを比較し、異なるタイプの文字列であれば必ず異なり、それから短い文字列と長い文字列を区別し、短い文字列では、両者のポインタ値が等しい場合は同じで、そうでなければ同じではありません.長い文字列に対応する場合は、まずポインタ値を比較し、異なる場合は長さ値と内容を文字単位で比較します.
まとめ
(1)Luaのリザーブワードとメタメソッド名はいずれも短い文字列であり,仮想マシンの起動時にグローバルな短い文字列Hashテーブルに格納され,回収されない.
(2)文字の検索は比較的効率的であるが,文字列の修正や挿入はいずれも非効率であり,計算のほかに少なくとも外の文字列を仮想マシンにコピーしなければならない.
(3)長い文字列のHash値に対応してLuaは各文字を考察しないので、長い文字列のハッシュ値を素早く計算することを避けることができ、その対応するコードは以下の通りである(lstring.c).
(4)複数の文字列が接続されている場合は、演算子を文字列で直接接続する必要はありません.tableを使うのですconcat操作またはstring.formatは文字列接続の操作を高速化します.
(5)Luaにおける文字列HashアルゴリズムはJSHashを用いており,文字列に関する様々なHash関数について,ネットワーク上でまとめた文章がある.https://www.byvoid.com/blog/string-hash-compare(各種文字列Hash関数比較).
Luaは完全に8ビット符号化を採用し、Lua文字列の文字は任意の数値符号化を有し、数値0を含むことができる.すなわち、任意のバイナリデータを1つの文字列に格納することができる.Luaの文字列は可変値(immutable values)です.変更すると、実質的に新しい文字列が作成されます.前述の「Luaにおけるデータ型のソースコード実装」によれば、Luaでは、文字列は自動メモリ管理メカニズムによって管理されるオブジェクトであり、連合体TStringによって文字列値の格納が実現される.以下、Lua 5.2.1のソースコードから文字列の実装を見て、Luaで文字列を使用する際の注意点をまとめます.
ソース実装
まず、文字列に対応するデータ構造TStringを見てみましょう.そのソースコードは以下の通りです(lobject.h).
410 /*
411 ** Header for string value; string bytes follow the end of this structure
412 */
413 typedef union TString {
414 L_Umaxalign dummy; /* ensures maximum alignment for strings */
415 struct {
416 CommonHeader;
417 lu_byte extra; /* reserved words for short strings; "has hash" for longs */
418 unsigned int hash;
419 size_t len; /* number of characters in string */
420 } tsv;
421 } TString;この連合体の定義には、いくつかの点が説明に値します.
I、連合体TStringのメンバーL_Umaxalign dummyは、最大長のCタイプとの位置合わせを保証するために使用され、以下のように定義されています(llimits.h).
48 /* type to ensure maximum alignment */
49 #if !defined(LUAI_USER_ALIGNMENT_T)
50 #define LUAI_USER_ALIGNMENT_T union { double u; void *s; long l; }
51 #endif
52
53 typedef LUAI_USER_ALIGNMENT_T L_Umaxalign;他の回収可能なオブジェクト(tableなど)の実装では、この連合体メンバーも見られます.これは、メモリの位置合わせによって、CPUがメモリにアクセスする速度を速めることを目的としています.
II、連合体のメンバーtsvこそ文字列を実現するために本当に使われている.メンバーCommonHeaderはGCに使用され、マクロ形式ですべての回収可能オブジェクトで定義されます.コードは以下の通りです(lobject.h).
74 /*
75 ** Common Header for all collectable objects (in macro form, to be
76 ** included in other objects)
77 */
78 #define CommonHeader GCObject *next; lu_byte tt; lu_byte markedこのマクロに対応する構造体の形式は以下の通りである(lobject.h):
81 /*
82 ** Common header in struct form
83 */
84 typedef struct GCheader {
85 CommonHeader;
86 } GCheader;構造体Gcheaderは、一般的なリサイクル可能オブジェクトunion GCObjectの定義で役立ちます.
III、lu_byte extraは短い文字列に対して、この文字列が保留字であるかどうかを記録するために使用され、長い文字列に対して、Hash値を不活性に求めるために使用することができる.unsigned int hashメンバーは文字列に対応するHash値である(Luaが文字列のHash値をどのように計算するかは後述する).size_t lenは文字列の長さを表すために使用されます.
IV,上の構造体は1つの文字列の構造を記述しただけであり,真の文字列データ保存は構造体の後に続く保存である.
Lua 5.2.1以前は、文字列の長さと短い文字列を区別することなく、すべての文字列が1つのグローバルなHashテーブルに保存されていたが、Lua仮想マシンにとって、同じ文字列には1つのデータしかない.Lua 5から.2.1から、短い文字列(現在の定義は長さが40以下)をグローバルHashテーブルに配置するだけで、長い文字列は独立して生成され、Hash値を計算する際にランダムシードを導入することで、Hash Dos--攻撃者が同じHash値の異なる文字列を非常に多く構築することを防止し、Luaが外部から文字列を押し込んでグローバルな文字列Hashテーブルに入る効率を低下させる.次はLua 5.2.1では、対応するコードがlstringである新しい文字列を生成する.c中:
(1)文字列長がLUAI_より大きい場合MAXSHORTLEN(デフォルトは40)は、長い文字列であり、文字列インタフェースを作成する関数createstrobjを直接呼び出します(もちろん、文字列の長さはメンバーsize_t lenに保存する必要がありますが、そうでなければ直接戻ります).コードは以下の通りです(lstring.c).
95 /*
96 ** creates a new string object
97 */
98 static TString *createstrobj (lua_State *L, const char *str, size_t l,
99 int tag, unsigned int h, GCObject **list) {
100 TString *ts;
101 size_t totalsize; /* total size of TString object */
102 totalsize = sizeof(TString) + ((l + 1) * sizeof(char));
103 ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts;
104 ts->tsv.len = l;
105 ts->tsv.hash = h;
106 ts->tsv.extra = 0;
107 memcpy(ts+1, str, l*sizeof(char));
108 ((char *)(ts+1))[l] = '\0'; /* ending 0 */
109 return ts;
110 } 入力された文字列が構造体TStringメモリのすぐ後ろに具体的に格納されていることがわかり、108行に注意して、文字列は「0」でC言語文字列と互換性があります.
(2)文字列が短い文字列の場合、まず文字列のHash値を計算し、対応するチェーンテーブル(短い文字列のグローバルHashテーブルで、リンク法の方法を使用している.つまり、すべての衝突した要素を同じチェーンテーブルに置く)を見つけ、現在作成する文字列がHashテーブルに存在するかどうかを検索し、すでに存在する場合は、この文字列を直接返す.そうでない場合、関数newshrstrが呼び出され、関数newshrstrは上のcreatestrobj関数を呼び出して新しい文字列を作成し、新しく作成した文字列をHashテーブルに配置します.コードは次の通りです(lstring.c).
130 /*
131 ** checks whether short string exists and reuses it or creates a new one
132 */
133 static TString *internshrstr (lua_State *L, const char *str, size_t l) {
134 GCObject *o;
135 global_State *g = G(L);
136 unsigned int h = luaS_hash(str, l, g->seed);
137 for (o = g->strt.hash[lmod(h, g->strt.size)];
138 o != NULL;
139 o = gch(o)->next) {
140 TString *ts = rawgco2ts(o);
141 if (h == ts->tsv.hash &&
142 ts->tsv.len == l &&
143 (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
144 if (isdead(G(L), o)) /* string is dead (but was not collected yet)? */
145 changewhite(o); /* resurrect it */
146 return ts;
147 }
148 }
149 return newshrstr(L, str, l, h); /* not found; create a new string */
150 }グローバル文字列Hashテーブルは、仮想マシングローバルステータスメンバーstrtに保存されます(lstate.h):
119 stringtable strt; /* hash table for strings */タイプstringtableは構造体であり、以下のように定義されています(lstate.h).
59 typedef struct stringtable {
60 GCObject **hash;
61 lu_int32 nuse; /* number of elements */
62 int size;
63 } stringtable;メンバーGCObject*hashはポインタ配列であり、配列内の各メンバーは実質的にTStringを指す(TStringにはマクロCommonHeaderが含まれていることに注意し、マクロ内のnextメンバーはHashテーブルに分散したチェーンテーブルを構築することができる).nuseは配列hashですでに使用されている要素の数である.sizeは、現在の配列hashのサイズです.
関数newshrstrに新しい文字列を挿入する前にnuse値がsizeより大きいかどうかを判断します.大きい場合は、Hashテーブルのサイズが拡張する必要がないことを示します.Hashテーブルのサイズを元の2倍に拡張します.対応するコードは以下の通りです(lstring.c).
121 if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
122 luaS_resize(L, tb->size*2); /* too crowded */ gcの場合は、nuseがsize/2よりも小さいかどうか(Lua 5.1ではnuseとsize/4を比較)を判断し、もしそうならresizeというstringtableの大きさを元の半分に改めます.対応するコードは以下の通りである(lgc.c):
783 int hs = g->strt.size / 2; /* half the size of the string table */
784 if (g->strt.nuse < cast(lu_int32, hs)) /* using less than that half? */
785 luaS_resize(L, hs); /* halve its size */文字列の比較では、まずタイプを比較し、異なるタイプの文字列であれば必ず異なり、それから短い文字列と長い文字列を区別し、短い文字列では、両者のポインタ値が等しい場合は同じで、そうでなければ同じではありません.長い文字列に対応する場合は、まずポインタ値を比較し、異なる場合は長さ値と内容を文字単位で比較します.
まとめ
(1)Luaのリザーブワードとメタメソッド名はいずれも短い文字列であり,仮想マシンの起動時にグローバルな短い文字列Hashテーブルに格納され,回収されない.
(2)文字の検索は比較的効率的であるが,文字列の修正や挿入はいずれも非効率であり,計算のほかに少なくとも外の文字列を仮想マシンにコピーしなければならない.
(3)長い文字列のHash値に対応してLuaは各文字を考察しないので、長い文字列のハッシュ値を素早く計算することを避けることができ、その対応するコードは以下の通りである(lstring.c).
51 unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
52 unsigned int h = seed ^ l;
53 size_t l1;
54 size_t step = (l >> LUAI_HASHLIMIT) + 1;
55 for (l1 = l; l1 >= step; l1 -= step)
56 h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1]));
57 return h;
58 }
21 /*
22 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to
23 ** compute its hash
24 */
25 #if !defined(LUAI_HASHLIMIT)
26 #define LUAI_HASHLIMIT 5
27 #endif(4)複数の文字列が接続されている場合は、演算子を文字列で直接接続する必要はありません.tableを使うのですconcat操作またはstring.formatは文字列接続の操作を高速化します.
(5)Luaにおける文字列HashアルゴリズムはJSHashを用いており,文字列に関する様々なHash関数について,ネットワーク上でまとめた文章がある.https://www.byvoid.com/blog/string-hash-compare(各種文字列Hash関数比較).