d8tltanc commented on a change in pull request #9485:
URL: https://github.com/apache/kafka/pull/9485#discussion_r534477631
##########
File path:
jmh-benchmarks/src/main/java/org/apache/kafka/jmh/acl/AclAuthorizerBenchmark.java
##########
@@ -69,33 +70,39 @@
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class AclAuthorizerBenchmark {
- @Param({"10000", "50000", "200000"})
+ @Param({"10000", "40000", "80000"})
Review comment:
I just realized that my AclAuthorizer implementation is calling
`String::startWith` which also has an O(d) complexity where `d` is the length
of the "deny pattern" string of the given ACL. So the complexity would be O(n *
m * d).
So given all "allow pattern" and "deny pattern" of a given ACE, we have 2
algorithms now
1. Iterate through all the prefixes of the `allow pattern` string and check
if any prefix is contained in the set of `deny pattern`, which has a complexity
of O(n * a), where `a` is the length of the "allow pattern" string. My
interface default is using this approach.
2. Iterate through all the "deny patterns", which has a complexity of O(n *
m * d), where d is the length of the `deny pattern` string. My AclAuthorizer is
using this approach.
Comparasion: Since the average of the `allow pattern` string length should
be close to that of the `deny pattern`, we can say `a = d`. So O(n * a) = O(n *
d) > O(n * m * d), which means approach 1 is much better.
Conclusion: I'll change AclAuthorizer to use approach 1.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
