[SLING-3936] Poor performance when adding a large (?) number of sling.auth.requirements services

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: Auth Core 1.1.8
• Fix Version/s: Auth Core 1.3.0
• Component/s: Authentication
• Assignee: Robert Munteanu
• Reporter: Joerg Hoh
• Created: 15/Sep/14 19:21
• Updated: 20/Sep/14 13:35
• Resolved: 17/Sep/14 08:57

Description

When adding lot of paths, which need authentication, to the SlingAuthenticator, we encourage long times when the execution seems to starve at the PathBasedHolderCache.addHolder() method.

"FelixStartLevel" - Thread t@21
java.lang.Thread.State: RUNNABLE
at java.util.ComparableTimSort.sort(Unknown Source)
at java.util.ComparableTimSort.sort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at java.util.Collections.sort(Unknown Source)
at org.apache.sling.auth.core.impl.PathBasedHolderCache.addHolder(PathBasedHolderCache.java:68)
at org.apache.sling.auth.core.impl.SlingAuthenticator$SlingAuthenticatorServiceListener.registerService(SlingAuthenticator.java:1511)
at org.apache.sling.auth.core.impl.SlingAuthenticator$SlingAuthenticatorServiceListener.addService(SlingAuthenticator.java:1528)
at org.apache.sling.auth.core.impl.SlingAuthenticator$SlingAuthenticatorServiceListener.serviceChanged(SlingAuthenticator.java:1494)

    locked <643be70> (a java.util.HashMap)
    at org.apache.felix.framework.util.EventDispatcher.invokeServiceListenerCallback(EventDispatcher.java:932)
    at org.apache.felix.framework.util.EventDispatcher.fireEventImmediately(EventDispatcher.java:793)
   ...

obviously the problem is the sorting of the ArrayList "byPathList" in the PathBasedCacheHolder.addHolder() method; this ArrayList is always taken from the already present cache, and then sorted again. We you add some tens of thousands items to this list, we might into a n^2 complexity.

Would it be possible to replace this implementation with something more performant, which benefits from the fact, that the byPathList is already sorted; or have a better datastructure (TreeSet?), which has the semantics we need?