Page 2 of 3
Re: [Patch] Improve large map creation speed
Posted: 15 Feb 2014 13:08
by 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.
Re: [Patch] Improve large map creation speed
Posted: 15 Feb 2014 20:37
by 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).
Re: [Patch] Improve large map creation speed
Posted: 15 Feb 2014 21:05
by Eddi
sounds like you're using the wrong metric
Re: [Patch] Improve large map creation speed
Posted: 15 Feb 2014 23:34
by HackaLittleBit
- hit.PNG (5.5 KiB) Viewed 2428 times
I think this is what rubidium means.
Your algoritm can indicate town (town2) that is 'not' closest town (town1) centre.
Re: [Patch] Improve large map creation speed
Posted: 16 Feb 2014 02:23
by 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.
Re: [Patch] Improve large map creation speed
Posted: 16 Feb 2014 11:00
by 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.
Re: [Patch] Improve large map creation speed
Posted: 16 Feb 2014 14:07
by 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.
Re: [Patch] Improve large map creation speed
Posted: 16 Feb 2014 14:29
by 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.
MJP wrote: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.
Re: [Patch] Improve large map creation speed
Posted: 16 Feb 2014 14:38
by 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.
Re: [Patch] Improve large map creation speed
Posted: 16 Feb 2014 14:58
by cirdan
MJP wrote: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).
MJP wrote: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.
Re: [Patch] Improve large map creation speed
Posted: 17 Feb 2014 16:59
by 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
: in r2 of tile indexer: added comments, renamed variables and functions.
EDIT2: forgot to call ResetIndex() in Load_TOWN() => r3
Re: [Patch] Improve large map creation speed
Posted: 20 Feb 2014 21:41
by 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.
Re: [Patch] Improve large map creation speed
Posted: 21 Feb 2014 16:49
by MJP
cirdan wrote: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).
cirdan wrote: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.
cirdan wrote: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.
cirdan wrote: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.
cirdan wrote: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
Re: [Patch] Improve large map creation speed
Posted: 21 Feb 2014 22:44
by cirdan
MJP wrote: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.
Re: [Patch] Improve large map creation speed
Posted: 22 Feb 2014 20:25
by MJP
cirdan wrote: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.
Re: [Patch] Improve large map creation speed
Posted: 22 Feb 2014 23:54
by 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.
Re: [Patch] Improve large map creation speed
Posted: 23 Feb 2014 00:00
by 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)
Re: [Patch] Improve large map creation speed
Posted: 23 Feb 2014 10:02
by cirdan
MJP wrote: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.
Re: [Patch] Improve large map creation speed
Posted: 23 Feb 2014 12:34
by MJP
cirdan wrote:MJP wrote: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
girth wrote: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.
Re: [Patch] Improve large map creation speed
Posted: 23 Feb 2014 17:08
by cirdan
MJP wrote: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).