Loading ...
Sorry, an error occurred while loading the content.

Re: [pcgen_developers] Re: [ARCH] Using a Graph for Character Data Store

Expand Messages
  • Tom Parker
    ... [On removal of cloning] Wow!  That s great progress, I didn t realise that trunk was that far advanced already.  It s not 100% done, but you can see the
    Message 1 of 4 , Jun 16, 2009
    • 0 Attachment
      --- On Tue, 6/16/09, Martijn Verburg <martijnverburg@...> wrote:
      [On removal of cloning] Wow!  That's great progress, I didn't realise that trunk was that far advanced already. 

      It's not 100% done, but you can see the state here:
      http://www.pcgen-test.org/wiki/index.php?title=Architecture_Changes_5.17#Eliminate_Cloning

      > However, many of the
      > performance benefits of not cloning have not been realized in 5.17
      > (this is required work).

      Are the performance benefits primarily going to be realised simply because we're no longer doing expensive cloning or are there other advantages we can eek out because we will no longer be cloning?

      The literal cloning CPU effort is probably a small fraction of the performance issue.  It's the side effects of cloning that are painful.  In a clone environment, comparisons can't be instance equality (==), but must be string comparison on key... but you may not have the key to start, so you have to request the key (or abbreviation for a stat).  So even in trivial comparisons we can reduce:

      stat1.getAbbreviation().equalsIgnoreCase(stat2.getAbbreviation());
      to
      stat1.equals(stat2);

      Note that .equals() in this case for PCStat may have been reduced from a deep equals (that has to test values in the PCStat) to simply an instance equality (because no cloning means they are effectively type safe, thus can test solely on ==).  Thus for that equality test we're probably seeing 2 or 3 orders of magnitude of speed increase.  It's small savings each time, but keep in mind we do these tests thousands of times with every change to a PC.

      A concrete example is to look at PCStat objects (PCStats are Ability scores, things like STR, INT, WIS).  The cloning was literally removed in SVN 9690, but then SVN 9884-6, 9888-90, 9893-5, 9897, 9899, 9900 were all additional changes that removed behavior  required when a clone was present but wasteful when no cloning takes place.

      The removal of list searches, String comparisons, etc. provides improvement.  This is why I've been making the point that so much of the performance issue is dependent on other issues (and why I wanted to break the String dependencies between the LST files and the core).  We had to break the cloning behavior in order to be able to get to this point.  IMHO anyway.

      But do/can we have some visualisations of [the graph concept] on the wiki? 

      We will need some examples for the "thought cases"/"counter-cases" that drive us to the current design, so, yes, some will need to be done.


      Perhaps a link to a basic graph theory explanation/tutorial/paper/whatever on the web (even something like a Wikipedia article if it's not too complex).

      Wikipedia http://en.wikipedia.org/wiki/Graph_(mathematics) and http://en.wikipedia.org/wiki/Graph_theory are both pretty good, as is this:
      http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/graph_theory_review.html

      Note that PCGen will at least be using a directed graph (since we have objects granting other objects).  Some other items from the Graph page also come into play (likely a weighted graph as well)

      At some level, I need to concede that a good computer science education cannot be undervalued.  Reading something like "Introduction to Algorithms" or "The Algorithm Design Manual" might be a substitute if the individual in question learns enough by reading.  Then again, we don't really need a large subset of graph theory (one can stop after graph searches), so a bit of delving on Wikipedia and reading some related articles (depth first search, breadth first search, Dijkstra's algorithm) is probably sufficient.

      I haven't dived into the code around this area very much either, but to have a commented sample of how to ties two nodes together with a relationship on the wiki would be very useful.

      Your request is data structure dependent. We're not there yet :)

      TP.
      --
      Tom Parker
      thpr@... and tppublic@...


    • Martijn Verburg
      Hi all, Finally getting to commenting on all of the various architecture threads again, here s the first one (and the easiest!). ... Great to be able to track
      Message 2 of 4 , Jul 21, 2009
      • 0 Attachment
        Hi all,

        Finally getting to commenting on all of the various architecture threads again, here's the first one (and the easiest!).

        > It's not 100% done, but you can see the state here:
        > http://www.pcgen-test.org/wiki/index.php?title=Architecture_Changes_5.17#Eliminate_Cloning

        Great to be able to track this, I've got it bookmarked :)

        >> Are the performance benefits primarily going to be realised simply
        >> because we're no longer doing expensive cloning or are there other
        >> advantages we can eek out because we will no longer be cloning?
        >
        > The literal cloning CPU effort is probably a small fraction of the
        > performance issue.  It's the side effects of cloning that are
        > painful.  In a clone environment, comparisons can't be instance
        > equality (==), but must be string comparison on key... but you may
        > not have the key to start, so you have to request the key (or
        > abbreviation for a stat).  So even in trivial comparisons we can
        > reduce:
        >
        > stat1.getAbbreviation().equalsIgnoreCase(stat2.getAbbreviation());
        > to
        > stat1.equals(stat2);
        >
        > Note that .equals() in this case for PCStat may have been reduced
        > from a deep equals (that has to test values in the PCStat) to
        > simply an instance equality (because no cloning means they are
        > effectively type safe, thus can test solely on ==).  Thus for that
        > equality test we're probably seeing 2 or 3 orders of magnitude of
        > speed increase.  It's small savings each time, but keep in mind we
        > do these tests thousands of times with every change to a PC.
        >
        > A concrete example is to look at PCStat objects (PCStats are
        > Ability scores, things like STR, INT, WIS).  The cloning was
        > literally removed in SVN 9690, but then SVN 9884-6, 9888-90,
        > 9893-5, 9897, 9899, 9900 were all additional changes that removed
        > behavior  required when a clone was present but wasteful when no
        > cloning takes place.
        >
        > The removal of list searches, String comparisons, etc. provides
        > improvement.  This is why I've been making the point that so much
        > of the performance issue is dependent on other issues (and why I
        > wanted to break the String dependencies between the LST files and
        > the core).  We had to break the cloning behavior in order to be
        > able to get to this point.  IMHO anyway.

        OK, I understand this more clearly now, thanks for the explanation.

        > We will need some examples for the "thought cases"/"counter-cases"
        > that drive us to the current design, so, yes, some will need to be
        > done.

        OK, I see you have this in your http://www.pcgen-test.org/wiki/index.php?title=Tom%27s_Arch_%22TO_DO%22_List (which covers the other points raised in this discussion as well)

        >> Perhaps a link to a basic graph theory explanation/tutorial/paper
        >>/whatever on the web (even something like a Wikipedia article if
        >>it's not too complex).
        >
        > Wikipedia http://en.wikipedia.org/wiki/Graph_(mathematics) and
        > http://en.wikipedia.org/wiki/Graph_theory are both pretty good, as
        > is this:
        > http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/graph_theory_review.html
        >
        > Note that PCGen will at least be using a directed graph (since we
        > have objects granting other objects).  Some other items from the
        > Graph page also come into play (likely a weighted graph as well)
        >
        > At some level, I need to concede that a good computer science
        > education cannot be undervalued.  Reading something like
        > "Introduction to Algorithms" or "The Algorithm Design Manual" might
        > be a substitute if the individual in question learns enough by
        > reading.  Then again, we don't really need a large subset of graph
        > theory (one can stop after graph searches), so a bit of delving on
        > Wikipedia and reading some related articles (depth first search,
        > breadth first search, Dijkstra's algorithm) is probably sufficient.

        OK, I've posted this onto the wiki under http://www.pcgen-test.org/wiki/index.php?title=Graph_Theory#Graph_Theory_and_PCGen and linked to it from Architecture and Code Team pages.

        >> I haven't dived into the code around this area very much either,
        >> but to have a commented sample of how to ties two nodes together
        >> with a relationship on the wiki would be very useful.
        >
        > Your request is data structure dependent. We're not there yet :)

        Fair enough!

        K
      Your message has been successfully submitted and would be delivered to recipients shortly.