[Patch] Improve large map creation speed

[Rubidium]

Even though the 04 patch seems to significantly improve performance, it doesn't yield the same results. For example, the patch says that a town that is 57 tiles away is "closer" than one at 32 tiles. Or at least with the currently standing definition of "location of town" is "location of label".

To me it seems odd that by adding (funding) towns I can change the closest town of a particular tile, assuming the funded towns aren't near that particular tile. After all, more towns means smaller check radius after which one falls back onto the old algorithm.

[MJP]

I think a proper initialization of variable "best" should fix the problem.

If variable "best" is not initialized with the zone_check_radius (d1), the
function can return a town with a distance of d3 from the reference tile though
a town with only d2 exists (but is slightly out of the zone, represented as the
red square).

[Eddi]

sounds like you're using the wrong metric

[HackaLittleBit]

hit.PNG (5.5 KiB) Viewed 2406 times

I think this is what rubidium means.
Your algoritm can indicate town (town2) that is 'not' closest town (town1) centre.

[MJP]

Before, the red square was processed; with the problem of d2 being discarded due
to d3 potentially found first.

Searching the grey circle is OK (the purpose of initializing variable "best" with
the radius value).

Then the probability concerns all the tiles in the red square, so reducing the
area modifies it. But there is a 25% increase of zone_check_radius already.
I think it compensates enough so that things are correct.

[cirdan]

This patch is wrong, for the same reason that r26311 is, even if that one made it to trunk: it checks for houses, not towns. I wonder if it was really intended to change behaviour in openttd trunk so as to allow to found a town right next to another one, if you first bulldoze every building in that other town and there are more than 400 towns on the map, which is a highly non-obvious condition.

[MJP]

Oooh! I finally understand that GetTileType(Town::Get(whatever)->xy) may return
something else than MP_HOUSE. Thank you all for your explanations and patience

So unless CanDeleteHouse() forbids to clear the town center tile, the zone check
approach can be used only when the world is generated, which is where speed is
most wanted.

I'm still asserting the town center is at the center (or at least of type MP_HOUSE)
when a town has just been created.

[cirdan]

This is much better, but can still fail in corner cases, if a town cannot spawn a house at all, even during world generation.

Oooh! I finally understand that GetTileType(Town::Get(whatever)->xy) may return
something else than MP_HOUSE. Thank you all for your explanations and patience

So unless CanDeleteHouse() forbids to clear the town center tile, the zone check
approach can be used only when the world is generated, which is where speed is
most wanted.

I'm still asserting the town center is at the center (or at least of type MP_HOUSE)
when a town has just been created.

Err, no. In fact, the town center is always a road upon creation.

[MJP]

I just changed a few lines:

Code: Select all

				if (GetTileOwner(atile) == OWNER_TOWN) {
					const TileType tt = GetTileType(atile);
					if (tt == MP_HOUSE || tt == MP_ROAD) {
						Town *t = Town::GetByTile(atile);

EDIT: forgot limitation of use of GetTileOwner()... this is not good at all
EDIT2: proper use of GetTileOwner() in attached patches.

But Eddi suggested using a hashtable, it could be way faster, have to test to tell.

[cirdan]

I just changed a few lines:

Code: Select all

				if (GetTileOwner(atile) == OWNER_TOWN) {
					const TileType tt = GetTileType(atile);
					if (tt == MP_HOUSE || tt == MP_ROAD) {
						Town *t = Town::GetByTile(atile);

That is bound to trigger an assertion sooner than you expect, because GetTileOwner cannot be used on house or industry tiles (src/tile_map.h:156).

The real problem here is that there is absolutely no way to detect the centre of a town by looking at the map array. Usually there are some houses, and almost always there is a piece of road, but you cannot count on that (see some openttdcoop games where a town is completely obliterated to make room for a station).

But Eddi suggested using a hashtable, it could be way faster, have to test to tell.

I too think this is the way to go; divide the map into squares of 8×8 tiles or so, and store which towns are at each of these squares. Then you only have to retrieve the towns from a few of those slots and check their distances to the spot for the new town.

[MJP]

I wrote a tile indexer (CRTP style) to replace the faulty algorithm.

Map generation times are the same as before:

Code: Select all

r26348:
	4096*4096 -> 34 sec
	8192*4096 -> 72 sec
	8192*8192 -> 184 sec

r26348 with tileindexer:
	4096*4096 -> 31 sec
	8192*4096 -> 61 sec
	8192*8192 -> 136 sec

EDIT: in r2 of tile indexer: added comments, renamed variables and functions.
EDIT2: forgot to call ResetIndex() in Load_TOWN() => r3

[cirdan]

Code: Select all

template <typename Titem, uint Tindex_slice_width = 16>
class TileIndexer {
protected:
       TileIndex indexed_tile; ///< A copy of the indexed tile [...]
public:
       typedef std::map<TileIndex, Titem> MapSlice; ///< A slice is a portion of the map [...]
       static std::vector<MapSlice> slices;         ///< Store all slice startpoints in a vector.

Using static here may prove dangerous; if you ever happen to use this TileIndexer class in two different places but with the same template argument, they will inadvertently share this vector...

Also, you are only hashing along the X axis, so you will still have to iterate through full stripes of the map along the Y axis. Why not hash both axes?

Code: Select all

       static size_t item_count;                    ///< The number of referenced items in all the slices.

Is there a reason why you are adding this tileindex_count field, instead of using tileindex.size()?

Code: Select all

       static inline void AddToIndex(const TileIndex tile, Titem const item)

Here you are passing item by value. If Titem happens to be a large object, you will be needlessly copying it onto the stack, possibly invoking its copy constructor. Since you are not modifying item in the body of the function, a const reference would be better.

Code: Select all

/* Static variables of the TileIndexer class. */
template <typename Titem, uint Tindex_slice_width> size_t TileIndexer<Titem, Tindex_slice_width>::item_count;
template <typename Titem, uint Tindex_slice_width> std::vector<std::map<TileIndex, Titem>>
    TileIndexer<Titem, Tindex_slice_width>::slices;

This is untested, but I think that this definition here is bound to cause multiple definition errors at link time if you happen to include this header from two files and use TileIndexer with the same template parameter.

All in all, I think this is an overly complex implementation of what you want. Why not say something like

Code: Select all

template <typename T>
class TileIndexer : std::vector<std::vector<std::set<const T*> > > {
    // ...add suitable methods here...
    static inline add (TileIndex tile, const T *item)
    {
        // ...add item to bucket [TileX(tile) / 16][TileY(tile) / 16]...
    }
};

and then

Code: Select all

struct Town {
    // ...
    static TileIndexer<Town> indexer;
    // ...
};

This would better fit the conceptual model of what you want.

[MJP]

Also, you are only hashing along the X axis, so you will still have to iterate through full stripes of the map along the Y axis. Why not hash both axes?

TileIndex are already ordered on Y so all the wanted TileIndex are contiguously
arranged. One key search with lower_bound() followed by simple iterations til
the upper key is reached is not iterating through the full subset (but calling
upper_bound() like I did is not needed so I removed it).

Is there a reason why you are adding this tileindex_count field, instead of using tileindex.size()?

tileindex_count is the sum of all the slice sizes. tileindex.size() does not
exist, I assume you mean the size of the first vector but the number of slices
is just something else.

Here you are passing item by value.

No. Town* is used in TownTileIndexer definition. Therefore const references are
passed.

I can't get to pass a templatized invalid return value to GetClosestItemFromTile()
so I've forced the * in the template definition.

This is untested, but I think that this definition here is bound to cause multiple definition errors at link time if you happen to include this header from two files and use TileIndexer with the same template parameter.

Good point. More reliability can't hurt. I modified the patch accordingly.

class TileIndexer : std::vector<std::vector<std::set<const T*> > >

I wasn't aware that these components were derivable.

All in all, I like how the patches are challenged here

[cirdan]

TileIndex are already ordered on Y so all the wanted TileIndex are contiguously
arranged. One key search with lower_bound() followed by simple iterations til
the upper key is reached is not iterating through the full subset (but calling
upper_bound() like I did is not needed so I removed it).

Fair enough.

However, why are you using std::map<TileIndex, Titem*>? You are never trying to look up a town by tile, so std::set<Titem*> should do, as you can retrieve the town tile through t->xy. (If you are worried that this loses generality, because it forces Titem to have an xy field, you can add a template argument TileIndex T::*field, or a get method.) This does require you to use a custom Compare function to std::set though (to compare the town tiles instead of their pointers).

And a minor nit:

Code: Select all

       if (MapSizeX() % Tindex_slice_width != 0) new_sz++;

MapSizeX() is always a power of 2 and at least 64 (see map.cpp and map_func.h), so you can remove this line, or substitute an assert, to be sure, unless you plan to support Tindex_slice_with values which are not powers of 2.

[MJP]

However, why are you using std::map<TileIndex, Titem*>? You are never trying to look up a town by tile, so std::set<Titem*> should do, as you can retrieve the town tile through t->xy. (If you are worried that this loses generality, because it forces Titem to have an xy field, you can add a template argument TileIndex T::*field, or a get method.) This does require you to use a custom Compare function to std::set though (to compare the town tiles instead of their pointers).

From a library point of view, I do not assume that the Titem has a TileIndex. And the field used as a key being the right one makes it easy to understand how the indexer works. Using a set may eventually complicate a new use of this lib. As I can't imagine the context of an eventual reuse, I prefer the most simple and flexible approach.

[girth]

Given I've been looking at tree generation, does it factor into the large map creation times at all?
The code is a little too hit and miss, where it just keeps attempting to place trees, even though there's the probability the tile is already populated with a tree. An indexing system would be great, I think.
But if it doesn't really take that much time when generating a large map, optimisation might not be necessary.

[Eddi]

errr... what exactly are you trying to achieve? if placing a random tree, filter first for tiles that can actually grow a tree? doesn't sound very fast at all.

(but if you were trying to write such a function, please apply it to rail tiles and use that to make a uniform distribution to select the place to land for a large UFO)

[cirdan]

From a library point of view, I do not assume that the Titem has a TileIndex. And the field used as a key being the right one makes it easy to understand how the indexer works. Using a set may eventually complicate a new use of this lib. As I can't imagine the context of an eventual reuse, I prefer the most simple and flexible approach.

Even then, you should be using std::set<std::pair<TileIndex, const Titem*> > instead of std::map<TileIndex, const Titem*>, because you are not doing any lookup of Titem by tile.

[MJP]

From a library point of view, I do not assume that the Titem has a TileIndex. And the field used as a key being the right one makes it easy to understand how the indexer works. Using a set may eventually complicate a new use of this lib. As I can't imagine the context of an eventual reuse, I prefer the most simple and flexible approach.

Even then, you should be using std::set<std::pair<TileIndex, const Titem*> > instead of std::map<TileIndex, const Titem*>, because you are not doing any lookup of Titem by tile.

I compared the 2 asm outputs of GetClosestItemFromTile(): absolutely no difference (I'm ignoring padding here).

So I'm a bit reluctant to get away from the map as I see a) lesser readable source code, b) RemoveFromIndex() requiring keeping track of the indexed item and c) no real difference in the binary.

At least, now I have an idea of how a map is implemented in the VS STL

Given I've been looking at tree generation, does it factor into the large map creation times at all?

The tree generation takes ~0.5% of the time took to generate a 8192*8192 map.

[cirdan]

b) RemoveFromIndex() requiring keeping track of the indexed item

Ah, yes, you are right. Removing an item from the indexer involves a lookup (by tile or by item pointer).