Merge lp:~widelands-dev/widelands/request_supply_opt into lp:widelands

[TiborB]

This is small redesign of delivery of wares to requestors.
1. Engine now evenly distributes wares to all warehouses that are preferred for this type of ware (in other words, ware goes to a warehouse with lower stock of the material/worker)
2. Engine now test supplies in order starting from nearest one. This itself should lead to lesser computation. Additionaly I implemented a treshold (now 5) that test only 5 nearest supplies. The goal is to reduce CPU usage, especially on big maps. Routing is very expensive on long maps.

This was discussed on forum and must be yet considered.

[GunChleoc (gunchleoc)]

Forum thread: https://wl.widelands.org/forum/topic/1856/

We still need to think about the threshold, but the rest of the code LGTM :)

This still needs testing, but I think we can wait with that until we have decided how to solve this.

[TiborB (tiborb95)]

Resubmit.

I removed controversial treshold, and added two features
a) if more wares (of the same type) on one flag, only one ware is considered
b) wares on ships are ignored. Routing is deceived because it considers port's flag as a actual location of ware/worker.

[bunnybot (widelandsofficial)]

Hi, I am bunnybot (https://github.com/widelands/bunnybot).

I am keeping the source branch lp:~widelands-dev/widelands/request_supply_opt mirrored to
  https://github.com/widelands/widelands/tree/_widelands_dev_widelands_request_supply_opt

The latest continuous integration build can always be found here:
  https://travis-ci.org/widelands/widelands/branches
Please do not merge without making sure that it passes.

You can give me commands by starting a line with @bunnybot <command>. I understand:
 merge: Merges the source branch into the target branch, closing the pull request.

[bunnybot (widelandsofficial)]

Travis build 119 has changed state to: failed. Details: https://travis-ci.org/widelands/widelands/builds/99743957.

[bunnybot (widelandsofficial)]

Travis build 162 has changed state to: created. Details: https://travis-ci.org/widelands/widelands/builds/99874912.

[bunnybot (widelandsofficial)]

Travis build 162 has changed state to: started. Details: https://travis-ci.org/widelands/widelands/builds/99874912.

[bunnybot (widelandsofficial)]

Travis build 162 has changed state to: errored. Details: https://travis-ci.org/widelands/widelands/builds/99874912.

[Tino (tino79)]

LGTM.
I cannot really quantify the performance gain, but i did not find any regression.

review: Approve

[bunnybot (widelandsofficial)]

Travis build 162 has changed state to: errored. Details: https://travis-ci.org/widelands/widelands/builds/99874912.

[SirVer (sirver)]

I think this is broken in the current state. The problem is that logic depends on available_supply which is a multimap. The problem is that the map is sorted by distance, then by a pointer.

In a replay or in a multiplayer games, the order of elements in this map is different, yielding therefore different routing results. This will desync the game.

Change the ordering to use a tie-breaker, for example the game object id before the pointer.

review: Needs Fixing

[bunnybot (widelandsofficial)]

Travis build 162 has changed state to: passed. Details: https://travis-ci.org/widelands/widelands/builds/99874912.

[TiborB (tiborb95)]

@SirVer

What about:

std::multimap<<uint32_t,uint32_t>, Supply*> available_supplies;

Where <uint32_t,int32_t> is <distance, serial>, serial should be the same across the network clients, I presume...

[SirVer (sirver)]

That should work - but I would suggest to make a tiny private struct to improve readability.

struct SupplyQuality {
   uint32 distance;
   uint32 serial;

   bool operator<(const SupplyQuality& other) const {
       return std::forward_as_tuple(distance, serial) < std::forward_as_tuple(other.distance, other.serial);
   }
}

[TiborB (tiborb95)]

Well I am not that skillful in C++, I want(ed) to use trivial:

bool operator() (const uint32_t & p1, const uint32_t & p2) const {
 return p1.distance == p2.distance ? p1.serial < p2.serial : p1.distance < p2.distance;
}

(not tested of course)

[TiborB (tiborb95)]

Oh, I just read about comparison of tuples, so I understand your example now, thanks..

[TiborB (tiborb95)]

@SirVer

I reworked it and testing it. I am not satisfied with performance though. Perhaps you know that I proposed a treshold (f.e. 5) that would check only 5 nearest (as crow fly) wares and pick a one from them. This could improve performance, but was rejected and currently is not in the code.

However I have another suggestion - let revive the treshold and X nearest wares are checked all, and from other wares only the ones that are in the warehouses. It used to be this way before AFAIK. I mean only wares in warehouses were used for delivery.

I currently test 512x512 map and after 5 hours it can barely run at 2x speed. I dont say that the routing is culprit but I believe it has its share...

I have not pushed new code yet.

[SirVer (sirver)]

[threshold]
I did not follow the discussion about the threshold though, on a quick thought I can see downsides to this approach. I suggest doing more timing analysis (with AI disabled) to figure out what actually takes time here and if there are ways of improving the situation.

> I dont say that the routing is culprit but I believe it has its share...

you have to proof that to make me believe it :). In my benchmarks about timing with the drawing code, AI is always dwarfing everything else in profiles, especially in longer games - but I rarely look at very large maps, so I'd need to proof what actually takes the most time too.

If you feel this approach is an improvement, how about we merge it soonish and then go back and try timing a large map with AI disabled to see what actually eats cycles.

[TiborB (tiborb95)]

So I made a bit of profiling, first of all it seems the game (drawing itself) takes quite a lot of CPU time - perhaps problem on my side? Tests run for 3 minutes of gameplay, but loading took also quite a bit of time (not counted in 3 minutes)....

But results:
I compared
1. trunk + crater (small map after 45 min)
2. trunk + Cristobals sea (512x512 after 4 hours)
3. request_supply_opt + Cristobals sea (512x512 after 4 hours)

I used savegames...

I picked only 3 functions here, look at second column (cummulative %)

trunk+crater:
[79] 1.8 0.00 0.17 4530 DefaultAI::think() [79]
[90] 1.6 0.00 0.14 37761 Widelands::Economy::_find_best_supply()
[94] 1.6 0.00 0.14 5494 Widelands::Economy::find_route()

trunk + big map (Cristobals sea)
[16] 22.8 0.00 8.43 105284 Widelands::Economy::find_route()
[24] 17.5 0.26 6.20 1145776 Widelands::Economy::_find_best_supply() [24]
[65] 3.8 0.02 1.38 22120 DefaultAI::think()

this branch + big map (Cristobals sea)
[20] 15.7 0.00 5.76 112254 Widelands::Economy::find_route()
[24] 14.8 0.39 5.06 1302844 Widelands::Economy::_find_best_supply()
[61] 4.3 0.00 1.59 33740 DefaultAI::think() [61]

My conclusions:
On big maps, _find_best_supply takes significant portion of CPU time, many fold then AI.
My changes as they are now, brings reduction about 20% of _find_best_supply and about 35% of find_route() + on big maps.

I believe implementing a treshold would help to further reduction.....

[SirVer (sirver)]

> So I made a bit of profiling, first of all it seems the game (drawing itself) takes quite a lot of CPU time - perhaps problem on my side?

No, that is accurate. The render_queue branch makes this already better, but only a full texture_atlas will make this really fast. I picked up working on this today again.

The threshold will at most cut the time in half for find_best_supply if i understood correctly. How much will that actually buy us? I suggest getting the change in as is without the threshold - as it should be correct in all cases and then experiment on threshold or even completely different approaches. Let us know if you think it is ready for another look.

[TiborB (tiborb95)]

> The threshold will at most cut the time in half for find_best_supply if i understood correctly.

I dont think there is mathematical reason for 'half' but if it was half it would be great....

It depends on number of supplies - if supplies count<=treshold - no change at all. Or rather - savings depend on the size of player's teritorry/economy....

I did some changes today so you can look at the code again now

[SirVer (sirver)]

code lgtm now. A couple of minor nits, feel free to merge after addressing these.

review: Approve

[TiborB (tiborb95)]

Added a comment to your comment, see in diff

[TiborB (tiborb95)]

@SirVer

I incorporated your comments, with one exception, can I merge it?

[SirVer (sirver)]

Tibor, sure, go ahead and merge.

> I looked at other examples f.e. here: http://bazaar.launchpad.net/~widelands-dev/widelands/request_supply_opt/view/head:/src/economy/supply.h#L94 and everywhere it is done this way.

Ah, that is a philosophical question, really. Does local style trump global style? Should better paradigms be adapted peu-a-peu or in one big refactoring? There are many school of thoughts here. I think once you identified a better approach, you should start using it for new code and fix old code over time. Other people think that you should keep the old ways until you can change a full code base to new ways.

So there are really two questions for you here:

1) do you agree that passing mutable values by pointer is better than passing them by non-const reference? I find foo(&game) vs foo(game) a clear advantage for readability, so I'd say yes. This also follows the google style guide which I find a great reference of how and why to do things anyways. But you might disagree and I am in no position to enforce a 'true' widelands code style.

2) do you agree that new code should adopt new paradigms immediately at the cost of inconsistency in the code base or not?

As said, I answer yes to both questions, so I'd change the code to using a pointer. But it is entirely your call. I will not think any worse of you if you decide against changing the code :)

> Also note the 'const' at the end of line, does it not guarantee immutability of Game?

no, the const at the end of the line means that the object represented by 'this' cannot change, but does not say anything about the arguments of the method - they can change.

[TiborB (tiborb95)]

You are right, I will rework it, though I am not that good programmer so it is not as simple for me as for you. This is only reason why I opted to mimic the existing code.
But as there is no need to hurry with this branch so it can wait a bit again

[GunChleoc (gunchleoc)]

Changing a reference to a pointer can be a bit of a pain, but it isn't complex - the compiler will tell you if anything goes wrong, so you can't mess it up. What you need to do is change foo.bar to foo->bar within the function, and add & or * in front of foo when calling the function - I can never remember which symbol to use here, but the compiler will tell me :)

[TiborB (tiborb95)]

reworked, tested (not long time). Can you please look at it once more?

[SirVer (sirver)]

there are still NOCOM in the diff which need removing, otherwise lgtm.

review: Approve

[TiborB (tiborb95)]

Thanks!

@bunnybot merge

=== modified file 'src/economy/economy.cc'
--- src/economy/economy.cc	2015-11-11 09:52:55 +0000
+++ src/economy/economy.cc	2016-01-07 18:40:19 +0000
@@ -20,6 +20,7 @@
 #include "economy/economy.h"
 
 #include <memory>
+#include <unordered_set>
 
 #include <boost/bind.hpp>
 
@@ -664,14 +665,40 @@
 	Route  * best_route  = nullptr;
 	int32_t  best_cost   = -1;
 	Flag & target_flag = req.target_flag();
+	Map & map = game.map();
+
+	available_supplies.clear();
 
 	for (size_t i = 0; i < m_supplies.get_nrsupplies(); ++i) {
 		Supply & supp = m_supplies[i];
 
-		// Check requirements
+		// Just skip if supply does not provide required ware
 		if (!supp.nr_supplies(game, req))
 			continue;
 
+		const SupplyProviders provider = supp.provider_type(&game);
+
+		// We generally ignore disponible wares on ship as it is not possible to reliably
+		// calculate route (transportation time)
+		if (provider == SupplyProviders::kShip) {
+			continue;
+		}
+
+		const Widelands::Coords provider_position = supp.get_position(game)->base_flag().get_position();
+
+		const uint32_t dist = map.calc_distance(target_flag.get_position(), provider_position);
+
+		UniqueDistance ud = {dist, supp.get_position(game)->serial(), provider};
+
+		// std::map quarantees uniqueness, practically it means that if more wares are on the same flag, only
+		// first one will be inserted into available_supplies
+		available_supplies.insert(std::make_pair(ud, &m_supplies[i]));
+	}
+
+	// Now available supplies have been sorted by distance to requestor
+	for (auto& supplypair : available_supplies) {
+		Supply & supp = *supplypair.second;
+
 		Route * const route =
 			best_route != &buf_route0 ? &buf_route0 : &buf_route1;
 		// will be cleared by find_route()
@@ -685,11 +712,17 @@
 			 	 req.get_type(),
 			 	 best_cost))
 		{
-			if (!best_route)
-			log ("Economy::find_best_supply: Error, COULD NOT FIND A ROUTE!");
+			if (!best_route) {
+				log ("Economy::find_best_supply: Error, COULD NOT FIND A ROUTE!");
+				// To help to debug this a bit:
+				log (" ... ware at: %3dx%3d, requestor at: %3dx%3d!",
+					supp.get_position(game)->base_flag().get_position().x,
+					supp.get_position(game)->base_flag().get_position().y,
+					target_flag.get_position().x,
+					target_flag.get_position().y);
+			}
 			continue;
 		}
-
 		best_supply = &supp;
 		best_route = route;
 		best_cost = route->get_totalcost();
@@ -776,8 +809,9 @@
 		}
 
 		int32_t const priority = req.get_priority(cost);
-		if (priority < 0)
+		if (priority < 0) {
 			continue;
+		}
 
 		// Otherwise, consider this request/supply pair for queueing
 		RequestSupplyPair rsp;
@@ -825,8 +859,9 @@
 			rsps.nexttimer = 200;
 	}
 
-	if (rsps.nexttimer > 0) //  restart the timer, if necessary
+	if (rsps.nexttimer > 0) { //  restart the timer, if necessary
 		_start_request_timer(rsps.nexttimer);
+	}
 }
 
 
@@ -1037,12 +1072,30 @@
 
 		bool haveprefer = false;
 		bool havenormal = false;
+
+		// One of preferred warehouses (if any) with lowest stock of ware/worker
+		Warehouse * preferred_wh = nullptr;
+		// Stock of particular ware in preferred warehouse
+		uint32_t preferred_wh_stock = std::numeric_limits<uint32_t>::max();
+
 		for (uint32_t nwh = 0; nwh < m_warehouses.size(); ++nwh) {
 			Warehouse * wh = m_warehouses[nwh];
 			Warehouse::StockPolicy policy = wh->get_stock_policy(type, ware);
 			if (policy == Warehouse::SP_Prefer) {
 				haveprefer = true;
-				break;
+
+				// Getting count of worker/ware
+				uint32_t current_stock;
+				if (type == WareWorker::wwWARE) {
+					current_stock = wh->get_wares().stock(ware);
+				} else {
+					current_stock = wh->get_workers().stock(ware);
+				}
+				// Stocks lower then in previous one?
+				if (current_stock < preferred_wh_stock) {
+					preferred_wh = wh;
+					preferred_wh_stock = current_stock;
+				}
 			}
 			if (policy == Warehouse::SP_Normal)
 				havenormal = true;
@@ -1050,17 +1103,22 @@
 		if (!havenormal && !haveprefer && type == wwWARE)
 			continue;
 
-		Warehouse * wh = find_closest_warehouse
-			(supply.get_position(game)->base_flag(), type, nullptr, 0,
-			 (!haveprefer && !havenormal)
-			 ?
-			 WarehouseAcceptFn()
-			 :
-			 boost::bind
-				(&accept_warehouse_if_policy,
-				 _1, type, ware,
-				 haveprefer ? Warehouse::SP_Prefer : Warehouse::SP_Normal));
-
+		// We either have one preferred warehouse picked up or walk on roads to find nearest one
+		Warehouse * wh = nullptr;
+		if (preferred_wh) {
+			wh = preferred_wh;
+		} else {
+			wh = find_closest_warehouse
+				(supply.get_position(game)->base_flag(), type, nullptr, 0,
+				 (!havenormal)
+				 ?
+				 WarehouseAcceptFn()
+				 :
+				 boost::bind
+					(&accept_warehouse_if_policy,
+					 _1, type, ware,
+					 Warehouse::SP_Normal));
+		}
 		if (!wh) {
 			log
 				("Warning: Economy::_handle_active_supplies "

=== modified file 'src/economy/economy.h'
--- src/economy/economy.h	2015-11-11 09:52:55 +0000
+++ src/economy/economy.h	2016-01-07 18:40:19 +0000
@@ -31,6 +31,7 @@
 #include "logic/instances.h"
 #include "logic/warelist.h"
 #include "logic/wareworker.h"
+#include "economy/supply.h"
 #include "economy/supply_list.h"
 #include "ui_basic/unique_window.h"
 
@@ -184,6 +185,22 @@
 	void rebalance_supply() {_start_request_timer();}
 
 private:
+
+	// This structs is to store distance from supply to request(or), but to allow unambiguous
+	// sorting if distances are the same, we use also serial number of provider and type of provider (flag,
+	// warehouse)
+	struct UniqueDistance {
+		bool operator<(const UniqueDistance& other) const {
+       		return std::forward_as_tuple(distance, serial, provider_type)
+				<
+				std::forward_as_tuple(other.distance, other.serial, other.provider_type);
+		}
+
+		uint32_t distance;
+		uint32_t serial;
+		SupplyProviders provider_type;
+	};
+
 /*************/
 /* Functions */
 /*************/
@@ -237,6 +254,9 @@
 	static std::unique_ptr<Soldier> m_soldier_prototype;
 	UI::UniqueWindow::Registry m_optionswindow_registry;
 
+	// 'list' of unique providers
+	std::map<UniqueDistance, Supply*> available_supplies;
+
 	DISALLOW_COPY_AND_ASSIGN(Economy);
 };
 

=== modified file 'src/economy/idleworkersupply.cc'
--- src/economy/idleworkersupply.cc	2015-11-11 09:52:55 +0000
+++ src/economy/idleworkersupply.cc	2016-01-07 18:40:19 +0000
@@ -71,6 +71,11 @@
 	return true;
 }
 
+SupplyProviders IdleWorkerSupply::provider_type(Game *) const
+{
+	return SupplyProviders::kFlagOrRoad;
+}
+
 bool IdleWorkerSupply::has_storage() const
 {
 	return m_worker.get_transfer();

=== modified file 'src/economy/idleworkersupply.h'
--- src/economy/idleworkersupply.h	2015-11-11 09:52:55 +0000
+++ src/economy/idleworkersupply.h	2016-01-07 18:40:19 +0000
@@ -34,6 +34,7 @@
 	PlayerImmovable * get_position(Game &) override;
 
 	bool is_active() const override;
+	SupplyProviders provider_type(Game *) const override;
 	bool has_storage() const override;
 	void get_ware_type(WareWorker & type, DescriptionIndex & ware) const override;
 	void send_to_storage(Game &, Warehouse * wh) override;

=== modified file 'src/economy/supply.h'
--- src/economy/supply.h	2015-11-11 09:52:55 +0000
+++ src/economy/supply.h	2016-01-07 18:40:19 +0000
@@ -33,6 +33,8 @@
 class WareInstance;
 class Worker;
 
+enum class SupplyProviders {kWarehouse, kFlagOrRoad, kShip};
+
 /**
  * A Supply is a virtual base class representing something that can offer
  * wares of any type for any purpose.
@@ -57,6 +59,12 @@
 	virtual bool is_active() const = 0;
 
 	/**
+	 * Return the type of player im/movable where the ware is now (warehouse,
+	 * flag or ship).
+	 */
+	virtual SupplyProviders provider_type(Game *) const = 0;
+
+	/**
 	 * Indicates whether this supply is in storage or on its way to
 	 * storage.
 	 *

=== modified file 'src/economy/ware_instance.cc'
--- src/economy/ware_instance.cc	2015-12-28 10:08:39 +0000
+++ src/economy/ware_instance.cc	2016-01-07 18:40:19 +0000
@@ -55,6 +55,7 @@
 	//  implementation of Supply
 	PlayerImmovable * get_position(Game &) override;
 	bool is_active() const override;
+	SupplyProviders provider_type(Game *) const override;
 	bool has_storage() const override;
 	void get_ware_type(WareWorker & type, DescriptionIndex & ware) const override;
 	void send_to_storage(Game &, Warehouse * wh) override;
@@ -126,6 +127,16 @@
 	return true;
 }
 
+SupplyProviders IdleWareSupply::provider_type(Game* game) const
+{
+	MapObject * const loc = m_ware.get_location(*game);
+	if (is_a(Ship, loc)) {
+		return SupplyProviders::kShip;
+	}
+
+	return SupplyProviders::kFlagOrRoad;
+}
+
 bool IdleWareSupply::has_storage()  const
 {
 	return m_ware.is_moving();

=== modified file 'src/economy/warehousesupply.h'
--- src/economy/warehousesupply.h	2015-11-11 09:52:55 +0000
+++ src/economy/warehousesupply.h	2016-01-07 18:40:19 +0000
@@ -55,6 +55,7 @@
 	// Supply implementation
 	PlayerImmovable * get_position(Game &) override;
 	bool is_active() const override;
+	SupplyProviders provider_type(Game *) const override;
 	bool has_storage() const override;
 	void get_ware_type(WareWorker & type, DescriptionIndex & ware) const override;
 

=== modified file 'src/logic/warehouse.cc'
--- src/logic/warehouse.cc	2015-11-21 11:34:10 +0000
+++ src/logic/warehouse.cc	2016-01-07 18:40:19 +0000
@@ -183,6 +183,7 @@
 
 /// Warehouse supplies are never active.
 bool WarehouseSupply::is_active() const {return false;}
+SupplyProviders WarehouseSupply::provider_type(Game *) const {return SupplyProviders::kWarehouse;}
 
 bool WarehouseSupply::has_storage() const
 {