Friday Facts #215 - Multithreading issues

[Klonan]

https://www.factorio.com/blog/post/fff-215

[TheTom]

Are you not using C++? YOu should be able to overwrite the allocator (new())?

Now, chunks - problematic.

But overwriting the allocator and redirecting it to "type specific" allocators (electricity, train, belts) should not be that complex.

[Chocolatetthunder]

I understand you are generating a new starting point for each team but they are still far different looking from that image. Is that the case? Or am I miss understanding? Just having to plow trees or not is a massive potential disadvantage.

[Proxy]

well i never thought PvP would be a thing, since you don't have that much to fight with, more weapons or ways to defend would be kinda cool, i mean you get walls at the start and that's it.

also the starting areas don't need to be exact copies, just make Ores work like in RSO so that everyone starts with a similar sized patch of each resource and with a bit more distance between eachother.

[HOSH]

Um, not a knee jerk response, as I have been thinking about this since starting in 0.12 that having multi-thread was a requirement for the game before it is in full release "1.0" This way we can have huge maps with everything going, without slowing down the game speed.

Almost like we need to a a 0.17 and maybe a 0.18 before going 1.0.

[ledow]

Are we talking:

list of train tracks
list of trains
list of stations
list of belts
list of electric poles
list of electric networks

Each holding their own contiguous memory list of items, but separate (so they don't reference each other)?

Such that the belt-thread can pull in the list of all belts into its cache and it writing to it doesn't interfere with anything else?

If so, that makes me wonder greatly about how you've been doing thing up until now if it's not already like that? Are we talking a bunch of OOP abstraction and random allocations for each object as and when the need arises? Because, yes, that would make a ginormous mess of any cache advantage you might glean. Even with hashtables, linked lists and cross-references, surely they shouldn't be that far out of order anyway.

Maybe it's just the way I was taught to program, but it would seem obvious - C++ or not - to have one contiguous area of memory for all the possible objects of a certain type, pre-allocated and grown in powers-of-2 (2 items, 4 items, 8 items, 16 items) to reduce malloc/realloc movements as it grows (and lazy-shrinking so you don't unallocate only to reallocate again a moment later), that the belt constructors etc. use to generate and return new objects of that type. But, then, I come from a C background where "= new (class)" laziness isn't present.

I know my C99 code and force-of-habit is positively sprawling with "int number_of_[object]", "[object] **all_objects;" and some malloc/realloc wrappers to add, remove and get particular entities.

[Gergely]

Optimisation is... (again) a way of life.

Oh don't tell me..!

You will do it don't you? (Don't get me wrong, I do not care about when will the new version of Factorio will come out.)

[Rseding91]

Are you not using C++? YOu should be able to overwrite the allocator (new())?

Now, chunks - problematic.

But overwriting the allocator and redirecting it to "type specific" allocators (electricity, train, belts) should not be that complex.

A given entity has many things it touches in its update cycle. The plain entity itself is most of the time the minority of what it touches.

[authorized411]

Terrain generation looks great, the picture looks like a jungle. However, the vanilla ore generation still looks like the same noise generation. Wasn't the ore generation going to get an update as well? I thought that was in a previous FFF.

[Facme]

just out of curiousity...why was chosen for the lua language?

[PunkSkeleton]

Better memory organisation should help single threaded performance as this will use cache more efficient and will allow better pre-fetching. This shouldn't be linked to multi-threading at all.
There are countless of reasons why multi-threaded solution can work slower than single-threaded one. I don't believe that in an application that uses many megabytes of memory during each update cycle 3 threads will often invalidate each other's cache lines that are 64 bytes. I am much closer to believe the reason for this is that you're hitting a memory bandwidth cap already and doing multiple threads will not magically increase the memory throughput.

[MasterBuilder]

But these tasks are almost independent as neither trains or belts use electricity and belts don't interact with trains.

There are mods that add electric trains. There's even a mod that makes belts use electricity.

[FrodoOf9Fingers]

"There are only two hard things in Computer Science: cache invalidation and naming things."

-- Phil Karlton

[evildogbot100]

But these tasks are almost independent as neither trains or belts use electricity and belts don't interact with trains.

There are mods that add electric trains. There's even a mod that makes belts use electricity.

Well, I think scripts is done outside those tasks like there is other update subroutine exclusively for scripts whatever it does after or before those tasks.

[shadetheartist]

But, then, I come from a C background where "= new (class)" laziness isn't present.
I know my C99 code and force-of-habit is positively sprawling with "int number_of_[object]", "[object] **all_objects;" and some malloc/realloc wrappers to add, remove and get particular entities.

But, then, I come from a C background where "= new (class)" laziness isn't present.

I know my C99 code

"= new (class)" laziness

C99

laziness

> using c
> 99
> complains about sugary syntax
> not even using assembly
> not even using a op code table and a hex editor
> not even interfacing with the computer through willpower alone

[shadetheartist]

I feel like once the game is released, (and i know this has been mentioned before, but tentatively) the devs should really consider open sourcing the code. Because there are some very enthusiastic and talented people out here that might actually be able to take the time to go through and figure things out. And i'm not saying the devs couldn't do it too, just that it seems like 1.0 launches they are going to back off hard, which is perfectly reasonable.

I for one just want to marvel at the optimized code. I mean, you think your belt maneuvering is clever, you should see what they must have under the hood.

[leitk]

overwrite the allocator (new())

A given entity has many things it touches in its update cycle. The plain entity itself is most of the time the minority of what it touches.

I had good luck overriding new for a dll issue (16 bit days, yes I've been doing this for too long).
It may be possible to split the memory into functional groups (belts, trains, electricity, bots) and assign each item to one of those group with an overridden new, so they all get loaded together.
Insterters may be a problem because they interact with everything.

[Zulan]

Don't want to nitpick, but maybe this helps to find better information. The piece of memory cache in question is a cache line, it's size is usually 64 byte (a page on OS level is 4096 byte). The effect in question is called false sharing is a common issue for multi-threaded programs.

However, I am quite surprised it happens here. Entities are multiple cache lines in size - so the figure actually looks different - I would not expect to have so much interference in this case. Also the L1/L2 cache is quite small compared to the typical Factorio working set, so the active cache lines change alot during the an update phase, reducing the probability of a conflict between threads. But parallel performance is often surprisingly different in reality versus expectation.

That makes me wonder, by what observation have you figured out the reason for the performance issue?

[ske]

Interesting cache invalidation effects! Have you (or somebody else) been comparing the performance of factorio on different CPU architectures like Intel i9 7900x, AMD Ryzen 1800X, AMD Threadripper 1950X (with/without NUMA)? I'm asking for a friend who can't decide which CPU to buy.

[ske]

The starting location improvements are very important in my opinion to obtain competitive game modes that are fun for years. That is a whole range of games on its own which will need detail attention on its own. This part is only just starting. (Factorio spin-off? Expansion pack? Contributors? Paid mods? Paid maps? In-game store?)

When looking at your map example I don't see all resources I need to start close enough. If it's really competitive I would expect a hand-made map or a much more similar distribution of resources in the starting location.