1.はじめに
javascriptに限らず長い処理をフロントエンドで実行すると画面がフリーズします。長い処理をしながら画面フリーズを回避するいろいろな仕組みがあります。本記事では、javaacriptでPromise,await,asyncを使って、長い処理(例として巡回セールスマン問題を再帰呼び出しで全経路計算)の、処理途中経過をプログレスバーで表示して、ボタンにより処理中の計算を中断するにはどのようにプログラミングすればよいのかを調べてゆきます。
以下の例は都市数を入力すると、総当たりで最短経路を求める計算をフロントエンドだけで実行し、途中経過と最終結果(10都市で10!=約360万経路のパスコスト計算)を表示するコード例です。リンクコストは接続される都市番号の相乗平均としています。どうやって、途中経過を画面に表示させているのかが本記事の主題です。
See the Pen Factoral by Hiroaki Hata (@h-hata) on CodePen.
1.1 そもそもこれはそんなに難しいことなのか?
スレッドが使えればそれほどの苦労はないのですが、ワンスレッドがjavascriptの特徴です。WebWorkerというスレッド生成技術もありますが、pthreadとは異なり親スレッドとのメモリ共有をせず、メモリ空間が分離しており排他制御などの機構が必要なく専用APIで通信を行う点はプロセスに似ています。フロントエンドでは扱いにくいとしてここでは取り上げませんでした。
ワンスレッドでは非同期処理を行うsetTiemoutやPromiseクラスが利用可能ですが、長い処理の性質に向き不向きがあるようです。長い処理は、ファイルや通信のような非同期APIを発行したら処理完了まで他のことができるタイプは比較的扱いやすいです。厄介なのは、多重ループでなどCPUを手放さず前後の2分割にしづらいタイプの処理です。javascriptでは基本的にコールバックにより、前半処理と後半処理に分けて中断をいれます。後半処理がコールバックに入ります。ループの途中で、処理をいったん中断して途中経過を表示して、残りをコールバックに入れるという分割は、多重ループでの長い処理ではどう分割するのか悩む難しいプログラミングでした。そこに現れたのがasync,awaitです。コールバックではなく、awaitが中断点となり、処理再開をawaitの次の行からできるようになったのです。長い処理はawaitをところどころに挿入することにより、javascriptでは禁忌であったCPUの長期占有という大罪から解放されたのです。それではasyc,awaitの前に、CPUの長期占有の害を振り返っておきます。
2.画面フリーズの仕組み
単純にボタンのイベントハンドラの中で、ラベルにHelloと表示して(CPUを手放さないスピンループで)5秒待ってreturnします。
See the Pen spin loop by Hiroaki Hata (@h-hata) on CodePen.
Helloと表示してから5秒待ったのに、画面にはHelloとは表示されず5秒間フリーズ(ボタンも押せない、文字も入力できない)してから、フリーズが解除してHelloと表示されました。javascriptに限らず、.NETのC#やVB,AndoroidでのJava,iOSやMacOSでのObjectiveCやswiftというほとんどのOSや言語で共通的に言えるのは、イベントハンドラで画面操作を行ってもその瞬間に画面は書き変わらず、イベントハンドラがretunしたあと、GUIシステム側で画面を描きなおします(レンダリング)。したがって、イベントハンドラが長い時間リターンしなければ画面はフリーズします。イベントハンドラは短時間でreturnすると、画面のフリーズ時間が短くなります。3. Promiseとasync/awaitの練習
3.1 Promiseで長時間処理をイベントハンドラから追い出す
イベントハンドラから早くreturnするため、Promiseクラスを使って長い処理をイベントハンドラから追い出します。本来Promiseクラスは、非同期関数を作るためのものであり、重い処理への非同期APIがコンストラクタにおかれますが、ここでは即座にコンストラクタは終了してthen節に重い処理を持ってきました。resolveにはうまくパラメータが引きわてされているかどうかを確認するために、5という適当な値を引き渡しています。
See the Pen Promise-1 by Hiroaki Hata (@h-hata) on CodePen.
ボタンを押してみますと、script2.jsと画面の様子は変わりません。innerHTMLと異なり、console.logは呼び出した瞬間に表示されます(埋め込みCodePenではconsole表示できません。お手元で試していただくか、そういうものかと下記の表示例を信じてください。)。コンソールへの出力は以下の通りで、イベントハンドラからreturnしたにもかかわらず画面はフリーズしたままthen節が実行されています。1
2
4(ここでイベントハンドラ終了)
3=>5(thenのコールバック)
loop out5
もうひとつjavascriptで重要なことは、GUIシステム側に置いてレンダリングの優先順位は低いという点です。このコードでは確かに素早くイベントハンドラからreturnしていますが、resolveを呼んだあとにreturnしています。その時点で、GUIシステムはイベントハンドラからリターンすると、すぐにthenを起動しなければならないという実行予約が入ってしまいます。このため、イベントハンドラからreturnされてもレンダリングが後回しにしてthenが起動されたのでした。イベントハンドラを単純に短くしただけではフリーズは解消しなかったということです。
3.2 async/awaitの練習
aync/awaitを組み合わせると、単にPromiseだけのときとどう変わるのかを確認しておきます。シングルスレッドのjavascriptでは本来自ベントハンドラ自体を非同期関数にすることはないのですが(C#などでは普通にやります)、ここではasync/awaitの振舞を理解するために、イベントハンドラを非同期関数にしてみます。
script3-1.jsにちょっとだけ変更します。asyncをイベントハンドラの頭につけて、awaitを new Promiseの左側に付加するだけです。
See the Pen async-await-1 by Hiroaki Hata (@h-hata) on CodePen.
画面がフリーズするのは同じですが、コンソールに表示される番号の順序が変化しています。Promiseだけだと3の5秒ループは4のreturn前でしたが、async/awaitを付けると、コード順に実行されてPromiseを付ける前に戻ってしまいました。このようなasync/awaitに何か意味があるのでしょうか。
1
2
3=>5(thenのコールバック)
loop out5
4(イベントハンドラ終了)
async関数は特殊な関数で、プログラミングの経験者は違和感を抱く動きをします。その奇妙な動作とは、async関数は2度リターンするのです。awaitが2個以上書かれていたら(ループでも)、そのたびに仮のリターンが起こります。awaitはreturnと同じくパラメータをとりますが、それはPromiseオブジェクトでなければなりません。そして何らかの方法で、そのPromiseオブジェクトのresolve()メソッドが呼び出されると、一時中断していたasync関数のawaitの次の行から実行が再開されます。そして最後に真のreturnが実行されてasync関数が終了します。script3-2.jsはPromiseのコンストラクター内でresolve()を呼んでいるので、awaitでいったん仮のreturnをするものの即座に残りの行から実行が再開されるため、async/awaitやPromiseが何の役に立っていないように見えたのでした。
resolve()を呼んでからawaitしても無意味なのなら、awaitしたあとにresolve()を呼ぶと面白いことが起こるのでは?と思われます。
3.3 仮のreturnの間に画面を描画してもらう 実は有用なawait
awaitしたあとにresolve()を呼ぶ方法で簡単に思いつくのはsetTimeoutです。Promiseのコンストラクタ内ですぐにresolveを呼ぶのではなく、setTimeoutのハンドラの中で呼ぶことで、ほんの少し実行を遅らせられます。これによりawaitでGUIシステムに仮リターンした1ミリ秒後にハンドラが起動再開するはずです。このコードは、ボタンを押すと5秒間フリーズするところは相変わらずなのですが、外面上決定的な違いがあります。それはボタンを押した瞬間に"Start"と表示されるところです。ボタンのclickイベントハンドラからの仮のリターンの間にGUIシステムは他に起動しなければならない仕事がなく、レンダリングをやってくれるので画面が更新されます。その1ミリ秒後に、setTimeoutのイベントハンドラが起動されresolve()がコールされ、それによりthenが実行されたのでした。
See the Pen then-async-await-StartMessage by Hiroaki Hata (@h-hata) on CodePen.
javascript4-1.jsのシーケンスチャートを載せておきます。
thenのあとにイベントハンドラの残りの部分が実行されるならthenなんかいらないんじゃないか?と思われるかもしれません。実はその通りで、フリーズする長い処理をイベントハンドラに戻しても、なんら変わりなく同じ動作になります。thenがないのは自然なのですが、javascriptではコールバックを使わないこのような自然な書き方ができず、プログラムをいったん止めたらコールバックという呪縛に囚われていたのでした。中断したいところでawaitすればよいというのはjavascriptでは画期的で、コールバックで長い処理を前後に分ける必要はないというだけで、プログラミングが大変楽になるのです。
しかしthenは一切不要なものではなく、後述しますが仮のリターンで戻した側でのthenはものすごく重要な意味があります。
See the Pen wo_then-async-await-StartMessage by Hiroaki Hata (@h-hata) on CodePen.
thenを省略したのでシーケンスチャートもシンプルになりました。4.実際のasync/await
4.0 確認のため関数を作って、Promiseオブジェクトを返すコードを作成する
これまでイベントハンドラ内でPromiseを生成していましたが、別関数に移してPromiseをreturnで返す変更をしました。実行順序を確認するため長い処理は省略しています。
See the Pen asyncFunc-0 by Hiroaki Hata (@h-hata) on CodePen.
詳細には、ハンドラ(1)からsubが呼ばれて(5)(6)(7)、ハンドラにPromiseオブジェクトが戻ります。ハンドラがawait pp で仮リターンする(2)ことでthen(3)が実行されます。thenの仮引数は10であることが確認できます。当たり前ですがreturnで返されるPromiseオブジェクトと、returnで得られたPromiseオブジェクトで、2つの関数で***同一のオブジェクトを参照***しています。4.1 Promiseオブジェクトをawaitで返すコードに修正する
script-5.1.jsと概要は変わりませんが、少しだけ変更します。
変更点は
- イベントハンドラを同期関数に戻し、sub関数を非同期関数にする
- イベントハンドラからasyncを削除する
- sub()にasyncを付ける
- sub()はPromiseを作成してawaitで仮リターンする
- sub()は真のリターンで整数を返すとする
- イベントハンドラか仮のreturnで返されたPromiseオブジェクトにthen節を登録する
変更後のコードは以下のようになります。特徴的なところは、sub()の真の返り値は整数型ですが、イベントハンドラではsubの返り値をPromise型として扱っているところです。真の返り値はどのように受け取ればよいのでしょうか。
See the Pen asyncFunc-1 by Hiroaki Hata (@h-hata) on CodePen.
script5-1.jsではPromiseをreturnで返しましたが、script5-2.jsではPromiseをawaitで返しています。実行してみると、イベントハンドラで登録したthenが、イベントハンドラ終了後のさらに非同期関数終了後コールバックされています。ここで重要な注意点が2つあります。ベテランプログラマほど、そんなバカなことがあるか!?と感じるルールです。- asyncで非同期にした関数の真の返り値のデータ型が何であろうが、呼び出し側では返り値をPromise型として受けなければならない pp = sub();//これです!
- awaitで返すPromiseオブジェクトと、返り値で受けたPromiseオブジェクトは別物である
このプログラムを実行してコンソール出力を見てみます。sub側で発行したresolveのパラメータは10ですが、イベントハンドラ側のthenの仮引数には100が代入されていました。この100とはsubの真の返り値でした。そしてそのthenはasync関数が真のリターンをすることにより起動されています。
まとめると
- async関数はawaitで仮のリターンをして呼び出し側にPromiseを与える
- 呼び出し側に返されたPromiseはsync関数で生成したPromiseとは別オブジェクト
- async関数側のPromiseでresolveが呼び出されればawait後の処理が再開される。このとき、呼び出し側関数(イベントハンドラ)が終了していてもかまわない
- async関数が終了すれば、呼び出し側で登録しておいたthenが起動する。その仮引数には、sync関数の真の返り値が格納されている
resolve(10)の10はどこに行ったのでしょうか?それはsub()のpでthenが登録されていないので、誰も受け取らなかったのです。非同期関数sub側のawait後の処理はthenに入れる必要がなかったのが利点でした。awaitする前にpにあえて仮引数つきのthenを登録すると5が得られます。script4-2でthenを省略したようにasync関数側のthenは特に使い道がありませんので、script5-2でも省略しました。
シーケンスチャートは以下のようになっています。
4.2 長い処理の途中経過を表示する方法
ここまでやってきても5秒間スピンループされたら画面をフリーズ解除する方法は思いつきません。しかし、長い処理の途中のどこかで、次の実行予約が入っていない状態でGUIシステムに短時間戻りレンダリングを実行する機会を設けてやれば途中経過を表示差出来るのではないかと考えられます。
for (let cur = new Date(); new Date() - cur < 5000; ) {}
は5秒間フリーズしますが、1秒を5回に分けてその間に一瞬awaitでGUIシステムに仮returnしてみます。このawait時にはresolveを発行していない状態でいなければなりません。このために、(本当はsleepなんかしたくないのですけど)sleep関数を作成して、その中で新しいPromiseをnewして、一瞬タイミングをずらしてresolveします。これを長い処理のところどころで、await sleep(1)すると遅れて発行されるresolveの間にレンダリングが発生します。
See the Pen async await by Hiroaki Hata (@h-hata) on CodePen.
このプログラムの実行したときのコンソールが以下です。一回目のawaitの仮リターン先はイベントハンドラですが、仮リターンするとすぐさまイベントハンドラは終了して結果的にGUIシステムに制御が戻ります。その間resolveの発行が行われていなければ、レンダリングが行われ画面にはStep=0と表示されます。イベントハンドラは終了していますが、myfuncはまだループが始まったばかりで1秒のスピンループに入ります。2回目以降のawait sleepではGUIシステムに仮リターンします。これを5回繰り返し、ループを抜けて真のリターンで100を返します。すると、1回目の仮リターンでイベントハンドラが得ていたPromiseのthenが起動します。 resolve()を遅延させる1ミリ秒はCPU速度やOSのバージョンによっては不十分かもしれません。PCやタブレットでは1ミリ秒で十分レンダリングが発生しますが、スマートフォンでは1ミリ秒では不十分でレンダリングの機会を取りこぼす可能性があります。1
myfunc in
2
sleep return
sleep return
sleep return
sleep return
sleep return
myfunc out
5.巡回セールスマン問題を途中経過つきで解く
これまでで、材料は出そろいました。
- sleep関数を作成する。この関数はPromiseを生成して、指定時間後にresolveを呼ぶ
- 長い処理はasync関数にして、適当にawait sleepを呼ぶ。このawaitの直前で画面表示を変更しておく。
これで、長い処理も途中経過が逐次表示されるはずです。
長い処理の例として巡回セールスマン問題を総当たりで解いてみます。ここでは簡単のため、街の数をnとして町番号を0からn-1とします。そしてnからmへ移動するコストを町番号の相乗平均として、すべての街を一筆書きで巡回するとして、最小コストで回れる街の順番と、そのコストを求めます。一度訪問した町は再度訪問できません。すると、巡回するパス(経路)は、0からn-1までの番号を並べる順列の数n!だけあることが分かります。
多くの問題の中でも、nが大きくなるにつれ計算量が大きくなり方が半端ない最もたちの悪いタイプの問題として有名です。
総当たりでの簡単な解き方は、街の数だけ多重ループを作る方法です。外側のループカウンタの値を内側のループカウンタでは使わない(continueする)と、最も内側のループに至ったらすべてのループカウンタは異なった値をとっているはず、という作戦です。ループカウンタの値を並べたものがパスで、パスが決定されるたびにパスコストを計算して、最小のパスを探します。ここで一番外側(図では上位と表現)のループカウンタAが更新されるたびにawait sleep(1)を呼んでAの値(一番外はcontinueなし)を途中経過として表示します。
これが完成形です。テキストボックスに11以下の数値を入れてStartを押してください。11で11!=4000万弱種類のパスを総当たりで比較します。
本記事の最初の埋め込みCodePenでの実行ではなく、読者自身のマシンのCPU動作を描くのんしてみてください。12コアのCPUを持つPCよりタブレット端末の方が速いかもしれません。ワンスレッドですから。
ボタンを押すと途中経過が逐次表示されますが、ボタンのvalueがStopに変わり、計算を中断できます。イベントハンドラをなるはやで終了しているので、計算実行中のイベントハンドラ起動も可能です。イベントハンドラ中で、計算実行中なら計算を中断して、もし計算中でなければ計算を開始するというフラグによる分岐処理が入っています。
最終的なJavascript付きHTMLはこの通りです。
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Document</title>
<script>
document.addEventListener("DOMContentLoaded", () => {
const txt = document.getElementById("txt_id");
const lbl = document.getElementById("lbl_id");
const lbl2 = document.getElementById("lbl2_id");
const btn = document.getElementById("btn_id");
const pgb = document.getElementById("pgb_id");
let run_flag = 0;
let d;
let cnt = 0;
let a = [];
let b = [];
let pass;
let cost = -1;
let step = 0;
const updatepass = () => {
let tmp = 0;
for (let i = 0; i < b.length - 1; i++) {
tmp += Math.sqrt(b[i] * b[i + 1]);
}
if (cost == -1 || tmp < cost) {
cost = tmp;
pass = [...b];
}
return tmp;
};
const sleep = (msec) => {
return new Promise(function (resolve) {
setTimeout(function () {
resolve();
}, msec);
});
};
async function factorial(n) {
//n桁目の数値を決定する
for (let i = 0; i < d; i++) {
//最上位桁を決定する前に少し休む
if (d - 1 === n) {
if (run_flag == 0) {
//中断指示があれば終了
return;
}
pgb.value = "" + step;
lbl.innerHTML =
"Step= " + step + "/" + d + " Count=" + cnt.toLocaleString();
lbl2.innerHTML = "cost=" + cost.toFixed(3);
step++;
await sleep(1);
}
//a[1]利用済み数値
if (a[i] === 1) {
continue; //使用済み数値だったので次を検査
}
//n桁目はiに決定
//console.log(n+"桁目は"+i+"に決定");
a[i] = 1;
//n桁目にiを書き込む
b[n] = i;
if (n === 0) {
//0桁目が決定された=全ての桁の数値が決定された
if (run_flag == 0) {
//中断指示があれば終了
return;
}
//全ての桁が確定された。決定された数値を表示
/*
let str = "";
for (let k = d - 1; k >= 0; k--) {
str += " " + b[k];
}
console.log(str);
*/
tmp = updatepass(); //パスコスト計算
//console.log("cost=" + tmp);
cnt++;
//iを未使用にする
a[i] = 0;
return;
}
//次の桁を決定する
factorial(n - 1);
//iを未使用にする
a[i] = 0;
}
}
btn.addEventListener("click", () => {
if (run_flag == 1) {
run_flag = 0;
pgb.value = "0";
lbl.innerHTML = "Stoped by user";
btn.value = "Start";
return;
}
const str = txt.value;
const n = parseInt(str);
if (isNaN(n) || n > 15 || n <= 0) {
lbl.innerHTML = "invalid value";
return;
}
d = n;
a = [];
b = [];
for (let i = 0; i < n; i++) {
a.push(0);
}
cnt = 0;
run_flag = 1;
step = 0;
cost = -1;
pgb.max = d;
btn.value = "Stop";
factorial(n - 1).then(() => {
if (run_flag != 0) {
console.log("total pass=" + cnt.toLocaleString());
lbl.innerHTML = "total pass=" + cnt.toLocaleString();
pgb.value = "0";
btn.value = "Start";
let str = "";
for (let k = d - 1; k >= 0; k--) {
str += " " + pass[k];
}
str += " cost=" + cost.toFixed(3);
console.log(str);
lbl2.innerHTML = str;
}
run_flag = 0;
});
return;
});
});
</script>
</head>
<body>
<input type="text" id="txt_id" />
<input type="button" id="btn_id" value="Start" />
<progress id="pgb_id" value="0" max="100"></progress>
<p id="lbl_id"></p>
<p id="lbl2_id"></p>
</body>
</html>
6.おわりに
長い処理が中断できるので画面は一見フリーズしていないように見えます。しかしこのプログラムに12を入力すると分かりますが、大方の時間はフリーズしておりawaitの呼ばれる定期的な瞬間だけフリーズが解除されています。ボタンを押したイベントはGUIシステム内部で記憶されており、フリーズが解除された瞬間にイベントハンドラが起動されます。このようにjavascriptをワンスレッドで動作させると、計算中は画面フリーズは避けられません。それをユーザからみていかにフリーズしていないかのように見せるのかは、awaitを入れるタイミングの設計に依ります。12!でユーザインタフェースの質を保つには最上位のループカウンタの更新タイミングではなく、2番目の再帰呼び出しのレベルでawaitを入れなければなりません。同じ問題でも、与えられるパラメータによりawaitを入れるタイミングを動的に変更したり、再帰でもいま何段目にいるのかが意識できるパラメータを追加したりと、かなり気を遣ったプログラミングが必要とされます。