tree 265081436d881832a1c6f3f82152dc7d2f64d85a
parent 3ba497a9d915d48d4dbeca3f51281c5b5bd4bd1d
author Andrew Jeffery <andrew@aj.id.au> 1525745179 +0930
committer Andrew Jeffery <andrew@aj.id.au> 1526258298 +0930

pathtree: Cache keys in a flat dict for fast lookup

This knocks about a second off of the depth stress tests:

$ python -m obmc.utils.testpathtree
Depth tests:
        1: 5.18097305298
        2: 6.18765211105
        3: 7.3427259922
        4: 8.33903598785
        5: 9.55236506462
        6: 10.7165560722
        7: 12.1563079357
        8: 13.3570129871
        9: 14.7827298641
        10: 16.0967490673

Width tests:
        1: 1.20649981499
        2: 1.20889282227
        4: 1.20902085304
        8: 1.22063994408
        16: 1.22446990013
        32: 1.21649098396
        64: 1.21024799347
        128: 1.21360588074
        256: 1.22187900543
        512: 1.23233604431
        1024: 1.21607708931
        2048: 1.21069407463
        4096: 1.22389698029
        8192: 1.20828580856
        16384: 1.21290493011
        32768: 1.21552395821
        65536: 1.23201704025
        131072: 1.21459794044
        262144: 1.24190402031
        524288: 1.21342992783
        1048576: 1.21248602867

However, we get just over a 300% improvement in the host reboot
scenario, which is captured by some separate tools used to analyse the
PathTree's performance issues:

$ # Before
$ ./replay.py -n 1000 ptinit.log ptreboot.log
deep copy: 1000 iterations took 3.0744523939938517s
ops script: 1000 iterations took 10.03650910500437s
net: 1000 iterations took 6.9620567110105185s
$ # After
$ ./replay.py -n 1000 ptinit.log ptreboot.log
deep copy: 1000 iterations took 6.784729664999759s
ops script: 1000 iterations took 9.0453162470003s
net: 1000 iterations took 2.260586582000542s

Change-Id: I6826b99950fa1561d292908c4ffff1137ecaa1bc
Signed-off-by: Andrew Jeffery <andrew@aj.id.au>