Friday Facts #215 - Multithreading issues

[galibert]

the devs should really consider open sourcing the code.

Heck No.

If you're interested in working on the code, reach out to the devs and ask for a Job, You can sign an NDA and I'm sure the'd love to have you, but open sourcing the code is business suicide.

Although I'd never try to tell anyone to open-source anything they don't want to, I think this statement is odd. Open source requires a very different business model to turn a profit but you can't just say "suicide" as there is a near-endless list of counterexamples.

There are a lot of counterexamples in the software-as-tool domain. I don't know of any in the game domain. There may be one or two exceptions, but making a gamedev studio make enough money to survive with open-sourced games seems illusory. Different dynamics apply.

[galibert]

Sharing and the whole invalidation protocol (MESI, MESIF, etc) is done at the cacheline level, not at the page level. That makes the granularity 64 bytes, not 4K. From the previous FFF I gather that not many structures are less than 64 bytes, so I doubt there's a sharing issue in practice. There's probably a locality issue, which update-by-chunks would help (it may even help in the single-threaded case), but the allocation layout is probably not very significant.

I think you're right about the main problem being memory bandwidth and not cpu, and no multi-core solution is going to solve that.

There's an easy way to check that too: run multiple factorio instances at the same time, with UPS unthrottled. The allocations will obviously be independant, they're in different processes. You'll then see how fast things go with perfect multi-threading with a virtual base size that's the sum of the different running ones. If it's not significantly better than the single-threaded version, there's no gain to get in that particular rabbit hole.

OG.

[ske]

On one specific save file:

That save runs at ~35 ups with my 7700k.

On Ryzen 7 1800X OC 4.1GHZ + DDR4 3200GHz I get 22.5 UPS

Thanks

That difference is bigger than what I expected. This probably means that even old/cheap intel processors are still faster than any Ryzen.

[sicklag]

.

[pleegwat]

Notwithstanding the interesting discussion about whether your analysis is right, I have a suggestion for achieving parallel thread update isolation at whatever granularity you need without moving data as entities move.

Given N threads that will be updating in parallel some object type T, create N slab allocators for T - one per thread - and place entities via the slab allocator chosen by some partition function based on the id. E.g. you could take the id & 0x0f to mask across 16 Threads. Or you could do a crc32 and then take the bottom N bits. Or whatever .

Entities affect each other, and the order in which they're evaluated matters. Consider a single chest with a single item remaining, and two inserters attempting to pick up the item in the same tick. Only the first inserter evaluated can pick up the item, and which one that is needs to be consistent.

There are other ways to fix that, but that's not a simple fix either.

[meganothing]

There are a lot of counterexamples in the software-as-tool domain. I don't know of any in the game domain. There may be one or two exceptions, but making a gamedev studio make enough money to survive with open-sourced games seems illusory. Different dynamics apply.

Open-sourcing the game now might be a bad idea, open-sourcing Factorio years after release (like someone already suggested) would be a good idea IMHO. At that time sales are already a slow trickle that is kept alive by a still active community and the occasional steam or gog sale to people who will just put the game on top of their pile of shame. The latter happens anyway, the former can be helped by open sourcing it (naturally with a non-commercial-only clause).

For a positive example see the original Doom which still sold 500.000 copies on steam since 2007, while the source code was released earlier, in 1997/1999. For a positive example of bug removal look at Gothic 3 which was buggy as hell at release. After open-sourcing it the community took over and polished the game (this is hearsay though, I didn't play it myself). That works quite well for bug fixing and polishing, I don't think this would work very well for optimizing the game loop though.

There are a lot of commercial games that were open-sourced later, by the way: https://en.wikipedia.org/wiki/Category: ... ource_code or https://en.wikipedia.org/wiki/List_of_c ... ource_code

[ske]

One thing missing about the "open sourcing factorio" scenario that is the definition of what we actually mean with "open source":

* Public domain like "do what you want with it".
* GPL or similar like "do what you want but you have to provide the source".
* Copyrighted but open to view like "look at it but you cannot use it without permission".
* Open only to auditors/collaborators like "if you sign this NDA we let you have a look".
* Licensed as a game engine like "you can change the source and compile it but we get royalties".
* many other models I forgot.

Then there is the split between code and art. Which is what id software did. Source is free but maps are copyright restricted. They did not suffer because of open sourcing the engine.

I don't think opening the source of factorio at this point would sway the pendulum much. It's a very specialized game engine built to run a particular kind of game very well. You probably have to invest considerable time to do anything useful with it beside changes to the core game itself. Once the big parts of development are done and it's up to modders to keep the game alive this changes. Then, modders can come in and develop their own games with the engine. There is Lua now but modders will really want or need to modify the core engine at some point in time. Choosing a licensing/business model that still keeps up a revenue stream for both, the engine developers, and modders would greatly benefit the game in the long run.

[TheTom]

Can we expect an early build this year? Possibly mid December, as my birthday gift?

Not asking for a date, just an indication on how you guys think you progress and when you plan to drop the next release.

[Alice3173]

* Copyrighted but open to view like "look at it but you cannot use it without permission".
* Open only to auditors/collaborators like "if you sign this NDA we let you have a look".
* Licensed as a game engine like "you can change the source and compile it but we get royalties".

In my opinion all three of these are completely fair. They allow people a look into the source code without running a huge risk of copycats.

I don't think opening the source of factorio at this point would sway the pendulum much. It's a very specialized game engine built to run a particular kind of game very well. You probably have to invest considerable time to do anything useful with it beside changes to the core game itself.

It could be useful for people trying to learn concepts that Factorio does well though.

[RobertTerwilliger]

I'm here to just say: You guys pay really much attention to optimising your "product" (in a good way), changing good to perfect. Probably, you do this even more thoroughly than most monsters of programming industry, and for sure much more than most indie game devs, whos games are usually fun as idea, but bugged as hell (not naming any).

Excellent job you're doing there : )

PS. Sorry if my language sucks today - it's 4:48 am here... : )

[Zulan]

Modern processors (think after ~2005) all have multi-way cache association with aggressive snooping via a concept of broadcasting (mostly only for SIMD instructions). The only time a total page invalidation should occur ('should' instead of 'could' because overclocking cache frequency really messes with this) is if 2 processors both modified the same cache line in their own caches and a flush was triggered within a few cycles of each other AND the first line to flush modified the location of the target of the second flush. The page is then synced from L3 and written to memory asynchronously so it's not the end of the world if it happens every now and then.

That's interesting I haven't seen this and was kinda assuming that the respective snoop requests prevent this from happening. Do you have any references for this effect?

From reading the blog, it clearly sounded like classic false sharing with a mixed up terminology to me.

Depending on which compiler you're using, you can hint L3 temporal locality for pointers. This approach can somewhat help with having a long reference chain if you keep pointers in the cache instead of objects as pointers are much less likely to get evicted; this might also be the most effective solution if most of the pointers don't change every frame (if they do change frequently then you should reconsider that design decision because it completely removes the processor's ability to cache A->D in the A->B->C->D chain). See GCC __builtin_prefetch and I'm sure Clang has an equivalent.

Prefetching is used for several update loops (see FFF-204) (in 0.16), it does use PREFETCHT0 (which basically puts the line in all the fastest possible cache levels) through the respective compiler intrinsics. The value was determined experimentally, but it also seems the most sensible thing to me. IIRC the performance difference between the different temporal hints were not so large, which non-temporal (i.e. fastest cache only) having a little benefit in some cases, but overall not better. Non-temporal might also be a bit more dangerous in terms of performance effect on different architectures, although that's speculation based on the discussion about MOVNT on Ryzen.

[CopperBoltwire]

After reading the news article on steam about multithreading, i felt the urge/need to say the following:

I understood most of what was explained, most of it.
But if you can't make that kind of update before v1.0 comes out, maybe make that as part of patch/update version 2.0?

I have, on purpose neglected to read and find any info on what you guys have planned for Factorio.
As i like to see it as a surprise when actually released.
More fun for me that way.
But making the game run better, ei. Multithreading IS a big deal, and could not help but see the article.

This is, as many have pointed out, a great game.

My only hope is the AI and Monsters become more... interesting. As is right now, they feel rather lackluster and even with mods, a tame experience.

[Impatient]

I just want to throw this at you: Is multithreading a first step to a multicore architecture of factorio?

If my observations are correct, then factorio runs on a single core. Though most computers have multicore processors today. Making factorio run on multiple cores would really speed things up.

[vanatteveldt]

I just want to throw this at you: Is multithreading a first step to a multicore architecture of factorio?

If my observations are correct, then factorio runs on a single core. Though most computers have multicore processors today. Making factorio run on multiple cores would really speed things up.

As soon as you have multiple threads, they can be run on different cores. The problem is efficiently using multiple threads for a game where a lot of entities can interact with each other, and where deterministic updates are used to enable multiplayer mode. Also, since factorio is pretty memory-heavy, it is not given that the CPU is the bottleneck, and multiple threads can actually require more memory fetching or make it more difficult to prefetch the right information.

As can be seen from multiple posts on the topic, (a) the devs are actively working on it, (b) it is far from simple to implement, (c) it is far from simple to predict performance gains due to caching, optimizing etc., so (d) benchmarking is the only way to see if something actually improves performance.

[someone1337]

Try this: Split the map into segments of chunks - like 32*32 chunks is a segment - there will be some size where the overhead outweights the benefits: to small segment: too much overhead, too big segment: no improvement.

Make a thread do all the update work for one segment - basically do what the main loop does/"run like multiple game instances" for parts of the world.
Make a thread update multiple segments in sequence - it doesnt make sense to have 1 thread per segment as some will be work intensive and others wont, only eating up more ram.
Make segments independent and basically self-sustaining. (and us modders a way to timefreeze/skip processing of selected segments )
This will basically give you multiple updated segments in parallel, but some synchronisation needs to happen on segment borders.
Maybe you can split the save-serialisation-data to multiple such files, going from one .zip to one directory with files and a segments/ with all the serialised files compressed separately - to even more decouple the one big thing into multiple smaller onces.

The challenge will be synchronisation all the time. That is, where you will need to partially get rid of the main-update-loop/tick based system and go partially event/message-based.

If you want to stay with a central global data block (for now), try going for update events: In paralell check what needs to get updated, push to update-event-queue.
Afterwards do the updates in a single RW thread.
This will most likely not really solve any issues in the long run, but may be a good start to a multithreaded architecture.

I would expect that you willl need to rewrite most of your current codebase, as transitioning from single-threaded to paralell computing is not a trivial task.

[Zavian]

Since people are making comments that have already been addressed elsewhere, here is the existing thread on multi-threading factorio. viewtopic.php?f=5&t=39893 . It contains a number of comments form the developers including viewtopic.php?f=5&t=39893&start=60#p238247 which is Harkonnen's writeup on the work he did on multithrading Factorio. If you are interested in this topic, then it might be worth scrolling through and reading the developer replies there.

[player8472]

Sad to hear, that there probably won't be any real multithreading in the "near" future.

Especially since i own a Ryzen 1600X, which seems to be worse than my Ivy-Bridge i5 (Which is used as my Server right now) for Factorio.

But at least now there is some definity, which probably means I'll have to spend another 2k on another pc just for factorio...

Regarding this:

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.

I'd have a look on this chart:
https://www.cpubenchmark.net/singleThread.html

It should give an overview on what to buy for more or less single-threaded processes.
And yes, if you don't do heavy multithreading you probably shouldn't get an i9.

In addition to the pricetag it isn't even the best for single-thread apps.

From what I've read so far in this and other threads, I'd also look into memory transfer speed. Even the slowest DDR4 Module will surpass the fastest DDR3 Module. (DDR3 1866 ~ 14.9 GB/s / DDR4 2133 ~ 17 GB/s)

[bobingabout]

Those maps look totally different. and I'm not talking about the multiple starting areas being seamless or not.

As for the multithreading memory allocation thing...
Well, you have Electrical, trains and belts.
You also plan to have different chunks as their own memory cluster for multithreading. bringing up the issue of what chunk memory cluster do you put a train in.

Well... Don't.

Most entities like assembling machines don't move between chunks, putting those in a chunk memory cluster would work.
Trains, cars, biters etc do move between chunks... instead of doing those as a per chunk basis... just do them as a per type instead!

I'm suggesting have a memory class for Vehicles (maybe two, one for Trains and one for cars/tanks), and another for enemies (unit types, so biters and spitters, plus anything added by modders)

It might not be as efficient as a memory class for a specific chunk when you're looking at a map consisting of hundreds of chunks, but how many cores does the typical PC have? 6 physical cores with 12 threads is likely what a high end gaming PC looks like these days, unless you have something like a threadripper or core i9. having a thread for trains, another for enemies, doesn't seem too... crippling, especially considering it's all done in the same thread right now.

You'll still have all the other stuff like Belts and Factories likely in small clusters of threads to distribute the load.

[ratchetfreak]

IMO the first step should be to make everything allocator aware. Create a (statefull) allocator API and default it to use your existing new/delete approach.

That way you have a platform to do experiments with. You can add logging to see where a lot of allocations happen and see if it makes sense to pool them. You may also be able to see spots where a lot gets allocated and then deleted, see if you can instead use a arena for that which has a noop free but instead just gets purged at the end.

There is very little to lose from starting the move to allocator awareness earlier rather than later.

[Lubricus]

Sad to hear, that there probably won't be any real multithreading in the "near" future.

It should give an overview on what to buy for more or less single-threaded processes.
And yes, if you don't do heavy multithreading you probably shouldn't get an i9.

Haven't the i9 double the memory bandwidth? Wube have stated Factorio is more memory latency/bandwidth limited than core speed limited? Then there is also different cache sizes on different CPU's