Uploaded image for project: 'Crowd'
  1. Crowd
  2. CWD-3799

Performance Problems due to O(n) group lookups and other perfomance problems

    XMLWordPrintable

    Details

    • Feedback Policy:

      Our product teams collect and evaluate feedback from a number of different sources. To learn more about how we use customer feedback in the planning process, check out our new feature policy.

      Description

      Our customer faces quite a big (sometimes large) performance problem when synchronizing their Confluence against their Crowd. A full sync (which sometimes happens although incremental sync is enabled) takes 400-600s on an idle, production-like (i.e. powerful) test system, and can take more than an hour in production.
      During most of the time, there are no requests to crowd, and only one thread is using a CPU core (100%), there are no I/O waits.

      Thread dumps show that the culprit is com.atlassian.crowd.directory.DbCachingRemoteChangeOperations.findUserMembershipForGroupChanges

      This method shows a few weaknesses:

      • contains lookups are performed that are O(n)
      • ~n lookups are performed, so we have O(n^2)
        first example is internalMembers:
        List<String> internalMembers = ...
        ...
        for (String remoteUser : remoteUsers)
        {
            if (!internalMembers.contains(remoteUser))
                usersToAdd.add(remoteUser);
        }
        

        second is remoteUsers:

        ... Collection<String> remoteUsers ...
        ...
        remoteUsers = Collections2.transform(remoteUsers, IdentifierUtils.TO_LOWER_CASE);
        ...
        for (String internalUser : internalMembers)
        {
            if (!remoteUsers.contains(internalUser))
                usersToRemove.add(internalUser);
        }
        
      • the contains lookups are performed against a life view made with Collections2.transform resp. Lists.transform, although
        • the documentation of Collections2.transform states that

          When a live view is not needed, it may be faster to copy the transformed collection and use the copy.

        • the documentation of Lists.transform even states

          The function is applied lazily, invoked when needed. This is necessary for the returned list to be a view, but it means that the function will be applied many times for bulk operations like List.contains(java.lang.Object)

        • which is exactly what is done here
        • so we are not only dealing with O(n^2) comparisons, but also with n^2 invocations of toLowerCase, while only n would be needed

      So I did what Google suggests, copy both collections into HashSets and use them for both iteration and contains lookup.

      Result:
      On the above mentioned test system, the sync takes about 15 seconds (30 times speedup).

      Patch is attached, it was taken from Confluence 5.1.5 (Crowd 2.6.2), but applies cleanly against Crowd 2.7.0 (Confluence 5.4.2), too.

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              Unassigned Unassigned
              Reporter:
              marvinthepa Martin Sander
              Votes:
              32 Vote for this issue
              Watchers:
              30 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: