Hacker News Reader

Comment by Twinklebreeze | Hacker News Reader

Every time multi-threading gets brought up one of the devs explains that being single threaded isn't the bottleneck. It is the cpu cache that is the bottleneck.

View on HN

And if it was written with a single thread in mind (which it most likely has been) naively 'multi-threading' it will likely not help do much except increase the number of bugs. Too many independent but intertwined systems communicating with each other.

Making DF use multiple cores efficiently would be amazing, but I have serious doubts its viable in the short-ish term without a significant rewrite. The most you're likely to see is some peripheral systems offloaded onto background threads when possible.

My hope is that with the upcoming Steam release they make enough money to hire another veteran game programmer or two to help them work on game and make it perform better.

DF has many things that could be multithreaded or perhaps even vectorized (such as the heat simulations) very easily.

I agree you can't make the whole agent-based system multithreaded overnight but there are many calculations happening with every 'tick' that I would be quite confident are easily parallelizable.

Isn't (a large part of) DF basically a huge cellular automaton? That problem is already solved for multiple threads.

In a lot of ways, yes it is. But that's where theory and practice diverge. Could all the current systems of DF be implemented anew in a way that easily scales to however many CPU cores are available? Most likely in some way yes they could be. Could the current systems as implemented be ported to better scale with the number of available CPU cores? Questionable.

Game engines are incredibly complex -- there are usually dozens if not hundreds of systems interacting with each other. Over time, this all ossifies to the point where making changes to one system requires changes to many other systems. This is kind of a fact of life with almost every game engine or codebase that I have encountered, worked with, or heard of. When you start getting into more than a decade of development, there are going to be a lot of tangled systems that are going to be very difficult to pull apart.

Yes, the fundamental problem may be solved for multiple threads, but DF solved it for one thread, and that solution is part of what makes DF fun. Messing with that solution is asking for trouble.

Just because something uses a grid doesn't mean it's a cellular automaton. You can probably write DF as a cellular automaton but that's probably not what happened.

If dwarfs have x,y coordinates that mark their position and the coordinates are changed when they move then it would not be a cellular automaton.

A cellular automaton would take a cell and look at surrounding cells to see if there is a dwarf that wants to move to the currently processed cell and switch the current cell to a new dwarf cell. The dwarf cell would see that the dwarf can successfully move and delete the dwarf cell.

Which method do you think is DF using?

I think individual dwarves could still be modeled as cells, if there was an additional layer (or a single cell?) holding their future actions.

The automaton would lose the nice property of being spatially isomorphic to the screen, and the possible states would explode, but if my understanding is correct, it could still be a cellular automaton.

Forgive my ignorance, but do you have any good references to multi-threaded cellular automata implementations? This is something I've been dabbling with myself.

You have two grids. Clear grid 2. Go over grid 1, calculate the new state for the current cell, write it to the second grid. At the end of a step you swap the grids.

Just slap on a good old "#pragma omp parallel for" with OpenMP (a nice guide is here [0]).

[0] https://bisqwit.iki.fi/story/howto/openmp/

I also found this pdf if you are interested. http://www.shodor.org/media/content/petascale/materials/UPMo...

You could even do it on the GPU, with 1 thread per cell.

We don't really know how feasible multithreading is, but the community suspects at least some tasks could be computed on different threads, such as e.g. the pathfinding stuff that one of the worst offenders when it comes to FPS.

Does that sound right? Do I have this wrong: there is too much to cache so some of the memory goes to RAM or disk where loading will take longer than cache. You could move some of the loading to another thread so that the UI (text or otherwise) can continue while other data in the backend is moved around between cache, RAM, and disk, and then processed before sending to the interface.

Don't modern processors have more cache available between all cores than available to a single core?

They must mean its memory I/O bound.

I think they meant it only runs quickly enough when everything's in cache? But that doesn't make much sense to me. It's really hard for me to believe it'd be I/O bound though, when memory bandwidth is like tens+ of gigabytes per second?

IO bound can also mean that memory latency is a problem. It's not difficult to believe that DF is doing lots of pointer chasing.

Reply on news.ycombinator.com