[Freecol-developers] lifetime of Map object

[Enrico Weigelt, metux IT consult]

Hi folks,


I'm currently reworking the (per-player) visibility map, by
a) doing it (mostly) lockless
b) using BitSet instead of the huge boolean array
c) encapsulating the whole logic into an own class

As it obviously needs the map dimensions (coming from the Map
object), I'm wondering whether these dimensions can change -
or the map object being replaced - after a player is initialized
(dont wanna call getGame().getMap() all the time)

So, could anyone give me some insight, when a Map is created
or dimensions can be changed ?

By the way: I'm a bit confused by Tile::isExplore() ... is that
method only valid on client side, assuming a Tile instance is
only used within context of a specific player ?


--mtx

[Michael T. Pope]

On Fri, 9 Dec 2016 00:28:29 +0100

Post by Enrico Weigelt, metux IT consult
I'm currently reworking the (per-player) visibility map, by
a) doing it (mostly) lockless
b) using BitSet instead of the huge boolean array
c) encapsulating the whole logic into an own class

(c) is obviously a win in terms of making things easier to read. The other
two are nice, but I doubt the existing locking is a serious problem, and
equally doubt that there is a huge win in going to a bitset. Can you
benchmark the bitset change? I have seen cases where it was slower.

Post by Enrico Weigelt, metux IT consult
As it obviously needs the map dimensions (coming from the Map
object), I'm wondering whether these dimensions can change -
or the map object being replaced - after a player is initialized

The map dimensions should be fixed after the game is generated. Note
though that the Game (and thus Map) gets replaced on reconnect (trunk is
currently broken due to this:-).

Post by Enrico Weigelt, metux IT consult
(dont wanna call getGame().getMap() all the time)

I doubt there is much choice. I recommend just calling it once at
the top of major routines.

Post by Enrico Weigelt, metux IT consult
By the way: I'm a bit confused by Tile::isExplore() ... is that
method only valid on client side

Correct. The type will always be non-null on the server side, but
exploration is only meaningful with respect to a European player.

Post by Enrico Weigelt, metux IT consult
assuming a Tile instance is
only used within context of a specific player ?

Not sure what you are saying there. Beware of Tile. The whole cached
tile structure confuses me regularly and I wrote it.

Cheers,
Mike Pope

[Enrico Weigelt, metux IT consult]

On 09.12.2016 06:24, Michael T. Pope wrote:

Hi,

Post by Michael T. Pope
(c) is obviously a win in terms of making things easier to read. The other
two are nice, but I doubt the existing locking is a serious problem,

not sure whether it's actually problem (IOW: notable slowdown), but we
for now require a lock on each canSee() call, which probably happens a
lot, eg. for each visible tile on repaint. (haven't seen a lag within
painting yet, but moving the map can take up to a second on my box)

Post by Michael T. Pope
and equally doubt that there is a huge win in going to a bitset.

I've read some people reporting a boolean array faster than a BitSet
(and ASF folks have an own implementation which they claim to be
way faster than BitSet for *very large* sets). OTOH, Android folks
(which are very concerned about optimizations) advice against such
boolean arrays.

But: with this array approach, we at least need two derefs and array
lookups for each access (as java doesn't have real multi-dimensional
arrays, but just arrays of arrays instead) - at least we should
linearize it.

OTOH, this big array of array blows up the required memory on a
factor of 32 or even 64, thus quickly polluting the cache - and just
wasting memory.

My new implementation also does several other optimizations, eg:

* directly operating on the tile array instead the (per tile) predicate
callbacks by Map::forEachTile() (no fog of war mode)
* direct list iterations instead of series of stream operations,
which cause not just allocations, but lots of (per tile) callbacks

https://github.com/oss-qm/freecol/commit/fba5e15659bced0f5a4a7f96318dc23193449833

Post by Michael T. Pope
Correct. The type will always be non-null on the server side, but
exploration is only meaningful with respect to a European player.

Okay, where's the exploration information maintained on server side ?
Does the client only get explored tiles from server ?


--mtx

[Michael T. Pope]

On Fri, 9 Dec 2016 07:36:13 +0100

Post by Enrico Weigelt, metux IT consult
not sure whether it's actually problem (IOW: notable slowdown), but we
for now require a lock on each canSee() call, which probably happens a
lot, eg. for each visible tile on repaint.

Actually I did not think the map display was calling canSee(), but it
does, albeit only per Unit, not per Tile. That would be a good place for
lock removal. AFAICT it is only contending with the main client thread
that is processing updates from the server, but I could be wrong there.

Post by Enrico Weigelt, metux IT consult
I've read some people reporting a boolean array faster than a BitSet

I have seen code where it was actually measured. However, that was
several years ago in a Java version far away. New figures would be
convincing.

Post by Enrico Weigelt, metux IT consult
(and ASF folks have an own implementation which they claim to be
way faster than BitSet for *very large* sets). OTOH, Android folks
(which are very concerned about optimizations) advice against such
boolean arrays.

I think it is memory consumption that the Android folks are (rightly) much
more worried about. More worried than us anyway (for now).

Post by Enrico Weigelt, metux IT consult
But: with this array approach, we at least need two derefs and array
lookups for each access (as java doesn't have real multi-dimensional
arrays, but just arrays of arrays instead) - at least we should
linearize it.

Agreed that swapping a multiply for a memory lookup is probably faster.
But no, I disagree that we *should* do this, *unless* it really is a
problem *and* the new code is significantly faster. Neither of these
conditions is clearly the case.

Post by Enrico Weigelt, metux IT consult
Okay, where's the exploration information maintained on server side ?

On the server side every Tile contains a map of Player to
player-view-of-the-Tile (Tile.cachedTiles). This is necessary so that if a
player sees some map feature (e.g. a settlement), then loses sight of it,
and then the feature changes (e.g. the settlement is destroyed), the server
still has enough information to continue to inform the player about the
*old* state of the tile, until such time as the player regains visibility
of the changed tile.

Post by Enrico Weigelt, metux IT consult
Does the client only get explored tiles from server ?

The client gets *everything* from the server. Unexplored tiles are
skeletal (just id,x,y IIRC), other tiles are either the current full
correct state of the tile including units (if visible to the player), or
the last view of the tile (if not visible).

Cheers,
Mike Pope

[Enrico Weigelt, metux IT consult]

Post by Michael T. Pope
Actually I did not think the map display was calling canSee(), but it
does, albeit only per Unit, not per Tile.

hmm, what is that flag actually used for ? all the tiles a player can
see (IOW: has been explored) or just changes in these tiles (eg. moving
enemies, etc) ?

Post by Michael T. Pope
That would be a good place for
lock removal. AFAICT it is only contending with the main client thread
that is processing updates from the server, but I could be wrong there.

my implementation only holds the lock while the visibility map is
recomputed, so IMHO we should keep that lock there, just in case any
other thread might cause that (IOW: calls canSee()).

Post by Michael T. Pope

Post by Enrico Weigelt, metux IT consult
I've read some people reporting a boolean array faster than a BitSet

I have seen code where it was actually measured. However, that was
several years ago in a Java version far away. New figures would be
convincing.

BitSets are kinda case that calls for a heavy machine specific
optimization, so I'd be surprised if they didn't invest more resources
into that.

Do we have some realistic workload example for a measurement ?

Post by Michael T. Pope

Post by Enrico Weigelt, metux IT consult
(and ASF folks have an own implementation which they claim to be
way faster than BitSet for *very large* sets). OTOH, Android folks
(which are very concerned about optimizations) advice against such
boolean arrays.

I think it is memory consumption that the Android folks are (rightly) much
more worried about. More worried than us anyway (for now).

Isn't there an android port ?

Post by Michael T. Pope
On the server side every Tile contains a map of Player to
player-view-of-the-Tile (Tile.cachedTiles). This is necessary so that if a
player sees some map feature (e.g. a settlement), then loses sight of it,
and then the feature changes (e.g. the settlement is destroyed), the server
still has enough information to continue to inform the player about the
*old* state of the tile, until such time as the player regains visibility
of the changed tile.

Do we really need an extra hashtable for each individual tile ?
Wouldn't it be even more logical to have one per player ?
(by the way would make killing a bit less complex)

Post by Michael T. Pope

Post by Enrico Weigelt, metux IT consult
Does the client only get explored tiles from server ?

The client gets *everything* from the server. Unexplored tiles are
skeletal (just id,x,y IIRC), other tiles are either the current full
correct state of the tile including units (if visible to the player), or
the last view of the tile (if not visible).

where does the ID come from and what it is exactly used for ?
isnt the coordinates just enough ?


--mtx

[Michael T. Pope]

On Fri, 9 Dec 2016 10:35:11 +0100

Post by Enrico Weigelt, metux IT consult

Post by Michael T. Pope
Actually I did not think the map display was calling canSee(), but it
does, albeit only per Unit, not per Tile.

hmm, what is that flag actually used for ? all the tiles a player can
see (IOW: has been explored) or just changes in these tiles (eg. moving
enemies, etc) ?

If by "that flag" you mean the contents of canSeeTiles[][], it is not
concerned with exploration, but with visibility. They are not the same
thing, although visible => explored. I am not sure I understand what you
are asking here.

Post by Enrico Weigelt, metux IT consult
my implementation only holds the lock while the visibility map is
recomputed,

Odd. Why is that an improvement? The current code only holds the lock
when actually switching the map over to the new version, which is
*much* smaller window than the duration of a map recomputation.

Post by Enrico Weigelt, metux IT consult
BitSets are kinda case that calls for a heavy machine specific
optimization, so I'd be surprised if they didn't invest more resources
into that.
Do we have some realistic workload example for a measurement ?

My standard regression test is 10 rounds of a 7-AI game played to 1700 on
two different maps, followed by a single round per map but with a complete
save-reload at each turn. This is not "realistic" in that there are no
human players, but it approaches repeatability. I accumulate averages of
several game parameters. One of these is turn speed. If you have
self-contained patches (i.e. just the bitset cutover, or just the lock
removal) then I can run an A-B test. It is however more customary for the
proponent of a change to produce the evidence that it is merited:-).

Post by Enrico Weigelt, metux IT consult

Post by Michael T. Pope
I think it is memory consumption that the Android folks are (rightly) much
more worried about. More worried than us anyway (for now).

Isn't there an android port ?

Not by us. Someone apparently hacked something together but never
contributed any code back again. It would be nice to do a proper Android
port, but as usual, major bugfixes are more important. Also, my eyesight
is bad enough already, so I am in no rush to play FreeCol on a phone!

Post by Enrico Weigelt, metux IT consult
Do we really need an extra hashtable for each individual tile ?
Wouldn't it be even more logical to have one per player ?
(by the way would make killing a bit less complex)

Perhaps, in hindsight. However keeping it all in Tile keeps all the
complex code in one place rather than spreading it out into Player.
Maintainability is important. Note also that Tile caches are created on
demand, so they only exist for tiles that have been explored by a European
player. At least in the beginning this is much less storage than outright
allocating a Map per European Player. You know I am going to say this,
but, I will need convincing that there is a problem here.

Post by Enrico Weigelt, metux IT consult
where does the ID come from and what it is exactly used for ?
isnt the coordinates just enough ?

All FreeColObjects have an id. It is fundamental. See Game.java.

Cheers,
Mike Pope