Open tjerman opened 4 months ago
Benchmarks for the reworked version:
goos: darwin
goarch: arm64
pkg: github.com/cortezaproject/corteza/server/pkg/rbac
Benchmark_AccessCheck_role100_rule1000-12 101308 11020 ns/op 5120 B/op 23 allocs/op
Benchmark_AccessCheck_role100_rule10000-12 106794 10392 ns/op 5119 B/op 23 allocs/op
Benchmark_AccessCheck_role100_rule100000-12 106137 10957 ns/op 5135 B/op 23 allocs/op
Benchmark_AccessCheck_role100_rule1000000-12 94984 13411 ns/op 5110 B/op 23 allocs/op
Benchmark_AccessCheck_role100_rule10000000-12 78258 13923 ns/op 5118 B/op 23 allocs/op
Benchmark_AccessCheck_role1000_rule1000-12 14739 79997 ns/op 52803 B/op 45 allocs/op
Benchmark_AccessCheck_role1000_rule10000-12 10000 111318 ns/op 53129 B/op 45 allocs/op
Benchmark_AccessCheck_role1000_rule100000-12 10000 119062 ns/op 53103 B/op 45 allocs/op
Benchmark_AccessCheck_role1000_rule1000000-12 10000 127920 ns/op 53166 B/op 45 allocs/op
Benchmark_AccessCheck_role1000_rule10000000-12 7801 406544 ns/op 53141 B/op 50 allocs/op
Benchmark_AccessCheck_role10000_rule1000-12 1609 744085 ns/op 508033 B/op 106 allocs/op
Benchmark_AccessCheck_role10000_rule10000-12 1227 959672 ns/op 509599 B/op 106 allocs/op
Benchmark_AccessCheck_role10000_rule100000-12 447 2711555 ns/op 502836 B/op 105 allocs/op
Benchmark_AccessCheck_role10000_rule1000000-12 723 2202073 ns/op 528585 B/op 110 allocs/op
Benchmark_AccessCheck_role10000_rule10000000-12 418 2587235 ns/op 496879 B/op 108 allocs/op
Comparing the numbers
Number for averages
time 3031 times better
memory 1.85 times better
allocs 53.64 times better
Numbers per benchmark
Benchmark_AccessCheck_role100_rule1000-12
time 26437/11020=2.39 times better
memory 10183/5120=1.98 times better
allocs 206/23=8.95 times better
Benchmark_AccessCheck_role100_rule10000-12
time 143348/10392=13.79 times better
memory 10195/5119=1.99 times better
allocs 206/23=8.95 times better
Benchmark_AccessCheck_role100_rule100000-12
time 1399730/10957=127.74 times better
memory 10132/5135=1.97 times better
allocs 205/23=8.91 times better
Benchmark_AccessCheck_role100_rule1000000-12
time 32568396/13411=2428.48 times better
memory 11196/5110=2.19 times better
allocs 226/23=9.82 times better
Benchmark_AccessCheck_role100_rule10000000-12
time 580995401/13923=41729.18 times better
memory 14075/5118=2.75 times better
allocs 286/23=12.43 times better
Benchmark_AccessCheck_role1000_rule1000-12
time 115692/79997=1.44 times better
memory 78850/52803=1.49 times better
allocs 1216/45=27.02 times better
Benchmark_AccessCheck_role1000_rule10000-12
time 260073/111318=2.33 times better
memory 87800/53129=1.65 times better
allocs 1578/45=35.06 times better
Benchmark_AccessCheck_role1000_rule100000-12
time 1521378/119062=12.77 times better
memory 87707/53103=1.65 times better
allocs 1593/45=35.4 times better
Benchmark_AccessCheck_role1000_rule1000000-12
time 26178927/127920=204.65 times better
memory 79729/53166=1.49 times better
allocs 1447/45=32.15 times better
Benchmark_AccessCheck_role1000_rule10000000-12
time 338761798/406544=833.27 times better
memory 87824/53141=1.65 times better
allocs 1502/50=30.04 times better
Benchmark_AccessCheck_role10000_rule1000-12
time 1113431/744085=1.49 times better
memory 875524/508033=1.72 times better
allocs 10173/106=95.97 times better
Benchmark_AccessCheck_role10000_rule10000-12
time 1259840/959672=1.31 times better
memory 877246/509599=1.72 times better
allocs 11239/106=106.02 times better
Benchmark_AccessCheck_role10000_rule100000-12
time 2661588/2711555=0.98 times better
memory 921948/502836=1.83 times better
allocs 14190/105=135.14 times better
Benchmark_AccessCheck_role10000_rule1000000-12
time 25640188/2202073=11.64 times better
memory 1038714/528585=1.96 times better
allocs 15395/110=139.95 times better
Benchmark_AccessCheck_role10000_rule10000000-12
time 265117083/2587235=102.47 times better
memory 882284/496879=1.77 times better
allocs 12844/108=118.92 times better
Instead of simple hash maps, we introduce a variation of a trie.
We split up the RBAC rule in chunks (separated by /
) and use it to represent all the rules as a trie.
This lets us look up the values optimally.
Looking back at the numbers, it's not exactly what it should be so I've probably messed up the implementation. The performance is more than enough so there is no much need to optimise further.
Stale issue message
The original versions index was sub optimal. Rules were indexed by role and some other bits. The issue arises when the number of rules increases as the lookup time is linear.
Benchmarks for the original implementation:
Important There is a noticeable time difference in building the original and reworked index. Since the index is built only once, we'll take the hit since the lookup times are much better.