D12659: two new UDS structures

[Jaime Torres Amate]

jtamate created this revision.
jtamate added reviewers: dfaure, Frameworks.
Restricted Application added a project: Frameworks.
jtamate requested review of this revision.

REVISION SUMMARY
  The two new UDS structures are similar to Frank's, but instead of using two vectors, use only one, with the index next to the data, and an overwritten == operator to test only the indexes (without it, the structures are slow).
  The first structure uses linear access and in the autotests is the fastest.
  The second structure uses binary access and scales better.
  
  I've modified the last 3 test to measure insertion time and read time as used in KFileItemPrivate::cmp.
  
  If you like one of the new structures, it can replace the one currently used in KIO::UDSEntryPrivate.

TEST PLAN
  run the test several times
  
  The interesing results in my pc:
  
    INFO   : UdsEntryBenchmark::testTwoVectorsSlave() warmup stage result      : 56
    INFO   : UdsEntryBenchmark::testTwoVectorsSlave() accumulation stage result: 55
    PASS   : UdsEntryBenchmark::testTwoVectorsSlave()
    RESULT : UdsEntryBenchmark::testTwoVectorsSlave():
         0.0016 msecs per iteration (total: 55, iterations: 32768)
    INFO   : UdsEntryBenchmark::testTwoVectorsApp() warmup stage result      : 67
    INFO   : UdsEntryBenchmark::testTwoVectorsApp() accumulation stage result: 68
    PASS   : UdsEntryBenchmark::testTwoVectorsApp()
    RESULT : UdsEntryBenchmark::testTwoVectorsApp():
         0.00051 msecs per iteration (total: 68, iterations: 131072)
    INFO   : UdsEntryBenchmark::testTwoVectorsSlaveAnother() warmup stage result      : 89
    INFO   : UdsEntryBenchmark::testTwoVectorsSlaveAnother() accumulation stage result: 91
    PASS   : UdsEntryBenchmark::testTwoVectorsSlaveAnother()
    RESULT : UdsEntryBenchmark::testTwoVectorsSlaveAnother():
         0.0013 msecs per iteration (total: 91, iterations: 65536)
    INFO   : UdsEntryBenchmark::testTwoVectorsAppAnother() warmup stage result      : 64
    INFO   : UdsEntryBenchmark::testTwoVectorsAppAnother() accumulation stage result: 64
    PASS   : UdsEntryBenchmark::testTwoVectorsAppAnother()
    RESULT : UdsEntryBenchmark::testTwoVectorsAppAnother():
         0.00048 msecs per iteration (total: 64, iterations: 131072)
    INFO   : UdsEntryBenchmark::testTwoVectorsSlaveAnotherV2() warmup stage result      : 98
    INFO   : UdsEntryBenchmark::testTwoVectorsSlaveAnotherV2() accumulation stage result: 101
    PASS   : UdsEntryBenchmark::testTwoVectorsSlaveAnotherV2()
    RESULT : UdsEntryBenchmark::testTwoVectorsSlaveAnotherV2():
         0.00154 msecs per iteration (total: 101, iterations: 65536)
    INFO   : UdsEntryBenchmark::testTwoVectorsAppAnotherV2() warmup stage result      : 65
    INFO   : UdsEntryBenchmark::testTwoVectorsAppAnotherV2() accumulation stage result: 68
    PASS   : UdsEntryBenchmark::testTwoVectorsAppAnotherV2()
    RESULT : UdsEntryBenchmark::testTwoVectorsAppAnotherV2():
         0.00051 msecs per iteration (total: 68, iterations: 131072)
    
    
    PASS   : UdsEntryBenchmark::testTwoVectorsSlave()
    RESULT : UdsEntryBenchmark::testTwoVectorsSlave():
         10,918 instruction reads per iteration (total: 10,918, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsApp()
    RESULT : UdsEntryBenchmark::testTwoVectorsApp():
         3,182 instruction reads per iteration (total: 3,182, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsSlaveAnother()
    RESULT : UdsEntryBenchmark::testTwoVectorsSlaveAnother():
         8,981 instruction reads per iteration (total: 8,981, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsAppAnother()
    RESULT : UdsEntryBenchmark::testTwoVectorsAppAnother():
         3,102 instruction reads per iteration (total: 3,102, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsSlaveAnotherV2()
    RESULT : UdsEntryBenchmark::testTwoVectorsSlaveAnotherV2():
         10,305 instruction reads per iteration (total: 10,305, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsAppAnotherV2()
    RESULT : UdsEntryBenchmark::testTwoVectorsAppAnotherV2():
         3,244 instruction reads per iteration (total: 3,244, iterations: 1)
    
    PASS   : UdsEntryBenchmark::testTwoVectorsSlave()
    RESULT : UdsEntryBenchmark::testTwoVectorsSlave():
         16,450 CPU ticks per iteration (total: 16,450, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsApp()
    RESULT : UdsEntryBenchmark::testTwoVectorsApp():
         4,736 CPU ticks per iteration (total: 4,736, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsSlaveAnother()
    RESULT : UdsEntryBenchmark::testTwoVectorsSlaveAnother():
         11,740 CPU ticks per iteration (total: 11,740, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsAppAnother()
    RESULT : UdsEntryBenchmark::testTwoVectorsAppAnother():
         4,297 CPU ticks per iteration (total: 4,297, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsSlaveAnotherV2()
    RESULT : UdsEntryBenchmark::testTwoVectorsSlaveAnotherV2():
         15,040 CPU ticks per iteration (total: 15,040, iterations: 1)
    PASS   : UdsEntryBenchmark::testTwoVectorsAppAnotherV2()
    RESULT : UdsEntryBenchmark::testTwoVectorsAppAnotherV2():
         5,136 CPU ticks per iteration (total: 5,136, iterations: 1)

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D12659

AFFECTED FILES
  autotests/udsentry_benchmark.cpp

To: jtamate, dfaure, #frameworks
Cc: michaelh, bruns
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-frameworks-devel/attachments/20180502/f55d8a04/attachment.html>