IRC logs for #openttd on OFTC at 2024-11-15
⏴ go to previous day
00:06:35 <peter1138> Right, vanilla 4kx4k is slightly faster, but not horrendous.
01:07:20 <_glx_> so `Industry::ResetIndustryCounts()` when loading industries was actually not needed
01:22:12 <peter1138> And definitely not with that branch 🙂
02:06:40 *** Smedles has joined #openttd
02:31:51 *** ChanServ sets mode: +v tokai
02:38:51 *** tokai|noir has quit IRC (Ping timeout: 480 seconds)
03:18:47 *** godbed_ has joined #openttd
03:22:06 *** debdog has quit IRC (Ping timeout: 480 seconds)
03:22:11 *** D-HUND has quit IRC (Ping timeout: 480 seconds)
03:37:40 *** Wormnest has quit IRC (Quit: Leaving)
04:48:54 <DorpsGek> - Update: Translations from eints (by translators)
05:58:58 *** keikoz has quit IRC (Ping timeout: 480 seconds)
07:35:53 <andythenorth> If I use Lambda@Edge for url rewrites to my static website, a bad crawler could bill-shock me
07:44:57 *** SigHunter has joined #openttd
08:46:49 <peter1138> Our line drawing algorithm isn't great for dashed lines...
09:12:10 <peter1138> Yeah, the industry lists are short enuogh that doing a sorted search/insert is quick enough.
09:13:30 <peter1138> The "one-industry-per-town" test could maybe be done by adding a list of industries for each town. Then there is an upper maximum to check.
10:12:07 <xarick> peter1138: but ... I did just that 😦
10:16:08 <peter1138> I'm timing it on a 2kx2k map.
10:18:13 <peter1138> It's about 2-3 seconds faster for than without.
10:18:53 <peter1138> So slightly faster but perhaps not worth the complexity.
10:20:43 <xarick> i need to learn what lower_bounds do
10:21:10 <xarick> not the first time I see you use it
10:23:54 <peter1138> It finds where to insert the element into the vector such that it will be sorted.
10:25:52 <peter1138> A prerequisite is that the list must already be completely sorted, but of course when you use this method it always is.
10:27:10 <xarick> will that speed up std::find_if or not really?
10:27:15 <peter1138> The reason the list is sorted is so that 1) removal is quick, we don't need to search the entire list. But industries aren't removed enough for that to really matter, to be honest, and 2) as they're sorted by index, iterating the list means the industries are found in exactly the same order as they would be by iterating the pool.
10:27:28 <peter1138> No, find_if always searches from start to end.
10:27:31 <peter1138> lower_bound is a binary search
10:27:54 <peter1138> If you want to find if an element is present, then std::binary_search works.
10:28:46 <peter1138> This all avoids the overheads of using a std::set.
10:29:06 <peter1138> Inserting into a vector is relatively slow, but when generating the map we'll always be inserting at the end anyway.
10:29:18 <peter1138> Inserting into the middle of a vector, that is.
10:30:46 <peter1138> We could probably do this unsorted so that insertion is quicker. Removal doesn't really matter. But keeping the list order the same as the pool order is a useful trait.
10:31:08 <peter1138> kdtree is probably quicker to find the nearest industry.
10:31:48 <xarick> sort insert by distance?
10:31:52 <peter1138> But that is a more complex structure and then with all the filtering needed it's... meh.
10:31:59 <peter1138> Distance from what?
10:32:08 <xarick> oh, right... neverming
10:32:48 <peter1138> My stuff doesn't change anything about the process of searching for the nearest industry.
10:32:55 <peter1138> It just reduces the amount that needs to be checked.
10:33:30 <peter1138> Checking for i->type == type is cheap but when doing it repeatedly it adds up.
10:42:34 <peter1138> Storing industry* instead of industry id might be quicker when iterating but also uses more memory and sorting the list is more work.
10:50:59 <xarick> gonna use the lower_bounds technique
10:51:17 <xarick> let's hope it doesn't complain about iterator invalidator bla
10:53:22 <peter1138> That's not appropriate with kdtree...
10:55:58 <xarick> i'm going to use it for the town_industryvector pair
11:04:59 <peter1138> I have no idea what that branch is about :p
11:05:10 <peter1138> kdtree at least makes sense, given it lets you find the nearest.
11:15:20 <peter1138> These unit-tests pass but I don't really have any idea what they are testing.
11:16:47 *** yiffgirl has joined #openttd
11:16:47 <yiffgirl> peter1138: which ones?
11:17:15 <peter1138> The ones I'm looking at.
11:22:28 <peter1138> Okay, I think I understand it.
11:22:48 <peter1138> And it's not doing anything much useful.
11:23:20 <peter1138> Mocking a service to say that if I pass it these parameters is the response. And then testing something against that response.
11:23:46 <peter1138> So if I change the real service to return something different... the unit-test won't know any different.
11:26:48 <peter1138> I think mocking the data sources is reasonable, but the unit-test should probably actually be using the services instead of mocking them, right?
11:27:56 <LordAro> depends how easy it is to mock the source vs the service, i guess
11:41:25 <peter1138> For reads, relatively easy I suppose. Writes less so.
11:41:43 <peter1138> It's just data models at that point.
11:43:02 <peter1138> Oh well, not my problem for now 🙂
11:49:10 *** merni has quit IRC (Quit: User went offline on Discord a while ago)
12:27:20 <xarick> unreferenced formal parameter
12:27:41 <xarick> is this the [[maybe_unused]] that's missing?
12:47:16 <kuhnovic> A time traveler! He's already on verion 14.4 😮
12:50:28 <peter1138> Do I just assume it's the usual path-reservation-goes-past-the-depot?
12:50:38 <peter1138> Is that even the cause?
12:52:29 <kuhnovic> The savegame doesn't really show the problem. Just the layout
13:00:10 <kuhnovic> Seem to work fine provided the order book is not empty
13:09:29 <xarick> game is hard confirmed
13:19:29 <xarick> ```/* Create a new vector for the industry IDs and add the industry ID. */
13:19:29 <xarick> std::vector<IndustryID> iid_vector;
13:19:29 <xarick> iid_vector.emplace_back(ind->index);```
13:19:29 <xarick> `counts[ind->type].emplace(pair_it, ind->town->index, std::move(iid_vector));`
13:19:30 <xarick> `counts[ind->type].emplace_back(ind->town->index, iid_vector);`
13:19:30 <xarick> what is std::move doing different than just iid_vector?
13:20:08 <peter1138> Moving it instead of making a copy.
13:20:42 <xarick> is that what I want here? this was a copilot change
13:29:51 <_glx_> if you create it as a local variable to be then stored in global space move seems to be the right thing
13:32:01 <xarick> copilot answers are so complete
13:32:16 <xarick> yeah, std::move is the correct approach
13:39:33 <xarick> ``` /* Find the correct position of the town entry using lower_bound. */
13:39:33 <xarick> auto pair_it = std::ranges::lower_bound(counts[ind->type], ind->town->index, {}, &std::pair<TownID, std::vector<IndustryID>>::first);```
13:39:33 <xarick> also a copilot suggestion
13:39:47 <xarick> i asked about using lower_bound and binary search
13:40:17 <xarick> but nothing in the code got a std::binary_search
13:42:13 <xarick> final test: check if the lower_bound and ordered insertion is faster than the previous method
13:43:36 <_glx_> ordered insertion is probably slower, but search should be slightly faster, it all depends on the main use case
13:44:35 <peter1138> Yes, your elements are much larger than mine.
13:45:33 <peter1138> Each vector after the insert point needs to be moved,
13:45:45 <_glx_> the main thing to think about is how the data will be used in the end
13:46:18 <_glx_> sorting has advantages and disadvantages
13:48:47 <_glx_> it's the same for everything when coding, like caching can speed up things, but it also increases memory usage
13:57:00 *** godbed is now known as debdog
13:57:40 <xarick> current usage doesn't require the vectors to be sorted if I'm not mistaken
13:58:00 <xarick> but in the future, someone might want them sorted
13:58:04 <peter1138> When you remove an item everything gets shuffled either way.
14:00:00 <kuhnovic> peter1138: Is this a known issue?
14:02:11 <peter1138> I can't remember if it's actually because the track is reserved or not, but seems likely.
14:02:13 <xarick> oh, wait, nevermind, i tested the wrong thing... im dumb
14:02:56 <xarick> i only tested "industry type counts tracks towns" + "ordered insertion", didn't test the kdtree
14:03:02 <_glx_> yeah IIRC pf won't see the depot is reservation exists
14:03:56 <peter1138> It should be possible to remove the reservation, look for a depot, and then put the reservation back if it's not found.
14:03:59 <_glx_> but it's mostly for automatic maintenance
14:04:13 <_glx_> manual should not be an issue
14:05:09 <_glx_> anyway the best thing to do is service order
14:05:34 <andythenorth> should articulated RVs be composable like trains?
14:05:35 <peter1138> Sure but it feels like a work around to me.
14:05:49 <peter1138> andythenorth: Would've been nice.
14:06:14 <_glx_> articulated RVs are like articulated loco
14:06:26 <LordAro> just make all vehicles actually be trains
14:18:24 <andythenorth> articulated log rafts
14:18:32 <andythenorth> articulated zeppelins
14:26:58 <squirejames> andythenorth: I can't seem to find a picture, but there was a proposal (and it may even have been built) for a collier that was hinged double in the middle, so it looked rather like those wooden toy snakes, so that it could be longer and not break it's back in rough seas
14:28:15 <squirejames> I remember it from a book I read as a kid. (all manner of weird ships, including those circular river monitors the Russians built)
14:48:20 <xarick> Last round of benchmarks
14:49:47 <xarick> I'm a bit surprised that #4 and #5 are so distant
14:51:09 <xarick> peter did something good, apparently, need to check why my stuff is slower just because I added towns
15:08:31 <peter1138> You are using a different more complex data structure.
15:09:15 <peter1138> Mine literally only has to move uint16_ts, and even then only when an Industry ID is reused during the game.
15:27:36 <_glx_> yeah during loading or mapgen data to insert is already ordered
15:28:30 <_glx_> and ingame there will be some remove and insert, but less visible than during initial fill
15:33:07 <_glx_> usually you want cache to be simpler than original data storage
15:35:38 <xarick> however, I also forgot to update CheckIfFarEnoughFromConflictingIndustry 😮
15:36:09 <_glx_> in peter's case it's replacing scanning whole industry pool with scanning a prefiltered version
15:36:26 <_glx_> so less data to handle, more speed
15:37:35 <peter1138> I added a list to towns as well, but I don't think it makes a lot of difference. It adds a lot more data, so more memory, is more complex to test, and doesn't improve performance much.
15:37:36 <_glx_> and only the usefull stuff for the complete Industry struct is in the cache
15:38:15 <peter1138> I made it search by industry type or by town depending on which list if smaller. It nearly always searched by industry type.
15:38:25 <peter1138> But that depends on the settings and newgrfs.
15:42:02 <_glx_> and with just replacing the per type counter with per type vector, you still have a working counter plus a subset of filtered data
15:43:28 <xarick> nevermind, I can do anything about CheckIfFarEnoughFromConflictingIndustry
15:43:51 *** HerzogDeXtEr has joined #openttd
15:44:06 <xarick> so I guess im going to take kdtree + peter's industry type list
15:44:41 <xarick> seems simpler enough that it's fast
15:45:37 <peter1138> With kdtree I don't know if my changes would give any benefit.
15:46:02 <xarick> kdtree can be used in CheckIfFarEnoughFromConflictingIndustry for example
15:46:29 <xarick> can also be used in GetClosestIndustry
15:47:33 <xarick> and not quite as good but also on the 2 other places FindTownForIndustry and filter waterver layout snippet
15:54:54 <xarick> peter's vs kdtree vs master
15:58:58 <xarick> i have a feeling peter's approach still faster
16:01:18 <xarick> for this one, I believe kdtree is faster, the power of FindNearest is just too good to ignore
16:02:39 *** Flygon has quit IRC (Read error: Connection reset by peer)
16:10:12 <xarick> this one... I'm leaning towards peter's
16:25:29 <xarick> hmm there are divergences, something is wrong
16:37:34 <Guest7968> squirejames/andythenorth: Are you aware of the 'Tom Pudding' barge trains used on the Aire & Calder?
16:38:31 <squirejames> I is not. I shall googleth
16:39:43 <Guest7968> I'm just looking for a good picture/video ;-)
16:39:46 <andythenorth> they had a boat lift
16:39:53 <Guest7968> very long trains of very short tippleable barges
16:40:36 <Guest7968> they had a chain down each side with a winch, so you could actively bend the whole snake to one side or the other to a degree
16:40:46 <Guest7968> oh, why was I a Guest
16:43:33 *** Guest7968 is now known as FLHerne
16:47:20 <FLHerne> originally they were pushed in trains of about 8, and later pulled in trains of 17 or 21
17:00:11 <xarick> what is potable supposed to mean?
17:00:29 <andythenorth> in English, or in-game?
17:05:15 <xarick> all of my kdtrees diverge in industry placements...
17:06:16 <xarick> drinkable in openttd context ?
17:07:32 <xarick> but the industry type counts tracks towns is correct... 😐
17:10:15 <xarick> waiting for master to finish generation... 15 minutes
17:17:33 <andythenorth> xarick: literally means 'potable' in english 🙂
17:18:43 <andythenorth> it also means 'most people won't be sure, and will have to look it up'
17:18:48 <andythenorth> which is why it's not another name 😛
17:33:39 *** benjaminv has joined #openttd
17:39:59 <xarick> I have a big suspicion on this
17:40:06 <xarick> ` assert(CheckIfFarEnoughFromConflictingIndustryOriginal(tile, type).GetErrorMessage() == CheckIfFarEnoughFromConflictingIndustryKdtree(tile, type).GetErrorMessage());`
17:45:08 <_glx_> yeah classic MSVC warning
17:45:45 <_glx_> size_t is 64 or 32bit (depending on target), uint is always 32bit
17:46:10 <peter1138> clang doesn't seem to care about doing that.
17:46:26 <peter1138> There are warnings to enable but that throws up a LOT.
17:50:36 <xarick> something tells me the first part of the original code doesn't do the same as the second part
17:51:50 <xarick> took 6547 industries to trigger
18:05:04 <xarick> original code is bugged
18:05:36 <_glx_> or the new code doesn't do the same thing 🙂
18:06:06 <peter1138> I guess Xarick means the two code-paths don't do the same thing?
18:07:23 <xarick> must be an extreme rare case
18:07:50 <xarick> i only noticed with this specific newgrf and on a different openttd.cfg
18:07:55 <_glx_> it doesn't need to do the same in both, it's a different algo
18:08:01 <xarick> Improved Town Industries
18:08:52 <xarick> gonna check if Part2 matches Kdtree
18:09:29 <_glx_> first algo might ignore some industries
18:09:51 <_glx_> since location is the northernmost tile
18:10:14 <peter1138> Second algorithm uses location.tile too.
18:10:29 <_glx_> and detecting industries by tile may not see the same as purely checking all industries
18:11:35 <xarick> I made kdtree to use location.tile
18:11:59 <_glx_> imagine a huge 10x10 industry on the left, with one tile in the search area, and an industrie on the right just outside the search area
18:12:18 <_glx_> right one might be closer, but invisible in area search
18:14:35 <xarick> it passed the critical phase
18:15:05 <_glx_> not a bug, different algo means different result
18:15:36 <peter1138> Okay, if the top-corner of the industry is not part of the layout (fairly common) then it could be excluded by the first algorithm.
18:16:28 <peter1138> Actually maybe that isn't the industry location? Dunno.
18:17:10 <xarick> i will investigate which kind of industry this is with debug build...
18:17:10 <peter1138> Either way, I realised I only need to check the 3 conflicting industry types, not all industries.
18:17:16 <peter1138> (And there only be one)
18:17:33 <_glx_> anyway area search may ignore closer industries
18:18:13 <_glx_> and you can prevent it, unless you increase the area
18:19:14 <_glx_> just try increasing dmax
18:19:40 <xarick> i used dmax for kdtree
18:20:25 <xarick> which is 15 for kdtree because it's [x, y) interval
18:20:44 <_glx_> hmm increasing has side effect as it's used to define area and also distance check
18:21:33 <peter1138> To be honest, I don't know what algo 1 is doing.
18:22:00 <peter1138> Oh, the i/i2 tests is just so that it doesn't test the same industry so often.
18:22:16 <peter1138> I don't see why that algorithm would ignore any particular industries.
18:22:28 <_glx_> it does a circle around tile and check industry tiles
18:22:41 <peter1138> It only needs one conflicting industry to abort, and it doesn't matter what type.
18:24:06 <_glx_> but industries on one side are visible with location outside the area, while on the other side the location could be closer but just outside the search area
18:24:49 <_glx_> depends on intersections
18:24:58 <peter1138> If they're visible but the location is outside, then distance check ignores it. Same as algo 2.
18:25:52 <peter1138> The only possibilty is if the origin tile is inside the area, but no industry tiles of the industry are.
18:26:11 <peter1138> In which case, just increasing the search area a little would 'fix' that.
18:26:44 <_glx_> oh indeed I missed the distance check
18:31:17 <_glx_> arable farm, brewery or cement plant in FIRS may trigger the difference I think
18:32:06 <peter1138> It's an interesting idea though.
18:32:18 <_glx_> `TileArea tile_area = TileArea(tile, 1, 1).Expand(dmax + something);` should work
18:32:20 <peter1138> Technically that tile isn't part of the industry... so it isn't too close?.
18:32:47 <peter1138> Of course, perhaps industry size should be taken into account.
18:33:18 <peter1138> A large industry is a northern direction is considered further away than it is.
18:38:09 <peter1138> Tweaking that function doesn't gain anything much as by the time iterating the pool is a problem it's already long before switched to the map scan.
18:38:14 <_glx_> so not really a bug in algo 1, but an omission of special cases
18:43:20 <_glx_> what's funny with the whole function is a 5x5 industry visually 2 tiles distant might be seen less close than a 3x3 visually 4 tiles distant
18:48:19 <xarick> debug build generating industries 1 per second 😦
18:49:13 <xarick> I wanna visualize the thing this is on about
18:51:42 <peter1138> I wonder if it's worth changing the distance check to take industry size into account.
18:52:06 <xarick> just wait for my kdtree
18:53:07 <xarick> if it's do do the same as the Part2, then the Kdtree implementation I have already matches
19:46:05 <peter1138> peter1138: Called it.
19:47:24 <xarick> the funny part, the industry was still not built on both cases
19:47:29 <johnfranklin> Is “Let’s” formal?
19:47:57 <xarick> so it it did not fail here, it failed later on in some other check
19:48:00 <johnfranklin> Sounds like oral language
19:56:44 <xarick> what's the correct thing to do now?
20:03:45 <xarick> what would be the new horrendous time to generate industries with just the part 2
20:09:43 *** ahyangyi has quit IRC (Quit: User went offline on Discord a while ago)
20:14:03 <andythenorth> because only max 3 types conflict? 😛
20:15:37 <xarick> by investigating the spec?
20:16:12 <xarick> it needs to know which type conflicts with which
20:17:24 <peter1138> The 3 conflicting types are the same for every test.
20:20:24 <xarick> ah, I think I understand
20:21:31 <xarick> possibly slower for kdtree, must also test
20:49:17 <xarick> how to delete a branch on the remote which has a PR
20:50:53 <xarick> oh... github fake deletes my stuff
20:51:03 <xarick> visual studio actually deletes them
20:58:06 <xarick> reminds me of those reports of ppl with phones that have deleted pictures only for them to resurge out of nowhere
20:59:50 <andythenorth> can I patch nmlc for cargo classes yet? 😛
21:03:18 <xarick> i started a 14 AAAHogEx run some days ago, trying to aim for 5000 trains
21:03:27 <xarick> the script is crashing 😦
21:06:04 <xarick> maybe SimpleAI with its simplicity could make 5000 trains
21:06:37 <xarick> but the networks are non existant
21:09:58 <xarick> woah, I didn't know AAAHogEx would do this kind of partitioning
21:11:06 <xarick> I see I generated a map with too much water
21:33:49 <xarick> all that without kdtree, impressive
21:38:48 <andythenorth> hmm what's the saying about swamps and alligators?
21:39:47 <andythenorth> some months ago I was drawing these food hoppers 😛
21:40:13 <andythenorth> now I'm about to learn how to monitor AWS Lambda@Edge so I can avoid bill shock
21:40:45 <andythenorth> so I can redirect a stable inbound link from newgrf wiki to whatever latest version of cargo class docs is
22:28:43 *** keikoz has quit IRC (Ping timeout: 480 seconds)
22:43:29 <_glx_> Oh this one was in branch for some time now IIRC
22:52:31 <peter1138> I dunno though. It seems slower now. Maybe something else changed.
22:53:58 <peter1138> I'm sure I had 12ms on the 4kx4k save. Wondering...
22:55:11 <peter1138> 619: + C:/Program Files/Microsoft Visual Studio/2022/Enterprise/VC/Tools/MSVC/14.41.34120/include/vector(202) : Assertion failed: vector iterators incompatible
22:55:22 <peter1138> Actual errors from the Windows unit tests now.
22:57:20 <xarick> there is a problem with...
22:57:37 <xarick> IndustryType sometimes can go over 240
22:58:00 <xarick> in your GetClosestIndustry
23:04:26 <peter1138> So where is my iterator being invalidated... hmm.
23:06:21 <peter1138> Hmm, AddAnimatedTile during the loop, I guess.
23:08:51 <peter1138> Just noticed the old code did not use iterators... it uses pointers.
23:09:24 <xarick> andythenorth: such a great name
23:09:43 <peter1138> Hmm, ctest doesn't show that happening though. Hmm.
23:12:53 *** HerzogDeXtEr has quit IRC (Read error: Connection reset by peer)
23:19:37 <peter1138> Ok, deleting the last element in the tile list.
23:29:12 *** Wolf01 has quit IRC (Quit: Once again the world is quick to bury me.)
23:39:21 <xarick> I invented code based on your work for CheckIfFarEnoughFromConflictingIndustryTypeList
23:39:40 <xarick> only iterate over 3 industry types
23:40:49 <peter1138> Well I guess it's a bit better.
23:41:19 <xarick> will test with a newgrf tomorrow
continue to next day ⏵
