Cargodist code review

[fonso]

This topic is for specific questions and discussion about the cargodist code. I'll be using it to make the code review publicly visible. I'll start with Rubidium's questions. The ones I don't answer here have been answered by obvious code changes.

http://rbijker.net/openttd/cd/0000-Feat ... inks.patch

What if the loading time is huge (e.g. way too long train), is that going to trigger deadlocks?

Deadlock may be a bit unclear in this context.
The vehicle is going to some station and could load cargo also going to that station. However, if the vehicle has not visited the station yet, there might not be a link, yet. Thus we add the links here so that in the next link graph run (while the vehicle may still be loaded) cargo can be sent to the vehicle's next stop. This is unrelated to vehicle length or loading time.

No need for else if you return from the if statements.

The elses are there for clarity. I find that explicit depiction of alternatives much more readable. I'll change them for you, though.

What if this next yields NULL? In the 'true' case you explicitly check for it

GetNext never returns NULL if there is a valid station in the list. As the given "next" is already valid and a station in the list, we
don't have to check for NULL here.

In my opinion these averages should be removed when a station is removed, not when RunAverages is ran. As in this manner it could create a non-existing link between (two) just removed and constructed (possibly by another player) stations

That could be done, but requires more code and more review work. I tried to minimize the code volume. It's not so bad if a bogus link occurs from time to time. The link will be removed when it times out. The cargo will then be rescheduled and the problem solves itself.

The tick counter overflows ever 65536 ticks. So every 2.5 years half of the stations are missing one RunAverages call.

That is not really a problem either. The averages are not so very accurate anyway. Handling that case would increase code complexity for little gain.

Not quite true. It's actually two or three (rotor), but bailing out might be better yes. However, can't it just go through the normal procedures?

It cannot go through the normal procedure because of the weird mail_capacity thing with DetermineCapacity() a few lines above. You cannot separately refit the shadow or the rotor.

http://rbijker.net/openttd/cd/0001-Add- ... raph.patch

Station * could be const Station * as far as I could see. It shows the intention you do not change anything and the compiler can use that for optimisations

Actually not. The last_component member of GoodsEntry is updated in the process. So station cannot be const.

Wouldn't this "corner case" belong in the savegame loading code? Or can't it be placed there in a nice manner?

This involves either another "friend" declaration or an extra public method for this purpose. Is that worth it?

What ways are there to prevent an onverflow in the component_id? If there is one, is that a problem?

The component ids are the same bit length as the station ids. There cannot be more components than stations for a given cargo and so as long as the station IDs don't overflow, the component IDs can't overflow, either.

Why aren't threads spawned and joined in the same tick, or maybe one tick apart? In the current method you "lose" roughly half a game day of processing power per recalc_interval

Because the joining and spawning itself may be noticable on slow computers. I'm trying to space them apart as far as possible in order to not make the lags induced by them appear as one big lag.

The "cat" seems to be missing, compared to trunk settings.ini. Not sure how important it is as it's new for me

If it's not given the setting is shown in the "advanced" category. I found that adequate.

[fonso]

What ways are there to prevent an onverflow in the component_id? If there is one, is that a problem?

I have to elaborate on this a bit. The answer I've given is not quite complete.

In each run over the link graph at most half of the available component IDs can be assigned. That's 32768. There is one special INVALID_COMPONENT_ID which should not be used, so let's say 32767. A new component ID is only issued if a station with a link for the respective cargo is found. That means there have to be at least two stations in that component. Each station can only be in one component at a time. There can be up to 65534 stations in the game (2 ^ 16 available IDs - 2 special ones: INVALID_STATION and NEW_STATION). So we need at most 65534 / 2 == 32767 component IDs in each run. Thus, the component IDs will not overflow.

I'll add a comment and an assert for that.

[fonso]

* Loading an old game should not automatically activate cargodist.
* I wonder whether cargodist should be enabled by default since it makes
beginning for an user harder. For the cargodist branch it makes sense,
but for trunk inclusion maybe not.

This is a matter of changing the defaults to DT_MANUAL in settings.ini lines 599, 613, 627 and 641. I've auto-enabled cargodist so that I don't get tons of questions like "I'm playing your patch but nothing changed? What is going on?". I'll change the defaults when everything else is ready.

[fonso]

It's probably a better idea to just add comments to the code that answer the more specific questions. After all, anyone reading the code later may have the same questions and in this thread the context is missing. I'll just do it like this then. I'll still answer the more general questions here.

[Alberth]

It's probably a better idea to just add comments to the code that answer the more specific questions. After all, anyone reading the code later may have the same questions and in this thread the context is missing. I'll just do it like this then. I'll still answer the more general questions here.

Sounds like a good idea!

[fonso]

http://rbijker.net/openttd/cd/0007-Feat ... stin.patch

Where has the autorefit code gone to?
Where did this go to?

Basically, I do all the stuff related to reservation in ReserveConsist(). There should be the following comment in that method, which I accidentally added to the wrong commit:

We could count the cargo in one round and then assign the quantities in another round over all vehicles. This would lead to an equal distribution of cargo over all vehicles in the consist. I don't think it's worth it, though.

The autorefit code was added after I wrote that stuff and it seems I messed it up when merging. The current behaviour in trunk can be summarized like this:

1. if not improved_loading, skip any reservation.
2. else if full_load but no autorefit reserve for the whole consist in each loading round. Do not assign cargo to specific parts, yet.
3. else if autorefit reserve for each single wagon once it loads anything, no matter if full_load.
4. if gradual_loading load some cargo determined by vehicle characteristics, else load up to vehicle capacity

Is that correct so far? In that case cargodist does some things "wrong":

1. It assigns cargo to specific parts of the consist when reserving. This is hard to avoid.
2. When reserving it "greedily" reserves and fills up the wagons one by one instead of equally distributing the cargo. This could be avoided as detailed above. As cargo is loaded in chunks, the result may still not be optimal if it's done the naive way. We may need to use the chunk size here.
3. It reserves for the whole consist when autorefit and full_load, but doesn't reserve at all when autorefit and not full_load. That can be fixed with a little bit of refactoring.

Did I get that right this time?

[fonso]

http://rbijker.net/openttd/cd/0012-Add- ... -for.patch

This seems unfinished to me

Obviously this only works if we have GetSmallmapStationMiddle and/or GetViewportStationMiddle. Those are added in the following commits, where also LinkGraphOverlay::GetStationMiddle is changed. In order to produce smaller patches I intentionally left that unfinished in the abstract overlay implementation. The alternative is making one big patch for viewport and smallmap overlay combined.

The same holds for "remnant of something" in http://rbijker.net/openttd/cd/0013-Add- ... rlay.patch. I can only attach the legend to the overlay once the overlay is implemented. However, for the overlay to work it needs a legend.

[keoz]

I can't understand the technical aspects you are speaking about here, but it would be really nice if all this work can lead into an eventual inclusion in trunk

Once again, thank you fonso for all this great work. I could'nt play openttd anymore without some kind of d(estina|istribu)tions for cargos.

[Eddi]

[*] When reserving it "greedily" reserves and fills up the wagons one by one instead of equally distributing the cargo.

i don't think this should be changed. if you "distribute" the cargo over all wagons, you cannot sensibly have mixed cargo (autorefit) trains.

e.g. a station has 60 coal and 60 ore, the train has 4 wagons with 30 capacity each. now if the train reserves the wagons equally, each wagon would get 15 coal (three loading steps each), but no wagon can be refitted to ore. instead if you reserve "greedily" instead, you have room for 30 coal in the first two wagons, and 30 ore in the second two wagons each.

you may get suboptimal loading times if there is not enough cargo to fill the whole train, but i think this is a worthwhile tradeoff.

[fonso]

[*] When reserving it "greedily" reserves and fills up the wagons one by one instead of equally distributing the cargo.

i don't think this should be changed. if you "distribute" the cargo over all wagons, you cannot sensibly have mixed cargo (autorefit) trains.

Trunk is smart enough to distinguish between autorefit and normal full loading. If the consist does autorefit only single parts reserve cargo when they start loading, otherwise the whole consist does even before it loads. Cargodist should do the same.

[fonso]

Actually I'm wrong. If autorefit and full load are both set, trunk first reserves cargo for the whole consist and then reserves again for each wagon that starts loading. As that happens in different ticks and reservations are transient in trunk this does no harm, though.

[fonso]

Reservation in trunk

This is how it really works in trunk. I'm only talking about full load orders with improved load as everything else doesn't reserve.

1. If a consist is not going to load because of load_unload_ticks != 0, it reserves cargo for the whole consist, no matter if it autorefits, see economy.cpp:1249

   Code: Select all

   /* We have not waited enough time till the next round of loading/unloading */
   if (front->load_unload_ticks != 0) {
   	if (_settings_game.order.improved_load && (front->current_order.GetLoadType() & OLFB_FULL_LOAD)) {
   		/* 'Reserve' this cargo for this vehicle, because we were first. */
   		for (Vehicle *v = front; v != NULL; v = v->Next()) {
   			int cap_left = v->cargo_cap - v->cargo.Count();
   			if (cap_left > 0) cargo_left[v->cargo_type] -= cap_left;
   		}
   	}
   	return;
   }
   

2. Otherwise it does not reserve at all, but tries to load the vehicles one by one.
3. If a vehicle successfully loads something
   1. In case of autorefit it reserves cargo for the whole vehicle (not consist), see economy.cpp:1500

      Code: Select all

      if (use_autorefit) {
      	/* When using autorefit, reserve all cargo for this wagon to prevent other wagons
      	 * from feeling the need to refit. */
      	int total_cap_left = v->cargo_cap - v->cargo.Count();
      	cargo_left[v->cargo_type] -= total_cap_left;
      	consist_capleft[v->cargo_type] -= total_cap_left;
      } else {
      [...]
      

   2. Otherwise it does not reserve, but only subtracts the loaded cargo from the cargo left, see economy.cpp:1510

      Code: Select all

      [...]
      } else {
      	/* Update cargo left; but don't reserve everything yet, so other wagons
      	 * of the same consist load in parallel. */
      	cargo_left[v->cargo_type] -= cap;
      }
      

4. After loading all vehicles, if it's not autorefitting, it reserves cargo for their remaining capacity. See economy.cpp:1567

   Code: Select all

   /* For consists without autorefit-order we adjust the reserved cargo at the station after loading,
    * so that all wagons start loading if the consist is the first consist.
    *
    * If we use autorefit otoh, we only want to load/refit a vehicle if the other wagons cannot already hold the cargo,
    * to keep the option to still refit the vehicle when new cargo of different type shows up.
    */
   if (_settings_game.order.improved_load && (front->current_order.GetLoadType() & OLFB_FULL_LOAD) && !use_autorefit) {
   	/* Update left cargo */
   	for (Vehicle *v = front; v != NULL; v = v->Next()) {
   		int cap_left = v->cargo_cap - v->cargo.Count();
   		if (cap_left > 0) cargo_left[v->cargo_type] -= cap_left;
   	}
   }
   

So, what is the intention of that code? The whole point of reservation is that vehicles load "one by one" and the first vehicle that starts loading is filled up first. Later vehicles can load in parallel, but only the cargo that's left over from earlier ones. This idea has its problems with autorefit. When autorefitting the cargo may change while a vehicle is loading. In that case we have to reserve different cargo. However, we can only know which cargo to reserve when the vehicle has decided to autorefit. So, for pragmatic reasons, when the vehicle doesn't load, we assume that the cargo to be loaded will not change and reserve like that. When it can load, the consist either finds something to load; then it reserves whatever it has loaded. Or it doesn't; then there's no need to reserve as there's no cargo anyway.

Reservation in cargodist

Now lets take a look at the solution in cargodist. The intention stays the same. I want the vehicles to load "one by one". However, I'm applying a different strategy. Instead of only counting the cargo to be loaded I actually assign reserved cargo to specific vehicles. This is done because the counting becomes complicated when cargo packets have different destinations. In order to keep the code simple I just reserve cargo in every tick, not only the non-loading ones. And, following the strategy of assuming the cargo won't change, I do that also in case of autorefit.

Then, when a vehicle actually loads, I don't have to change anything about the reservation as I've sufficiently reserved before. I also don't have to change anything after loading as that has been done, too.

The only problem is that I'm reserving some "wrong" cargo for vehicles that would actually autorefit. So far this is solved by not letting vehicles with active reservations autorefit. See economy.cpp:1446

Code: Select all

while (w->HasArticulatedPart()) {
	w = w->GetNextArticulatedPart();
	if (w->cargo.Count() > 0) new_cid = CT_NO_REFIT;
	refit_mask |= EngInfo(w->engine_type)->refit_mask;
}

Count(), in contrast to OnboardCount(), contains not only the loaded, but also the reserved cargo. So this will actually return CT_NO_REFIT for all vehicles having either reserved or loaded cargo. In order to restore the exact same behaviour as in trunk a little change is necessary, see https://github.com/fonsinchen/openttd-c ... a07654a973 .

The powers that be may choose if they want those extra 10 lines or if they are content with a slight deviation from the original behaviour.

Balancing cargo across parts of one consist

In trunk, due to the way reservation and loading is split, vehicles in one consist may load all in parallel even if there is not enough cargo to fill them all. This leads to vehicles being half empty after all the cargo is consumed. In cargodist the parts of a consist are filled up one by one. If there's not enough cargo to fill them all only at most one of them is partly filled. All others are either full or empty. This has the disadvantage of taking slightly longer to load the cargo as not all wagons will load in parallel. The wagons with cargo, however, will load in parallel, as cargo is always reserved before loading.

This, too, can be changed. It's a matter of counting free cargo in the ReserveConsist method and distributing it evenly. Shall I do that or rather not?

(edit: actually the behaviour in trunk is not detrimental to autorefit)

[fonso]

The new experimental branch "reserve" in my github repository tries to be as compatible with trunk as possible. I've implemented a balancing algorithm which distributes reserved cargo between vehicles that got too much cargo and ones that got too little.

I figured that counting the available capacity, finding the load chunk size for each wagon and then distributing the reserved cargo in another loop over all vehicles in the consist is way too much overhead for the intent of just having the vehicles load in parallel. Instead I basically keep a second pointer into the vehicle list of a consist which points to the vehicle to be balanced with next. If a reserving vehicle gets less cargo than its share of the already reserved cargo should be and the balancing vehicles still has some excess reserved cargo the reserving vehicle takes away some of that so that both have the same amount of reserved cargo. If the balancing vehicle doesn't have any excess cargo the next vehicle is tried for balancing (looping back to the first one if necessary). This doesn't incur a lot of overhead but also doesn't give a perfect distribution. However, it will always give each further vehicle at least total_reseved_cargo / num_vehicles / 2 as soon amount of reserved cargo is strictly decreasing from one reserving vehicle to the next (before that we don't have this problem). By that property it allows all vehicles of a consist to load in parallel.

[fonso]

After trying different approaches to resolve the situation with reservation, I've settled for the following:

1. Reserved cargo is kept in the same cargolist as the actual cargo. To distinguish onboard from reserved (or to be loaded) cargo and further split up onboard cargo into chunks to be transfered, delivered or kept, four counters are added to the vehicle cargo list and the cargo packets are always kept in a certain order so that reserved cargo is at the back of the list.
2. Before unloading cargo is staged. That means it's sorted into contiguous batches to be transferred, delivered and kept. As a side effect transfer cargo is always unloaded first, possibly making it available for re-loading by other vehicles earlier.
3. Thus, in contrast to previous versions, cargo can be reserved before all cargo to be transferred or delivered is unloaded. The action (transfer, deliver, keep, load) counts keep track of how much cargo can be reserved (vehicle capacity - keep). That means vehicles can momentarily have a higher cargo count than capacity while unloading. This change brings cargodist in line with the intention of improved loading, which is mostly (except for http://bugs.openttd.org/task/5438) implemented in trunk. Previous versions of cargodist could only start reserving cargo for a vehicle when it had finished unloading. This meant that vehicles of the same consist could start reserving at different times, increasing the chance for cross-consist parallel loading.
4. When aborting the loading before it's finished (that means skipping an order or stopping), reserved cargo is returned to the station (as it was in previous versions). As a side effect of the staging mechanism cargo which was staged for transfer will collect its feeder share early in that case and may collect another feeder share when really transferring at a different place. I'm aware that this may artificially increase vehicles' visible profit. However, because of the inaccuracies inherent in the feeder share mechanism I decided rather not to allocate two more bytes per cargopacket just to avoid that.
5. Regarding the balanced vs. greedy loading I decided to always use greedy loading in the case of full load with improved loading. That means vehicles of the same consist will reserve cargo in a way so that they are completely filled up one by one, possibly leaving whole vehicles empty at the end of the consist. Thus, if not enough cargo is there to fill the whole consist, the consist may take longer than with trunk to load the available cargo because not all of its vehicles can load in parallel. This is mostly mitigated by the fact that it will wait until at least one cargo type is fully loaded anyway. I have an algorithm which does the same balanced loading as trunk does in that case. However, it's a rather complex piece of code which has rather little effect. After some discussions on IRC I decided it's not worth it.
6. In the station cargo list a counter is kept for the sum of cargo currently reserved for any loading vehicles. That number is then displayed as a yellow line (like en-route) in the station GUI. The overall count in the station GUI is the amount of cargo really in the station cargo list plus the amount of reserved cargo.

The resulting code is ready for review. I've conveniently placed the whole reserving business at the start of the cd branch.

[fonso]

I forgot: The reserved cargo is shown correctly in the old (non-cargodist) station GUI but not in the new one that shows source, next hop and destination. I'll add that. However, as the station GUI is a pretty isolated piece of code the rest can already be reviewed.

[fonso]

Now that a lot of my patch queue has been merged I feel pretty confident about redesigning the linkstats/linkgraph handling code. See #3 to #6 at https://github.com/fonsinchen/openttd-cargodist/issues. There are still some open questions Maybe we should wait with further merging that until I've gotten to some conclusion there.

[fonso]

I've rewritten most of the link graph scheduling and stats collection now, closing #3, #4 and #5 on my issues list. #6 is a big project in itself and can be done as an add-on later. Basically cargodist doesn't take "no unload", "unload all" and "transfer" orders into account when calculating the cargo flows. This can be changed by adding additional, virtual nodes to the link graph when encountering those orders. I won't do this for now as it significantly increases the complexity of the stats collection and flow assignment code. I have implemented a prototypical solution before and I know it can be done, though.

The basic link graph data structures could probably be done more elegantly by implementing operator[] more often and providing better encapsulation and possibly inheritance for nodes, edges and their respective annotations. Refactoring that across 15 commits is significantly more work than doing it for all the code at once later on. Considering that, I propose to wait for some public testing to happen while I recheck all the code for coding style. Then we can restart the merging effort around next weekend.

[fonso]

In fact I have rewritten the link graph API for better encapsulation and elegance now. You basically get two APIs, one for component handlers which get to modify annotations to the link graph, but not its node and edge properties, and one for the main game which gets to modify the node and edge properties, but doesn't see any annotations. Nodes/Edges and their annotations are wrapped into unified accessor objects for component handlers, so that you don't have to drag around two references for each edge or node.

When creating a link graph job, (as before) a constant copy of the underlying component and the necessary annotations are created and all the handlers are called in a separate thread.

You can use operator[] on link graphs, jobs and their node accessors, with the obvious semantics. Nodes also provide iterators which iterate over edges with capacity and ignore all others. That construction is slightly weird as it is inconsistent with operator[] (which can also look up edges without capacity). I still did it like that because it's just very handy in the vast majority of cases.

The result of the rewrite is already in the "cd" branch in my repository. I've also split up the patch queue into more and smaller parts again, while trying to do the changes on a file-by-file base. For example the whole link graph save/load file is added in one commit and not modified in later ones. That has the advantage of less code fragmentation between commits and the disadvantage of creating non-functional intermediate versions. You cannot really use the link graph without saving and loading it, but I didn't want to add saving and loading "before" the data structures are complete. I think you should just merge all link graph commits in a row when you're ready to do so.

[fonso]

I've identified two potential problems with the current code base:

1. If links or stations are removed while a link graph calculation is running the results of that calculation don't cleanly map to the actual link graph. There are basically two ways to handle that:

a, Check the results in the main thread after the calculation and remove bad flows. This can be expensive and contradicts the idea of doing all the calculation in the link graph threads. However, that is the solution currently implemented.

b, Prevent stations from being deleted and links from being removed while their link graph calculation is running. The deletion would be deferred until the calculation is done. This allows a blind replacement of flows but entangles the link graph more with the rest of the game. Due to the way link graph calculations are scheduled there may also be no point in time where a station is actually "free to be deleted". The calculations for different cargoes could overlap in a way that keeps the station blocked forever. It would be possible to remove the station's nodes from the different link graphs and delete the station when all its nodes are gone.

2. The measurement of link capacities is too imprecise. Sometimes links are dropped that are still alive - especially long links with slow vehicles, like ships. This is due to the fact that they are timed out and the timeout depends only on the length of the link. Maybe it would be better if the link would only be dropped if all orders defining it disappear. There are various ways in which this may fail, though: stopped vehicles, conditional orders that are never reached, conditional refitting ...