kobo電子書籍リーダーを微妙に速くする (sqlite編)

# 概要
koboの電子書籍リーダーは，CPUにARMのCortex-A8やCortex-A9を採用しています．動作クロックも低く，動作はもっさりしています．

このもっさり動作を改善するために，CPUが持つ機能をフルに活用すべく改良を試みます．

具体的には，オープンソースのソフトウエアをより最適化が効くようにコードを書き換えたり，コンパイルオプションを変更してコンパイルすることで実行速度を上げる，というものです．

同様の試みとして，その昔[libjpeg-turbo](http://libjpeg-turbo.virtualgl.org/)に差し替えて使うのが流行りました．後に標準ファームウエアに採用されるようになり，意味をなさなくなりましたけれども(全くの余談ですが，標準ファームウエアのバージョンアップでABIが変更になり，差し替え後に起動しなくなるなんて事故がありました)．

今回はやや導入のハードルが高い(後述)ですが，[sqlite](https://sqlite.org/)を題材にしてみます．koboに組み込まれているsqliteは，qt-5.2.1に同梱されている3.7.17ですが，これをもう少し新しいものに変えてみましょう．

また，本稿では具体的な手順は割愛し，コード書き換えのポイントを示します．お好きな開発ホスト，コンパイル環境を用意してください．

当方はVirtualBoxでUbuntuを動作させ，gcc-arm-linux-gnueabihfやclangを用いてコンパイルしています．

# コード書き換えのポイント
最初に申し上げておきますと，プログラミング言語の標準仕様で表現できる範囲のコードにおいては，概ね最適化はコンパイラに任せるのがよいです．

「それだとコードを書き換える必要がないじゃないか」と考えるのが自然なわけですが，実はアセンブラレベルではプログラミング言語の標準仕様で表現できない便利な命令が色々あります．

今回は，その中のエンディアン変換命令について触れます．

# sqliteにおけるエンディアン変換
sqliteのデータベースファイルは，バイトオーダーに依存しない形式になっています．

これはつまり，ビッグエンディアンの処理系で作成したデータベースファイルは，リトルエンディアンの処理系にも使いまわせるということです．こういう形式の場合，概ねデータ自体はビッグエンディアン形式に統一しており，リトルエンディアンの処理系では頻繁にエンディアン変換処理を行うことになります．

ネットワーク通信のコードを書いたことがある方には，`htonl()`や`ntohl()`に相当する処理，と言えば理解が早まるでしょうか．

さて，このエンディアン変換をC言語の標準仕様の範囲で実装する場合は，概ね以下のようになるでしょう．

    SQLITE_PRIVATE u32 sqlite3Get4byte(const u8 *p){
      return (p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
    }
 これを`-march=armv7-a -mthumb -O2`オプションを付加してコンパイルすると，以下のようになります．

    00000000 <sqlite3Get4byte>:
       0:   7843            ldrb    r3, [r0, #1]
       2:   7801            ldrb    r1, [r0, #0]
       4:   78c2            ldrb    r2, [r0, #3]
       6:   041b            lsls    r3, r3, #16
       8:   7880            ldrb    r0, [r0, #2]
       a:   ea43 6301       orr.w   r3, r3, r1, lsl #24
       e:   4313            orrs    r3, r2
      10:   ea43 2000       orr.w   r0, r3, r0, lsl #8
      14:   4770            bx      lr
      16:   bf00            nop
バイトロードを4回，ビットシフトや論理和を駆使して`r0`に結果を入れてリターンしています．`r1`から`r3`まで汎用レジスタを3つも使用し，命令数が9というコードが出力されていることがわかります(実際はインライン展開されると思うので，もうちょっと違った出力になる可能性があります)．
 
 ところがARMにはバイト序列を反転する`rev`命令があります．Cのコードで書きやすくするため，gccのコンパイラ拡張を用いると以下のように実装できます．

    SQLITE_PRIVATE u32 sqlite3Get4byte(const u8 *p){
      const u32 *q = (const u32*)p;
      return __builtin_bswap32(*q);
    }
 
これを同様のオプションを付加してコンパイルすると，以下のようになります． 

    00000000 <sqlite3Get4byte>:
       0:   7800            ldr     r0, [r0, #0]
       2:   ba00            rev     r0, r0
       4:   4770            bx      lr
       8:   bf00            nop

ワードロードを1回実行，同一の汎用レジスタ内でバイト序列を反転し，リターンするだけになりました．命令数は1/3，一時的に使用する汎用レジスタはゼロという非常に効率の良いコードが出力されるようになりました．

ところで最近のsqliteでは少々改良(? 後述)され，以下のように実装されています．

    SQLITE_PRIVATE u32 sqlite3Get4byte(const u8 *p){
    #if SQLITE_BYTEORDER==4321
      u32 x;
      memcpy(&x,p,4);
      return x;
    #elif SQLITE_BYTEORDER==1234 && !defined(SQLITE_DISABLE_INTRINSIC) \
        && defined(__GNUC__) && GCC_VERSION>=4003000
      u32 x;
      memcpy(&x,p,4);
      return __builtin_bswap32(x);
    #elif SQLITE_BYTEORDER==1234 && !defined(SQLITE_DISABLE_INTRINSIC) \
        && defined(_MSC_VER) && _MSC_VER>=1300
      u32 x;
      memcpy(&x,p,4);
      return _byteswap_ulong(x);
    #else
      testcase( p[0]&0x80 );
      return ((unsigned)p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
    #endif
    }

`__builtin_bswap32()`の前に，`memcpy()`が書かれています．これはCPUがワード幅(32bit)のデータアクセスをするときに，対象になるアドレスがワード境界であることを保証するための実装です．

これはワード幅のデータアクセスをするときはアドレスもワード境界，ハーフワード幅のデータアクセスをするときにはアドレスもハーフワード境界の必要があるCPUがあるからです(そういったCPUでは，これを守らないと例外が発生してしまいます)．

と思っていたのですが，コンパイルしてみると以下のようになりました．

    00000000 <sqlite3Get4byte>:
        0:   6800            ldr     r0, [r0, #0]
        2:   b082            sub     sp, #8
        4:   9001            str     r0, [sp, #4]
        6:   9801            ldr     r0, [sp, #4]
        8:   ba00            rev     r0, r0
        a:   b002            add     sp, #8
        c:   4770            bx      lr
        e:   bf00            nop

全くお構いなしにワードロード命令を使いやがってます．コンパイラがlittle endianのARM CPUはワード境界を考慮しないアクセスができることを知っていて，気を利かせてくれたのかもしれません．しかも`memcpy()`が意味もなくスタックに退避という無駄処理に化けてしまっています．困ったものです．

これまではコンパイラにgccを使用していましたが，ここでclangを使用してみると，恐らく実装者が期待したであろうコードを出してきます．

    sqlite3Get4byte:
            ldrb    r1, [r0]
            ldrb    r2, [r0, #1]
            ldrb    r3, [r0, #2]
            ldrb    r0, [r0, #3]
            orr     r1, r1, r2, lsl #8
            orr     r0, r3, r0, lsl #8
            orr     r0, r1, r0, lsl #16
            rev     r0, r0
            bx      lr

バイト序列を反転する命令を使用しているものの，これでは最適化前の実装と差がありません．

そんなわけで，最も最適な実装は見えたかと思います．そのようにコードを書き換えてコンパイルしておきましょう．

# ハードルについて
最初の方に「sqliteはハードルが高い」と書きました．

これはsqliteが単体でshared libraryとしてインストールされているのではなく，qt-5.2.1に組み込まれてしまっているからです．ですからsqliteを差し替えられるようにするには，qt-5.2.1のコンフィグレーションを変更してコンパイルし直さなければいけません．

慣れている人なら`-system-sqlite`を付与してコンフィグレーションしてコンパイル，できたsqldriverを差し替えてsqliteのshared libraryを入れる，で通じるかと思います．

# 終わりに
koboの電子書籍リーダーを快適に使うべく，CPUが持つ機能をフルに活用するためにオープンソースのソフトウエアを再コンパイルする例を示しました．

近年ではCPUのパワー不足は時やお金が解決してくれる風潮がありますが，電子書籍リーダーのような限られたハードウェア性能の製品においては，まだまだ工夫の余地があります．C言語の仕様の範囲では表現不可能な機能を多く備えているCPUがありますので，ニーモニック表とか眺めるのも良いかと思います．コンパイラ拡張のマニュアルから見てみるのが早いかもしれません．

とはいえ，汎用的に活用できる事例とは思えないので，労力や時間，お金のバランスを考えて手段を選択するのがよいでしょう．

# 参考文献
* [Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc-8.2.0/gcc/Other-Builtins.html)
* [ARM and Thumb2 Instruction Set Quick Reference Card](http://infocenter.arm.com/help/topic/com.arm.doc.qrc0001l/QRC0001_UAL.pdf)