(Full) Crowd Sync is very slow

As it seems that no one looks at issues for Crowd, and we are mainly affected by this in Confluence, here it goes again:

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 lookups are performed, so we have O(n^2)
• 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

See https://jira.atlassian.com/browse/CWD-3799 for a patch.