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

[Ralph Versteegen]

On 10 June 2017 at 08:50, Ralph Versteegen <teeemcee at gmail.com> wrote:

> 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.
>

Err, it does still do statistical sampling of what the program is doing,
but it uses a high resolution interrupt instead of a SIGALARM signal
handler.


>
> 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-motherh
>>>>>> amster.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/8c315be5/attachment.htm>