18

昨天搞定了单线程优化（虽然还是没有达标），并写完和调试了多线程，但是多线程比单线程慢
今日目标：解决多线程比单线程慢的问题，尽量优化到达标（奇迹了）

上午

• 1
  • th=1和tsk划分测试
    • tsk划分是原因！
  • th=32测试多种tsk sz，因为毕竟还是比单线程快不了很多
• 2
  • operf 32th 2f
    • ohno 没有什么可以改进的结论发现
  • 把时间测量撤掉（反正看operf看的出来+多线程累加不准）
  • code multiple run
• 3
  • debug multiple run
  • 1000x: 一种最快的tsk sz测不同th
• 4(half)
  • 对比下之前单线程和现在多线程的结果：只快了一点点
    • operf看看
  • 推测原因可能和缓存竞争有关系，operf一下单线程的
  • 对比1th_1f和原先的单线程的operf结果，看时间占比，找原因
    • 发现占比没有很大区别，区别应该是来自于对static数据的访问
    • 初始化static数据比原先普通数据成员要慢
• 在25000上跑th和f的组合，看看结果
  现在的现象是：

# 之前的单线程：
compute 167,501us
    init_bfs        595us
    bfs     2,323us
    collect_risky_spine     33,821us
# 1th_1f：
get_cc  31,085us
solve   213,093us 
# 4th_2f:
get_cc  13,606us
solve   153,839us
# 8th_2f:
get_cc  9,283us
solve   139,048us
# 32th_2f:
get_cc  7,600us
solve   183,930us

1th_1f比之前的单线程慢一点，可能慢很多
8th_2f比1th_1f加速较少

下午

• 1
  • 看25000 gap有多大
    现象：
    solve: 1th->4th，加速两倍，4th达峰值
    color: 1th->20th，始终在加速
    1th-20th 1f-3f最快的组合：决定color用32th，solve用4th

[4th 2f] 
compute 4,660,916us
        get_cc  597,641us
        solve   4,063,274us

[8th 1f]
compute 4,695,444us
        get_cc  459,420us
        solve   4,236,022us
        
[8th 2f]
compute 4,692,330us
        get_cc  480,149us
        solve   4,212,180us
        
[12th 1f]
compute 4,622,508us
        get_cc  439,691us
        solve   4,182,815us
        
[20th 1f]
compute 4,678,752us
        get_cc  394,137us
        solve   4,284,613us

- 从case2tree中获得启示，重新思考算法中

• 2
  • 从case2tree中获得启示，重新思考算法中
  • 想出了优化版的算法！耶！赶紧写！
    • 这告诉我：从复杂度角度思考算法优化（我是从现在的算法和可以达标的算法，它们访问的边数到底分别有多少）
  • code above
• 3
  • debug
• 4
  • debug

晚上

目标：operf，尽量优化呀！因为复杂度其实大概只是case2tree的两倍，所以应该可以400拿下

• 1
  • operf opt
• 2
  • operf opt
• 3
  • operf opt
• 4
  • operf opt
    好棒！是谁从4000us优化到250us我不说[旺柴]