tek1​/oldlog​/001 :: OSASK計画

旧 tek1​/comp^[1]の内容 ^[2]

tek1^[3]の続き ^[4]

• (by K^[5], 2004.06.23)
• tek1～tek4の圧縮展開比較表
  • MLに書いたら読みにくくなってきたのでこっちにまとめ

• （註）tek1～tek3の意味付けが旧版とは違うので、このページの下の説明で確認すること。
  • たくさんの形式があってよく分からない人へ：tek1～tek4は今のところベータ版であり、今理解できないならまだ理解しないほうがいいです。このページは、現在の開発状況を確認するためだけのものです。
    • もし現状を少しでも知りたいということであれば、とりあえずtek4が本命で、それ以外はオマケだという認識でいてください。

比較表 ^[6]

• サイズ （num128以外では、tek1～4とstk1～4はほぼ同じなので、stk1～4は省略）

  無圧縮		tek0	tek1	tek2	tek3	tek4	lh7	gzip	bzip2	LZMA	LZO	rk
  hellok1	272	128	144	135	126		205	143	166	121	193	208
  zero4k	4096	27	25	25	27		86	49	43	39	91	100
  zero64k	65536	28	27	29	30		117	108	43	90	422	108
  bim2binc	53792	15019	17166	16323	14424		14181	14029	12903	12787	16015	11608
  kdun00b	655360	46246	49855	46794	41432		45520	44589	47306	34517	52148	36736
  osaskgo	1973741	1149662	1274931	1172344	1087673		1099064	1111648	1047411	953821	1177820	909824
  osask.bmp	393334	6389	7740	7135	5633		6467	6341	4906	4779	8618	4344
  num128	131072	106953					118548	124645	25542	84237	131136	1192

• 規格化指数

  無圧縮		tek0	stk1	tek1	stk2	tek2	stk3	tek3	stk4	tek4	lh7	gzip	bzip2	LZMA	LZO	rk
  hellok1	224.8	105.8	119.0	119.0	111.6	111.6	104.1	104.1			169.4	118.2	137.2	100.0	159.5	171.9
  zero4k	16384	108.0	100.0	100.0	100.0	100.0	108.0	108.0			344.0	196.0	172.0	156.0	364.0	400.0
  zero64k	242726	103.7	100.0	100.0	107.4	107.4	111.1	111.1			433.3	400.0	159.3	333.3	1563	400.0
  bim2binc	463.4	129.4	147.9	147.9	140.6	140.6	124.3	124.3	121.7?		122.2	120.9	111.2	110.2	138.0	100.0
  kdun00b	1899	134.0	144.4	144.4	135.6	135.6	120.0	120.0	117.8?		131.9	129.2	137.1	100.0	151.1	106.4
  osaskgo	216.9	126.4	140.1	140.1	128.9	128.9	119.5	119.5	?		120.8	122.2	115.1	104.8	129.5	100.0
  osask.bmp	9055	147.0	178.2	178.2	164.2	164.2	129.7	129.7	120.4?		148.9	146.0	112.9	110.0	198.4	100.0
  num128	327680	267383									296370	311613	63855	210593	32840	2980
  (max)		147.0	178.2	178.2	164.2	164.2	129.7	129.7			148.9	146.0	137.1	110.2	198.4	106.4

  • (max)は、bim2binc、kdun00b、osaskgo、osask.bmpのみ対象（他はあまりにtek系が得意なため除外）
  • (max)で判断すると安定して圧縮率のよいものは以下の順になる。

    rk	LZMA	tek4	stk4	tek3	stk3	bzip2	gzip	tek0	lh7	tek2	stk2	tek1	stk1	LZO
    106.4	110.2			129.7	129.7	137.1	146.0	147.0	148.9	164.2	164.2	178.2	178.2	198.4

  • ↑これは主にosask.bmpの結果で決まっているともいえるので、参考までにosask.bmpを除いて集計すると以下のようになる。
    • しかし、「汎用圧縮符号」としては弱点があるというのは好ましくない。そしてosask.bmpの内容は多くの符号の共通の弱点を突く内容なのだろう。

      rk	LZMA	tek4	stk4	tek3	stk3	gzip	lh7	tek0	bzip2	tek2	stk2	tek1	stk1	LZO
      106.4	110.2			124.3	124.3	129.2	131.9	134.0	137.1	140.6	140.6	147.8	147.8	151.1

    • bzip2が落ちてlh7が少し回復する以外は、順位そのものの傾向は変わらない。
• tar+tek4（.tar.tk/.ttk）

  tar		ttk	lh7	tgz	tbz	tar.lzma
  bim2bi4j	266725		902616	84581	72747	65314
  osat45i	759808		532093	528923	547131	503545
  cantrbry[7]	2821120		714769	735997	568667	483768

  • ディスクイメージへの強さが、tarへの強さにつながったのかも？
  • ロングファイルネーム対応のSF16ができるまで.img.tk(.itk)は不便だろうから、とりあえず.tar.tk(.ttk)で。
  • cantrbryはよく分からないけど有名な圧縮対象のようです。
    • http://www.emit.jp/gca/cmptest.html^[8]
    • http://compression.ca/act-canterbury.html^[9]

• 展開速度
  • 参考：EPIA-VE5000でのosaskgoの展開速度

    meth.	deco.time	t-idx	size	vs rk	score	言語	備考
    tek1	0.15[sec]	1.0	1274931	140.1	40.1	ASKA	Cでは0.18[sec]
    LZO	0.18[sec]	1.3	1177820	129.5	38.4	?	←おそらくasm
    tek2	0.18[sec]	1.3	1172344	128.9	37.6	ASKA	Cでは0.27[sec]
    tek3	0.51[sec]	4.6	1087673	119.5	89.7	C	ASKA版開発中
    tek4						C
    lh7	1.04[sec]	9.9	1099064	120.8	205.9	?
    gzip	1.24[sec]	11.9	1111684	122.2	264.2	?
    tek0	1.39[sec]	13.4	1149662	126.4	353.8	C
    LZMA	1.42[sec]	13.7	953821	104.8	65.8	C
    bzip2	2.52[sec]	24.7	1047411	115.1	373.0	?
    GCA	4.91[sec]	48.6	1002311	110.2	495.7	?

  • いずれも圧縮データを読み込む時間がデコードタイムに加算されてしまっています。
    • したがって、tek1やLZOは小さくない誤差を含んでいる可能性が高い。
    • 試しに1274931バイトのファイルリードだけやらせてみたら0.05[sec]だった。
  • 「言語」はこの展開速度の測定につかったデコードルーチンの記述言語です。
  • たぶんLZOは既にアセンブラ化されていると思います（そうでないとこの圧縮率でこの速さは出ない）。bzip2はアセンブラ化されているかどうかは僕には想像がつきませんが、ブロックソート法では圧縮率の代償として展開速度低下があるという傾向はつかめると思います。
  • GCA、gzip、lh7に関しては展開ルーチンの記述言語は不明です。
  • t-idx = (time - 0.05) x 10
  • score = (t-idx) x (vs_rk - 100)
    • なんとなく計算してみたくなったので（笑）。小さければ小さいほど圧縮率と展開速度のバランスに優れていることを示していると思う。

• • 補足（履歴）
    • 2004.06.23　　tek1～tek3の全面刷新により、いったん出直し。
    • 2004.06.24　　tek2の情報を記載
    • 2004.06.26　　tek2の情報を改定
    • 2004.06.28　　tek3の情報を記載
    • 2004.07.03　　kdun00bの規格化指数を計算ミスしていたので修正

圧縮形式の説明 ^[10]

• 無圧縮
• tek0
  • 引退間近の圧縮形式。今までごくろうさま。旧tek1～3の祖。
• tek1 --- 全てバイトストリーム、主なライバル：LZO
  • LZOよりも速い展開速度の圧縮形式。圧縮率はやや劣る場合もあるが、得意不得意の差は小さく、その点でLZOよりも扱いやすい（旧tek3の子孫）。
• tek2 --- ほとんどバイトストリーム・一部ビットストリーム、主なライバル：LZO
  • tek1の7割くらいの展開速度の圧縮形式。圧縮率ではLZOをほぼ完全に凌駕し、展開速度の点ではLZOと同等（旧tek3の子孫）。
• tek3 --- ほとんどビットストリーム・一部バイトストリーム、主なライバル：tek0
  • tek2のさらに7割くらいの展開速度で、圧縮率を結構追求したもの（旧tek1の子孫）。これはtek0よりも圧縮率がよい。ひょっとすると既にこの段階でlh7よりもいい？
• tek4 --- 全てビットストリーム、主なライバル：lh7、gzip、bzip2など （デフォルト推奨）
  • tek3のさらに7割くらいの展開速度で、圧縮率をかなり追求したもの（旧tek2の子孫）。lh7やgzipよりも高い圧縮率で、ものによってはLZMAにかなり近い圧縮率になる（予定）。tek1～4の中では一番展開速度が遅いが、それでもtek0やLZMAの2倍くらいは速い。
• stk1
  • tek1でBS:0かつ補助バッファを使わないもの（subset-tek1）
• stk2
  • tek2でBS:0かつ補助バッファを使わないもの（subset-tek2）
• stk3
  • tek3でBS:0かつ補助バッファを使わないもの（subset-tek3）
• lh7
• gzip
• bzip2
• LZMA
• LZO
• rk

• 展開ルーチンのコンパクトさにこだわる人向けの情報
  • stk1の展開ルーチンは100行（dtk1s.c）
  • stk2の展開ルーチンは161行（dtk2s.c） --- サイズ優先で最適化したら154行になる。
  • stk3の展開ルーチンは401行（dtk3s.c）
  • stk4の展開ルーチンは490行？（dtk4s.c）
  • 展開速度はフルセット版もサブセット版もほぼ同じ
  • （参考）
    • l2d3の展開ルーチンは107行（マルチスレッド非対応）
    • tek0の展開ルーチンは191行（マルチスレッド非対応）
  • C言語の行数で考えるのは、単にC言語がビットストリームを効率よく記述できないという言語の欠陥を示しているだけのような気がしてきたので、ASKAで作った展開ライブラリのバイト数も併記します。これこそまさにアルゴリズムの規模を反映しているといえるでしょう。
    • なおこれでも、どちらかといえばASKA版はサイズよりも展開速度優先で書かれています。
  • stk1の展開ルーチンは270バイト（dtk1s.ask）
  • stk2の展開ルーチンは531バイト（dtk2s.ask）

過去ログ ^[11]

• tek1​/oldlog​/000^[12]

こめんと欄 ^[13]

• これだけ見てデコードルーチンの簡単さ、圧縮率を総合評価するとtek0が圧勝じゃない？こんな結果でいいのか？ -- 名無しさん^[14] 2004-06-24 (木) 17:15:00
• （tek1^[3]系のページは議論向きではないので、こういう意見は是非impressions^[15]やroom​/000^[16]にお願いします。） -- K^[5] 2004-06-24 (木) 17:29:36
• tek1～tek3の名称が展開速度の順で再整理されたってことですよね?(これに関して記事を書くかもしれないので確認) -- Zakky 2004-06-24 (木) 18:41:19
• はいそうです。このページは数日後にリリースされるbim2bin4の告知の際に投稿するOSASK-MLの内容を（結果的に先取りして）書いています。ここでは詳細なデータばかりでなぜ再整理するのかの理由などがありませんが、それはMLの本文のほうに書く予定なので、ご了承ください。＞Zakkyさん -- K^[5] 2004-06-24 (木) 19:32:24