59 réponses à ce sujet

[Failed.Bard]

FunkySwerve wrote...

Failed.Bard wrote...

  I was curious about this myself, so I set up a test for it in my little mod using OnCick on placeables to trigger the scripts.  133 placeables in the area, exactly 100 barrell placeables placed between script trigger placeable and the placeable it was looking for, to simulate a somewhat crowded are.
  I'm not sure my complete mod placeable count, likely 1500-2000 though, since it's 50 areas.

It's not just placeables, remember, but all objects. Places are typically the most numerous types, but there's still other heavy hitters, like items, and triggers, along with creatures, doors, waypoints, etc.

Funky

  I used a test area to do it in.  With GetObjectByTag, the Lexicon says it checks through in this order:

OBJECT_TYPE_STORE (128)
OBJECT_TYPE_PLACEABLE (64)
OBJECT_TYPE_WAYPOINT (32)
OBJECT_TYPE_AREA_OF_EFFECT (16) (spell effects, like web)
OBJECT_TYPE_DOOR (8)
OBJECT_TYPE_TRIGGER (4)
OBJECT_TYPE_ITEM (2)
OBJECT_TYPE_CREATURE (1)

 

  I'm assuming GetNearestObjectByTag checks the same.  In that particular area, it was just placeables out of those, and my dm avatar triggering the switch, so there wouldn't have been any signifigant additional overhead that GetNearestObjectByTag needed to check through.
 

[FunkySwerve]

Failed.Bard wrote...

  I used a test area to do it in.  With GetObjectByTag, the Lexicon says it checks through in this order:

OBJECT_TYPE_STORE (128)
OBJECT_TYPE_PLACEABLE (64)
OBJECT_TYPE_WAYPOINT (32)
OBJECT_TYPE_AREA_OF_EFFECT (16) (spell effects, like web)
OBJECT_TYPE_DOOR (8)
OBJECT_TYPE_TRIGGER (4)
OBJECT_TYPE_ITEM (2)
OBJECT_TYPE_CREATURE (1)

 

  I'm assuming GetNearestObjectByTag checks the same.  In that particular area, it was just placeables out of those, and my dm avatar triggering the switch, so there wouldn't have been any signifigant additional overhead that GetNearestObjectByTag needed to check through.
 

I was just pointing that out in case you'd misunderstood my focus on places in my earlier responses (the place count doc). If indeed GObT uses that ordering, that could well explain my experience - we have a fair amount of items in stores - enough that we had to put in separate shops for selling, to avoid massive lag spikes on close of the store. I may well wind up doing some profiling, if Mavrixio doesn't become a little more forthcoming with data.

Funky

[ffbj]

I remember this argument from the old boards, and as FS said theory and practice, well it was pretty much settled that gnobt was faster. But what I am wondering is, just using basic logic, would not the time be dependent on the location of the object? That is if you were standing right next to the object, assuming that it is checking from the focal point of the location where the function is called. Of course I guess what is being said is that is not how the function works. Also just pointing out the gnobt is very useful if you have multiples, more than one object with the same tag. Of course that is probably why they have the function in the first place.Finally, maybe something useful, if speed was the paramount criterion would not something like using the object type be even faster?  As in object type placeable, store, etc... since you would cut out the needless search for objects that were not of that type? In other words a further refining of the search.

Modifié par ffbj, 21 août 2011 - 07:54 .

[Mavrixio]

The test was done in an area with 70 objects, The module has about 14k objects in its tag list.

[FunkySwerve]

There were also a ton of posts on the old board about speed of variable reads with X variables on them (also a long-settled dispute). Unfortunately finding them with the boards down is very difficult, and I didn't find the 5000-mark one I mentioned, but I did find a number of others, including remarks by Primogenitor (who studied it extensively when writing the PRC CCC) on 03/21/06 00:21:

The number of locals on the object being one though you have to get into thousands to make a difference. In 99% of cases, this will be the fastest method of reading or writing data. If you do have thousands of locals, its simple enough to split them over several objects with a couple of hundred on each.

.

Of course, were someone to present that to me, I would probably dismiss it as anecdotal, if I didn't know Primo or his work on the Conversation Character Creator, so meh. He also was NOT comparing GetLocalObject to other object-getting methods, but to other data-storage/retrieval methods - something I did a lot of comparison and profiling on myself.

As to placement of objects, I'll probably check that in my runs, if I wind up doing them. I'm also curious to know, as was speculated about on the last page, whether or not all objects in the area are looked at by GNObT, before the nearest of a tag is identified - I suspect they are. That would mean the placement of the reference object for the GN wouldn't matter, only the object count in the area.

As far as object types and speed, we use a combination of GetWaypointByTag and GetNearest to find objects quickly - GWbT is quite fast, in our experience, so there is some merit to limiting by object type. I'm unaware of any hash-like optimization there, either, however, so I would tend to be wary of adding too many waypoints to your mod (but then, I'm sure we have thousands total in HG).

I haven't done much profiling in the last couple of years, and it IS kind of fun...

Funky

[FunkySwerve]

Mavrixio wrote...

The test was done in an area with 70 objects, The module has about 14k objects in its tag list.

Thanks. Could you post the full script you used, so I can create a close analogue for my runs? I understand the Timer functions are Win NWNX, but there's also the question of how you got the pc, etc etc - the more similarity, the better. I appreciate your patience - if you're right about this, it'll be very handy to know.

Since we're on the subject, the other main reason we stopped using GObT was nonunique tags, which created some curious bugs in the module we inherited. So long as you have a good naming convention pre-established, though, that shouldn't be a huge hurdle. There were also some idiotic uses of GObT to find the caller of the script (instead of simply using OBJECT_SELF), but that's neither here nor there.

Thanks,
Funky

[Mavrixio]

FunkySwerve wrote...

Mavrixio wrote...

The test was done in an area with 70 objects, The module has about 14k objects in its tag list.

Thanks. Could you post the full script you used, so I can create a close analogue for my runs? I understand the Timer functions are Win NWNX, but there's also the question of how you got the pc, etc etc - the more similarity, the better. I appreciate your patience - if you're right about this, it'll be very handy to know.

void TestLocalVars(int nCount)
{
object oTest = CreateObject(OBJECT_TYPE_WAYPOINT, "nw_waypoint001", GetStartingLocation());
int i;
for (i=0; i<nCount; i++) SetLocalObject(oTest, IntToString(i), oTest);
StartTimer();
for (i=0; i<10000; i++) GetLocalObject(oTest, "test");
SendMessageToPC(OBJECT_SELF, IntToString(nCount)+"vars: " + IntToString(EndTimer())+"ms");
DestroyObject(oTest);
}
void main()
{
object oPC = OBJECT_SELF;
//test of GetLocalObject
TestLocalVars(10);
TestLocalVars(20);
TestLocalVars(100);
TestLocalVars(200);
TestLocalVars(500);
TestLocalVars(1000);
TestLocalVars(2000);
//test of GetObjectByTag
StartTimer();
for (i=0; i<10000; i++) GetObjectByTag("theres no objects with this tag");
SendMessageToPC(oPC, "GetObjectByTag: " + IntToString(EndTimer())+"ms");
//test of GetNearestObjectByTag
StartTimer();
for (i=0; i<10000; i++) GetNearestObjectByTag("theres no objects with this tag");
SendMessageToPC(oPC, "GetNearestObjectByTag: " + IntToString(EndTimer())+"ms");
}

[ffbj]

So the tag is theres no object with this tag. So is that so it will just keep running until it has found/checked all the objects in the module, or the actual tag is such? Just wondering, since I'm not all the up on this sort of stuff.

[Mavrixio]

ffbj wrote...

So the tag is theres no object with this tag. So is that so it will just keep running until it has found/checked all the objects in the module, or the actual tag is such? Just wondering, since I'm not all the up on this sort of stuff.

It will do the longest search, but it wont compare it with all tags, since the tags are sorted, it will do a binary search which is very quick no matter the number of tags that theres in your module.

[ffbj]

I see, so you then compare the various methods since they are all doing the longest search, and arrive at the conclusion that those other two methods are slower, since they take longer to complete the longest search. I think. Thanks. I suppose that's a standard methodology for testing search algorithms, but since I don't know about such things, that's just a guess.

[Hardcore UFO]

Some of this is going over my head, but I'm glad I'm not the only one wondering about this.

[GhostOfGod]

So is unique tag and "GetObjectByTag" now the way to go? I've been doing the opposite this whole time since I was always told that GOBT was inefficient. Just let me know which way the crowd is going so I can join.

[FunkySwerve]

I wouldn't jump to that conclusion just yet. I'm going to do a series of tests to see if practice confirms theory.

Funky

[GhostOfGod]

FunkySwerve wrote...

I wouldn't jump to that conclusion just yet. I'm going to do a series of tests to see if practice confirms theory.

Funky

Awesome.

[FunkySwerve]

First test is complete. I may not have to do any others.

This used the bioware profiler - first time I've done profiling with it, rather than NWNX (also the first time since 1.69).

This was done on HG, with the normal placeable counts, etc, in an actual-practice situation. We retrieve an object to use as an effect creator for diseases that inflict vulnerability. Nowadays, we set effect ids using nwnx_structs, but we didn't convert everything to that. Anyway, here's the actual code in the module for it. As you can see, we use the waypoint/tag technique:

void DoDiseaseVuln (object oDiseased) {
    object oArea = GetArea(oDiseased);

    if (!GetIsObjectValid(oArea)) {
        DelayCommand(6.0, DoDiseaseVuln(oDiseased));
        return;
    }

    int nAmount = GetLocalInt(oDiseased, "DiseaseVuln");

    if (!nAmount)
        return;

    if (GetIsDead(oDiseased)) {
        DeleteLocalInt(oDiseased, "DiseaseVuln");
        return;
    }

    object oEffectWay = GetWaypointByTag("effectsareawaypo");
    object oDiseaseControl = GetNearestObjectByTag("disease_vuln", oEffectWay);
    effect eTest = GetFirstEffect(oDiseased);
    int nApplied = FALSE;

    while (GetIsEffectValid(eTest)) {
        if (GetEffectCreator(eTest) == oDiseaseControl)
            nApplied = TRUE;
        eTest = GetNextEffect(oDiseased);
    }


    if (!nApplied) {
        AssignCommand(oDiseaseControl, ApplyDiseaseVuln(oDiseased, nAmount));
    }

    DelayCommand(6.0, DoDiseaseVuln(oDiseased));
}

That waypoint, effectsareawaypo, is in a small, 4x4 area, with very few objects - just a waypoint and 7 places - it was designed specifically to keep GNObT streamlined.

I placed 3 objects in our test area in the mod, each with a different heartbeat script:

test_gnobt

void main()
{
    object oDiseaseControl;
    int nX;
    for (nX = 0; nX < 1000; nX++)
        oDiseaseControl = GetNearestObjectByTag("disease_vuln", GetWaypointByTag("effectsareawaypo"));
}

test_gobt

void main()
{
    object oDiseaseControl;
    int nX;
    for (nX = 0; nX < 1000; nX++)
        oDiseaseControl = GetObjectByTag("disease_vuln");
}

test_glo

void main()
{
    object oDiseaseControl;
    int nX;
    for (nX = 0; nX < 1000; nX++)
        oDiseaseControl = GetLocalObject(GetModule(),"disease_vuln");//set on modload
}

Here are the results of the profiling run:

test_gnobt     runs 348     total time 4900
test_gobt       runs 348     total time 685
test_glo         runs 348     total time 1395

So, according to this test, at least, GetObjectByTag outperforms even GetLocalObject, even on a huge mod like HG which probably has upwards of 70,000 objects in play (wild-ass guess based on 50k place count and 566 areas). We don't have a lot of vars on the mod, either - under 20, if I had to guess. Note that I used GetModule() each time, rather than assigning a var - again, because that's likely what you would be doing in practice, unless you happened to be working on a script where OBJECT_SELF was the mod.

I'm a little concerned at the number of runs - I think load may have played a role in the numbers, perhaps distorting them, since I let this run quite a while, and there should've been more runs. Still, the numbers speak for themselves. Looks like the common wisdom was wrong again - props to Mavrixio for pointing this out.

I'll probably do some additional runs this evening to see whether all objects in an area get checked by GNObT before it picks one, but that's sort of irrelevant, now. All you need is a good prefixing system to ensure unique tags - with that, GObT is definitely the way to go. I may also compre GObT to GetWaypointByTag, to see if GWbT has similar optimization.

Funky

Modifié par FunkySwerve, 22 août 2011 - 04:47 .

[Kato -]

Very interesting and surprising indeed, I'm making a good note of this...

[Hardcore UFO]

I started a revolution! I'm so proud... Now to take on society.

But seriously, thanks for taking the time to look into this. I know it wasn't just for my benefit but I'm sure it'll help a lot of scripters to know this.

[henesua]

+1 Very useful information.

[ffbj]

Wow that's quite a difference, like 9x faster to use gobt, props Mavrixio . Thanks FS for construction of the test, results and explanation. So the only real use for gnobt should only be non-unique tags, to differentiate between the same tag and get the nearest one. I suppose that indirectly also answers the question about proximity, which does'nt seems to matter.

Modifié par ffbj, 23 août 2011 - 12:45 .

[Failed.Bard]

  Actually, if you're just getting the absolute nearest object with that tag in the area, I wouldn't use the standard function either.
  I expect, based on the ability to find nNth nearest, that it has to specify quite a large number of floats and objects, then search every object in the mod, compare distances, find the nearest one, and then start over excluding the ones found already until they reach the number needed.

  I wrote this as a "true" GetNearestObjectByTag, and for finding the nearest in the same test I did the others in (500 loops of the function), it averaged 4.5ms compared to GNOBT's 24ms+ average.

I haven't tested it much yet, but I expect part of the difference in speed may be in the for loop itself, which when I switched all my scripts over when I switched to the better compiler seemed to run about 40% faster than while loops.

  Likely it could be optimized even further still, I wrote this pretty quickly yesterday just as a test.
 
// (8/21/2011) Failed Bard
// GNOBT replacer.
object FB_GetNearestObjectByTag (string sTag, object oSource = OBJECT_SELF)
{
 object oNearest, oTest, oArea;
 float  fNearest, fTest;
 int i;
 oArea = GetArea (oSource);
 fNearest = 1000.0;
 oTest = GetObjectByTag (sTag, i);
// the 500 here can be set higher if a module has a huge number of identically named tags. 
 for (i = 1; i < 500 && GetIsObjectValid (oTest); i ++)
    {
     if (GetArea (oTest) == oArea)
        {
         fTest = GetDistanceBetween (oTest, oSource);
         if (fTest < fNearest)
            {
             oNearest = oTest;
             fNearest = fTest;
            }
        }
     oTest = GetObjectByTag (sTag, i);
    }
 return oNearest;
}

Modifié par Failed.Bard, 23 août 2011 - 01:07 .

[OldTimeRadio]

Great work, everyone!  And hella useful stuff to know.  One error, which I am guilty of, is using Google (or the NWN Omnibus) to search the old BioWare forums for answers and then giving those answers a little too much weight- usually because it's a PITA to test (whatever).  This problem gets compounded when you think that the test results you might find are, say, from 2004 and on a much earlier build of NWN. 

Getting fresh tests like this against 1.69 is solid gold, IMO.

[Rolo Kipp]

<looking all around...>

How does GetFirstObjectInShape compare for finding near-by things? Is that looking through the whole list also?

Very interesting thread :-) I dig this stuff.

<...at the *Big* dogs>

[FunkySwerve]

I'll be running more tests. It seems likely that the second function call (GetModule()) is responsible for the doubled time of GLO vs GObT - function calls have non-negligible overhead. Might ask Skywing for an OBJECT_MODULE const as a result (GetModule() almost alawys returns object 0, according to acaos - the only case in which it doesn't is if you use StartNewModule()) . Will be caching the waypoint and module in vars in order to isolate function runtimes, and comparing GetWaypointByTag to GObT on waypoints to see a) whether GObT's optimization might actually make it better (unlikely), and whether I can stop worrying about our mod's waypoint count (likely, if GWbT has similar optimization to GObT's).

As for GetFirstObjectInShape, I can't imagine it'd be better than Nearest - if you needed to find the nearest - since you'd wind up measuring distance manually. Those you would just use as-needed. Bear in mind that this is all sort of wonky in terms of impact - using one of these functions versus another is unlikely to have a noticeable impact on your server. It's more of a fetish, really, though those of us who indulge it like to tell ourselves that our servers run marginally more smoothly as a result. You need huge numbers of repetitions in order to see significant runtimes on these methods. In the case of GObT, it's particularly noteworthy, because many of us were going to pains to avoid using it - it's both more convenient and more efficient than getting Nearest to a Waypoint.

Funky

Modifié par FunkySwerve, 23 août 2011 - 05:16 .

[Rolo Kipp]

<ears ring...>

I asked that because I ran across some default functions somewhere in the AI that was using GetFirst/NextObjectInShape... I'll try and remember where I saw it, but that seems a viable target for re-scripting - if it hasn't been already.

With the amount of background stuff I (eventually) want to have going, *every* bit helps. Or, um, lack of bit, I suppose... =)

<...he's listening so hard>

[FunkySwerve]

Ran some more tests. I modified the old scripts to cache the GetModule() and GetWaypointByTag() calls on variables, so that the functions were only called once, in an effort to pinpoint exact costs. Here are the scripts for this run:

test_gobt (unchanged)

void main()
{
    object oDiseaseControl;
    int nX;
    for (nX = 0; nX < 1000; nX++)
        oDiseaseControl = GetObjectByTag("disease_vuln");
}

test_gnobt

void main()
{
    object oDiseaseControl, oWay = GetWaypointByTag("effectsareawaypo");
    int nX;
    for (nX = 0; nX < 1000; nX++)
        oDiseaseControl = GetNearestObjectByTag("disease_vuln", oWay);
}

test_glo

void main()
{
    object oDiseaseControl, oMod = GetModule();
    int nX;
    for (nX = 0; nX < 1000; nX++)
        oDiseaseControl = GetLocalObject(oMod,"disease_vuln");//set on modload
}

Run results:

test_gnobt 314 runs 3333 total time
test_gobt 314 644
test_glo 314 1216

Clearly overhead from functions had little to do with it. GNObT is only about 5 times as slow, as opposed to 9, when you don't have to get the waypoint - not that such a situation comes up in practice. GLO is still about twice as slow, meaning that GetModule() is very fast, as expected. I didn't clock GWbT against GObT, but plan to.

Funky