BUG-7464: Enable parallel CNode size computation

Re-enable code which was disabled during the initial port
from Scala, as ThreadLocalRandom is available in Java 7
and newer.

Also make the code a bit smarter by adding special-cases
for empty and single-entry arrays, when it does not make
sense to generate a random number.

Change-Id: Ie7fa98450bf1381a14a7a5e63fd9de6f3b1d17a0
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java
index 9b20a1bb03103df1ace56a6c1b14059c4a725303..c185412ca0c44570879b233a1733bd046dda90b7 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java
@@ -16,6 +16,7 @@
 package org.opendaylight.yangtools.triemap;
 
 import com.google.common.base.Verify;
+import java.util.concurrent.ThreadLocalRandom;
 import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
 
 final class CNode<K, V> extends MainNode<K, V> {
@@ -86,27 +87,33 @@ final class CNode<K, V> extends MainNode<K, V> {
     // at different positions, so they are more likely to
     // to be independent
     private int computeSize(final TrieMap<?, ?> ct) {
-        int i = 0;
-        int sz = 0;
-        // final int offset = (array.length > 0) ?
-        // // util.Random.nextInt(array.length) /* <-- benchmarks show that
-        // // this causes observable contention */
-        // scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt (0,
-        // array.length)
-        // : 0;
-
-        final int offset = 0;
-        while (i < array.length) {
-            int pos = (i + offset) % array.length;
-            BasicNode elem = array [pos];
-            if (elem instanceof SNode) {
-                sz += 1;
-            } else if (elem instanceof INode) {
-                sz += ((INode<?, ?>) elem).cachedSize(ct);
-            }
-            i += 1;
+        final int len = array.length;
+        switch (len) {
+            case 0:
+                return 0;
+            case 1:
+                return elementSize(array[0], ct);
+            default:
+                final int offset = ThreadLocalRandom.current().nextInt(len);
+                int sz = 0;
+                for (int i = offset; i < len; ++i) {
+                    sz += elementSize(array[i], ct);
+                }
+                for (int i = 0; i < offset; ++i) {
+                    sz += elementSize(array[i], ct);
+                }
+                return sz;
+        }
+    }
+
+    private static int elementSize(final BasicNode elem, final TrieMap<?, ?> ct) {
+        if (elem instanceof SNode) {
+            return 1;
+        } else if (elem instanceof INode) {
+            return ((INode<?, ?>) elem).cachedSize(ct);
+        } else {
+            throw new IllegalStateException("Unhandled element " + elem);
         }
-        return sz;
     }
 
     CNode<K, V> updatedAt(final int pos, final BasicNode nn, final Gen gen) {