ループの前に行が大量にあると実行速度が落ちるか？

# 検証内容

IchigoJam BASIC において、ループの前に大量の行がある時、ループの速度が落ちるかを検証する。
以下のパターンを検証する。

* ループの方法
  * `GOTO`命令
  * `FOR`～`NEXT`命令
* ループの前に配置する行
  * なし
  * 長い行を置けるだけ置く
  * 長さと行数のバランスを取る
  * 短い行を大量に置く

# 予想

* `GOTO`命令を用いたループでは、飛ぶたびに飛び先の行の探索が発生し、行数が多いと遅くなる。
  * 各行の長さが行の最初に格納されるため、行の長さにはよらず、行数によって遅くなる。
* `FOR`～`NEXT`命令を用いたループでは、飛び先がスタックに記録され、行数が多くても遅くならない。

# 実験用プログラム

それぞれの「ループの前」のプログラムに続けて「ループ」のプログラムを配置する。

## ループの前

### なし

```
```

### 長い行を置けるだけ置く

```
1'012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567
2'012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567
3'012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567
4'012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567
5'012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
```

### 長さと行数のバランスを取る

<details><summary>プログラム (31行)</summary><div>

```
1'012345678901234567890123456
2'012345678901234567890123456
3'012345678901234567890123456
4'012345678901234567890123456
5'012345678901234567890123456
6'012345678901234567890123456
7'012345678901234567890123456
8'012345678901234567890123456
9'012345678901234567890123456
10'012345678901234567890123456
11'012345678901234567890123456
12'012345678901234567890123456
13'012345678901234567890123456
14'012345678901234567890123456
15'012345678901234567890123456
16'012345678901234567890123456
17'012345678901234567890123456
18'012345678901234567890123456
19'012345678901234567890123456
20'012345678901234567890123456
21'012345678901234567890123456
22'012345678901234567890123456
23'012345678901234567890123456
24'012345678901234567890123456
25'012345678901234567890123456
26'012345678901234567890123456
27'012345678901234567890123456
28'012345678901234567890123456
29'012345678901234567890123456
30'012345678901234567890123456
31'0123456
```

</div></details>

### 短い行を大量に置く

せっかくなのでIchigoJamのプログラムでプログラムを生成してみよう。

```
FORI=1TO162:?I;"'":NEXT
```

<details><summary>プログラム (162行)</summary><div>

```
1'
2'
3'
4'
5'
6'
7'
8'
9'
10'
11'
12'
13'
14'
15'
16'
17'
18'
19'
20'
21'
22'
23'
24'
25'
26'
27'
28'
29'
30'
31'
32'
33'
34'
35'
36'
37'
38'
39'
40'
41'
42'
43'
44'
45'
46'
47'
48'
49'
50'
51'
52'
53'
54'
55'
56'
57'
58'
59'
60'
61'
62'
63'
64'
65'
66'
67'
68'
69'
70'
71'
72'
73'
74'
75'
76'
77'
78'
79'
80'
81'
82'
83'
84'
85'
86'
87'
88'
89'
90'
91'
92'
93'
94'
95'
96'
97'
98'
99'
100'
101'
102'
103'
104'
105'
106'
107'
108'
109'
110'
111'
112'
113'
114'
115'
116'
117'
118'
119'
120'
121'
122'
123'
124'
125'
126'
127'
128'
129'
130'
131'
132'
133'
134'
135'
136'
137'
138'
139'
140'
141'
142'
143'
144'
145'
146'
147'
148'
149'
150'
151'
152'
153'
154'
155'
156'
157'
158'
159'
160'
161'
162'
```

</div></details>

## ループ

### `GOTO`命令

```
900 CLT:I=0
910 I=I+1:IFI<=30000GOTO910
920 ?TICK()
```

### `FOR`～`NEXT`命令

```
900 CLT
910 FORI=0TO30000:NEXT
920 ?TICK()
```

# 実験結果

それぞれのプログラムの組み合わせを1回ずつ実行し、出力された`TICK()`の値を掲載する。
また、それぞれの環境とループの種類について、
ループの前にコードが無い場合と比べた時の`TICK()`の値の差と比も示す。

## IchigoJam U / IchigoJam BASIC 1.0.0 (`VER() = 10017`)

|ループの前|GOTO命令|FOR～NEXT命令|
|---|---|---|
|なし|9951|4568|
|長い行を置けるだけ置く|9964 (+13 / 100.13%)|4568 (±0 / 100.00%)|
|長さと行数のバランスを取る|10031 (+80 / 100.80%)|4568 (±0 / 100.00%)|
|短い行を大量に置く|10371 (+420 / 104.22%)|4568 (±0 / 100.00%)|

## IchigoJam S / IchigoJam BASIC 1.3.1 (`VER() = 13106`)

|ループの前|GOTO命令|FOR～NEXT命令|
|---|---|---|
|なし|3215|2316|
|長い行を置けるだけ置く|3222 (+7 / 100.22%)|2316 (±0 / 100.00%)|
|長さと行数のバランスを取る|3261 (+46 / 101.43%)|2316 (±0 / 100.00%)|
|短い行を大量に置く|3453 (+238 / 107.40%)|2316 (±0 / 100.00%)|

## IchigoKamuy / IchigoJam BASIC 1.4.1 (`VER() = 14114`)

|ループの前|GOTO命令|FOR～NEXT命令|
|---|---|---|
|なし|3172|2289|
|長い行を置けるだけ置く|3180 (+8 / 100.25%)|2289 (±0 / 100.00%)|
|長さと行数のバランスを取る|3221 (+49 / 101.54%)|2289 (±0 / 100.00%)|
|短い行を大量に置く|3432 (+260 / 108.20%)|2289 (±0 / 100.00%)|

## IchigoJam R / IchigoJam BASIC 1.5b (`VER() = 15001`)

|ループの前|GOTO命令|FOR～NEXT命令|
|---|---|---|
|なし|381|277|
|長い行を置けるだけ置く|383 (+2 / 100.52%)|277 (±0 / 100.00%)|
|長さと行数のバランスを取る|390 (+9 / 102.36%)|277 (±0 / 100.00%)|
|短い行を大量に置く|426 (+45 / 111.81%)|277 (±0 / 100.00%)|

## IchigoJam web / IchigoJam BASIC 1.4.3web (`VER() = 14323`)

|ループの前|GOTO命令|FOR～NEXT命令|
|---|---|---|
|なし|22501|7501|
|長い行を置けるだけ置く|22501 (±0 / 100.00%)|7500 (-1 / 99.99%)|
|長さと行数のバランスを取る|22501 (±0 / 100.00%)|7501 (±0 / 100.00%)|
|短い行を大量に置く|22501 (±0 / 100.00%)|7501 (±0 / 100.00%)|

※`TICK()`の値が1秒あたり60増える通常のIchigoJamと異なり、
　今回測定したところ、IchigoJam webでは`TICK()`の値は10秒で約110しか増えないようであった。
　すなわち、`TICK()`の値の同じ増分が、通常のIchigoJamより5～6倍の時間を表すということになる。

# 考察

* 今回実験を行った全環境において、`FOR`～`NEXT`命令によるループの実行時間にはループの前の行数の影響がほぼ見られず、行数に依存しない管理方法が使われていることがうかがえる。
* 1.0.0と1.3.1や1.4.1を比べた時、`GOTO`命令によるループの全体の実行時間は3分の1程度になっているのに対し、ループの前の行数の増加に伴う実行時間の増加は2分の1程度にとどまり、実行時間の増加量は相対的に大きくなっている。
* 1.5bでも1.4.1と似た割合で`GOTO`命令によるループの実行時間が増加しており、IchigoJam Rの大きくなったメモリを利用した効率化などは行われていなそうだと考えられる。
* IchigoJam webでは`GOTO`命令によるループにおいてもループの前の行数の実行時間への影響は見られなかった。例えば以下の可能性が考えられる。
  * 各行が実機とは異なる効率の良いアルゴリズムで管理されている可能性
  * 飛び先を決める処理にかかる時間が、他の部分にかかる時間と比べて大幅に短かった可能性
  * `TICK()`の計算方法が実機と異なり、実行時間と比例していない可能性

# 結論

`GOTO`命令を用いたループでは、ループの前の行数を増やすと最大12%程度の実行時間の増加が見られたが、
`FOR`～`NEXT`命令を用いたループでは、ループの前の行数を増やしても実行時間の増加は全く見られなかった。
それだけでなく、ループの前に行が無い場合でも、
`GOTO`命令を用いたループより`FOR`～`NEXT`命令を用いたループの方が実行時間が短かった。
文字数も少なくなるため、単純なループには`GOTO`命令より`FOR`～`NEXT`命令の方が優れていると考えられる。

さらに、`FOR`～`NEXT`命令は0.9.9から対応しているようなので、互換性の問題も少ないと考えられる。

参考：
[IchigoJam BASIC リファレンス 0.9.8](https://ichigojam.net/IchigoJam-0.9.8.html)
[IchigoJam BASIC リファレンス 0.9.9](https://ichigojam.net/IchigoJam-0.9.9.html)

# おわりに

* IchigoJamはjig.jpの登録商標です。
* IchigoKamuyは株式会社syushuの登録商標です。