[
https://issues.apache.org/jira/browse/SLING-9077?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17044395#comment-17044395
]
Dirk Rudolph commented on SLING-9077:
-------------------------------------
There are various use cases for PathSets, here is a incomplete list:
# The paths of ObserverConfiguration (form ResourceChangeListeners)
# The excludePaths of overlapping ResourceProviders (used for Observation and
Querying) since SLING-8946
# any more?
For 1) a typical PathSet contains either just a few paths and/or glob patterns
where as for 2) the set may grow large with paths only.
The current {{optimize()}} works well (good-enough) for 1) but does not scale
for 2).
A solution to resolve this for 2) would be to take the information typical for
paths (hierarchy information) into account and implement a tree that is
auto-optimising and can be traversed with O(n+m), where m is the maximum depth
of the tree in the worst case scenario. In a typical repository n (number of
paths) is growing much more than m (depth of tree). This ends in nearly O\(n)
for large sets of paths but has a minimal higher memory impact and absolute
runtime for small sets. Because of that keeping both ways of optimisation make
sense. Also nearly O\(n), because for completeness reasons the tree has to
handle patterns as well.
> Improve runtime complexity of o.a.s.api.resource.path.PathSet's factory
> methods
> -------------------------------------------------------------------------------
>
> Key: SLING-9077
> URL: https://issues.apache.org/jira/browse/SLING-9077
> Project: Sling
> Issue Type: Improvement
> Reporter: Dirk Rudolph
> Priority: Major
> Attachments: PerformanceScript.sh
>
>
> With SLING-8946 the PathSet used to keep track of the excluded paths for
> resource observation event propagation of individual ResourceProviders
> started to grow. (The excludes PathSet of the root-ResourceProvider / now
> contains all other ResourceProviders in a system).
> While registering a new ResourceProvider the context update builds a new
> PathSet which is optimised with in PathSet#optimize() with O(n^2). Esp. when
> starting up the environment this is consuming massive CPU time as it grows to
> O(n^3): for each RP calculate the exclusion PathSet with O(n^2).
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
