1 2 3 Previous Next 32 Replies Latest reply on Aug 24, 2009 8:20 AM by alesj

    Does ScopeKey need to maintain a sorted (in ScopeLevel.level

    smarlow

      In my quest to understand the MC internals and help make improvements. I'm looking at ScopeKey and wondering what would happen if an unordered collection was used internally (with adjustments made to isParent() of course).

      I would like to add some contractually comments to ScopeKey that explain the "ordered" expectation, if there is one.

      Is the ScopeKey ordering so that we will look at metadata in the following order (from CommonLevels)? { domain, cluster, machine, node, jvm, server, subsystem, application, ... }

        • 1. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
          alesj

          Order is definitely there for a purpose. ;-)
          Adrian could comment on it more.

          I guess internally you can implement it how ever you feel like,
          and this is exactly the goal of this task,
          to try out different approaches; e.g. unordered impl detail could out-perform ordered impl

          This is motly used with MDR, and it's "connectors":
          * ControllerContext/ScopeInfo
          * DeploymentUnit/Context

          You can check for the "ordered" explanation there,
          but I think it's pretty natural in the way of hierarchy you mentioned.
          (from CommonLevels? { domain, cluster, machine, node, jvm, server, subsystem, application, ... } )

          • 2. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
            smarlow

            Internally, I started a second unordered collection in ScopeKey but haven't switched over the cases that need the ordered collection yet (for obvious reasons :).

            Looking at the cases for ordered access to ScopeKey.scopes, I see the following methods that seem to need sorted access to ScopeKey.scopes collection.

            1. The getParent() which returns a collection of Scopes (in sorted order). The parent seems to be all Scopes except the highest ScopeLevel entry (last value in ScopeKey.scopes collection). In my search for meaning, I will assert that the child value must always be the one with the highest ScopeLevel. I haven't yet come across any processing for the child only, so maybe there really isn't a "child" concept embedded into the code. If this was a Lisp list, I might almost mistake getParent as returning some sort of "cdr" (except from the tail instead of list head).

            2. isParent(ScopeKey key), returns true if the passed key's Scopes match the "this" Scopes (ignoring the last entry, which I will again call the child for no good reason).

            3. getScopes() returns immutable collection of the Scopes (in sorted order). One caller to getScopes(), that might need a sorted result is in DefaultScopeBuilder.initMetaDataRetrieval which builds a collection of metadata in the lowest to highest ScopeLevel order. AbstractScopeInfo also depends on a sorted result from getScopes(). FuzzyMetaDataRepositoryVisitor also depends on getScopes returning a sorted result.

            There could be other dependencies (on a sorted result) that I missed as well.

            It doesn't seem very difficult to eliminate the get/is Parent depenency on a sorted scopes collection as we always know the "maxScopeLevel" which identifies the "child" entry (I'm still not sure if it is correct to refer to the last entry as the "child" ;). Given an unordered collection, getParent, returns all entries minus the "maxScopeLevel" and the same can be used for isParent checking.

            This leaves getScopes(), I'll wait to hear responses to this post before drilling further into getScopes().

            • 3. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
              smarlow

               

              "smarlow@redhat.com" wrote:

              It doesn't seem very difficult to eliminate the get/is Parent depenency on a sorted scopes collection as we always know the "maxScopeLevel" which identifies the "child" entry (I'm still not sure if it is correct to refer to the last entry as the "child" ;). Given an unordered collection, getParent, returns all entries minus the "maxScopeLevel" and the same can be used for isParent checking.


              I made the above changes to isParent + getParent and we pass the unit tests (for what that is worth ;)

              • 4. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                smarlow

                I tested with as trunk (just booting up the app server) and my ScopeKey refactoring didn't seem to cause any problems. I'm using an unsorted collection in all places except for getScopes, which is currently news up a sorted collection on the fly and returns the sorted values.

                I would like to work towards making ScopeKey an immutable class, which pushes the sorting effort onto the constructor (depending on what is passed in). This will have an impact on the callers and probably require solving some problems without using ScopeKey.

                Is this a direction that we want to move towards? I'm about to enter a pretty deep refactoring and could use some feedback. :)

                • 5. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                  jason.greene

                  This class should *definitely* be immutable. Then all synchronization can be removed. The memory footprint of this class could also be reduced quite a bit if it used an array (or arraylist) instead of a treemap. The only issue is the perf of getScopeLevel, but we have such a small number of fixed levels that there probably is no noticeable perf diff using a treemap.

                  • 6. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                    dmlloyd

                     

                    "jason.greene@jboss.com" wrote:
                    . The only issue is the perf of getScopeLevel, but we have such a small number of fixed levels that there probably is no noticeable perf diff using a treemap.


                    If you keep the array or arraylist sorted, you can get the same O(log n)-type performance by using e.g. Arrays.binarySearch()....

                    • 7. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                      jason.greene

                       

                      "david.lloyd@jboss.com" wrote:

                      If you keep the array or arraylist sorted, you can get the same O(log n)-type performance by using e.g. Arrays.binarySearch()....


                      Ah yes, of course! This should definitely be converted to an array then.

                      • 8. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                        alesj

                         

                        "jason.greene@jboss.com" wrote:
                        This class should *definitely* be immutable.

                        I don't think this class was ever meant to me immutable,
                        otherwise there wouldn't be a freeze()/isFrozen() methods.

                        Afaik the idea is to have it mutable/dynamic to a certain point,
                        e.g. different layers add different scopes,
                        once we're past of allowing this additions we freeze it in order to be able to do deterministic lookups.

                        From reading Scott's observations, array looks like a possible impl.
                        e.g. the parent get/check could easily be done with System::arraycopy

                        • 9. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                          jason.greene

                           

                          "alesj" wrote:
                          "jason.greene@jboss.com" wrote:
                          This class should *definitely* be immutable.

                          I don't think this class was ever meant to me immutable,
                          otherwise there wouldn't be a freeze()/isFrozen() methods.

                          Afaik the idea is to have it mutable/dynamic to a certain point,
                          e.g. different layers add different scopes,
                          once we're past of allowing this additions we freeze it in order to be able to do deterministic lookups.


                          Right, I am saying that this class wants to be immutable and that the freeze/unfreeze is just a hack to make the current approach work . Its primary purpose is to represent a "path" to a scoped value, which is logically a fixed construct. As you mention, the mutation methods are just there to make assembling it easier, however this introduces a number or problems:


                          • Collections need fixed keys, so now you have to "freeze" it somehow
                          • Since the object is passed between threads you need to synchronize state now. This ends up being very costly on a heavily accessed object, since even a non-contended lock still triggers a cpu fence, which typically involves waiting on particular cycle (wmb etc), and invalidates portions of the cpu cache.
                          • The usage is now error-prone. What if someone forgets to freeze? What if they don't check that it's frozen before they modify it?


                            There are other better ways to have easy assembly of an immutable class:

                            If all scope path elements are known, a varargs constructor / factory
                             scopeKey = new ScopeKey(serverScope, deploymentScope, classScope);
                            


                            If the assembly process is done in a phased multi-participant process, than a chained-copy constructor can be used:

                            parentScopeKey = new ScopeKey(serverScope);
                            ....
                            childKey = new ScopeKey(parentScopeKey, deploymentScope, classScope)
                            


                            If you prefer an even more flexible assembly approach, then a builder can be used:

                            builder = new ScopeKeyBuilder();
                            builder.add(serverScope).add(deploymentScope).add(classScopeA);
                            builder.remove(classScopeA);
                            builder.add(classScopeB);
                            
                            key = builder.toScopeKey();
                            


                          • 10. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                            alesj

                             

                            "jason.greene@jboss.com" wrote:

                            Right, I am saying that this class wants to be immutable and that the freeze/unfreeze is just a hack to make the current approach work .

                            This is a bold statement, one I think neither you or me can confirm.
                            ScopeKey and MDR span across many layers, existing and to-be-done,
                            so I think the only one to call this is the one who wrote it.

                            Unless you know MDR better, hence are the best candidate for this
                            * MDR performance improvements

                            "jason.greene@jboss.com" wrote:

                            The usage is now error-prone. What if someone forgets to freeze? What if they don't check that it's frozen before they modify it?

                            ScopyKey is actually impl detail or at least high dev detail.
                            Current deployment code assures we don't forget to freeze -> freeze once we're fully installed or past certain state.

                            If they don't check is it frozen and it's, an exception is thrown, hence this is not an issue.

                            But this argument in general seems empty to me - you can always say similar thing for all things.
                            But that doesn't make it wrong.
                            It might be a bug or api abuse, but that's why we should have proper tests.

                            "jason.greene@jboss.com" wrote:

                            If all scope path elements are known, a varargs constructor / factory
                             scopeKey = new ScopeKey(serverScope, deploymentScope, classScope);
                            


                            Scope elements are only known once you move through deployment lifecycle.

                            "jason.greene@jboss.com" wrote:

                            If the assembly process is done in a phased multi-participant process, than a chained-copy constructor can be used:
                            parentScopeKey = new ScopeKey(serverScope);
                            ....
                            childKey = new ScopeKey(parentScopeKey, deploymentScope, classScope)
                            


                            This wont work as you have to modify existing instance,
                            as although it's mutable, you cannot change its ref.

                            "jason.greene@jboss.com" wrote:

                            If you prefer an even more flexible assembly approach, then a builder can be used:

                            builder = new ScopeKeyBuilder();
                            builder.add(serverScope).add(deploymentScope).add(classScopeA);
                            builder.remove(classScopeA);
                            builder.add(classScopeB);
                            
                            key = builder.toScopeKey();
                            

                            How's this different from what we have right now?

                            • 11. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                              smarlow

                              Up to this point, I have been making my changes on the jboss-mdr trunk. So far, I have merged back locally to 2.0.2.GA for testing.

                              I would like to make a deeper pass of changing some of the calls into ScopeKey. This work will be across different projects (aop and others).

                              I heard that some active development is on non-trunk branches (intended to be merged to trunk at some point).

                              I would like my work to show up in as 6. Which MC branches should I work off of (trunk only or something else)?

                              By the way, I love the ScopeKey unit tests, they were very helpful in catching mistakes in my ScopeKey changes! :)

                              • 12. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                                alesj

                                 

                                "smarlow@redhat.com" wrote:

                                I would like to make a deeper pass of changing some of the calls into ScopeKey. This work will be across different projects (aop and others).

                                What kind of changes are we talking about here?
                                Or why is the change to an array not good enough?

                                • 13. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                                  jason.greene

                                   

                                  "alesj" wrote:
                                  "jason.greene@jboss.com" wrote:

                                  Right, I am saying that this class wants to be immutable and that the freeze/unfreeze is just a hack to make the current approach work .

                                  This is a bold statement, one I think neither you or me can confirm.
                                  ScopeKey and MDR span across many layers, existing and to-be-done,
                                  so I think the only one to call this is the one who wrote it.

                                  Unless you know MDR better, hence are the best candidate for this
                                  * MDR performance improvements


                                  I looked at its usage and the original design forum posts.

                                  Nevertheless the MDR's use case is irrelevant. The claim is accurate because it refers to the interaction of ScopeKey with Java collections, and concurrency. If something is a key in a java collection it should be immutable. If something is passed between threads, it's faster if its immutable. No use case makes the above items not true.


                                  "jason.greene@jboss.com" wrote:

                                  The usage is now error-prone. What if someone forgets to freeze? What if they don't check that it's frozen before they modify it?

                                  ScopyKey is actually impl detail or at least high dev detail.
                                  Current deployment code assures we don't forget to freeze -> freeze once we're fully installed or past certain state.

                                  If they don't check is it frozen and it's, an exception is thrown, hence this is not an issue.

                                  But this argument in general seems empty to me - you can always say similar thing for all things.
                                  But that doesn't make it wrong.
                                  It might be a bug or api abuse, but that's why we should have proper tests.


                                  The exception is a runtime failure that would never happen in any of other approaches I mentioned were used. The point is that there is nothing better about the approach this class takes, so we are paying perf losses, extra error checking, etc for something that could be much simpler and faster.


                                  "jason.greene@jboss.com" wrote:

                                  If the assembly process is done in a phased multi-participant process, than a chained-copy constructor can be used:

                                  parentScopeKey = new ScopeKey(serverScope);
                                  ....
                                  childKey = new ScopeKey(parentScopeKey, deploymentScope, classScope)
                                  


                                  This wont work as you have to modify existing instance,
                                  as although it's mutable, you cannot change its ref.


                                  You would have to fix the code that calls it (which you have to do to change to this anyway). The key has to be "frozen" to be in the MDR anyway, so it shouldn't be a big deal.


                                  "jason.greene@jboss.com" wrote:

                                  If you prefer an even more flexible assembly approach, then a builder can be used:

                                  builder = new ScopeKeyBuilder();
                                  builder.add(serverScope).add(deploymentScope).add(classScopeA);
                                  builder.remove(classScopeA);
                                  builder.add(classScopeB);
                                  
                                  key = builder.toScopeKey();
                                  

                                  How's this different from what we have right now?


                                  You have 2 classes instead of one. The version that is used in a java collection is truly immutable, and therefore isnt dog slow on every MDR lookup operation like what we have right now.

                                  • 14. Re: Does ScopeKey need to maintain a sorted (in ScopeLevel.l
                                    jason.greene

                                    To better illustrate one of the perf issues, take a look at the two most prevalent methods that are called by a key in a map, equals() and hashCode(). equals() aquires a lock and then iterates every scope in the treemap, and for each scope of that key aquires a lock on the scopekey it is being compared to. hashCode() aquires a lock while it calculates a value off of every scope, something that could have been cached if the type was immutable.

                                    1 2 3 Previous Next