Create account / Log in

CPU profiling

Discussion area for the development team.

Moderators: uckelman, Tim M

Re: CPU profiling

Postby uckelman » July 30th, 2020, 10:55 pm

Thus spake Flint1b:
>
> "uckelman" wrote:
> > VisualVM's profiler isn't showing me any time taken by
> > PieceCloner.clonePiece()
>
> Exactly, this is why I don't trust this profiler. There wouldn't be any
> companies that earn money only by selling profilers if the VisualVM
> profiler was any good.

That doesn't follow. There are companies selling compilers, and there are
very good free compilers available...

> I just took a good old stopwatch and measured the following in Vassal
> 3.3.2 and PR 75:
> - start stalingrad 42
> - in wizard select "new game", "campaign game", wait until that loads
> - select "solitaire", click "finish" and __start__ the stopwatch
> - wait until the map is fully loaded and CPU usage goes down to idle
> levels
> - __stop__ stopwatch
>
> I got 1:20min for 3.3.2 versus 0:40 for PR 75.

Ah. We were not timing the same things. I will check again.

--
J.
User avatar
uckelman
Site Admin
 
Posts: 9014
Joined: December 10th, 2007, 9:48 am
Location: Durham, England

Re: CPU profiling

Postby Flint1b » July 30th, 2020, 11:13 pm

uckelman wrote:That doesn't follow. There are companies selling compilers, and there are
very good free compilers available...


They have to add things on top to compete with very good free stuff, usually support, a good IDE that is tailorcut to their compiler, features that the free compilers don't have, licensing.
User avatar
Flint1b
 
Posts: 461
Joined: May 19th, 2020, 12:27 am
Location: Colonia Agrippina

Re: CPU profiling

Postby uckelman » July 30th, 2020, 11:15 pm

Thus spake Flint1b:
>
> I got 1:20min for 3.3.2 versus 0:40 for PR 75.

I got 0:08.59 for master vs. 0:05.31 for PR 75. Yes, those are _seconds_,
that's not a mistake.

As I'm getting times which are about 1/9 of yours, you can see why I didn't
notice the difference.

--
J.
User avatar
uckelman
Site Admin
 
Posts: 9014
Joined: December 10th, 2007, 9:48 am
Location: Durham, England

Re: CPU profiling

Postby Flint1b » July 30th, 2020, 11:27 pm

I know, I know, I need a faster computer. OTOH, this makes me a human performance profiler, maybe I should open up a profiling company and offer my services :D
User avatar
Flint1b
 
Posts: 461
Joined: May 19th, 2020, 12:27 am
Location: Colonia Agrippina

Re: CPU profiling

Postby uckelman » July 30th, 2020, 11:39 pm

So, visualvm counted Decorator.getProperty() being called 5 MILLION TIMES while loading the Campaign scenario of Stalingrad '42, and Decorator.getMap() was called another 2m times. That could be largely avoided by having direct property access via the outermost piece. Traversal of the trait stack's not free.
User avatar
uckelman
Site Admin
 
Posts: 9014
Joined: December 10th, 2007, 9:48 am
Location: Durham, England

Re: CPU profiling

Postby Flint1b » July 30th, 2020, 11:52 pm

What does this mean for the overall CPU time, for PR 75, what is a Trait stack, what is a "outermost piece".. I don't know the internals well enough, I'm afraid this is beyond me.
User avatar
Flint1b
 
Posts: 461
Joined: May 19th, 2020, 12:27 am
Location: Colonia Agrippina

Re: CPU profiling

Postby uckelman » July 31st, 2020, 12:09 am

Thus spake Flint1b:
> What does this mean for the overall CPU time, for PR 75, what is a Trait
> stack, what is a "outermost piece".. I don't know the internals well
> enough, I'm afraid this is beyond me.

Each trait class except for BasicPiece wraps another trait class, which
is the "inner" piece. (That's Decorator.inner, literally.)

So if you have, say, a piece that can has two sides and can be marked
moved, you might have this:

MovementMarkable -> Embellishment -> BasicPiece

The instance of MM is the "outermost". It has some properties, but
delegates inward to Embellishment any properties its asked about but
doesn't have itself, and Embellishment does the same thing. If you
get to the bottom and BasicPiece doesn't have the property, then nothing
does and a null gets returned.

Ask Brian how many traits he has on some of the pieces in his modules. It's
more than three. :)

This is a totally inappropriate design once you start getting traits more
than a few deep. Just do do a simple thing like get the value of a string,
you may have to go through all the layers one at a time, and that can be
horribly slow. This is *the* main reason why operations on pieces take
ages sometimes.

The solution to this problem is what I was talking about in the post
linked below:

viewtopic.php?p=62433#p62433


This all orthogonal to PR 75. I'll see about merging that on Friday.

--
J.
User avatar
uckelman
Site Admin
 
Posts: 9014
Joined: December 10th, 2007, 9:48 am
Location: Durham, England

Re: CPU profiling

Postby Flint1b » July 31st, 2020, 12:34 am

Oh my, that's some good design.

Would it be possible to just put these traits with their properties into a list?

Something like this:

Code: Select all
interface TraitProperty<T> {
  String getName();
  T getValue();
}

interface Trait {
  String getName();
  List<TraitProperty<?>> getTraitProperties();
}

interface GamePiece {
  List<Trait> getTraits();
  Object getTraitPropertyValue(String traitName, String traitPropertyName);
}


Or with classes or enums instead of String traitName..

Why was the Decorator pattern chosen anyways, it's good for hiding what's inside from the outside world, why do traits need to hide the other traits underneath them?
User avatar
Flint1b
 
Posts: 461
Joined: May 19th, 2020, 12:27 am
Location: Colonia Agrippina

Re: CPU profiling

Postby Brent Easton » July 31st, 2020, 1:11 am

Decorator was chosen because the original author had read the Design Pattern book and thought it sounded like a good idea.

Conceptually, Decorator is actually an excellent match, because each trait potentially draws something on top of and hides or modifies the drawing of Decorators below it.

Unfortunately, instead of just using this for the visual drawing pipeline of the pieces, everything non-drawing related also got sucked into the Decorator design including property handling, status information (like Does Not Stack), Command & Control (Triggers), Reporting (Report State) etc.

In the early days, this wasn't really a problem as the number of traits per counter was relatively small. As more and more functionality was crammed into Decorators, the efficiency problem has been getting steadily worse, regardless of the increase in CPU power over that time.

There is no shortcut to fix this that won't completely break every module currently in existence. In my book, this is the fundamental, unfixable flaw. In one fell swoop it locks the core behavior into an unsustainable, inefficient design that also tightly binds the Model, View and Control into an untangle-able knot.

Unfortunately, flattening out the Decorator pattern to a List is not really going to help performance as the entire flow of control of all information will still have to pass through every trait. Joel's mod is an attempt to short-circuit trait stack search for get/set property calls be essentially indexing direct links to the traits by property name.

The best we can do is remedial work in two main ways:
1. Short-circuit the trait stack traversals where possible. (Joel's property work)
2. Locate and optimise expensive operations (PieceCloner fix).
3. Try and prevent unnecessary Decorator traversals in the first place.

BTW, I thought Joel's and you results on PR#75 where comparable. Both showed a 40-50% improvement.
User avatar
Brent Easton
 
Posts: 3229
Joined: December 21st, 2007, 3:06 am
Location: Berry, NSW, Australia

Re: CPU profiling

Postby uckelman » July 31st, 2020, 1:12 am

Thus spake Flint1b:
>
> Would it be possible to just put these traits with their properties into
> a list?

O(n) access is not the best you can do for this. A map giving O(1) access
would be better.

Go reread the post I linked to further up this thread. It is possible and
I did some of the design work for it about 10 years ago.

> Something like this:
>
>
> Code:
>
> interface TraitProperty {
> String getName();
> T getValue();
> }
>
> interface Trait {
> String getName();
> List> getTraitProperties();
> }
>
> interface GamePiece {
> List getTraits();
> Object getTraitPropertyValue(String traitName, String
> traitPropertyName);
> }

You'll find something similar to this in the VASSAL.property package
already.

> Or with classes or enums instead of String traitName..

Enums unfortunately don't work so well for this because custom traits
will need to define more properties.

> Why was the Decorator pattern chosen anyways, it's good for hiding
> what's inside from the outside world, why do traits need to hide the
> other traits underneath them?

It's not to hide the traits. The purpose of it is to build up the pieces
in a particular order, in layers. Order matters. E.g., a rotation trait
rotates what's inner with respect to it, so moving it in the order rotates
different stuff.

This is ok-ish as a design concept for module designers for thinking about
how pieces are assembled, but it's not a good idea to have the code directly
mirror that. It was really easy for Rodney to implement initially, and I
imagine that he never expected anyone to have traits more than a few deep.

--
J.
User avatar
uckelman
Site Admin
 
Posts: 9014
Joined: December 10th, 2007, 9:48 am
Location: Durham, England

Re: CPU profiling

Postby Brent Easton » July 31st, 2020, 1:19 am

If you get to the bottom and BasicPiece doesn't have the property, then nothing
does and a null gets returned.


If BasicPiece doesn't have the property, then it passed to the Current Zone to resolve as a zone property, then to the Current Map to resolve as a Map level property, then to the GameModule to resolve as a top-level Global Property.

So,

1. Global Properties are resolved on GamePieces by first searching the full trait stack. There's a real low-hanging fruit. The only advantage of searching through the trait stack for them is if a trait 'over-rides' a Global Property name for some reason. This would normally be a bug.

2. There are a large number of properties satisfied by BasicPiece that will greatly benefit from Joel's approach.

3. BasicPiece also has a scratch-pad HashMap for property storage. Any SetProperty call that reaches BasicPiece stores into this HashMap. These property values are ephemeral and are not encoded in the GameState. This HashMap is used by several traits for temporary storage and also by the map-level GUI to store some state. The SELECTED property used to be stored here, but years ago I did some work to store it in the top-most Decorator as it is essentially a 'global' variable for the GamePiece. You will see some special code handling for this in Decorator that may need to be reworked into the new scheme.

4. There are some properties that have no 'home', but are built up piece by piece from all traits. PieceName, visibleState

Rgds.
User avatar
Brent Easton
 
Posts: 3229
Joined: December 21st, 2007, 3:06 am
Location: Berry, NSW, Australia

Re: CPU profiling

Postby Flint1b » July 31st, 2020, 9:57 am

Well you know the internals better than I do, and figured out the improvements. Let's get working. Can I help somehow?
User avatar
Flint1b
 
Posts: 461
Joined: May 19th, 2020, 12:27 am
Location: Colonia Agrippina

Re: CPU profiling

Postby uckelman » July 31st, 2020, 10:41 am

Let me type up a description of what needs to be done later today. This is a task where a similar change will be applied to each class which implements GamePiece, but it's entirely internal to each of those classes and won't affect their behavior---so the bulk of the changes can be done in parallel and we could split them up and not step on each others' toes.
User avatar
uckelman
Site Admin
 
Posts: 9014
Joined: December 10th, 2007, 9:48 am
Location: Durham, England

Re: CPU profiling

Postby uckelman » July 31st, 2020, 8:39 pm

Here's a sketch of what we need to do for flattening GamePiece property access:

Code: Select all
// We're turning get/set for each property into lambdas, so we need a
// single-method interface for each
interface PropertyGetter {
  Object get(Object key);
};

interface PropertySetter {
  void set(Object key, Object value);
}

// Add to GamePiece:

  java.util.Map<String, PropertyGetter> getPropertyGetter();
  java.util.Map<String, PropertySetter> getPropertySetter();

// Implementation for Decorator

  // It would be great if this could be a constant static map
  // with the accessors and lambdas having an argument for the piece;
  // that way, we could have one of these per class rather than one per
  // instance. Unfortunately, if we're going to use the accessors for
  // direct access, we need with them the trait which they will access,
  // so one per instance looks necessary.
  //
  // It would also be great if we could have ONE map rather than two,
  // but unfortunately there are some properties where the get and set
  // are not at the same level. Which may be necessary, or may be something
  // we can rectify.

  // The contents of lgmap are extracted from the old getProperty();
  // "l" is for "local". It's proably useful to compare the contents of this
  // map with what's in Decorator.getProperty() now, as that's the
  // source of it.
  private final java.util.Map<Object, PropertyGetter> lgmap = java.util.Map.ofEntries(
    java.util.Map.entry(
      Properties.KEY_COMMANDS,
      k -> getKeyCommands();
    ),
    java.util.Map.entry(
      Properties.INNER,
      k -> piece
    ),
    java.util.Map.entry(
      Properties.OUTER,
      k -> dec
    ),
    java.util.Map.entry(
      Properties.VISIBLE_STATE,
      k -> myGetState() + piece.getProperty(Properties.VISIBLE_STATE),
    ),
    java.util.Map.entry(
      Properties.SELECTED,
      k -> selected
    )
  );

  // Isn't it annoying that the best name for one of the items we deal with
  // is "map" when the interface is also called "Map"?

  private final PropertyGetter default_getter = k -> piece.getProperty(k);

  // The contents of lsmap are extracted from the old setProperty()
  private final java.util.Map<Object, PropertySetter> lsmap = java.util.Map.ofEntries(
    java.util.Map.entry(
      Properties.INNER,
      (k, v) -> setInner(v)
    ),
    java.util.Map.entry(
      Properties.OUTER,
      (k ,v) -> dec = (Decorator) v
    ),
    java.util.Map.entry(
      Properties.SELECTED,
      (k, v) -> {
        setSelected(v instanceof Boolean ? v : false);
        piece.setProperty(Properties.SELECTED, v);
      }
    )
  );

  private final PropertySetter default_setter = (k, v) -> piece.setProperty(k, v);

  // getPropertyGetters(), getPropertySetters() should return a modifiable
  // map (i.e., NOT lgmap, lsmap which are unmodifiable) so that we can add to the
  // map from the bottom up:

  public java.util.Map<Object, PropertyGetters> getPropertyGetters() {
    java.util.Map<Object, PropertyGetters> m = piece.getPropertyGetters();
    m.putAll(lgmap);
    return m;
  }

  public java.util.Map<Object, PropertySetters> getPropertySetters() {
    java.util.Map<Object, PropertySetters> m = piece.getPropertySetters();
    m.putAll(lsmap);
    return m;
  }

  // Anything which is terminal (I think that's only BasicPiece, all the
  // other GamePieces should be Decorators?) would implement it like this:
 
  public java.util.Map<Object, PropertyGetter> getPropertyGetters() {
    return new HashMap<>(lgmap);
  }

  public java.util.Map<Object, PropertySetter> getPropertySetters() {
    return new HashMap<>(lsmap);
  }

  // This will work for property access, but won't do any flattening:
  // It might still be faster, though, since the lookups at each stage
  // are O(1) instead of O(n)---that depends on what the constant is...

  private java.util.Map<Object, PropertyGetter> gmap = getPropertyGetters();
  private java.util.Map<Object, PropertySetter> smap = getPropertySetters();

  public Object getProperty(Object key) {
    return gmap.getOrDefault(key, default_getter).get(key);
  }

  public void setProperty(Object key, Object val) {
    smap.getOrDefault(key, default_setter).set(key, val);
  }

  // So... for flattening property access.
  //
  // The outermost trait must use the maps returned by getPropertyGetters()
  // and getPropertySetters() to get and set properties. That's the point
  // of all of this and how we achieve flat property access.
  //
  // We _could_ store the result of getPropertyGetters() and
  // getPropertySetters() at each level, but that is potentially massively
  // expensive in memory---it's quadratic in the number of properties in a
  // trait stack. Hence, it would be better not to do that. This is the tricky
  // bit, and I'm not entirely sure of the best way.
  //
  // The following bit of code would work so long as we could be sure it ran
  // only after the whole trait stack was constructed:
 
  if (this == getOutermost(this)) {
    // we are the top of the stack, resolve properties using the flat maps
    gmap = getPropertyGetters();
    smap = getPropertySetters();
  }
  else {
    // we are an inner trait, resolve properties using our local map
    gmap = lgmap;
    smap = lsmap;
  }

  // As I said, I'm not certain where precisely this should go, but there
  // will be a suitable place somewhere, or perhaps a slightly different
  // method---e.g., if we had a new pass-through trait that did nothing but
  // served as the top-level wrapper, that class could do the job. I don't
  // know what will be simplest.

It should be possible to convert all the getProperty() and setProperty() methods in the classes which implement GamePiece fairly straightforwardly and without much risk of breakage.
User avatar
uckelman
Site Admin
 
Posts: 9014
Joined: December 10th, 2007, 9:48 am
Location: Durham, England

Re: CPU profiling

Postby Flint1b » July 31st, 2020, 9:16 pm

I think I understand this, roughly.

Do you want to start a draft PR and implement the main structure and I'll help by filling in the implementation in the various trait classes?

About the naming, can we use regular Java syntax i.e. camelCase, getterMap setterMap localGetterMap localSetterMap instead of gmap smap lgmap lsmap and C-style "variable_name"?
User avatar
Flint1b
 
Posts: 461
Joined: May 19th, 2020, 12:27 am
Location: Colonia Agrippina

PreviousNext

Return to Developers

Who is online

Users browsing this forum: No registered users and 2 guests