日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

ストレージストラテジーによる組み込み向け

JavaScript バーチャルマシンのメモリ使用量の削減
永谷 龍彦

鵜川 始陽

JavaScript をはじめとする動的型付け言語では，静的型付け言語と比べ，多くのメモリが要求される．これは，動的型付け言語は実行時にデータ型を決定するため，値とともにデータ型もメモリに保存しておく必要があるためである．しかし，動的型付け言語においても，配列などのコレクションは，同じ型の値を格納するために用いられることが多い．本研究では，同じ型の値だけが格納されたコレクションに対して，データではなくコレクションにデータ型の情報を持たせるストレージストラテジーという手法を，配列に適用してメモリ使用量を削減する．さらにメモリ使用量を削減するために，配列のデータ型には 1 バイト整数のような 1 ワードより小さいデータ型を導入する．これを組み込み向けシステム向け JavaScript バーチャルマシンに実装して評価した．

領域に配置することで，高いメモリ効率を実現する．

1 はじめに提案手法を組み込みシステム向け JavaScript VM

JavaScript などの動的型付け言語の普及は，ソフである eJSVM [7] に実装し，メモリ使用量を平均 13%

トウェア開発の敷居を大幅に引き下げたが，組み込み削減することに成功した．実行時間のオーバーヘッド

システム向けの開発では未だ C や C++ といった伝は平均 3.8% であった．

統的な言語が用いられる場合が多い．これは，組み込みシステム向け開発では，メモリサイズの制約が特に

2 ストレージストラテジー

厳しいためである．

動的型付け言語のメモリ使用量は静的型付け言語

本 研 究 で は ，ス ト レ ー ジ ス ト ラ テ ジ ー [1] を ，より多くなる．これは，プログラムに型を記述しない

JavaScript 仮想機械 (VM) の配列 (Array オブジェ

ため，値ごとに型を記録する必要があるからである．

クト) の実装に用い，メモリ使用量を削減する．スト

単純な VM の実装では，全ての値についてボクシン

レージストラテジーは，リストや辞書などのコレクグを行う．すなわち，値の実体と型情報をメモリ上のションに格納された値のメモリ表現を，追加された値

別の場所に配置しておき，本体にはそのアドレスのみのデータ型に応じて自動的に最適化する手法である．

を持たせる．配列のようなコレクションにおいては，

本研究では，値のデータ型だけでなく，その大きさに

図 1 右のように全ての値に対してボクシングが行わ着目し，必要に応じて各要素を 1 ワードより小さなれることになり，図 1 左のような C や C++ の配列と比べて無駄が多くなる．

Reducing Memory Footprint of JavaScript Virtual
Machines for Embedded Systems Using Storage
Strategy
Tatsuhiko Nagaya, 東京大学情報理工学研究科, Graduate School of Information Science and Technology,
the University of Tokyo.
Tomoharu Ugawa, 東京大学情報理工学研究科, Graduate School of Information Science and Technology,
the University of Tokyo.

ストレージストラテジーが実装された VM では，
図 2 のように，コレクションの値のデータ型が各要
素にではなくコレクション本体に格納されるようになる．この設計は，動的型付け言語であっても，コレクションには同じデータ型の値が格納される場合が多い [1] ことに由来する．すなわち，数値や文字列，オ
ブジェクトといった異なる種類のデータが同じコレク

C / C++JavaScript

[0]

0

[0]

<address>

[1]

1

[1]

<address>

[2]

2

[2]

<address>

[3]

3

[3]

<address>

int8[] array = {0, 1, 2, 3};
図1

type

number

value

0

type

number

value

3

type

number

value

1

type

numbervalue

2

var array = [0, 1, 2, 3];

C や C++ と JavaScript の配列の表現の違い．左: C / C++, 右: JavaScript

int

図2

[0]

0

[1]

1

[2]

2

[3]

3

ストレージストラテジーによる配列の表現

ションに格納されていることは少ない．この変更によトラテジーで，このストラテジーを持つコレクション

り，コレクションのメモリ使用量が，各要素が保持しの値は，ストレージストラテジーを導入していないていた型情報の分だけ削減される．

VM と同一の方法で格納される．

コレクションごとに定まるデータ型を，ストラテ
ジーと呼ぶ．ストラテジーは，コレクションに追加さ3 設計れた値に応じて自動的に決定される．図 3 のように，ストレージストラテジーは本来様々なコレクション

コレクションが作成された時点では，未だ何も値が格に対して適用可能な手法だが，本研究は JavaScript

納されていないことを表す EmptyStrategy が設定さを対象とするため，JavaScript の仕様である EC-

れ，初めて値が格納された時点でその値に特化したス

MAScript 5 [2] 時点で利用できるコレクションとしトラテジーに遷移する．また，ストラテジーが対応でて，配列のみに適用する．また，実行速度の改善ではきない要素が追加された場合，より汎用的なストラテ

なく，メモリ使用量の削減を優先した設計を行う．

ジーに遷移する．一度汎用的なストラテジーに遷移したコレクションは，コレクションが空にされない限り，特化したストラテジーに戻ることはない．

3. 1 データサイズに着目したストラテジー
提案手法では，小さな値のみを格納できるストラ

例えば，図 4 のプログラムの場合，1 行目終了時

テジーを導入することで，メモリの使用量を積極的

点では list1 は EmptyStrategy だが，2 行目には整に削減する．Bolz らの提案したストレージストラテ

数のみを格納することができる IntegerStrategy に遷

ジーは，整数や文字列など，データの種類のみに着目移する．3 行目では文字列がリストに追加されている

していた．しかし，データの種類だけでなく，その大が，文字列は IntegerStrategy では対応できないため，

きさについても同様の性質が存在すると考えられる．

ストラテジーはより汎用的な ObjectStrategy に遷移

すなわち，小さな値がほとんどを占めるコレクション

する．ObjectStrategy は，任意の値を格納できるスにおいて，少数の要素のみが大きい値となることは起IntegerStrategy
Add integer

Add non-integer

Add float

Add non-float

EmptyStrategy

ObjectStrategy
FloatStrategy

図3

ストレージストラテジーの遷移

3. 2 空要素の表現
1
2
3

list1 = []list1.append(123)list1.append("foo")

JavaScript では，図 7 のプログラムのように，Array
コンストラクタの引数に要素数を指定して配列を作成することで，要素の一部を空にすることができる．

図4

ストレージストラテジーが遷移する例

ここでいう空とは，図 8 右のように，未定義を表す

JavaScript の値である undefined が格納されている
こりづらい．このため，小さな値のみが格納できるス状態とは異なり，図 8 左のように，配列の要素自体がトラテジーを用意することで，大きな値も格納できる存在しない状態を表している．

よう，余分なメモリを使用する必要がなくなる．

この仕様は，JavaScript の配列がインデックスを

図 5 は，数値のみが格納された配列を効率的に扱キーとする辞書の形で定義されていることに由来しうストラテジーの組み合わせの例である．JavaScriptており，要素が存在しないインデックスでのアクセスの数値は，仕様により 64 ビット浮動小数点数と定義

では，同名のプロパティを持つ継承元のオブジェクトされているが，異なるデータ型の値が混在する配列がを探索する必要がある．ただ，実用上は配列を敢えあまり用いられないのと同様に，整数と浮動小数点数て辞書のように用いることはほとんどないため，VMが混在する配列や，大きな整数と小さな整数が混在すの実装においては，配列の要素はメモリ空間に連続的る配列もあまり用いられないと考えられる．このたに配置される．空要素を表現するには，空である状態

め，図 5 の例では，仕様上すべての数値を表現できを表現するための内部的な値を用意し，その場所に格る NumberStrategy のほかに，そのサブセットである

納しておけばよい．

8 ビット符号付き整数のみを表現できる Int8Strategy

本研究のストレージストラテジーの実装では，空要を導入している．この VM で，図 6 に示したプログ

素をどう保持するかはストラテジー側の責務とする．

ラムを実行すると，まずは 1 行目で EmptyStrategy

このため，各ストラテジーが表現できる値の範囲は，の配列が生成される．続いて，2 行目で配列に整数

1 要素に割り当てられたメモリ領域を用いて表現可能

100 が追加されると，これは 8 ビット符号付き整な全ての値よりも 1 つ以上少なくなる．例えば，true

数の範囲に収まる値なので，Int8Strategy に遷移すまたは false のみを表現できる BooleanStrategy のる．さらに整数 1000 が追加されると，より汎用的な

1 要素には， 2 bit を割り当てる．

NumberStrategy に遷移し，最終的に適切なストラテ
ジーが存在しなければ JSValueStrategy となる．

各ストラテジーに空要素を扱う責務を持たせず，一つでも空要素を持つ配列を全て JSValueStrategy とす

この実装により，Int8Strategy が利用されれば，るのは適切ではない．これは，図 9 のように，Array

NumberStrategy しか実装しない場合に比べ，メモリ

コンストラクタに要素数を指定して配列を作成した

使用量を 8 分の 1 に削減できる．ただし，Int8Strategy

場合，初期状態で配列の各要素は空となるためであが適用された後，その範囲に収まらない数値が格納さる．このプログラムでは，配列には明らかに整数しかれようとした場合，NumberStrategy として必要なメ

格納されないが，1 行目で Array コンストラクタにモリを確保し直す必要がある．

要素数を指定しているため，JSValueStrategy が適用

Add non-number
Add number

EmptyStrategy

Add integer < 2^8

Int8Strategy

Add number

NumberStrategy

Add non-number

JSValueStrategy

Add non-number

図5

1
2
3
4

値の大きさを考慮したストラテジー遷移の例 (JSValue は JavaScript の任意の値を表す)

array = [];array.push(100);array.push(1000);array.push("foo");である．搭載メモリが非常に小さい環境での動作を想定し，消費メモリが少なくなるよう設計されている．

4. 1 前提: eJSVM における値と配列の表現
図6

値の大きさを考慮してストラテジーが選択される例

図 10 は，eJSVM における値の表現を表している．

eJSVM では，値は 64 bit で表現され，下位 3 ビッ12
3

array = [];array[2] = "foo"; // [ <2 empty items>, ’foo’ ]array[0] = undefined; // [ undefined, <1 empty
item>, ’foo’ ]トがタグとして値の種類を区別するために用いられている．残りの 61 ビットの中に収まる整数や真理値，undefined などの特殊な値は直接埋め込まれ，浮動小数点数やオブジェクトは，タグ付きポインタ [4] の図7

配列の空要素が生じるプログラム形で表現されている [7]．この 64 ビットを JSValueと呼ぶ．

されてしまう．

オブジェクトは JSValue からタグを外して得られるアドレスに保存されており，これを JSObject と呼3. 3 EmptyStrategy とリストの長さの関係

ぶ．オブジェクトが持つプロパティは全て JSValue

3. 2 節で提示したように，JavaScript では，Arrayと同じ 64 bit で表現される．

コンストラクタを用いて配列の要素を入れる前に長Array オブジェクトは JSObject の特殊なケースとさを指定できる．このため，配列のストラテジーがして扱われ，ECMAScript の定める仕様を満たすた

EmptyStrategy であっても，配列の長さが 0 になる

めに，次のような特殊なプロパティが作成される．

とは限らない．図 9 の 1 行目のように，Array コン• length: プログラムから見える配列の長さストラクタにより要素数を指定して配列が作成され• body: 配列内部の値が JSValue[] の形で格納さた場合，ストラテジーは EmptyStrategy だが，配列の長さは正となる．

れたアドレスへのポインタ• size: そのポインタが指し示す先の空間の大きさ

これによって，配列本体のメモリを確保するタイミ
ングが，配列を作成した時点から，配列に初めて値が4. 2 ストラテジーの導入追加された時点に遅延される．図 9 のプログラムのストレージストラテジーの導入にあたり，図 11 の場合，1 行目では配列のコンテナのみを用意し，2 行

ように，4. 1 節の配列オブジェクトのスロットの部分

目で初めて Int8Strategy の 3 要素分のメモリを確保

を，次のように変更する．

される．

• 配列の現在のストラテジーを格納する strategy
スロットを追加する

4 実装
提案手法を eJSVM [7] に実装した．eJSVM は，
組み込みシステム向けに開発された JavaScript VM• body スロットの型は JSValue[] ではなくスト
ラテジーに応じて変わる
ストラテジーは，配列に要素が保存される際に，受array = [];array[2] = "foo";
2

"foo"

図8

1
2
3
4

array = [undefined, undefined, "foo"];0

undefined1

undefined

2

"foo"

左: 空要素を含む配列, 右: undefined が入った配列の小さいものが自動的に選択される．

array = Array(3);array[0] = 12;
array[1] = 34;
array[2] = 56;

ストラテジーが遷移する際，既に保存されている要素は新しいストラテジーに合わせて変換しなければならないが，最適化のため，一度 JSValue を経由す

図9

JSValueStrategy が誤って適用される例

ることなく，専用のコードパスによって変換する．

け取った JSValue をそれぞれに最適化された表現に

4. 4 浮動小数点数のボクシング

変換する．また，配列から要素が取り出される際は，

Float64Strategy の導入により，配列からの要素の再度 JSValue の形に戻す．

取得は，メモリアロケーションが発生する操作とな

このインターフェースに沿って，次に挙げた 6 つのストラテジーを実装する．

る．4. 1 節で提示したように，eJSVM ではタグ付きポインタを用い，JSValue のタグを除いた領域に埋• EmptyStrategy: まだ要素が追加されていない配列のストラテジー．

め込める値は直接埋め込んでいる．しかし，浮動小数
点数は 64 bit 全てを消費するため，ポインタの形で• Int8Strategy: [−27 + 1, 27 − 1] の範囲の整数を

JSValue に格納されている．Float64Strategy は浮動8 ビット符号付き整数で保存するストラテジー．

小数点数を値の格納の際にアンボクシングして保存−2 は空要素を表す値とする．

するため，値の取り出しの際には再びボクシングする

7• Int16Strategy: [−21515+ 1, 2− 1] の範囲の整数必要があるためである．

を 16 ビット符号付き整数で保存するストラテ
ジー．−215 は空要素を表す値とする．

5 評価• Float64Strategy: 64 ビット浮動小数点数を保存

第 4 章で示した実装を用いて，メモリ使用量の削するストラテジー．NaN は空要素を表す値とする．

減性能を評価した．各ストラテジーは EmptyStrategy• BooleanStrategy: 2 ビットで真理値を保存すると JSValueStrategy を除いて個別に無効化できるできストラテジー．00 が false，01 が true，10 がるようにし，それぞれの結果に対する貢献を調べた．

空要素を表すとする．

加えて，提案手法の実装によるオーバーヘッドの大き• JSValueStrategy: JSValue を保存するストラテ

さを確認するため，実行時間も計測した．さらに，そジー．ストレージストラテジー導入前の実装とれぞれのストラテジーが，各ベンチマークプログラム

同等．

どれだけ使用されているかを調査した．

4. 3 ストラテジーの遷移

5. 1 実験設定

ストラテジー間の遷移は，図 12 に示された条件

ベンチマークプログラムには，Marr らの Cross-で行われる．数値を表す Int8Strategy, Int16Strategy,

language compiler benchmarking [6] と，独自に作成

Float64Strategy の間で遷移する場合は，最もサイズ

した温度センサーの計測データの解析プログラム

{ a: 12, b: 34 }
[12, 34, 56]

61 bitsTag
3 bitsMemory address000

Memory address000

true (Immediate valule)110

61 bitsTag
3 bitsa

12 (Immediate valule)111b

34 (Immediate valule)111

61 bitsTag
3 bits12 (Immediate valule)

111

34 (Immediate valule)

111

56 (Immediate valule)111

Empty (Immediate valule)110

Empty (Immediate valule)110

JSObject

JSObject (Array)

true
12
3.14

12 (Immediate valule)
Memory address

111

size

5

body

Memory address
3 (Immediate valule)

length101

111

Floting point number

3.14

図 10

eJSVM における値の表現
Tag
3 bits61 bits

8 bits

JSObject (Array)

size

5

body

Memory address
int8

strategylength123 (Immediate valule)

34

111

56

図 11

提案手法導入後の配列表現

Add int8

EmptyStrategy

Add boolean

Int8Strategy
Add int16
Add float64

Add int16

Add float64

Int16Strategy

BooleanStrategy

Add float64

Float64Strategy
Add non-number Add non-boolean

Add non-number

図 12

JSValueStrategy

実装したストラテジーの遷移

dht11 を用いた．
メモリの使用量は，プログラムが 3 分以内に正常に終了する最小のヒープサイズとして測定した．精度は 128 KB である．これは，ガベージコレクタを実装した処理系でヒープサイズを小さくすると，ガベー
ジコレクションの頻度が急激に上昇し，実行時間が伸
びてしまうためである．
実行時間は，ヒープサイズを 128 MB に設定した

うえで計測した．128 MB はこのベンチマークプロと BooleanStrategy の導入による影響が大きい．

グラムに対して十分な大きさで，これ以上ヒープサイ

この結果をベンチマークプログラムごとに表しズを増やしても実行時間はほとんど変わらないことたのが図 14 である．著しい変化を示しているのがを確認している．

Havlak, Sieve, Storage, dht11 の 4 つで，25% 〜

比較対象は，次の 9 種類である．

50% 程度メモリ使用量が減少している．その中で• 提案手法実装前 (baseline)

も，Havlak と Storage に関しては，EmptyStrategy• EmptyStrategy と JSValueStrategy のみ実装しと JSValueStrategy しか実装されていないにも関わらたもの (none)

ず，メモリ使用量は大幅に減少している．一方，Sieve• 加えて Int8Strategy を実装したもの (int8)

は BooleanStrategy が実装されているとき，dht11 は• 加 え て Int16Strategy を 実 装 し た も のInt8Strategy が実装されているときにメモリ使用量の(int8,int16)• 加 え て Float64Strategy を 実 装 し た も の(int8,int16,ﬂoat64)• 前 4 つの構成に BooleanStrategy を加えたもの(boolean[,int8[,int16[,ﬂoat64]]])
ストラテジーの使用状況の調査では，全てのストラ減少が起きている．Havlak については Int16Strategy
による効果も見て取れる．
すべてのベンチマークプログラムの平均からは，実装するストラテジーの数が増えれば増えるほど，メモリの使用量は減少するが，実行時間が若干増加していることが読み取れる．

テジーを有効にした上で，新しく配列が作成されると
きと，配列のストラテジーが遷移するときにその遷移

5. 3 ストラテジーの使用状況

元と遷移先を記録することで，各ストラテジーに最図 15 は，各ベンチマークプログラムにおいてそれ終的に到達した Array オブジェクトを数えた．また，ぞれのストラテジーに最終的に到達した Array オブ

Array オブジェクトがプログラム全体で必要なメモリ

ジェクトの数の比率を表している．また，図 16 は，な中でどれだけ支配的なのかを調べるため，ガベー確保されたオブジェクト全体 (Allocated) のサイズ

ジコレクションが発生した際に，確保されたオブジェと，ガベージコレクションが起きた時点で生存してクト全体と生存しているオブジェクト全体のメモリ使いるオブジェクト全体 (Live) のサイズのうち，それ用量の中で Array オブジェクトが占める割合を計測

ぞれ Array オブジェクトが占める割合を表している．

した．

Havlak, Json, List, Mandelbrot, NBody, Permute,

実験環境の計算機の CPU は Intel Xeon W-2235

Richards, Storage は，全て EmptyStrategy で終わる

(6 コア，6 スレッド，クロックは 3.80 GHz に固定)配列が多い．このうち，生存オブジェクトの多くをを，DRAM は 32 GB の DDR4 を搭載した．OS はArray オブジェクトが多くを占めている Havlak とLinux 5.15 Ubuntu 20.04.4 を用いた．

Storage のメモリ使用量が大幅に削減されていることから，これらのメモリ使用量の減少の理由が，初期化

5. 2 メモリの使用量と実行時間されたまま値の追加が行われない配列の存在にある

図 13 は，メモリの使用量と実行時間の baseline 比と結論付けられる．

での増加率の，全ベンチマークでの幾何平均である．

Queens や Sieve は，BooleanStrategy が多く使用

none と int8，none と int8 の比較により，Int8Strategy

されている．Sieve に関しては生存オブジェクトに占と BooleanStrategy によるメモリ使用量の減少率が大

める Array オブジェクトの割合は高くないものの，確きいことが分かる．また，EmptyStrategy のみを実装

保されたメモリ全体に占める配列の割合は高く，また，した none もメモリ使用量を 3% 程度減少させている．

Sieve のアルゴリズムが内部的に非常に長い Array オ

一方，Int16Strategy や Float64Strategy の効果は限定

ブジェクトを用いていることから，提案手法によりメ的である．実行時間については，特に Float64Strategy

モリ使用量が減少したものと考えられる．Queens は

Average increase from baseline (+%)

5.0
2.5
0.0
2.5
5.0
7.5
10.0

Memory
Time

12.5
e

non

8

int

16

flo
16,

t

8,in

int

4

at6

int

8,
int

n

lea

boo

t8

,in

an
ole

bo

Enabled strategies

図 13

le

boo

in

t8,

in
an,

4

at6

,flo
t16

全ベンチマークプログラムの平均の消費メモリと実行時間 (対ベースライン)

Benchmark Strategy
memory (+% to baseline)
time (+% to baseline)
memory (+% to baseline)CDtime (+% to baseline)
memory (+% to baseline)
DeltaBlue
time (+% to baseline)
memory (+% to baseline)
Havlaktime (+% to baseline)
memory (+% to baseline)
Json
time (+% to baseline)
memory (+% to baseline)
List
time (+% to baseline)
memory (+% to baseline)
Mandelbrot
time (+% to baseline)
memory (+% to baseline)
Nbodytime (+% to baseline)
memory (+% to baseline)
Permutetime (+% to baseline)
memory (+% to baseline)
Queenstime (+% to baseline)
memory (+% to baseline)
Richards
time (+% to baseline)
memory (+% to baseline)
Sievetime (+% to baseline)
memory (+% to baseline)
Storagetime (+% to baseline)
memory (+% to baseline)
Towerstime (+% to baseline)
memory (+% to baseline)
dht11
time (+% to baseline)
Bounce

n,

lea

boo

16
int

8,
int

int8

none
0.16
4.92
0.94
-0.32
3.36
2.16
-17.35
-1.24
1.18
0.01
0.18
6.32
0.00
-4.73
0.14
2.99
0.19
6.35
0.00
2.67
-0.25
1.75
0.09
-0.74
-30.39
-3.28
0.18
7.37
0.56
0.56

図 14

int8
int16
float64
0.16
0.16
0.94
3.79
0.94
0.92
0.27
-0.13
3.35
3.35
4.16
3.55
-26.96-26.96
-1.56
-0.94
-4.13
-4.14
0.43
1.43
0.18
0.18
5.64
10.35
0.16
0.81
2.65
-0.69
0.14
0.99
4.32
4.90
0.00
0.00
9.42
7.04
0.00
0.00
3.29
5.39
-0.25
-0.25
1.09
-0.90
0.09
0.09
2.94
7.72
-30.39-30.42
-3.88
-3.29
0.18
0.18
7.39
6.38
-47.97-47.97
-1.76
2.75

int8
int16

0.16
1.82
0.92
0.04
3.35
2.58
-17.63
-1.83
-4.14
1.23
0.18
4.70
0.97
-0.49
0.99
1.65
0.00
6.20
0.00
3.40
-0.25
0.96
0.09
7.90
-30.40
-3.53
0.18
4.89
-47.97-0.19

実験結果の内訳

boolean boolean boolean boolean
int8
int8
int8
int16
int16
float64
0.16
0.16
0.16
0.16
1.45
4.79
0.04
2.35
0.92
0.94
0.92
0.92
0.10
-0.02
-0.39
1.98
3.35
3.35
3.35
3.35
2.73
4.25
2.33
3.75
-17.35-17.63-26.97-26.97
-0.61
-0.32
-1.33
0.45
1.18
-4.13
-4.14
-4.14
1.96
2.50
1.12
2.82
0.18
0.18
0.18
0.18
8.77
9.11
12.80
12.28
0.81
0.00
0.81
0.97
5.46
-5.71
3.12
1.89
0.99
0.28
0.99
0.99
5.57
2.83
5.06
4.10
0.19
0.00
0.00
0.00
5.63
10.17
6.19
9.18
-0.54
-0.71
-0.71
-0.71
7.06
9.74
6.07
7.82
-0.25
-0.25
-0.25
-0.25
-1.84
0.96
-2.85
3.77
-52.53-52.53-52.53-52.53
14.39
12.83
14.86
18.33
-30.42-30.39-30.42-30.42
-3.40
-4.26
-3.52
-1.22
0.18
0.18
0.18
0.18
10.31
6.40
6.38
9.42
0.45
-47.97-47.97-47.97
7.90
-3.28
3.00
4.03

20

図 15

ストラテジーの使用状況

dht11

Towers

Sieve

Storage

QueensRichards

Permute

NBody

List

BenchmarkMandelbrot

0
Json

BounceCD
DeltaBlue
HavlakJson
List
Mandelbrot
NBody
PermuteQueensRichards
Sieve
Storage
Towers
dht11

20

40

Havlak40

60

CDStrategy
Empty
Boolean
Int8
Int16
Float64
JSValue

80

DeltaBlue

60

Live
Allocated

BounceStrategy usage [%]80

Array memory usage [%]100

Benchmark

図 16配列の使用状況

Sieve ほどではないにせよ，BooleanStrategy の恩恵

しまう．メモリ使用量の減少という結果が得られないを受けられている．

のであれば，実装しないほうが良いと考えられる．

Int8Strategy が多く用いられているのは Havlak,

BooleanStrategy の実装については注意が必要であ

Json, Permute, Queens, dht11 の 5 つだが，中でもる．真理値の配列を扱うプログラムでは，そのメモ

dht11 は全体に占める割合が大きく，生存している割

リ削減効果は大きいが，その代わりに 3% 程度のパ合も高いことから，Int8Strategy の実装により大きく

フォーマンスオーバーヘッドが発生するためである．

メモリ使用量が減少していることが分かる．

これは，バイト境界を無視した値の取り出しと書き込

Float64Strategy が用いられていたのは主に List,
Mandelbrot, NBody の 3 つだが，いずれもプログラ
ム中で Array オブジェクトはほとんど確保されておらず，メモリ使用量への影響は限定的だった．

みのために必要なビット演算のコストが大きいためだと考えられる．

EmptyStrategy や Int8Strategy，Int16Strategy は
軽量ながらも，メモリ使用量の削減には大きく貢献しており，バランスの取れたストラテジーである．

5. 4 考察以 上 の こ と か ら ，ポ イ ン タ ー タ ギ ン グ を 行 う

5. 2 節と 5. 3 節の結果から，提案手法により，確か

JavaScript VM では，Int8Strategy と Int16Strategy，にメモリ使用量が減少することが明らかになった．一

必要に応じて BooleanStrategy を導入することが適方で，実行時間の計測結果は，実装するストラテジー

切であるといえる．

の数を増やせば増やすほど，ストラテジーによる処理の分岐にかかるコストが増加し，パフォーマンスに悪6 関連研究・技術影響を与えることを示唆している．このため，導入すECMAScript 2015 以 降 の JavaScript に は ，るストラテジーの選択は慎重に行わねばならない．

TypedArray と呼ばれるバイナリデータを扱うためのFloat64Strategy は，JavaScript の仕様で定められオブジェクトが定義されている [3]．TypedArray は，た数値をすべて表現できるストラテジーでありな

Uint8Array や Float64Array などの要素のデータ型

がらも，Int8Strategy と Int16Strategy が存在していを明示したオブジェクトの総称で，通常の Array オブる環境下では，ほとんど用いられることがないこと

ジェクトに似たインターフェースが提供されている．

が分かった．eJSVM のようなタグ付きポインター

データ型が決まっているためメモリ効率は高いが，Cを利用している VM では，4. 2 節で示したように，などの配列と同じく要素数の変更は許されておらず，

Float64Strategy の実装により，配列からの値の取り

通常の Array オブジェクトに利便性の点で劣る．な出しがメモリアロケーションが発生する操作になって

お，eJSVM では TypedArray は利用できない．

高速な JavaScript VM として知られる V8 では，ラムのうち，数値や真理値といったプリミティブから

数値のみを対象としたストレージストラテジーとなる配列を扱っている，4 個のメモリ使用量を大幅にして，ElementsKind を配列に対して設定している．

削減することに成功した．残り 11 個のプログラムのElementsKind は，空要素が含まれる場合と含まれな多くで利用されているオブジェクトの配列に対して有い場合で別の ElementsKind を定義しているという効な手法を考案することは今後の課題である．

点で，全てのストラテジーが空要素に対応可能な本研
究の実装と異なっている [5]．

7 おわりに
本研究では，ストレージストラテジーを応用し，JavaScript VM のメモリ使用量を削減するための手法を提案した．この手法は，値の大きさに応じたスト
ラテジーを自動的に適用し，配列の要素を必要に応じて 1 ワードより小さなメモリ領域で表現することで，積極的なメモリ最適化を実現している．また，提案手法の設計では，JavaScript に特有である空要素を含む配列が，各ストラテジーによって対応されるべきであることを指摘した．
提案手法を組み込み向け JavaScript VM である

eJSVM に実装し，既にメモリ最適化が進んでいる処
理系においても，手法が有効であることを示した．さらに，各ストラテジーの効果を定量的に測定し，スト
ラテジーの設計者が実装すべきストラテジーについての指針を提示した．
提案手法は，用意した 15 個のベンチマークプログ

参 考 文 献[1] Bolz, C. F., Diekmann, L., and Tratt, L.: Storage
strategies for collections in dynamically typed languages, Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications, (2013),
pp. 167–182.
[2] ECMA International: Standard ECMA-262 - ECMAScript Language Speciﬁcation 5.1 Edition, 2011.
[3] ECMA International: Standard ECMA-262 - ECMAScript 2015 Language Speciﬁcation, 2015.
[4] Gudeman, D.: Representing Type Information in
Dynamically Typed Languages, Technical Report
TR93-27, The University of Arizona, 1993.
[5] Hosking, A. L., Bond, M., Cliﬀord, D., Payer, H.,
Stanton, M., and Titzer, B. L.: Memento mori: dynamic allocation-site-based optimizations, Proceedings of the 2015 International Symposium on Memory Management, (2015), pp. 105–117.
[6] Marr, S., Daloze, B., and Mössenböck, H.: Crosslanguage compiler benchmarking: are we fast yet?,
Proceedings of the 12th Symposium on Dynamic
Languages, (2016), pp. 120–131.
[7] Ugawa, T., Iwasaki, H., and Kataoka, T.: eJSTK:
Building JavaScript virtual machines with customized datatypes for embedded systems, Journalof Computer Languages, Vol. 51(2019), pp. 261–279.