1 Reply Latest reply on Feb 12, 2010 9:57 AM by Kabir Khan

    Optimizing ScopeKey

    Kabir Khan Master

      Continued from http://community.jboss.org/message/525925#525925

       

      1001 puts into BasicMetaDataRepository.retrievals results in 499500 UnmodifiableScopeKey calls. That is the sum of all numbers from 1 to 999, so it seems like the hashing is not working properly and that we iterate over all entries when doing a put to check if they exist.

        • 1. Re: Optimizing ScopeKey
          Kabir Khan Master

          Yes, the hashing function is broken

           

             int iterations = 15;
          
             public void testScopeKeyHashing()
             {
                List<ScopeKey> scopes = createScopeKeys();
                List<ScopeKey> lockedScopes = createFroxenScopeKeys(scopes);
                
                assertSame(scopes.size(), lockedScopes.size());
                
                for (int i = 0 ; i < iterations ; i++)
                {
                   assertTrue(scopes.get(i).equals(lockedScopes.get(i)));
                   assertTrue(lockedScopes.get(i).equals(scopes.get(i)));
                   assertEquals(scopes.get(i).hashCode(), lockedScopes.get(i).hashCode());
                   System.out.println(scopes.get(i).hashCode() + "  " + scopes.get(i));
                   assertNotSame(scopes.get(i), lockedScopes.get(i));
                }
             }
             
             private List<ScopeKey> createScopeKeys()
             {
                List<ScopeKey> keys = new ArrayList<ScopeKey>();
                for (int i = 0 ; i < iterations ; i++)
                {
                   ScopeKey scopeKey = ScopeKey.DEFAULT_SCOPE.clone();
                   scopeKey.addScope(CommonLevels.INSTANCE, "Bean" + i + Math.random() + 10000);
                   scopeKey.addScope(CommonLevels.CLASS, Object.class.getName());
                   keys.add(scopeKey);
                }
                return keys;
             }
          
           
             private List<ScopeKey> createFroxenScopeKeys(List<ScopeKey> scopes)
             {
                List<ScopeKey> frozens = new ArrayList<ScopeKey>();
                for (ScopeKey key : scopes)
                {
                   ScopeKey frozen = key.getOptimizedKey();
                   frozen.freeze();
                   frozens.add(frozen);
                }
                return frozens;
             }
          

           

          gives the same value 3400

           

          3400  [JVM=THIS, APPLICATION=xyz0, CLASS=java.lang.Object, INSTANCE=Bean00.724748247059574310000]

          3400  [JVM=THIS, APPLICATION=xyz1, CLASS=java.lang.Object, INSTANCE=Bean10.821575642383577510000]

          3400  [JVM=THIS, APPLICATION=xyz2, CLASS=java.lang.Object, INSTANCE=Bean20.3658072070977499410000]

          3400  [JVM=THIS, APPLICATION=xyz3, CLASS=java.lang.Object, INSTANCE=Bean30.17405710442802047

          10000]

          3400  [JVM=THIS, APPLICATION=xyz4, CLASS=java.lang.Object, INSTANCE=Bean40.328947822381441710000]

          3400  [JVM=THIS, APPLICATION=xyz5, CLASS=java.lang.Object, INSTANCE=Bean50.853785127372253610000]

          3400  [JVM=THIS, APPLICATION=xyz6, CLASS=java.lang.Object, INSTANCE=Bean60.308661441767311610000]

          3400  [JVM=THIS, APPLICATION=xyz7, CLASS=java.lang.Object, INSTANCE=Bean70.3214439497564738310000]

          3400  [JVM=THIS, APPLICATION=xyz8, CLASS=java.lang.Object, INSTANCE=Bean80.73783778624132910000]

          3400  [JVM=THIS, APPLICATION=xyz9, CLASS=java.lang.Object, INSTANCE=Bean90.301807484250228210000]

          3400  [JVM=THIS, APPLICATION=xyz10, CLASS=java.lang.Object, INSTANCE=Bean100.4474778106602691510000]

          3400  [JVM=THIS, APPLICATION=xyz11, CLASS=java.lang.Object, INSTANCE=Bean110.1197707023336379610000]

          3400  [JVM=THIS, APPLICATION=xyz12, CLASS=java.lang.Object, INSTANCE=Bean120.313969251914117510000]

          3400  [JVM=THIS, APPLICATION=xyz13, CLASS=java.lang.Object, INSTANCE=Bean130.609491494722042910000]

          3400  [JVM=THIS, APPLICATION=xyz14, CLASS=java.lang.Object, INSTANCE=Bean140.713736711778368310000]

          That must be the real problem, causing UnmodifiableScopeKey.equals()->ScopeKey.getArray()->Collection.toArray() to be called too many times. Looking at the ScopeKey.computeHashCode function it only takes the levels into account:

           

             protected static int computeHashCode(Iterable<Scope> scopeCollection)
             {
                int hashCode = 0;
                for (Scope scope : scopeCollection)
                   hashCode += scope.getScopeLevel().hashCode();
                return hashCode;
             }
           
          

           

          I've rewritten this to hash properly, which makes the retrievals map behave like a map, giving less ScopeKey.equals() hits

           

          Scope constructor:

             public Scope(ScopeLevel level, Object qualifier)
             {
                if (level == null)
                   throw new IllegalArgumentException("Null level");
                if (qualifier == null)
                   throw new IllegalArgumentException("Null qualifier");
                
                this.level = level;
                this.qualifier = qualifier;
          
                int hash = 17;
                hash = 31 * hash + level.hashCode();
                hash = 31 * hash + qualifier.hashCode();
                hashcode = hash;
             }
          

           

             protected static int computeHashCode(Iterable<Scope> scopeCollection)
             {
                int hashCode = 0;
                for (Scope scope : scopeCollection)
                   //hashCode += scope.getScopeLevel().hashCode();
                   hashCode += scope.hashCode();
                return hashCode;
             }
          

           

          I'll add a test and commit against https://jira.jboss.org/jira/browse/JBMDR-65 and then see what this does to AS boot times