FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

ISSのバイナリロードが遅い問題を解決する (stl::vector, stl::set, stl::mapを試す)

ISSでxv6のバイナリをロードすると、ロードだけで現在1分近く掛っている。 現在、バイナリをロードするためのメモリには、0x1000バイト分のメモリブロックを、STLvectorを使って連結している。

github.com

class Memory
{
 private:
    std::vector <MemoryBlock *> m_memory_vec;  // memory table

    MemResult SearchMemTable (Addr_t addr, Byte_t *data);
    MemResult InsertMemTable (Addr_t addr, Word_t data);

 public:

    MemResult LoadMemByte  (Addr_t addr, Byte_t  *data);
    MemResult LoadMemHWord (Addr_t addr, HWord_t *data);
    MemResult LoadMemWord  (Addr_t addr, Word_t  *data);
    MemResult StoreMemByte  (Addr_t addr, Byte_t data);
    MemResult StoreMemHWord (Addr_t addr, HWord_t data);
    MemResult StoreMemWord  (Addr_t addr, Word_t data);
};

まずは、vectorで実装している現在のバージョンで速度を測ってみる。

$ time swimmer_mips --binfile kernel --debug --out debug.log --debug_func --debug_gvar  --init_pc 0x80100000

xv6...

real    1m29.578s
user    1m29.288s
sys     0m0.104s

遅いなあ。。。

次に、setを使ったのと、ブロックを探索する際にfind_if()を使って探索するようにしてみた。

MemResult Memory::InsertMemTable (Addr_t addr, Word_t data)
{
    // at first, traverse memory table and check memory region is already registered or not
    std::set<MemoryBlock *>::iterator it; // = m_memory_vec.begin ();
    if ((it = std::find_if (m_memory_vec.begin(),
                            m_memory_vec.end(),
                            MemoryBlock::LessA (addr))) != m_memory_vec.end()) {
        (*it)->WriteByte (addr - (*it)->GetBaseAddr(), static_cast<Byte_t>(data));
        return MemNoExcept;
    }

STL使うし、ちょっとは速くなるんじゃなかろうか。さっそくトライ。

time swimmer_mips --binfile kernel --debug --out debug.log --debug_func --debug_gvar  --init_pc 0x80100000

xv6...

real    1m39.708s
user    1m39.532s
sys     0m0.060s

遅くなった!

うーん、やはりfind_if()とはいえ、実際の比較関数は自分で書いている訳だし、あまり効果が無いのかな。 次は、mapを使って実装してみるしかない。mapの場合は、firstにベースアドレス、secondにメモリブロックへのポインタ、という感じかな。

github.com

探索は、通常通りfindを使うが、mapなのでハッシュで一発で探索できるはずだ。

MemResult Memory::SearchMemTable (Addr_t addr, Byte_t *data)
{
    std::map<Addr_t, MemoryBlock *>::iterator it;
    Addr_t baseaddr = addr & 0xFFFFF000ULL;
    if ((it = m_memory_vec.find (baseaddr)) != m_memory_vec.end()) {
        MemoryBlock *memory_block = it->second;
        *data = memory_block->ReadByte (static_cast<Addr_t>(addr - baseaddr));
        return MemNoExcept;
    } else {
        return MemNotDefined;
    }
}

これでどうだ!

$ time swimmer_mips --binfile kernel --debug --out debug.log --debug_func --debug_gvar  --init_pc 0x80100000

xv6...

real    0m3.228s
user    0m3.192s
sys     0m0.028s

mapに切り替えたので、格段に速くなった!

このときのパフォーマンスについて、gperftoolsで観測すると、

$ pprof ~/swimmer_riscv/build_mips/swimmer_mips /tmp/swimmer.log
Using local file /home/vagrant/swimmer_riscv/build_mips/swimmer_mips.
Using local file /tmp/swimmer.log.
Welcome to pprof!  For help, type 'help'.
(pprof) top
Total: 316 samples
      45  14.2%  14.2%      154  48.7% std::_Rb_tree::_M_lower_bound
      30   9.5%  23.7%       30   9.5% std::less::operator
      25   7.9%  31.6%       82  25.9% std::_Rb_tree::_S_key
      21   6.6%  38.3%       21   6.6% std::__addressof
      19   6.0%  44.3%       52  16.5% std::_Rb_tree::_S_value
      19   6.0%  50.3%       37  11.7% std::_Rb_tree_node::_M_valptr
      18   5.7%  56.0%       18   5.7% __gnu_cxx::__normal_iterator::__normal_iterator
      10   3.2%  59.2%       10   3.2% std::_Select1st::operator
       9   2.8%  62.0%       48  15.2% EnvBase::FindSymbol
       9   2.8%  64.9%       12   3.8% __gnu_cxx::__normal_iterator::operator++

だいぶ様相が変わってきたなあ。less::operatorとかが出てくるということは、やはりfind_if系で時間がかかっているのかな。