Factorio Forums

orzelek wrote:One possible solution to allow for overall bigger Factories would be making them multi-surface. Factorissimo already does that on small scale.
It would allow for each surface to run on separate thread (should also help with memory bottlenecks - each core can have own cache and memory controller can handle more requests looking at stats given in this thread).
Then we would need some nice in game abstraction for this

Something like caves/varying levels of terrain and then entities that would share power and transport items/fluids between those.

Quite plausible would be making terrain semi-3d. And when you go over to higher level you would switch surface. With ability to dig through lower levels and build ramps up/down plus pillars for levels above this would make game both 3d and nicely scalable for multithreading. Seems like win-win

hoho wrote:Biggest problem with connected worlds is how to ensure they all stay synchronized.

As it stands, each player simulates actions of all other players. If you have several different worlds running in a grid, how would you verify that they're all still running in same overall state? If one server slows down for whatever reason and tick rate drops <60, would others also have to drop lower? What if some items get sent from the faster server to slower one and due to lower tick rate it won't be able to accept them all?

orzelek wrote:One possible solution to allow for overall bigger Factories would be making them multi-surface. Factorissimo already does that on small scale.
It would allow for each surface to run on separate thread (should also help with memory bottlenecks - each core can have own cache and memory controller can handle more requests looking at stats given in this thread).
Then we would need some nice in game abstraction for this

Something like caves/varying levels of terrain and then entities that would share power and transport items/fluids between those.

Quite plausible would be making terrain semi-3d. And when you go over to higher level you would switch surface. With ability to dig through lower levels and build ramps up/down plus pillars for levels above this would make game both 3d and nicely scalable for multithreading. Seems like win-win

ssilk wrote:TL;DR
The most interesting part about multi-threading etc. is to make even bigger worlds. But instead of targeting to multi-threading this can be achieved also, by concentrating more into interconnecting game-worlds (servers), cause that is similar - if made clever: The size of a world can be doubled by connecting a second server to the first.

ssilk wrote:But now I think RAM is the limiting bottleneck and so it is not possible/useful to go that way (increasing world by using more CPUs but everything on one computer) much further.

mrvn wrote:Can't you normalize the data and output MB/s or something? You numbers are pretty much meaningless and look quite the opposite of what you want to show.

BenSeidel wrote:If you don't believe me, benchmark it yourself. It's easy enough to do. Create a massive array (couple of 100 megs, even up to a gig) and access it randomly (don't use a rng generator as it will affect your results, just do something like x = x^7 or something similar). You can play round with the test to get all sorts of memory throughput, right the way up to 100% for sequential access

#include <atomic>
#include <chrono>
#include <iostream>
#include <stdint.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <thread>
#include <vector>

template <uint32_t Access(uint32_t)>
class AccessTest {
  uint32_t *memory;
  volatile uint32_t trash;
public:
  static const uint64_t allocSize = 1LL << 30;
  static const uint32_t sizeInMB = (allocSize * 4) >> 20;
  typedef std::chrono::duration<uint32_t, std::chrono::nanoseconds::period> ns;

  AccessTest() {
    memory = (uint32_t*)mmap(nullptr, allocSize * 4, PROT_READ | PROT_WRITE,
        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    for (uint32_t i = 0; i < allocSize; i++) {
      memory[i] = rand();
    }
  }
  ~AccessTest() {
    munmap((void*)memory, allocSize * 4);
  }

  ns accessPattern(uint32_t first) {
    uint32_t sum = 0;
    uint32_t index = first & (allocSize - 1);
    auto start = std::chrono::high_resolution_clock::now();
    for (uint32_t i = 0; i < allocSize; i++) {
      sum += memory[index];
      index = Access(index) & (allocSize - 1);
    }
    auto end = std::chrono::high_resolution_clock::now();
    trash = sum;
    return end - start;
  }

  double testNThreads(int N) {
    std::vector<std::thread> threads;
    std::atomic<uint32_t> nReady(0);
    std::atomic<uint64_t> totalTime(0);
    for (int i =0; i < N; i++) {
      threads.emplace_back([&](uint32_t start) {
          nReady++;
          while (nReady < N);
          totalTime.fetch_add(accessPattern(start).count());
      }, rand());
    }
    for (auto & t : threads)
      t.join();
    return totalTime / N;
  }

  static double getAverage(int N) {
    AccessTest<Access> base;
    return base.testNThreads(N);
  }
};

uint32_t sequential(uint32_t start) { return start + 1; }
uint32_t random(uint32_t x) {
  x ^= x << 13;
  x ^= x >> 17;
  x ^= x << 5;
  return x;
}
uint32_t zero(uint32_t start) { return random(start) & 1 + 1; }

double rateCalc(double timeInNS) {
  return AccessTest<sequential>::sizeInMB / timeInNS * 1e9;
}

int main() {
  for (int i = 1; i <= 16; i *= 2) {
    std::cout << "For " << i << " threads:\n";
    double seqTime = AccessTest<sequential>::getAverage(i);
    double rngTime = AccessTest<random>::getAverage(i);
    double zeroTime = AccessTest<zero>::getAverage(i);
    std::cout << "Sequential access did " << rateCalc(seqTime) << "MiB/s\n";
    std::cout << "Random access did " << rateCalc(rngTime) << "MiB/s\n";
    std::cout << "Pure cache access did " << rateCalc(zeroTime) << "MiB/s\n";
  }
}

mrvn wrote:Can't you normalize the data and output MB/s or something? You numbers are pretty much meaningless and look quite the opposite of what you want to show.

jcranmer wrote:Microbenchmarks are actually very hard to design because you very often end up measuring (and optimizing!) for results that are completely pointless. But since you're so insistent on this point, I'll indulge. Here's my results (note that it's per-thread average throughput, not total throughput):

BenSeidel wrote:Sooo true, microbenchmarks are absolutely pointless as you can get them to say whatever you wish. The main reason I did not post my code is that it's shocking and doesn't do a bunch of stuff that you need to do in this sort of test, like synchronise the threads using a busy loop like you did. But when I saw an increase in performance by removing the modulo and using a bitmask, I knew I was in the ball-park. And that's all you want, a ball-park figure. In this case I don't believe that you really want to spend hours trying to get as much performance out of your benchmark as possible, we are not trying to sell the chip to someone. The point of the exercise is to try and look at "general" code and how it would behave if you could run it over multiple threads, which I believe both tests have done. Who cares that you have 3 exponent operations in one test and an addition on the other. If you swap the index bitmask with a modulo operation then you can see that yours is also in the ballpark.

It's strange that the cache access was soooo much slower than the sequential access for one thread. In theory it should be much much faster, or at least be somewhat similar. I find it really surprising that running multiple threads closes the gap between sequential access and random access so dramatically, that is something I have never seen before as I have always found a marked improvement with the sequential reads over the random reads. Now I want to see if other machines exhibit this behaviour. If they do then it really blows the whole "we can make it faster by looking at our memory access" argument out of the water.

jcranmer, your cache bandwidth doesn't really seem to have too much to do with actual cache performance. Reading from L2 cache should be an order of magnitude greater, at around 300GB/s.

jcranmer wrote:It is surprisingly common that an attempt to repeatedly measure a tight loop instead measures the time it takes to do nops

jcranmer wrote:It's not at all strange, not if you look at the generated assembly code

jcranmer wrote:As for why the sequential access fell behind random access, my suspicion is that the hyperthreaded core scheduling screwed up the cache prefetching

hoho wrote: I should also be working right now so I can't really come up with better code either

BenSeidel wrote:

hoho wrote: I should also be working right now so I can't really come up with better code either

Meh, ball-park guys... unless there is something really off, why bother? (and "coz I want to" is a valid answer , Don't let me stop you)

hoho wrote:I found another benchmark I'd like to get running: https://github.com/maleadt/pChase

BenSeidel wrote:

hoho wrote:I found another benchmark I'd like to get running: https://github.com/maleadt/pChase

Cool, I would like to see if a pointer read is any slower than an arithmetic generated version for random access. If the prefetcher is unable to work, how far can the out-of-order instruction execution go? Is it able to start the next load? And I don't mean a 2x slowdown, I want to see face-planting 486 speeds. In theory, a stall is a stall. If you are "chasing pointers" then it will stall until you get the next pointer, if you are generating the next address then at some point you must have saturated the pipeline, thereby stalling until the oldest "sum" has been completed.

• Which data structures are used and accessed the most, linked list, array / vector?
• What type are the elements, fixed size structures (objects) or references to objects?
• What size is the typical element?
• What are the access patterns that happen most of the time, sequential traversal/access or random-access to a specific index?

mrvn wrote:Get it right and 2 cores will be nearly twice as fast and for something like factorio you can do 16 cores at bascialy 16 times the speed given a large enough factory.

hansinator wrote:Based on that information we can do benchmarks that are more representative.

hansinator wrote:Consider this and the fact that insertion and removal often requires copying the whole array to a new one. If you google for "vector vs list performance" you can find some peoples opinions and benchmarks on that topic (C++ related).

hoho wrote:I'm fairly certain that factorio devs themselves have ran benchmarks on the actual code itself while trying various solutions.

They have vastly better overview of where the bottlenecks exist and why. No amount of synthetic benchmarks are as useful as running a game session through VTune.

hoho wrote: Speed difference between linked lists and arrays VASTLY depends on how you use them. If you don't have to have the list sorted meaning you won't be inserting stuff randomly in the middle then it's pretty darn hard to write array-based thingy that's slower than linked list.

Similarly, if you require sorted list and are moving or adding stuff to the middle of the list/array but you do those additions/removals at vastly lower rate than iterating over it or searching from it, using arrays can easily be more effective even if each addition/removal requires moving around half the array.

hansinator wrote:Mentioning a $900+ profiling tool doesn't help either.

hansinator wrote:From my point of view your argumentation more or less translates to "you don't know what you are talking about and there is no way you can ever achieve something meaninful here". Which is something I don't agree to. So maybe we can continue discussing that memory stuff and do benchmarks as we like to do, please?

hansinator wrote:That's what they told you in algorithms & data structures class based on books written in the late 90's

hansinator wrote:Nowadays we have memory speeds commonly approaching 50gb/s for sequential accesses. Thus copying around arrays is dirt-cheap.

Zulan wrote: In general, my feeling is that chunks are too small for dynamic scheduling (as Harkonnen also indicates), and larger subgrids would still expose enough parallelism.

   ______                           ______
  |      |                         |      |
  |chunk | -- interacts with -->   |chunk |
  |______|                         |______|


 Tiles to claculate inside "chunk": 9
 Border, that interacts with other "chunks": 12
 

Participation probability =  Perimeter (outer) / Area (inner)