How to reduce GC processing on real time JavaScript game.
Introduction
You know, I've been implementing a STG with JavaScript and HTML5. (This article follows the previous article http://d.hatena.ne.jp/takahirox/20130819/1376894048)
Recently, the low performance of the STG was getting serious, therefore I got the profile. I found the GC was one of the most heavy processings (though the heaviest processing is canvas drawing), and I attempted to reduce GC occurrence.
In this article, I'll show you what I did to reduce GC and how it worked well.
Play and video
First, I'll let you know the latest and older version of the game and the video. You can understand what I've been implementing. In the latest one has low GC implementation, while the older one doesn't it and GC occurs a lot.
You can register your playing to the server in the latest version and let the other players see your playing! Try it!
the latest one
http://takahirox.github.io/toho-like-js/index.html (Click this link to play! You can play this game on your chrome.)
Before (Bad code)
Then, I'll show you the older code which made GC happen a lot. This class, named ElementManager, manages almost all elements of my STG, like fighter, bullet, enemies, and so on.
// Note that I simplified this code to let you easily understand. function ElementManager( ) { this.elements = [ ] ; } ; ElementManager.prototype.reset = function( ) { this.elements = [ ] ; } ; // Element is the class represents an element of my STG. ElementManager.prototype.create = function( ) { this.elements.push( new Element( ) ) ; } ; // This function removes dead elements. ElementManager.prototype.checkLoss = function( callback ) { var elements = [ ] ; for( var i = 0; i < this.elements.length; i++ ) { if( ! this.elements[ i ].isDead( ) ) { elements.push( this.elements[ i ] ) ; } } this.elements = elements ; } ;
You know, in STG much many elements appear. They are generated, deleted, generated, deleted... much many elements are repeatedly generated and deleted.
I mean, this is the main resource management logic. I expected JavaScript automatically allocate and free memory well, so I didn't care them by myself at all, as you see in the code.
After (Good code)
I read this document when I decided to reduce GC processing.
- How to write low garbage real-time JavaScript
I'll quote the most important technique written in this document. (In this document, you can see many useful techniques. I recommend you to read through it.)
Where possible, try to create the object on startup, and simply re-use the same object for as long as possible.
I changed the memory management strategy. I decided to manage memory by myself. I wrote an abstract memory(element=object) management class, named FreeList.
/** * This class manages object resources to reduce GC. */ function FreeList( num ) { this.num = num ; this.head = null ; this.tail = null ; this.list = [ ] ; this._init( ) ; } FreeList.prototype._init = function( ) { // Just in case. if( this.num <= 0 ) return ; for( var i = 0; i < this.num; i++ ) { var element = this._generateElement( ) ; element.listId = i ; // compulsorily add a property. this.list.push( { 'element': element, 'listForw': null, 'available': true } ) ; if( i > 0 ) this.list[ i - 1 ].listForw = this.list[ i ] ; } this.head = this.list[ 0 ] ; this.tail = this.list[ this.num - 1 ] ; } ; /** * Child class must override this method. */ FreeList.prototype._generateElement = function( ) { return { } ; } ; /** * TODO: must implement the proper object shortage handler. * TODO: verify the functionality. */ FreeList.prototype.get = function( ) { if( this.head == null ) { window.alert( 'ran out of object resources.' ) ; throw new Error( 'ran out of object resources.' ) ; } var head = this.head ; this.head = head.listForw ; head.available = false ; head.listForw = null ; if( this.head == null ) this.tail = null ; return head.element ; } ; FreeList.prototype.free = function( element ) { this.list[ element.listId ].available = true ; if( this.tail != null ) this.tail.listForw = this.list[ element.listId ] ; this.tail = this.list[ element.listId ] ; if( this.head == null ) this.head = this.tail ; } ;
The FreeList has an element list. Outer class uses get( ) to get an object from the element list and free( ) to return an object to the element list. As you see, objects are generated only once (I mean memory allocation for elements occurs only once) when the FreeList instance is generated. And also, the FreeList keeps freed objects in the element list. So, you can reuse objects.
And, I modified the ElementManager to use FreeList.
// Note that I simplified this code to let you easily understand. /** * Utility function for inherit. */ function __inherit( child, parent ) { var getPrototype = function( p ) { if( Object.create ) { return Object.create( p ) ; } function f( ) { } ; f.prototype = p ; return new f( ) ; } ; child.prototype = getPrototype( parent.prototype ) ; child.prototype.constructor = child ; } function ElementFreeList( num ) { FreeList.call( this, num ) ; } __inherit( ElementFreeList, FreeList ) ; ElementFreeList.prototype._generateElement = function( ) { return new Element( ) ; } ; function ElementManager( ) { this.elements = [ ] ; this.freelist = new ElementFreeList( 1000 ) ; } ; ElementManager.prototype.reset = function( ) { for( var i = 0; i < this.elements.length; i++ ) { this.freelist.free( this.elements[ i ] ) ; } this.elements.length = 0 ; } ; ElementManager.prototype.create = function( ) { var e = this.freelist.get( ) ; e.init( ) ; // initialize Element this.elements.push( e ) ; } ; // A technique written in the above document is used, // that is to change length properties. ElementManager.prototype.checkLoss = function( callback ) { var j = 0 ; for( var i = 0; i < this.elements.length; i++ ) { if( ! this.elements[ i ].isDead( ) ) { this.elements[ i - j ] = this.elements[ i ] ; } else { this.freelist.free( this.elements[ i ] ) ; j++ ; } } this.elements.length -= j ; } ;
Comparison
I compared the new implementation with the old one by seeing CPU profile. I used the 2nd stage boss bullets pattern for the comparison because its bullet number is around 400(see the circle of the following image) which is the currently most greatest number in my STG. I mean, Element generation and deletion happen a lot.
This is the (partial) result. The top one is the older one result, and the bottom one is the newer one.
You can see that CPU spent around 5% for GC and idle time is only 25% in the older one. But, GC didn't occur in the newer one and idle time much increased, that is 73%. This idle time increase is much important to be stable running on 60FPS.
When you see this result number, be careful that I modified the entire source code not only to use new ElementManager and FreeList, but also to prevent new memory allocation in many parts as fine tune.
And this result is just on my environment. On your environment, the result number can change.
Conclusion
I implemented low GC STG which manages memory by myself. It reduced GC processing a lot and much increased idle time.
I confirmed the memory reuse technique works well to implement low GC game.
Probably, this is the basic and well-known technique. But it's interesting that you can see the actual number on the actual game, isn't it?
The following is the Japanese translation of this article.
Introduction
JavaScriptとHTML5でSTGを作っています。(このエントリは前のエントリの続き http://d.hatena.ne.jp/takahirox/20130819/1376894048)
処理の重さが最近問題になってきたので、プロファイルを取得しました。GCが一つの重い処理だということがわかったので、GCの発生を減少させる試みを行いました。(一番重い処理は描画処理なんだけれども)
このエントリでは、GCの発生を減少させるために行ったことと、それが如何によく効いたかを紹介します。
Play and video
最初に、最新版とその前のバージョンのSTGとその動画を紹介します。私が何を作っているのかがわかるでしょう。最新版ではGC減少ロジックが実装されています。前のバージョンでは実装されておらず、GCがたくさん発生します。
ところで、最新版ではあなたのプレイがサーバに登録でき、他プレイヤーにそのプレイを見せることができるので、お試しあれ。
the latest one
http://takahirox.github.io/toho-like-js/index.html (Click this link to play! You can play this game on your chrome.)
Before (Bad code)
次に、GCをたくさん発生していた古いバージョンのソースコードを紹介します。このElementManagerクラスは、STG中のほぼ全ての要素(自機、弾、敵など)を管理するクラスです。
// Note that I simplified this code to let you easily understand. function ElementManager( ) { this.elements = [ ] ; } ; ElementManager.prototype.reset = function( ) { this.elements = [ ] ; } ; // Element is the class represents an element of my STG. ElementManager.prototype.create = function( ) { this.elements.push( new Element( ) ) ; } ; // This function removes dead elements. ElementManager.prototype.checkLoss = function( callback ) { var elements = [ ] ; for( var i = 0; i < this.elements.length; i++ ) { if( ! this.elements[ i ].isDead( ) ) { elements.push( this.elements[ i ] ) ; } } this.elements = elements ; } ;
STGではたくさんの要素が画面上に現れます。それらは生成され、削除され、生成され、削除され……と、生成と削除を繰り返します。
つまり、このクラスはメインのリソース管理ロジックです。JavaScriptは自動的にメモリの割当てと解放を効率的に行ってくれると期待していたので、コードを見てわかるように、全く自分自身ではメモリ管理を考慮していませんでした。
After (Good code)
GCの発生を減らすと決めたとき、このドキュメントを読みました。
- How to write low garbage real-time JavaScript
最も重要なテクニックを引用します。(このドキュメントには有用なテクニックがたくさんかかれているので、一度目を通すことをお勧めします)
Where possible, try to create the object on startup, and simply re-use the same object for as long as possible.
メモリの管理方法を変え、自分自身で管理することに決めました。FreeListと呼ばれるメモリ(要素＝オブジェクト)管理クラスを書きました。
/** * This class manages object resources to reduce GC. */ function FreeList( num ) { this.num = num ; this.head = null ; this.tail = null ; this.list = [ ] ; this._init( ) ; } FreeList.prototype._init = function( ) { // Just in case. if( this.num <= 0 ) return ; for( var i = 0; i < this.num; i++ ) { var element = this._generateElement( ) ; element.listId = i ; // compulsorily add a property. this.list.push( { 'element': element, 'listForw': null, 'available': true } ) ; if( i > 0 ) this.list[ i - 1 ].listForw = this.list[ i ] ; } this.head = this.list[ 0 ] ; this.tail = this.list[ this.num - 1 ] ; } ; /** * Child class must override this method. */ FreeList.prototype._generateElement = function( ) { return { } ; } ; /** * TODO: must implement the proper object shortage handler. * TODO: verify the functionality. */ FreeList.prototype.get = function( ) { if( this.head == null ) { window.alert( 'ran out of object resources.' ) ; throw new Error( 'ran out of object resources.' ) ; } var head = this.head ; this.head = head.listForw ; head.available = false ; head.listForw = null ; if( this.head == null ) this.tail = null ; return head.element ; } ; FreeList.prototype.free = function( element ) { this.list[ element.listId ].available = true ; if( this.tail != null ) this.tail.listForw = this.list[ element.listId ] ; this.tail = this.list[ element.listId ] ; if( this.head == null ) this.head = this.tail ; } ;
FreeListはリストを持ちます。外部クラスは、オブジェクトをリストから取得するためにget()を使用し、オブジェクトをリストに返すためにfree()を使用します。
見てわかるように、オブジェクトの生成はFreeListインスタンス生成時に一度しか行われません(つまり、オブジェクトのためのメモリ割当はインスタンス生成時に一度しか行われません)。そして、FreeListは返されたオブジェクトもリストにキープしておきます。よって、オブジェクトの再利用が可能となります。
FreeListを使うようにElementManagerを修正しました。
// Note that I simplified this code to let you easily understand. /** * Utility function for inherit. */ function __inherit( child, parent ) { var getPrototype = function( p ) { if( Object.create ) { return Object.create( p ) ; } function f( ) { } ; f.prototype = p ; return new f( ) ; } ; child.prototype = getPrototype( parent.prototype ) ; child.prototype.constructor = child ; } function ElementFreeList( num ) { FreeList.call( this, num ) ; } __inherit( ElementFreeList, FreeList ) ; ElementFreeList.prototype._generateElement = function( ) { return new Element( ) ; } ; function ElementManager( ) { this.elements = [ ] ; this.freelist = new ElementFreeList( 1000 ) ; } ; ElementManager.prototype.reset = function( ) { for( var i = 0; i < this.elements.length; i++ ) { this.freelist.free( this.elements[ i ] ) ; } this.elements.length = 0 ; } ; ElementManager.prototype.create = function( ) { var e = this.freelist.get( ) ; e.init( ) ; // initialize Element this.elements.push( e ) ; } ; // A technique written in the above document is used, // that is to change length properties. ElementManager.prototype.checkLoss = function( callback ) { var j = 0 ; for( var i = 0; i < this.elements.length; i++ ) { if( ! this.elements[ i ].isDead( ) ) { this.elements[ i - j ] = this.elements[ i ] ; } else { this.freelist.free( this.elements[ i ] ) ; j++ ; } } this.elements.length -= j ; } ;
Comparison
CPUプロファイルを取ることで、新しい実装と古い実装の比較を行いました。2面ボスの弾パターンを比較の題材としました。その理由は、画面上に約400発の弾が現れ(下図の白丸参照)、その400という数字はこのSTGの中で一番大きい数字だからです。つまり、要素の生成と削除が最も行われるということです。
これが比較結果(の一部分)です。上が古い実装で、下が新しい実装のものです。
古い実装では、CPUは約5%をGCに費やし、またアイドルタイムはたったの25%です。一方新しい実装では、GCが発生せず、アイドルタイムも73%まで増加しました。このアイドルタイムの増加は、安定して60FPSを出すためにとても必要です。
この改善度を見るとき、新しいElementManagerとFreeListの使用だけでなく、新たなメモリ獲得を防ぐようにソースコード全体で細かいチューンも行ったことには注意してください。
また、この比較結果は私の環境での結果です。環境によってはこの数字は変わってくるかもしれません。
