On 08.06.2022 15:49, Julian Foad wrote:
I did some profiling for SVN-4832 "Authz perf regression 1.9 -> 1.10" <https://subversion.apache.org/issue/4832>.I updated the issue with my findings, including a sample of the debug timings output from my debug code. TL;DR: if an authz file specifies a large number of ACLs and a large number of users, it is slow. Nearly all the time is used by svn_authz__parse() calling update_user_rights() this many times: (total number of ACLs in the authz file) x (total number of "concrete users" mentioned in the authz file). This bottleneck apparently was not present in the previous implementation (svn 1.9), but I understand other cases were slow then. The optimization in svn 1.10 apparently optimizes for other cases but makes things worse in these cases. As far as I can see the "update_user_rights" code looks functionally trivial and the problem is just the accumulated time over a huge number of iterations of it. I am looking to see if there is anything that can be done about speeding it up, whether algorithmic or local optimization. If anyone can lend insight or a hand, I know there are some users who would appreciate it. It's in subversion/libsvn_repos/authz_parse.c: update_user_rights() called right at the end of expand_acl_callback(), which is called right at the end of svn_authz__parse(). In pseudo-code: for each of all ACLs: for each of all users: update_user_rights()
That's all mine, isn't it. You're right, there's an O(n * m) in there and it can't be resolved unless we find a better way to do this. Local optimisations won't help much, we either need a better algorithm or we have to parallelize this code. Although note that even parallelizing will only speed up by a constant factor.
Hm. Thinking ... I surely never considered we'd have so many ACL's * users that this would be a problem. One assumption of the authz rewrite was that we'd parse the authz file once, then keep the result cached over many requests -- the parsed representation is immutable and can be read in parallel from any number of request threads.
Is this something we could fix by adding lazy evaluation? That is, to expand only when a lookup for a given user happens? Lazy evaluation would break that immutability promise and we'd have to add locking.
-- Brane
