[jira] [Commented] (SLING-9077) Improve runtime complexity of o.a.s.api.resource.path.PathSet's factory methods

["Dirk Rudolph (Jira)" <ji...@apache.org>]

    [ 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)