Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 11 12 [13] 14 15 16

Author Topic: Pathfinding is not a major cause of FPS death  (Read 59342 times)

Treah

  • Bay Watcher
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #180 on: January 31, 2023, 11:24:04 am »

I did another 3-minute profile on my 260-citizen fort, this time with the knowledge of the source. Percents are going to overlap some. Specific seconds are not.

The slowest thing was line-of-sight checks. Due to the fact that it was only counting the checks in the function itself, this was a total of 14.7% of CPU time. However, if you remove one specific thing from line-of-sight checks (more on that later), it's 8%, and thus faster than the next thing. 13.181s in the function itself.

The slowest individual thing in the fort was checking family relationships. This was mostly, so far as I could tell, called in the context of watching performances, probably to tell if they should be feeling love at their family members or whatever. This was 9% of CPU time. 15.537 in the function.

Next is getting glowtiles. This is required for line-of-sight tests, naturally. Glowtile'd creatures are visible from farther in the dark. 5.7%. This is the slowest part of line-of-sight checks, at least as far as stuff that's actually done. 11.749s.

#4 is the game's software rescale function. 4.3%, 7.440s

#5 is probably tile rendering. I think. I see a couple xmms in there and there's a lot of bizarre magic numbers that suggest a switch-case to me. 13.2%, most of which is in subcalls. 5.350s.

#6 is... uh, temperature stuff, I think? 6.3%, 4.888s.

...it just goes like this for a while.

The main point I'm getting to is that 1%, 0.687s, is path finding. 1%. 1%. I was wrong earlier and I apologize; pathfinding is not a cause of FPS death at all. It is completely irrelevant to the "slow, inevitable" FPS death people complain about.

Last time I had FPS issues however they were fixed by walling off the cavern. Unless something major changed with DF 50 vs 47 walling off the cavern made the game go from 4fps to 45... That is pretty significant change and that cant really be explained with what your encountering. Maybe there is some kind of edge cases where path finding does indeed consume more CPU then what your seeing here. I would probably gather some save files from community members that have FPS death and check this again.
Logged

Shepanator

  • Escaped Lunatic
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #181 on: January 31, 2023, 11:30:48 am »

older generations of intel core are also worse than newer ones, believe it or not, and the best CPU on the market for playing dwarf fortress is probably an 8-core AMD CPU, and, as of next month, a 16-core CPU with 32 threads... because it has 144MB of L2+L3 cache.

This might not be entirely true. The cpu cores in the upcoming 12 and 16 core 3D v-cache CPUs from AMD are split over 2 dies, and the increased chunk of cache is actually only present on one of those dies. Also critically for single threaded apps only cores on the die without the extra chunk of cache can boost up the max advertised frequency. Granted the faster cores can still access the big cache on the other die, but that's only after it's already checked it's own cache and at the penalty of increased latency. This higher cache latency might negate the clock frequency benefit to the point where the 8 core is just as fast as the 12 & 16 core in single threaded cache bound apps like DF. I'm also wondering if our OS's thread manager is going to be aware of these split-cache chips and will be smart enough to schedule threads onto the most appropriate cores. I guess we will have to wait until somebody has run benchmarks with these CPUs to see.
Logged

Sethatos

  • Bay Watcher
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #182 on: January 31, 2023, 11:48:49 am »

So what would that mean for a multi generational fort like Archcrystal? Does it only do a check for family members that are still alive? In the relationships window it will only show up to grandparents I think, although you can select and see their grandparents from that menu.
Logged

mislavcro

  • Escaped Lunatic
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #183 on: January 31, 2023, 01:22:26 pm »

Has anybody ever thought about making dedicated hardware for running DF?

With access to source code, how feasiable would be to design DF optimized hardware? I know that modern processors, RAMs and motherboards are extremely complex to design and would take eons. But what if by using smaller processors like the ones on raspberry and using some clever memory channels on it, and with help of few dedicated FPGAs for some complex number crunching, would it be possible to make custom DF hardware that wouldn't take ages to develop?

It's been well over 10 years since I meddled with FPGAs and hardware design so my knowledge is a little bit rusty.
Logged

Telgin

  • Bay Watcher
  • Professional Programmer
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #184 on: January 31, 2023, 02:01:35 pm »

It's at least possible in theory, but I can't imagine that it would be possible to do in anything approaching a reasonable amount of time or effort.  As Putnam has discovered, even multithreading parts of the game that are amenable to it has been difficult and not always worth doing.  Offloading parts to dedicated hardware would be an order of magnitude harder, even with tools that try to do things like convert C code to Verilog or VHDL.

I'm pretty sure centralized memory access would always be the bottleneck in a system like that.  As an example, Putnam mentioned that looking up familial relationships was a surprisingly big time sink in the game right now.  That's almost certainly because of random memory accesses across GB of RAM.  An accelerator board would mean the game has to pause at that step, shuttle the data over to the accelerator, let it do its job, shuttle the data back and then pick up where it left off.  Isolating those bits of the historical figure data so only that has to be copied would help, but it's still a problem and adds complexities of its own.

I guess if you had a truly amazing FPGA with a modern x86 CPU attached that shared a memory bus, you might be able to build some FPGA logic that accelerated some parts of the game and get speedups from it.  One advantage of an FPGA circuit is that at least you might not suffer penalties in places a normal CPU would with branch mispredictions, but it depends on the circuit design.  Long, complex circuits are going to have terrible clock rates.

Actually, I'd really like to see just how much of DF's time is spent waiting on RAM.  I haven't used a modern profiler in ages so I don't know if you can even get that information readily
Logged
Through pain, I find wisdom.

A_Curious_Cat

  • Bay Watcher
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #185 on: January 31, 2023, 02:15:36 pm »

Has anybody ever thought about making dedicated hardware for running DF?

Even assuming it were possible, would it make economic sense?
Logged
Really hoping somebody puts this in their signature.

mislavcro

  • Escaped Lunatic
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #186 on: January 31, 2023, 02:23:54 pm »

Has anybody ever thought about making dedicated hardware for running DF?

Even assuming it were possible, would it make economic sense?

Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.

Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy? 
Logged

Putnam

  • Bay Watcher
  • DAT WIZARD
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #187 on: January 31, 2023, 02:30:07 pm »

So what would that mean for a multi generational fort like Archcrystal? Does it only do a check for family members that are still alive? In the relationships window it will only show up to grandparents I think, although you can select and see their grandparents from that menu.

Each person who is doing a "listen to story" or whatever is checking that the person they are listening to is their family member or vice versa, so it gets exacerbated massively by having highly populated, tightly-packed taverns (which I did in this profile). The search looks through every historical figure, in a binary search, i.e. it's O(logn), but if you take into account how many units do it it's sorta O(mlogn), which can indeed grow pretty fast.

Last time I had FPS issues however they were fixed by walling off the cavern. Unless something major changed with DF 50 vs 47 walling off the cavern made the game go from 4fps to 45... That is pretty significant change and that cant really be explained with what your encountering. Maybe there is some kind of edge cases where path finding does indeed consume more CPU then what your seeing here. I would probably gather some save files from community members that have FPS death and check this again.

There are multiple known edge cases. There was probably something stuck in some trees in the caverns that wanted to get into your fort or out onto the surface, and walling it off made the caverns completely cut off, thus making it stop trying to do that. Being stuck in trees makes things pathfind every tick or so, which is indeed extremely slow, but most of the time stuff just isn't pathfinding that much.

I did another 3-minute profile on my 260-citizen fort, this time with the knowledge of the source. Percents are going to overlap some. Specific seconds are not.

The slowest thing was line-of-sight checks. Due to the fact that it was only counting the checks in the function itself, this was a total of 14.7% of CPU time. However, if you remove one specific thing from line-of-sight checks (more on that later), it's 8%, and thus faster than the next thing. 13.181s in the function itself.

Great to see numbers here, thanks!

I know 14.7% doesn't point to any massive optimization potential, but -- is the line-of-sight implementation more amenable to a concurrent/thread-pool approach than the pathfinding?  I would not expect LOS to use global mutable state, but I wouldn't have expected that for pathfinding either, so what do I know.

Technically yeah, could make a bunch of futures that fill out the line-of-sight info for each individual unit before they're used for the individual units, but the biggest intervention right now is probably just optimizing the "get glowtile" function lol

PK1312

  • Bay Watcher
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #188 on: January 31, 2023, 02:43:20 pm »

Wow, really cool stuff here. Never would have guessed this was playing such a big part in FPS death. Thanks for sharing!
Logged

A_Curious_Cat

  • Bay Watcher
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #189 on: January 31, 2023, 02:49:13 pm »

Has anybody ever thought about making dedicated hardware for running DF?

Even assuming it were possible, would it make economic sense?

Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.

Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy?

There’s a difference between someone sitting down and writing a program, and someone creating a microchip.  One just requires time, dedication, knowledge, and a basic computer (at a minimum.  It’s best to also have a decently recent computer to test it on, as well…).  The other requires a lot of very expensive machinery.  That machinery must be paid for somehow, which means selling the chips.  My question is whether enough chips can be sold to offset the costs of producing them.
Logged
Really hoping somebody puts this in their signature.

mislavcro

  • Escaped Lunatic
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #190 on: January 31, 2023, 02:53:09 pm »

Has anybody ever thought about making dedicated hardware for running DF?

Even assuming it were possible, would it make economic sense?

Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.

Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy?

There’s a difference between someone sitting down and writing a program, and someone creating a microchip.  One just requires time, dedication, knowledge, and a basic computer (at a minimum.  It’s best to also have a decently recent computer to test it on, as well…).  The other requires a lot of very expensive machinery.  That machinery must be paid for somehow, which means selling the chips.  My question is whether enough chips can be sold to offset the costs of producing them.

Nobody said anything about creating a microchip. It's about buying already created microchips and developing board for them, and then programming them to suit your need.

I'm guessing you have no knowledge of how FPGAs work. They're not really expensive and you could start out with almost the same money it takes to buy a computer. There are already kits with FPGAs on them which are little more expensive, but almost the same money as a computer. The real way would be to design the PCB yourself, and still that's not expensive to produce either. You can get 100 pieces 200x200 mm 8 layer PCBs for the price of 7.4$ per PCB.
« Last Edit: January 31, 2023, 03:04:45 pm by mislavcro »
Logged

mislavcro

  • Escaped Lunatic
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #191 on: January 31, 2023, 02:57:20 pm »

This message was posted by error.
« Last Edit: January 31, 2023, 02:58:55 pm by mislavcro »
Logged

Mason11987

  • Bay Watcher
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #192 on: January 31, 2023, 03:04:42 pm »

So what would that mean for a multi generational fort like Archcrystal? Does it only do a check for family members that are still alive? In the relationships window it will only show up to grandparents I think, although you can select and see their grandparents from that menu.

Each person who is doing a "listen to story" or whatever is checking that the person they are listening to is their family member or vice versa, so it gets exacerbated massively by having highly populated, tightly-packed taverns (which I did in this profile). The search looks through every historical figure, in a binary search, i.e. it's O(logn), but if you take into account how many units do it it's sorta O(mlogn), which can indeed grow pretty fast.

Am I right in assuming then that the more historical figures there are (ie, the more history that has been generated) the bigger impact this has?

A_Curious_Cat

  • Bay Watcher
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #193 on: January 31, 2023, 03:10:27 pm »

Has anybody ever thought about making dedicated hardware for running DF?

Even assuming it were possible, would it make economic sense?

Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.

Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy?

There’s a difference between someone sitting down and writing a program, and someone creating a microchip.  One just requires time, dedication, knowledge, and a basic computer (at a minimum.  It’s best to also have a decently recent computer to test it on, as well…).  The other requires a lot of very expensive machinery.  That machinery must be paid for somehow, which means selling the chips.  My question is whether enough chips can be sold to offset the costs of producing them.

Then you have no knowledge of how FPGAs work. They're not really expensive and you could start out with almost the same money it takes to buy a computer

I’m not talking about FPGAs.  The question was whether dedicated hardware would make economic sense to produce.  FPGAs can be reprogrammed.  That means they are not “dedicated”.  “Dedicated hardware” would mean something like an ASIC or perhaps even a dedicated CPU.

In any case, you may want to consider the case of the PhysX engine.  It was originally developed to run on an FPGA board that it shipped with.  Eventually, the company that made it was bought out by NVidia.  Nvidia rewrote it using CUDA and ceased sales of the FPGA boards as all that was required now was a decently recent graphics card (note, of course, that this is all academic as I don’t consider GPGPU programming to be using dedicated hardware either…).
Logged
Really hoping somebody puts this in their signature.

mislavcro

  • Escaped Lunatic
    • View Profile
Re: Pathfinding is not a major cause of FPS death
« Reply #194 on: January 31, 2023, 03:18:20 pm »

Has anybody ever thought about making dedicated hardware for running DF?

Even assuming it were possible, would it make economic sense?

Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.

Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy?

There’s a difference between someone sitting down and writing a program, and someone creating a microchip.  One just requires time, dedication, knowledge, and a basic computer (at a minimum.  It’s best to also have a decently recent computer to test it on, as well…).  The other requires a lot of very expensive machinery.  That machinery must be paid for somehow, which means selling the chips.  My question is whether enough chips can be sold to offset the costs of producing them.

Then you have no knowledge of how FPGAs work. They're not really expensive and you could start out with almost the same money it takes to buy a computer

I’m not talking about FPGAs.  The question was whether dedicated hardware would make economic sense to produce.  FPGAs can be reprogrammed.  That means they are not “dedicated”.  “Dedicated hardware” would mean something like an ASIC or perhaps even a dedicated CPU.

In any case, you may want to consider the case of the PhysX engine.  It was originally developed to run on an FPGA board that it shipped with.  Eventually, the company that made it was bought out by NVidia.  Nvidia rewrote it using CUDA and ceased sales of the FPGA boards as all that was required now was a decently recent graphics card (note, of course, that this is all academic as I don’t consider GPGPU programming to be using dedicated hardware either…).

Okay sorry for giving you a disservice by distrusting your knowledge. English is not my native language and I guessed that what I meant by dedicated hardware was explained in the follow up in post which talked about FPGAs. Which the commenter above you promptly understood and gave me an answer I was hoping for and not wasting my time discussing what is meant by dedicated hardware, and also not giving me a stupid condescending answer like 'does it have any economic sense?' If you read my comment in whole you would understand that I was not talking about developing microchips. Thank you for conversation.
« Last Edit: January 31, 2023, 03:20:46 pm by mislavcro »
Logged
Pages: 1 ... 11 12 [13] 14 15 16