JavaScript: garbage collectionの負荷を減らす設計

objectにobjectを追加していくとどんどんmemory解放が大変になっていくらしいので、その対処法を紹介します。
代表的な方法はobjectを平坦な数値配列で表現する事。できればTypedArrayが良い。

let A=[{a:0,b:1},{a:2,b:3}]

上記を以下のようにする。

let a=new Uint8Array([0,2]),b=new Uint8Array([1,3])

木構造(Trie)

もう少し複雑な例。PPM(情報圧縮)をTrieで実装した例

object連打

function Leaf(s,a){this.s=s,this.n=a<<1|1}Leaf.prototype={c:1,e:0};
//圧縮
function PPMe(A,mo,ml,done,rate){
	ml&=65535;
	var sync="function"!=typeof rate,a=0,m=1,o=2,z=A.length,
		L=0,R=-1>>>0,B=ml&255,C=0, // coder
		root={c:1,e:0,n:0},x=new Leaf(0,0),Cx=[root], // tree
		O=[mo&=255,ml>>8];
	done=done||function(O){return O};rate=rate||function(){};
	mo+=2,ml=4e9/ml;
	function F(){
		var c,e,f,i,l,n,p,q,r,t,E=[],b=sync?-1:4095,d=sync?1/0:+new Date;
		for(rate(a,z);a&b||new Date-d<200;E.length=0){
			if(m>mo)m=mo;c=a<z?A[a]:256;
			for(i=m;;){
				if(i){
					n=Cx[--i];p=n.n;
					if(!p.c&&p&1)n.e++,ml--,p=n.n=new Leaf(A[p>>=1],p+1);
					for(q=l=t=0;p;p=p.p)if(!E[p.s])f=p.c,p.s^c||(l=f,r=t,q=p),t+=f;
					if(!t)continue;e=n.e;
					if(!l)l=e,r=t;t+=e}
				else for(r=0,q=l=1,e=t=257;e;)E[--e]?t--:e<c&&++r;
				R=R/t>>>0;L+=R*r;
				for(R*=l;R<16777216;R*=256,L=L<<8>>>0)
					if(L>>24^-1)
						for(l=0xffffffff<L,O[o++]=255&l+B,B=L>>>24,l+=255;C;C--)O[o++]=255&l;
					else++C;
				if(q){if((q.c+=2)>250)for(p=n.n;p;p=p.p)p.c-=p.c>>1;break}
				for(p=n.n;p;p=p.p)E[p.s]=1
			}
			if(++a>z){
				for(a=5;a--;L=L<<8>>>0)
					if(L>>24^-1)
						for(l=0xffffffff<L,O[o++]=255&l+B,B=L>>>24,l+=255;C;C--)O[o++]=255&l;
					else++C;
				return done(O,z,o)
			}
			// deepen rest context
			for(;i;){n=Cx[--i];p=n.n;
				if(!p.c&&p&1)n.e++,ml--,n.n=new Leaf(A[p>>=1],p+1)
			}
			// update tree
			up:for(i=++m;--i;Cx[i]=p){
				for(e=0,n=Cx[i-1],p=n.n;p;e=p,p=p.p)
					if(p.s===c){
						f=p.p,e?e.p=f:n.n=f,p.p=n.n,n.n=p;
						continue up
					}
				if(ml>0)e=n.n,n.n=p=new Leaf(c,a),n.e++,ml--,p.p=e;
				else p=x;m=i
			}root.c++ // order 0
		}setTimeout(F)
	}return F()
}
//展開
function PPMd(A,done,rate){
	for(var sync="function"!=typeof rate,a=3,m=1,o=5,z=A.length,mo=A[0]+2,ml=4e9/(A[1]<<8|A[2]),
		L,R=-1>>>0,E=[],O=[], // coder
		root={c:1,e:0,n:0},x=new Leaf(0,0),Cx=[root];--o;)L=(L<<8|A[a++])>>>0;
	done=done||function(O){return O};rate=rate||function(){};
	function F(){
		var c,e,f,i,n,p,r,t,b=sync?-1:4095,d=sync?1/0:+new Date;
		for(rate(a,z);a&b||new Date-d<200;E.length=0){
			if(m>mo)m=mo;
			for(i=m;;){
				if(i){
					n=Cx[--i];p=n.n;
					if(!p.c&&p&1)n.e++,ml--,p=n.n=new Leaf(O[p>>=1],p+1);
					for(t=0;p;p=p.p)if(!E[p.s])t+=p.c;
					if(!t)continue;e=n.e;
					r=L/(R=R/(t+e)>>>0)|0;
					if(t>r){
						for(t=0,p=n.n;t+(f=p.c&-!E[p.s])<=r;p=p.p)t+=f;
						c=p.s,f=p.c
					}else for(c=256,f=e,p=n.n;p;p=p.p)E[p.s]=1
				}else{c=r=t=-1;
					for(f in E)r++;
					for(r=L/(R=R/(256-r)>>>0)>>>0;E[++c]||r>++t;);
					if(c>255)return done(O,z,o);f=1
				}
				for(L-=R*t,R*=f;R<16777216;R*=256)L=(L<<8|A[a++])>>>0;
				if(c<256){if(p&&(p.c+=2)>250)for(p=n.n;p;p=p.p)p.c-=p.c>>1;break}
			}
			for(O[o++]=c;i;){n=Cx[--i];p=n.n;
				if(!p.c&&p&1)n.e++,ml--,n.n=new Leaf(O[p>>=1],p+1)
			}
			up:for(i=++m;--i;Cx[i]=p){
				for(e=0,n=Cx[i-1],p=n.n;p;e=p,p=p.p)
					if(p.s===c){
						f=p.p,e?e.p=f:n.n=f,p.p=n.n,n.n=p;
						continue up
					}
				if(ml>0)e=n.n,n.n=p=new Leaf(c,o),n.e++,ml--,p.p=e;
				else p=x;m=i
			}root.c++
		}setTimeout(F)
	}return F()
}

TypedArray版

/*
各node(Leaf object、あるいはroot,x)をTypedArray のindexとして表現する。
index 0: NULL(未使用/末尾)
index 1: root(最初は空: NN[1] = 0)
index 2: x(memory枯渇時の共有dummy葉: NN[2] = 0<<1|1 で初版の`new Leaf(0,0)` と同じ「位置0への遅延pointer」を再現)
index 3.. : 動的に確保される実node

構造:
NS[i]: 子としての記号(0-255),頻度(上位8bits,0-255) … 元 Leaf.s
NE[i]: このnodeを「文脈」として使った時のescape数、初期値255(=0) … 元 .e
NP[i]: 兄弟リストの次node(実index, 0=終端) … 元 .p
NN[i]:「文脈」としての子先頭pointer。0=空、奇数=遅延(位置<<1|1)、偶数(非0)=実nodeへの参照(node番号<<1) … 元 .n

初版は `!p.c && p&1` で「p がまだ実体化していない生の整数(奇数)か、実体化済みobjectか」を判定していたが、
実index参照を idx<<1 という偶数値することで同じ判定を `raw & 1` だけで再現できる(0とidx>=1の偶数値は衝突しない)
*/
function makeTrie(cap){
	var NS=new Uint16Array(cap), NE=new Uint8Array(cap).fill(255),
		NP=new Int32Array(cap), NN=new Int32Array(cap), n=3;
	NN[1]=0; // root: 空
	NS[2]=256,NE[2]=255,NP[2]=0,NN[2]=1; // x: Leaf(0,0) 相当
	return{
		alloc:function(sym,pos){
			if(n>=cap){
				let a=new Uint16Array(this.a=cap*=2);a.set(NS);NS=a;
				a=new Uint8Array(cap).fill(255,cap>>1,cap);a.set(NE);NE=a;
				a=new Uint32Array(cap);a.set(NP);NP=a;
				a=new Uint32Array(cap);a.set(NN);NN=a
			}
			NS[n]=sym|256,NP[n]=0,NN[n]=pos<<1|1;//NE[n]=255
			return n++
		},
		get NS(){return NS},get NE(){return NE},
		get NP(){return NP},get NN(){return NN},
		ROOT:1,X:2
	}
}
function PPMe(A,mo,ml,done,rate=a=>a){
	ml&=65535;
	var sync="function"!=typeof rate,a=0,m=1,o=2,z=A.length,
		L=0,R=-1>>>0,B=ml&255,C=0, // coder
		T=makeTrie(1024),ROOT=T.ROOT,X=T.X,
		O=[mo&=255,ml>>8],
		Cx=new Int32Array(mo+=2);
	Cx[0]=ROOT;ml=4e9/ml;
	done=done||function(O){return O};rate=rate||function(){};
	function F(){
		var c,e,f,i,l,n,p,q,r,s,t,
			NS=T.NS,NE=T.NE,NP=T.NP,NN=T.NN,
			E=[],b=sync?-1:4095,d=sync?1/0:+new Date;
		for(rate(a,z);a&b||new Date-d<200;E.length=0){
			if(m>mo)m=mo;c=a<z?A[a]:256;
			for(i=m;;){
				if(i){
					n=Cx[--i];q=NN[n];p=q>>1;
					if(q&1){
						NE[n]++,ml--;
						p=T.alloc(A[p],p+1);
						if(T.a)T.a=0,NN=T.NN,NS=T.NS,NP=T.NP,NE=T.NE;
						NN[n]=p<<1
					}
					for(q=l=t=0;p;p=NP[p])if(!E[(s=NS[p])&255]){f=s>>8;(s&255)===c&&(l=f,r=t,q=p);t+=f}
					if(!t)continue;e=NE[n]+1;e=e>>8||e;
					if(!l)l=e,r=t;t+=e}
				else for(r=0,q=-1,l=1,e=t=257;e;)E[--e]?t--:e<c&&++r;
				R=R/t>>>0;L+=R*r;
				for(R*=l;R<16777216;R*=256,L=L<<8>>>0)
					if(L>>24^-1)
						for(l=0xffffffff<L,O[o++]=255&l+B,B=L>>>24,l+=255;C;C--)O[o++]=255&l;
					else++C;
				if(q){
					if(q>0&&(NS[q]+=512)>0xfdff)
						for(e=0,p=NN[n]>>1;p;p=r)
							r=NP[p],f=NS[p],NS[p]=f=f>>9<<8|f&255,
							f>255?e=p:NE[e?NP[e]=r:NN[n]=r<<1,n]--;//unlink 0 count node
					break
				}
				for(p=NN[n]>>1;p;p=NP[p])E[NS[p]&255]=1
			}
			if(++a>z){
				for(a=5;a--;L=L<<8>>>0)
					if(L>>24^-1)
						for(l=0xffffffff<L,O[o++]=255&l+B,B=L>>>24,l+=255;C;C--)O[o++]=255&l;
					else++C;
				return done(O,z,o)
			}
			// deepen rest context
			for(;i;){n=Cx[--i];p=NN[n];
				if(p&1){
					NE[n]++,ml--;
					p=T.alloc(A[p>>=1],p+1);
					if(T.a)T.a=0,NN=T.NN,NS=T.NS,NP=T.NP,NE=T.NE;
					NN[n]=p<<1
				}
			}
			// update tree
			up:for(i=++m;--i;Cx[i]=p){
				n=Cx[i-1];e=0;
				for(p=NN[n]>>1;p;p=NP[e=p])
					if((NS[p]&255)===c){
						f=NP[p];e?NP[e]=f:NN[n]=f<<1;
						NP[p]=NN[n]>>1;NN[n]=p<<1;
						continue up
					}
				if(ml>0){
					t=NN[n];
					p=T.alloc(c,a);
					if(T.a)T.a=0,NN=T.NN,NS=T.NS,NP=T.NP,NE=T.NE;
					NN[n]=p<<1,NE[n]++,ml--;
					NP[p]=t>>1
				}else p=X;
				m=i
			}
		}setTimeout(F)
	}return F()
}
function PPMd(A,done,rate=a=>a){
	for(var sync="function"!=typeof rate,a=3,m=1,o=5,z=A.length,mo=A[0]+2,ml=4e9/(A[1]<<8|A[2]),
		L,R=-1>>>0,E=[],O=[], // coder
		T=makeTrie(1<<16),ROOT=T.ROOT,X=T.X,
		Cx=new Int32Array(mo);--o;)L=(L<<8|A[a++])>>>0;
	Cx[0]=ROOT;
	done=done||function(O){return O};rate=rate||function(){};
	function F(){
		var c,e,f,i,n,p,r,t,
			NS=T.NS,NE=T.NE,NP=T.NP,NN=T.NN,
			b=sync?-1:4095,d=sync?1/0:+new Date;
		for(rate(a,z);a&b||new Date-d<200;E.length=0){
			if(m>mo)m=mo;
			for(i=m;;){
				if(i){
					n=Cx[--i];q=NN[n];p=q>>1;
					if(q&1){
						NE[n]++,ml--;
						p=T.alloc(O[p],p+1);
						if(T.a)T.a=0,NN=T.NN,NS=T.NS,NP=T.NP,NE=T.NE;
						NN[n]=p<<1
					}
					for(t=0;p;p=NP[p])if(!E[NS[p]&255])t+=NS[p]>>8;
					if(!t)continue;e=NE[n]+1;e=e>>8||e;
					r=L/(R=R/(t+e)>>>0)|0;
					if(t>r)for(t=0,p=NN[n]>>1;c=NS[p],t+(f=c>>8&-!E[c&=255])<=r;p=NP[p])t+=f;
					else for(c=256,f=e,p=NN[n]>>1;p;p=NP[p])E[NS[p]&255]=1
				}else{c=r=t=-1;
					for(f in E)r++;
					for(r=L/(R=R/(256-r)>>>0)>>>0;E[++c]||r>++t;);
					if(c>255)return done(O,z,o);f=1
				}
				for(L-=R*t,R*=f;R<16777216;R*=256)L=(L<<8|A[a++])>>>0;
				if(c<256){
					if(p&&(NS[p]+=512)>0xfdff)
						for(e=0,p=NN[n]>>1;p;p=r)
							r=NP[p],f=NS[p],NS[p]=f=f>>9<<8|f&255,
							f>255?e=p:NE[e?NP[e]=r:NN[n]=r<<1,n]--;
					break
				}
			}
			for(O[o++]=c;i;){n=Cx[--i];p=NN[n];
				if(p&1){
					NE[n]++,ml--;
					p=T.alloc(O[p>>=1],p+1);
					if(T.a)T.a=0,NN=T.NN,NS=T.NS,NP=T.NP,NE=T.NE;
					NN[n]=p<<1
				}
			}
			up:for(i=++m;--i;Cx[i]=p){
				n=Cx[i-1];e=0;
				for(p=NN[n]>>1;p;p=NP[e=p])
					if((NS[p]&255)===c){
						f=NP[p];e?NP[e]=f:NN[n]=f<<1;
						NP[p]=NN[n]>>1;NN[n]=p<<1;
						continue up
					}
				if(ml>0){
					t=NN[n];
					p=T.alloc(c,o);
					if(T.a)T.a=0,NN=T.NN,NS=T.NS,NP=T.NP,NE=T.NE;
					NN[n]=p<<1,NE[n]++,ml--;
					NP[p]=t>>1
				}else p=X;
				m=i
			}
		}setTimeout(F)
	}return F()
}