Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
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 :) -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
Review: Approve code lgtm now. A couple of minor nits, feel free to merge after addressing these. Diff comments: > === modified file 'src/economy/economy.cc' > --- src/economy/economy.cc2015-11-11 09:52:55 + > +++ src/economy/economy.cc2016-01-04 18:44:46 + > @@ -664,14 +665,45 @@ > 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; prefer UniqueDistance ud = { dist, ...get_serial(), provider }; if anybody ever adds more fields to UniqueDistance, this code will fail to compile (which is good!) while your old code might slip through unnoticed. > + ud.distance = dist; > + ud.serial = supp.get_position(game)->serial(); > + ud.provider_type = 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::pairSupply*>(ud, _supplies[i])); nit: insert(std::make_pair(ud, _supplies[i])) is a bit more readable imho > + > + } > + > + // Now available supplies have been sorted by distance to requestor > + for (auto& supplypair : available_supplies) { > + remove empty line? > + Supply & supp = *supplypair.second; > + > Route * const route = > best_route != _route0 ? _route0 : _route1; > // will be cleared by find_route() > @@ -700,6 +738,7 @@ > > cost = best_cost; > return best_supply; > + remove empty line? > } > > struct RequestSupplyPair { > > === modified file 'src/economy/economy.h' > --- src/economy/economy.h 2015-11-11 09:52:55 + > +++ src/economy/economy.h 2016-01-04 18:44:46 + > @@ -237,6 +238,24 @@ > static std::unique_ptr m_soldier_prototype; > UI::UniqueWindow::Registry m_optionswindow_registry; > > + // This structs is to store distance from supply to request(or), but to > allow unambiguous nit: I prefer to have the following ordering after private: types, functions, variables. Your call. > + // sorting if distances are the same, we use also serial number of > provider and type of provider (flag, > + // warehouse) > + struct UniqueDistance { > + uint32_t distance; > + uint32_t serial; > + SupplyProviders provider_type; > + > + 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); > + } > + }; > + // 'list' of unique providers > + std::map available_supplies; > + > + > DISALLOW_COPY_AND_ASSIGN(Economy); > }; > > > === modified file 'src/economy/idleworkersupply.cc' > --- src/economy/idleworkersupply.cc 2015-11-11 09:52:55 + > +++ src/economy/idleworkersupply.cc 2016-01-04 18:44:46 + > @@ -71,6 +71,11 @@ > return true; > } > > +SupplyProviders IdleWorkerSupply::provider_type(Game &) const nit: prefer to take mutable parameters (Game) as pointers - so that on the callsite it is immediately visible that game might be mutated. > +{ > + return SupplyProviders::kFlagOrRoad; > +} > + > bool IdleWorkerSupply::has_storage() const > { > return m_worker.get_transfer(); > > === modified file 'src/logic/widelands_geometry.h' > --- src/logic/widelands_geometry.h2014-09-19 12:54:54 + > +++ src/logic/widelands_geometry.h2016-01-04 18:44:46 + > @@ -55,6 +55,10 @@ > } > }; > > + uint32_t hash() const { seems unused? remove. > + return x << 16 | y; > + }; > + > // Move the coords to the 'new_origin'. > void reorigin(Coords new_origin, const Extent & extent); >
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
@SirVer I incorporated your comments, with one exception, can I merge it? -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
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() 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. -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
Added a comment to your comment, see in diff Diff comments: > > === modified file 'src/economy/idleworkersupply.cc' > --- src/economy/idleworkersupply.cc 2015-11-11 09:52:55 + > +++ src/economy/idleworkersupply.cc 2016-01-04 18:44:46 + > @@ -71,6 +71,11 @@ > return true; > } > > +SupplyProviders IdleWorkerSupply::provider_type(Game &) const 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. Also note the 'const' at the end of line, does it not guarantee immutability of Game? > +{ > + return SupplyProviders::kFlagOrRoad; > +} > + > bool IdleWorkerSupply::has_storage() const > { > return m_worker.get_transfer(); -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
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 -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
> 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 -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
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.80.000.174530 DefaultAI::think() [79] [90] 1.60.000.14 37761 Widelands::Economy::_find_best_supply() [94] 1.60.000.145494 Widelands::Economy::find_route() trunk + big map (Cristobals sea) [16]22.80.008.43 105284 Widelands::Economy::find_route() [24]17.50.266.20 1145776 Widelands::Economy::_find_best_supply() [24] [65] 3.80.021.38 22120 DefaultAI::think() this branch + big map (Cristobals sea) [20]15.70.005.76 112254 Widelands::Economy::find_route() [24]14.80.395.06 1302844 Widelands::Economy::_find_best_supply() [61] 4.30.001.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. -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
> 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. -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
[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. -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
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) -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
Oh, I just read about comparison of tuples, so I understand your example now, thanks.. -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
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); } } -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
Review: Approve LGTM. I cannot really quantify the performance gain, but i did not find any regression. -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
Review: Needs Fixing 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. -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/request_supply_opt. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
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. -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is requested to review the proposed merge of lp:~widelands-dev/widelands/request_supply_opt into lp:widelands. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp
[Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
TiborB has proposed merging lp:~widelands-dev/widelands/request_supply_opt into lp:widelands. Requested reviews: Widelands Developers (widelands-dev) For more details, see: https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 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. -- Your team Widelands Developers is requested to review the proposed merge of lp:~widelands-dev/widelands/request_supply_opt into lp:widelands. === modified file 'src/economy/economy.cc' --- src/economy/economy.cc 2015-11-11 09:52:55 + +++ src/economy/economy.cc 2015-12-10 20:19:31 + @@ -38,6 +38,9 @@ #include "logic/tribes/tribe_descr.h" #include "logic/warehouse.h" +// To speed up searching for nearest supply, we check only n nearest supplies +constexpr int kSuppliesToCheck = 5; + namespace Widelands { Economy::Economy(Player & player) : @@ -664,14 +667,38 @@ 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 uint32_t dist = map.calc_distance( + target_flag.get_position(), + supp.get_position(game)->base_flag().get_position()); + + // Inserting into 'queue' + if (available_supplies.count(dist) == 0) { + available_supplies[dist] = _supplies[i]; + } + } + + // Now available supplies are sorted by distance to requestor + // And we will check only first n (kSuppliesToCheck) from them + uint16_t counter = 0; + for (auto& supplypair : available_supplies) { + + if (++counter > kSuppliesToCheck) { + break; + } + + Supply & supp = *supplypair.second; + Route * const route = best_route != _route0 ? _route0 : _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 = best_route = route; best_cost = route->get_totalcost(); @@ -813,7 +846,7 @@ !_has_request(*rsp.request) || !rsp.supply->nr_supplies(game, *rsp.request)) { - rsps.nexttimer = 200; + rsps.nexttimer = 250; continue; } @@ -822,11 +855,12 @@ // for multiple wares if (rsp.request && _has_request(*rsp.request)) - rsps.nexttimer = 200; + rsps.nexttimer = 250; } - 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 +1071,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::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 +1102,22 @@ if (!havenormal && !haveprefer && type == wwWARE) continue; - Warehouse * wh = find_clos
Re: [Widelands-dev] [Merge] lp:~widelands-dev/widelands/request_supply_opt into lp:widelands
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. -- https://code.launchpad.net/~widelands-dev/widelands/request_supply_opt/+merge/280193 Your team Widelands Developers is requested to review the proposed merge of lp:~widelands-dev/widelands/request_supply_opt into lp:widelands. ___ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp