12 - zhiqiuyuan's blog

今日目标：优化原始实现(msbfs series & baseline)然后operf看瓶颈；（有时间的话，设计和实现新的直接实现）

上午

1
- code prec&succ 复用
- debug
2
- debug
- see effect of share
3
- operf下看看情况
- code检查培养方案对不对
4
- code prec&succ opt for msbfs

下午

1
- run新的msbfs prec&succ on wiki
- merge的prec&succ design&code
2
- code merge prec&succ opt
3
- code merge prec&succ opt
4
- debug above (msbfs_merge, msbfs_1step2)
5
- debug above (msbfs_merge, msbfs_1step2)
- run and operf
  - 根据operf的结果，只有3%左右的时间是记录反向边和inner edge的前驱的，这是不是意味着idea“传送”没啥用？
    - idea传送可能可以优化的part在下面用注释标注了

76        3.8618  main                     MsbfsMerge::OneBatch<BuiltinUIntWrapper<unsigned long> >::path(bool)
  227      31.7927  main                     MsbfsMerge::OneBatch<BuiltinUIntWrapper<unsigned long> >::init_static_data(unsigned int, unsigned long)
  82       11.4846  main                     BuiltinUIntWrapper<unsigned long>::operator|=(BuiltinUIntWrapper<unsigned long> const&)
记录prec,succ（这是在正常CSR邻居中的前驱）
  76       10.6443  main                     MsbfsMerge::OneBatch<BuiltinUIntWrapper<unsigned long> >::path(bool) [self]
  76       10.6443  main                     MsbfsMerge::OneBatch<BuiltinUIntWrapper<unsigned long> >::path(bool)
// 可能可以减少搜索层数（因为传送了则是一下走了几层；但是这个依赖于p1和p2有抵消交集的点对的占比）
// 比特操作相应得可能减少
  50        7.0028  main                     BuiltinUIntWrapper<unsigned long>::operator&(BuiltinUIntWrapper<unsigned long> const&) const
  39        5.4622  main                     Neighbors<BuiltinUIntWrapper<unsigned long> >::Neighbors(Graph&, unsigned int, BuiltinUIntWrapper<unsigned long> const&, unsigned int, bool, unsigned int*, GraphUpdate<BuiltinUIntWrapper<unsigned long> > const*)
// 获取邻居操作可能更快
  33        4.6218  main                     BuiltinUIntWrapper<unsigned long>::andnot(BuiltinUIntWrapper<unsigned long> const&)
  23        3.2213  main                     OneBatchMerge<BuiltinUIntWrapper<unsigned long> >::adjust_p1p2()
// 抵消p1p2可能更快
  22        3.0812  main                     BuiltinUIntWrapper<unsigned long>::zero_all()
  21        2.9412  main                     BuiltinUIntWrapper<unsigned long>::is_all_zero(unsigned int) const
  17        2.3810  main                     MsbfsMerge::OneBatch<BuiltinUIntWrapper<unsigned long> >::reverse_path1()
// 但是反向p1可能会更慢
  17        2.3810  main                     Neighbors<BuiltinUIntWrapper<unsigned long> >::next(BuiltinUIntWrapper<unsigned long>&, bool, unsigned int&&, Graph&&)
  13        1.8207  main                     std::unordered_map<unsigned int, std::unordered_map<unsigned int, BuiltinUIntWrapper<unsigned long>, std::hash<unsigned int>, std::equal_to<unsigned int>, std::allocator<std::pair<unsigned int const, BuiltinUIntWrapper<unsigned long> > > >, std::hash<unsigned int>, std::equal_to<unsigned int>, std::allocator<std::pair<unsigned int const, std::unordered_map<unsigned int, BuiltinUIntWrapper<unsigned long>, std::hash<unsigned int>, std::equal_to<unsigned int>, std::allocator<std::pair<unsigned int const, BuiltinUIntWrapper<unsigned long> > > > > > >::operator[](unsigned int const&)
记录add_prec,add_succ（这是不在正常CSR邻居中的前驱）
// 记录不在正常CSR邻居中的前驱可能会更快，但也可能更慢，因为可能记录了不必要的非正常CSR前驱
  8         1.1204  main                     std::unordered_map<unsigned int, BuiltinUIntWrapper<unsigned long>, std::hash<unsigned int>, std::equal_to<unsigned int>, std::allocator<std::pair<unsigned int const, BuiltinUIntWrapper<unsigned long> > > >::operator[](unsigned int const&)

晚上

1
- design&code direct impl
2
- code direct impl
  - 一些完全静不下心来想吃东西的小豹x 决定撤退先吃东西和跑步再看情况x