memo0010

Kの開発メモ #0010

• (by K, 2014.09.16)
• ここは川合の開発の進捗などをレポートするところです。

2014.09.16 Tue

• ひさしぶりの近況を。
• フロントエンドコードをもっと小さくしたくて、ついにレンジコーダに手を出しました。これをやると、もうバイナリエディタで内容を「読む」のは非常に難しくなってしまうのですが、しかし究極のサイズというものがどういうものなのか見たいということもあって、せっせと頑張っています。

2014.10.01 Wed

• このサイトのトップページのアクセス数がすごいです。たぶん定期的にチェックしてくれている人が結構いるのだと思います。その期待に応えたいです。今年度はキャンプ後も細々と継続的にやっていきますので、少しずつ前進できると思います！

2015.11.13 Fri

• rev3の構想があるのですが、まだ着手できていません。
• で、rev3にとりかかると大変なので、まずはrev2のままで、簡単にできそうなことはやってしまうことにします。

• 先日、OSECPUアプリで円周率の計算プログラムを書いてみました。速度よりもサイズを重視して作ってみたところ、31バイトになりました。

  05 E2 27 88 17 D7 84 00 02 11 1A 60 03 03 59 70
  00 32 4A 21 D6 A0 45 10 60 20 01 46 89 0A 20
  
  0000: 05e2                            バイナリシグネチャ
  0004: 2_78817d78400_0                 R00 = 400000000;
  0011: 2_1_1                           R01 = 1;
  0014: 1                           label:
  0015: a6_0_0_3                        R03 = R00 / R01;
  001a: 0_3_5                           R02 += R03;
  001d: 97_0_0                          R00 = 0 - R00;
  0021: 0_3_2                           R01 += 2;
  0024: 4_a2_1_d6a_0                    if (R01 < 0x8000000) goto label;
  002c: 4_5_1_0_6_0200_1_4_6_89_0_A2    R02を10進数でコンソールに出力

• このプログラムを書いて思ったのは、まず数値の出力にかなりサイズを食ってしまっているということです。なんと8.5バイトも使っています。全体が30.5バイトなので、28%も使っていることになります。複雑な書式とかは使えなくていいから、とにかく単純なやつがあればいいのにと思いました。仮に2バイト命令を新設すれば、それだけで24バイトまで小さくできます。
• また、定数400000000の扱いも不満です。10のベキ数をうまく表現できないかなと考えています。仮にこれが2.5バイトで書ければ3バイト減らせます。これで21バイトまでいけます。

• ということでVM側を対応させました。以下の21バイトのバイナリが手元では動いています。

  05 E2 2D 5F 45 02 11 1A 60 03 03 59 70 00 32 4A
  21 D6 A0 DF D2
  
  0000: 05e2                            バイナリシグネチャ
  0004: 2_d5f45_0                       R00 = 400000000;
  000b: 2_1_1                           R01 = 1;
  000e: 1                           label:
  000f: a6_0_0_3                        R03 = R00 / R01;
  0014: 0_3_5                           R02 += R03;
  0017: 97_0_0                          R00 = 0 - R00;
  001b: 0_3_2                           R01 += 2;
  001e: 4_a2_1_d6a_0                    if (R01 < 0x8000000) goto label;
  0026: dfd_2                           R02を10進数でコンソールに出力

• ついでにこんなのもやりました。0から100までをスペースで区切って表示。

  05 E2 6C 65 0D FD 05 16 40 (9バイト)
  
  0 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

• 区切りのスペースを省略してもいいのならもっと小さくできます。

  05 E2 6C 65 0D FD (6バイト)
  
  0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

• 0から100までの和を計算。

  05 E2 6C 65 00 15 87 DF D1 (9バイト)
  
  5050

2015.11.14 Sat

• フロントエンドコードのプレフィクス4について考える。
  • プレフィクス4がもしなかったらこうなる。
    • opeが4ビット：7個（0～6）
    • opeが8ビット：57個（87～bf）
    • opeが12ビット：448個（cc0～dff）
  • プレフィクス4があるとこうなる（rev1, rev2）。
    • opeが4ビット：6個（0～3, 5～6）
    • opeが8ビット：63個（57+6）
    • opeが12ビット：505個（448+57）
  • なるほど、4ビット命令をひとつ犠牲にした代わりに、8ビット命令を6個増やして、12ビット命令を57個増やしたわけか。
  • これを逆に考えれば、8ビット命令を6つ12ビット側に追い出すことにすれば、4ビット命令をもうひとつ増やすことができる。

2015.11.16 Mon

• for構文のcontinue周りを改良していたんだな。それに気づけなくて悩んでしまった。
  • continue0を使って解決。

• 円周率を求めるプログラムを少し改良しました。これで20バイトです。

  0000: 05e2                            バイナリシグネチャ
  0004: 2_1_0                           R00 = 1;
  0007: 2_d5f45_1                       R01 = 400000000;
  0014: 1                               do {
  0015: a6_1_1_3                            R03 = R01 / R00;
  001a: 0_3_5                               R02 += R03;
  001d: 97_3_0                              R01 = 0 - R01;
  0021: 0_0_2                               R00 += 2;
  0024: 4_a1_3_0_0                          if (R03 != 0) continue0;
  002a:                                 }
  002a: dfd_3                           R02を10進数でコンソールに出力

  • このプログラムの隠れたポイントは、もしR00～R03が256ビットで、かつデフォルトの精度が256ビットになっていれば、R01の初期値の400000000を大きくするだけで、求められる桁数を簡単に増加させられることです。ようするにこのプログラムで演算精度に関する情報を持っているのは、最初のR01だけなのです。

• 今まで、命令コード長さは、Kの勘だけで調整されてきました。これはまあ正しいこともあるのですが、間違うことだってあると思うのです。そこで、どんな命令がどのくらいの頻度で使われているのかの統計を取って、それで命令コードの長さを再検討したらいいのではないかと思いました。今はそれをやっています。

2015.11.19 Thu

• OSECPU-VMはアプリが非常に小さくなる傾向があります。まあ何をいまさらという感じですが。これをどのように役立てたらいいのかと考えてみました。
• 可逆圧縮の研究の世界では、主にデータの圧縮に主眼を置いて研究していると思います。これは多くのユーザが持っているファイルのうち、容量の大きなものは実行ファイルではなくデータファイルなので、データファイルが小さくできないと、総容量は少ししか改善しないからです。
• ということで、コードが小さくなることそのものは、あまり大きなインパクトはありません。
• しかし一方で、コードも結局は作業手順を記した「データ」であり、これが半減するなどというのは尋常なことではありません。
• たとえばwindows用に書かれた2560バイトのインベーダゲームを、現在知られているもっとも強力な圧縮プログラムで圧縮したとしても、430バイトにはなりません。まあたとえば1000バイトになったとしましょう。これと430バイトとの差は570バイトもあります。なぜ570バイトもの無駄が残ったのか、それを解明する必要があります。
• そしてその過程で、きっとコードの圧縮に限定されないような、つまりデータの圧縮にも応用可能な、有意義な圧縮テクニックを見いだせるはずです。
• それは今の私の仕事ではないですが、でも誰もやらないなら私がいつかやりたいと思っています。

• 今はとにかくコードを限界まで究極に小さくすることに集中します。

2015.11.26 Thu

• OSECPU-VMには api_malloc_initInt() という命令があって、これを使うとmallocした上に指定した初期値で領域を初期化してくれるのですが、なんとこれにバグがあることが判明しました。原因は内部コードで==と!=を間違えていたという非常に情けないもので、そのせいで最初の1要素のみ初期化されて、ループがうまく回っていませんでした。これも次のバージョンまでには直します。

こめんと欄

• この情報は有益！機会を見つけて反映させなければ。 https://twitter.com/takeutchkemeco/status/668435488219332608 -- K 2015-11-24 (火) 19:00:42