BUG-7464: Optimize LNode.removed()

Using ListMap.size() is heavy if we have a lot of hash
collisions from a bad key hash function. LNode removal
does not need to know the precise size -- only the fact
that the ListMap is holding a single entry, so it can
compress down to an SNode.

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

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java
index 0fec28954ab440fe46308cbfe7f9e85288b03538..7d55a7442cc109a3c10bb1401f18a8f73b62fcf0 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java
@@ -34,17 +34,19 @@ final class LNode<K, V> extends MainNode<K, V> {
         return new LNode<>(listmap.add(k, v));
     }
 
+    // FIXME: can we also get the hashcode ?
     MainNode<K, V> removed(final K k, final TrieMap<K, V> ct) {
         // We only ever create ListMaps with two or more entries,  and remove them as soon as they reach one element
         // (below), so we cannot observe a null return here.
-        final ListMap<K, V> updmap = listmap.remove(k);
-        if (updmap.size() > 1) {
-            return new LNode<>(updmap);
+        final ListMap<K, V> map = listmap.remove(k);
+        final Optional<Entry<K, V>> maybeKv = map.maybeSingleton();
+        if (maybeKv.isPresent()) {
+            final Entry<K, V> kv = maybeKv.get();
+            // create it tombed so that it gets compressed on subsequent accesses
+            return new TNode<>(kv.getKey(), kv.getValue(), ct.computeHash(kv.getKey()));
         }
 
-        final Entry<K, V> kv = updmap.iterator().next();
-        // create it tombed so that it gets compressed on subsequent accesses
-        return new TNode<>(kv.getKey(), kv.getValue(), ct.computeHash(kv.getKey()));
+        return new LNode<>(map);
     }
 
     Optional<V> get(final K k) {

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
index fba40ded2c6ddbc4127b1afec8744a9d0e80ffa4..84e411474ee19c6928d4e2df2df46134f5bb2734 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
@@ -49,6 +49,10 @@ final class ListMap<K, V> {
         return new ListMap<>(k1, v1, new ListMap<>(k2, v2));
     }
 
+    Optional<Entry<K, V>> maybeSingleton() {
+        return next != null ? Optional.empty() : Optional.of(new SimpleImmutableEntry<>(k, v));
+    }
+
     int size() {
         int sz = 1;
         for (ListMap<?, ?> wlk = next; wlk != null; wlk = wlk.next) {