[Ohrrpgce] SVN: james/8832 A* Pathfinding now caches NPC locations in an NPCCollisionCache object

[Ralph Versteegen]

I used pprof, part of gperftools, to generate that. I couldn't get it to
work on 32 bit builds, so had to run it on 64 bit ones.
Strangely, I also couldn't get gprof to work.
I've only just figured out how to get oprofile to reconstruct the
callgraph. It probably can construct similar graphs out of the box; it
includes a bunch of tools with heaps of options. It can even show you spent
on each line of the kernel source while your program was executing! And one
advantage it has is that its timing resolution is far far better than the
other profilers, because it times context switches and other events instead
of using a statistical sampler with a low 100Hz resolution. So it produces
detailed results in a second instead of needing to leave the program
running a while.

I might do a couple more things, but mostly I would say the optimisation is
done.

On 10 June 2017 at 08:20, James Paige <Bob at hamsterrepublic.com> wrote:

> That chart is cool! Did oprofile generate that?
>
> I am really happy about how the A* performance is going right now. Thank
> you for all the optimizations :)
>
> On Fri, Jun 9, 2017 at 1:00 PM, Ralph Versteegen <teeemcee at gmail.com>
> wrote:
>
>> At this point, I'm having trouble speeding up pathfinding any further.
>> The main obvious remaining step I see is to split up AStarNode into two
>> UDTs.
>> Profiling (see attachment) shows time is spent fairly evenly all over the
>> place, largely in functions where it's hard to see any alternative way to
>> write the function.
>>
>> As for differences between different builds, here's a benchmark: I
>> commented out "npcmove_walk_ahead(npci)" in npcmove_pathfinding_chase after
>> calculating the path so the npcs never move, run with --runfast -z 1, and
>> then go to the 100 npc map and don't move. (Note that this means the NPCs
>> attempt to repath every tick, except those in the interior, which is most
>> of them.)
>>
>> debug=2 gengcc=0: 34fps
>> debug=0 gengcc=0: 122fps
>> debug=0 gengcc=1: 195fps
>> debug=0 gengcc=1 arch=64: 245fps
>> (If I don't comment out that line, and instead run around with F11
>> enabled, I get ~500fps)
>>
>> On 9 June 2017 at 18:02, Ralph Versteegen <teeemcee at gmail.com> wrote:
>>
>>> This makes a big difference!
>>> Amazingly pathfinding seems to be almost 10x faster if you compile with
>>> debug=0; the 100 NPC map only takes about 20% CPU time for me in that case,
>>> even without gengcc. I'm rather shocked that the difference is that much,
>>> since gengcc only adds overhead on each function call and pointer access,
>>> but there aren't that many of those.
>>>
>>> I found another profiling tool I'd installed on my system, oprofile.
>>> This one is very fancy indeed, it can simultaneously profile the whole
>>> system. Anyway, it shows that all the runtime is inside fb_TlsGetCtx and
>>> libpthread. I didn't realise that the -exx overhead when you call a
>>> function (calls to fb_ErrorSetFuncName and fb_ErrorSetFuncName) store the
>>> current function name in thread local storage.
>>>
>>> On 9 June 2017 at 07:34, James Paige <Bob at hamsterrepublic.com> wrote:
>>>
>>>> Now the 100 npc map runs *almost* completely smoothly on my computer.
>>>>
>>>> On Thu, Jun 8, 2017 at 12:33 PM, <subversion at hamsterrepublic.com>
>>>> wrote:
>>>>
>>>>> james
>>>>> 2017-06-08 12:33:51 -0700 (Thu, 08 Jun 2017)
>>>>> 195
>>>>> A* Pathfinding now caches NPC locations in an NPCCollisionCache object
>>>>> which is used for the whole pathfinding operation, rather that looping
>>>>> over every npc on every pathfinding collision check.
>>>>> ---
>>>>> U   wip/game.bas
>>>>> U   wip/game.bi
>>>>> U   wip/game_udts.bi
>>>>> U   wip/pathfinding.bas
>>>>> U   wip/pathfinding.bi
>>>>> U   wip/testgame/a-star.hss
>>>>> U   wip/testgame/a-star.rpg
>>>>> _______________________________________________
>>>>> Ohrrpgce mailing list
>>>>> ohrrpgce at lists.motherhamster.org
>>>>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Ohrrpgce mailing list
>>>> ohrrpgce at lists.motherhamster.org
>>>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>>>>
>>>>
>>>
>>
>> _______________________________________________
>> Ohrrpgce mailing list
>> ohrrpgce at lists.motherhamster.org
>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>>
>>
>
> _______________________________________________
> Ohrrpgce mailing list
> ohrrpgce at lists.motherhamster.org
> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170610/2dede535/attachment-0001.htm>