Re: svn commit: r1562360 - /jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/observation/EventGenerator.java

[Michael Dürig <md...@apache.org>]

On 29.1.14 6:12 , jukka@apache.org wrote:
> Author: jukka
> Date: Wed Jan 29 05:12:01 2014
> New Revision: 1562360
>
> URL: http://svn.apache.org/r1562360
> Log:
> OAK-1332: Large number of changes to the same node can fill observation queue
>
> Optimize and clean up the code for detecting reorderings
>

> @@ -156,27 +156,52 @@ public class EventGenerator {
>               if (beforeEvent()) {
>                   // check for reordering of child nodes
>                   if (OAK_CHILD_ORDER.equals(before.getName())) {
> -                    Set<String> beforeSet =
> -                            newLinkedHashSet(before.getValue(NAMES));
> -                    Set<String> afterSet =
> -                            newLinkedHashSet(after.getValue(NAMES));
> -                    afterSet.retainAll(beforeSet);
> -                    beforeSet.retainAll(afterSet);
> -                    String[] beforeNames = beforeSet.toArray(STRING_ARRAY);
> -                    String[] afterNames = afterSet.toArray(STRING_ARRAY);
> +                    // list the child node names before and after the change
> +                    List<String> beforeNames =
> +                            newArrayList(before.getValue(NAMES));
> +                    List<String> afterNames =
> +                            newArrayList(after.getValue(NAMES));
> +
> +                    // check only those names that weren't added or removed
> +                    beforeNames.retainAll(newHashSet(afterNames));
> +                    afterNames.retainAll(newHashSet(beforeNames));
>
>                       // Selection sort beforeNames into afterNames,
>                       // recording the swaps as we go
> -                    for (int a = 0; a < afterNames.length; a++) {
> -                        String name = afterNames[a];
> -                        for (int b = a + 1; b < beforeNames.length; b++) {
> -                            if (name.equals(beforeNames[b])) {
> -                                beforeNames[b] = beforeNames[a];
> -                                beforeNames[a] = name;
> -                                handler.nodeReordered(
> -                                        beforeNames[a + 1], name,
> -                                        this.after.getChildNode(name));
> +                    for (int a = 0; a < afterNames.size() - 1; a++) {
> +                        String beforeName = beforeNames.get(a);
> +                        String afterName = afterNames.get(a);
> +                        if (!afterName.equals(beforeName)) {
> +                            // Find afterName in the beforeNames list.
> +                            // This loop is guaranteed to stop because both
> +                            // lists contain the same names and we've already
> +                            // processed all previous names.
> +                            int b = a + 1;
> +                            while (!afterName.equals(beforeNames.get(b))) {
> +                                b++;
> +                            }
> +
> +                            // Swap the non-matching before name forward.
> +                            // No need to beforeNames.set(a, afterName),
> +                            // as we won't look back there anymore.
> +                            beforeNames.set(b, beforeName);
> +
> +                            // find the destName of the orderBefore operation
> +                            String destName = null;
> +                            Iterator<String> iterator =
> +                                    after.getValue(NAMES).iterator();
> +                            while (destName == null && iterator.hasNext()) {
> +                                if (afterName.equals(iterator.next())) {
> +                                    if (iterator.hasNext()) {
> +                                        destName = iterator.next();
> +                                    }
> +                                }
>                               }
> +
> +                            // deliver the reordering event
> +                            handler.nodeReordered(
> +                                    destName, afterName,
> +                                    this.after.getChildNode(afterName));
>                           }
>                       }
>                   }

I can't follow here. Apart from not doing beforeNames.set(a, afterName), 
I don't see any optimisation. Moreover the initial code was in my eye 
much clearer and more concise. Finally we shouldn't bother to much re. 
optimisation of reorder operation as they occur rather rarely and when 
they do we know that there won't be many child nodes as this is a design 
limitation anyway.

Michael

Re: svn commit: r1562360 - /jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/observation/EventGenerator.java

[Jukka Zitting <ju...@gmail.com>]

Hi,

On Wed, Jan 29, 2014 at 4:56 AM, Michael Dürig <md...@apache.org> wrote:
> I can't follow here. Apart from not doing beforeNames.set(a, afterName), I
> don't see any optimisation.

The code was O(n^2) for the common case when no reorderings (just
added/removed nodes) took place. With the added
!afterName.equals(beforeName) check that case is now an O(n)
operation.

> Moreover the initial code was in my eye much clearer and more concise.
> Finally we shouldn't bother to much re. optimisation of reorder operation
> as they occur rather rarely and when they do we know that there won't be
> many child nodes as this is a design limitation anyway.

The problem I see here is that the reordering detection gets triggered
also in the much more common case of adding or removing a node. In a
semi-flat hierarchy of up to 1k nodes (which is the rough limit for
orderable nodes we've used so far), the check without this
optimization would have ended making hundreds of thousands of
String.equals() calls for each commit that adds or removes a node.
Multiplied by the number of observation listeners, this seemed like an
important enough corner case to optimize for.

BR,

Jukka Zitting