[Timiditas]

Is this what you call "expensive", if called everytime a bullet is fired ingame... ?

PHP Code:


#pragma semicolon 1

#include <sourcemod>
#include <sdktools>
#include <profiler>

#define PLUGIN_VERSION "1.1c"
new String: weaponlist[][] = { "ak47", "m4a1", "awp", "deagle", "mp5navy", "aug",
                                                                "p90", "famas", "galil", "scout", "g3sg1", "hegrenade",
                                                                "usp", "glock", "m249", "m3", "elite", "fiveseven",
                                                                "mac10", "p228", "sg550", "sg552", "tmp", "ump45",
                                                                "xm1014", "knife" };
new hashlist[] = { 322, 312, 328, 610, 725, 317, 226, 520, 521, 558, 425, 931, 344,
                                        528, 283, 163, 531, 971, 403, 280, 382, 386, 337, 452, 433, 525 };
//hashlist is generated by adding up all ascii chars PLUS the numeric value of each char if they are numeric
//e.g. m3 = 109+51+3
//this will certainly not work on much strings, but does not generate any collisions on this short weapon list

get_weapon_hash(const String: weapon_name[])
{
    new hash, WPlen = strlen(weapon_name);
    for(new I = 0;I < WPlen;I++)
    {
        decl String:inmid[2];
        strcopy(inmid,2,weapon_name[i]);
        //new char:inmid = weapon_name[i];
        hash += inmid[0];
        if(IsCharNumeric(inmid[0]))
            hash += StringToInt(inmid);
    }
    
    new loop_break = 0, index = 0, hWPsize = sizeof(hashlist);
    
    while ((loop_break == 0) && (index < hWPsize))
    {
        if (hash == hashlist[index])
            loop_break++;
        index++;
    }

    if (loop_break == 0)
        return -1;
    else
        return index - 1;
}

get_weapon_index(const String: weapon_name[])
{
    new loop_break = 0, index = 0, sWPsize = sizeof(weaponlist);
    
    while ((loop_break == 0) && (index < sWPsize))
    {
        if (strcmp(weapon_name, weaponlist[index], true) == 0)
            loop_break++;
        index++;
    }

    if (loop_break == 0)
        return -1;
    else
        return index - 1;
}








public Plugin:myinfo = {
    name = "stringtest",
    author = "Timiditas",
    description = "string hashing",
    version = PLUGIN_VERSION,
    url = "nowhere to run"
};

public OnPluginStart() {
    RegConsoleCmd("hash", fhash);
    RegConsoleCmd("find", find);
}

public Action:fhash(client, args)
{
    if (args != 1)
    {
        ReplyToCommand(client, "usage: hash <anystring>");
        return Plugin_Handled;
    }
    decl String:argument[255];
    GetCmdArg(1, argument, 255);
    new Handle:myProf = CreateProfiler();
    decl IDX;
    StartProfiling(myProf);
    IDX = get_weapon_hash(argument);
    StopProfiling(myProf);
    new Float:TheTime = GetProfilerTime(myProf);
    CloseHandle(myProf);
    ReplyToCommand(client, "Returned index: %i, HPT needed in seconds: %f",IDX,TheTime);
    return Plugin_Handled;
}

public Action:find(client, args)
{
    if (args != 1)
    {
        ReplyToCommand(client, "usage: find <anystring>");
        return Plugin_Handled;
    }
    decl String:argument[255];
    GetCmdArg(1, argument, 255);
    new Handle:myProf = CreateProfiler();
    decl IDX;
    StartProfiling(myProf);
    IDX = get_weapon_index(argument);
    StopProfiling(myProf);
    new Float:TheTime = GetProfilerTime(myProf);
    CloseHandle(myProf);
    ReplyToCommand(client, "Returned index: %i, HPT needed in seconds: %f",IDX,TheTime);
    return Plugin_Handled;
} 


Performance results below:

] find ak47
Returned index: 0, HPT needed in seconds: 0.000001
] hash ak47
Returned index: 0, HPT needed in seconds: 0.000003
] find knife
Returned index: 25, HPT needed in seconds: 0.000002
] hash knife
Returned index: 25, HPT needed in seconds: 0.000003
] find m3
Returned index: 15, HPT needed in seconds: 0.000002
] hash m3
Returned index: 15, HPT needed in seconds: 0.000003
] find fiveseven
Returned index: 17, HPT needed in seconds: 0.000002
] hash fiveseven
Returned index: 17, HPT needed in seconds: 0.000003
] find UNKNOWNSTRING
Returned index: -1, HPT needed in seconds: 0.000002
] hash UNKNOWNSTRING
Returned index: -1, HPT needed in seconds: 0.000004

So simply comparing the INTs is faster of course, but the required hashing at the beginning of get_weapon_hash() makes it slower.


~~edit

Actually, if you pack it into two loops, the results differ significantly.

PHP Code:

public Action:fhash(client, args)
{
    if (args != 1)
    {
        ReplyToCommand(client, "usage: hash <anystring>");
        return Plugin_Handled;
    }
    decl String:argument[255];
    GetCmdArg(1, argument, 255);
    new Handle:myProf = CreateProfiler();
    decl IDX, Float:Times;
    for(new j = 1;j<1001;j++)
    {
        StartProfiling(myProf);
        for(new i = 1;i<1001;i++)
        {
            IDX = get_weapon_hash(argument);
        }
        StopProfiling(myProf);
        Times += GetProfilerTime(myProf);
    }
    Times /= 1000.0;
    CloseHandle(myProf);
    ReplyToCommand(client, "Returned index: %i, HPT needed in seconds: %f",IDX,Times);
    return Plugin_Handled;
}

public Action:find(client, args)
{
    if (args != 1)
    {
        ReplyToCommand(client, "usage: find <anystring>");
        return Plugin_Handled;
    }
    decl String:argument[255];
    GetCmdArg(1, argument, 255);
    new Handle:myProf = CreateProfiler();
    decl IDX, Float:Times;
    for(new j = 1;j<1001;j++)
    {
        StartProfiling(myProf);
        for(new i = 1;i<1001;i++)
        {
            IDX = get_weapon_index(argument);
        }
        StopProfiling(myProf);
        Times += GetProfilerTime(myProf);
    }
    Times /= 1000.0;
    CloseHandle(myProf);
    ReplyToCommand(client, "Returned index: %i, HPT needed in seconds: %f",IDX,Times);
    return Plugin_Handled;
} 


Results:

] find no
Returned index: -1, HPT needed in seconds: 0.001577
] hash no
Returned index: -1, HPT needed in seconds: 0.000444
] find no
Returned index: -1, HPT needed in seconds: 0.001581
] hash no
Returned index: -1, HPT needed in seconds: 0.000444
] find ak47
Returned index: 0, HPT needed in seconds: 0.000078
] hash ak47
Returned index: 0, HPT needed in seconds: 0.000750
] find knife
Returned index: 25, HPT needed in seconds: 0.001606
] hash knife
Returned index: 25, HPT needed in seconds: 0.000791
] find UNKNOWNSTRING
Returned index: -1, HPT needed in seconds: 0.001584
] hash UNKNOWNSTRING
Returned index: -1, HPT needed in seconds: 0.001692
] find m3
Returned index: 15, HPT needed in seconds: 0.001077
] hash m3
Returned index: 15, HPT needed in seconds: 0.000498
] find glock
Returned index: 13, HPT needed in seconds: 0.000948
] hash glock
Returned index: 13, HPT needed in seconds: 0.000729
] find hegrenade
Returned index: 11, HPT needed in seconds: 0.000764
] hash hegrenade
Returned index: 11, HPT needed in seconds: 0.001162
] find g3sg1
Returned index: 10, HPT needed in seconds: 0.000728
] hash g3sg1
Returned index: 10, HPT needed in seconds: 0.000960

The wiki says:

The compiler, in fact, is very poor at optimizing

I wonder how much of the 'poor' optimizations kick in in the above loops.

[p3tsin]

I used my own benchmark function below to run 200000 cycles (had to increase the heap size in my test plugin). I also optimized both of your lookup functions... get_weapon_hash was using way much more native function calls than it really needed to (function calls are "slow"). Anywho, here are the results:

[Benchmark] 200000 cycles of get_weapon_hash took 0.033935 seconds
[Benchmark] 200000 cycles of get_weapon_index took 0.158752 seconds

PHP Code:

benchmark(repeats) {
    static const String:list[][] = {
        "ak47", "m4a1", "awp", "deagle", "mp5navy", "aug",
        "p90", "famas", "galil", "scout", "g3sg1", "hegrenade",
        "usp", "glock", "m249", "m3", "elite", "fiveseven",
        "mac10", "p228", "sg550", "sg552", "tmp", "ump45",
        "xm1014", "knife", "UNKNOWNSTRING"
    };

    decl cycles[repeats], i;

    for(i = 0; i < repeats; i++) {
        cycles[i] = GetURandomInt() % sizeof(list);
    }

    new Float:start = GetEngineTime();

    for(i = 0; i < repeats; i++) {
        get_weapon_hash(list[cycles[i]]);
    }

    PrintToServer("[Benchmark] %d cycles of get_weapon_hash took %f seconds",repeats,GetEngineTime() - start);

    start = GetEngineTime();

    for(i = 0; i < repeats; i++) {
        get_weapon_index(list[cycles[i]]);
    }

    PrintToServer("[Benchmark] %d cycles of get_weapon_index took %f seconds",repeats,GetEngineTime() - start);
}

get_weapon_hash(const String:weapon_name[])
{
    decl String:inmid;
    new hash, WPlen = strlen(weapon_name);

    //for(new i = 0; (inmid = weapon_name[i]) != 0; i++)
    //the above would even get rid of the strlen call, but it looks a bit ugly :#
 
    for(new i = 0; i < WPlen; i++)
    {
        inmid = weapon_name[i];
        hash += inmid;

        if('0' <= inmid <= '9')    //IsCharNumeric without a function call
        {
            hash += inmid - '0';    //"CharToInt"
        }
    }

    new index = 0, hWPsize = sizeof(hashlist);

    while(index < hWPsize)
    {
        if(hash == hashlist[index])
        {
            return index;
        }

        index++;
    }

    return -1;
}

get_weapon_index(const String:weapon_name[])
{
    new index = 0, sWPsize = sizeof(weaponlist);
    
    while(index < sWPsize)
    {
        if(strcmp(weapon_name, weaponlist[index], true) == 0)
        {
            return index;
        }

        index++;
    }

    return -1;
} 


EDIT: oh, and I noticed you're not initializing Float:Times in your benchmark function

[Timiditas]

Originally Posted by p3tsin oh, and I noticed you're not initializing Float:Times in your benchmark function

oops yea corrected that. while you were posting I made another test with my version but a new hash method. turns out its slower on the ak47 but way faster on the knife.

PHP Code:

#pragma semicolon 1

#include <sourcemod>
#include <sdktools>
#include <profiler>

#define PLUGIN_VERSION "1.1c"
new String: weaponlist[][] = { "ak47", "m4a1", "awp", "deagle", "mp5navy", "aug",
                                                                "p90", "famas", "galil", "scout", "g3sg1", "hegrenade",
                                                                "usp", "glock", "m249", "m3", "elite", "fiveseven",
                                                                "mac10", "p228", "sg550", "sg552", "tmp", "ump45",
                                                                "xm1014", "knife" };

new hashlist[] = { 515, 468, 544, 811, 941, 531, 386, 719, 721, 772, 575, 1136, 576, 739, 427, 320, 740, 1178, 608, 430, 590, 592, 562, 669, 656, 742 };
//hashlist is generated by adding up all ascii chars, while the first and second chars are added twice
//e.g. m3 = 109+109+51+51, awp = 97+97+119+119+112
//this will certainly not work on much strings, but does not generate any collisions on this short weapon list

get_weapon_hash(const String: weapon_name[])
{
    new hash, WPlen = strlen(weapon_name);
    for(new I = 0;I < WPlen;I++)
    {
        hash += weapon_name[I];
        if(I==0 || I==1)
            hash += weapon_name[I];
    }
    
    new loop_break = 0, index = 0, hWPsize = sizeof(hashlist);
    
    while ((loop_break == 0) && (index < hWPsize))
    {
        if (hash == hashlist[index])
            loop_break++;
        index++;
    }
    
    if (loop_break == 0)
        return -1;
    else
        return index - 1;
}

get_weapon_index(const String: weapon_name[])
{
    new loop_break = 0, index = 0, sWPsize = sizeof(weaponlist);
    
    while ((loop_break == 0) && (index < sWPsize))
    {
        if (strcmp(weapon_name, weaponlist[index], true) == 0)
            loop_break++;
        index++;
    }

    if (loop_break == 0)
        return -1;
    else
        return index - 1;
}








public Plugin:myinfo = {
    name = "stringtest",
    author = "Timiditas",
    description = "string hashing",
    version = PLUGIN_VERSION,
    url = "nowhere to run"
};

public OnPluginStart() {
    RegConsoleCmd("hash", fhash);
    RegConsoleCmd("find", find);
}

public Action:fhash(client, args)
{
    if (args != 1)
    {
        ReplyToCommand(client, "usage: hash <anystring>");
        return Plugin_Handled;
    }
    decl String:argument[255];
    GetCmdArg(1, argument, 255);
    new Handle:myProf = CreateProfiler();
    new IDX, Float:Times;
    for(new j = 1;j<1001;j++)
    {
        StartProfiling(myProf);
        for(new i = 1;i<1001;i++)
        {
            IDX = get_weapon_hash(argument);
        }
        StopProfiling(myProf);
        Times += GetProfilerTime(myProf);
    }
    Times /= 1000.0;
    CloseHandle(myProf);
    ReplyToCommand(client, "Returned index: %i, HPT needed in seconds: %f",IDX,Times);
    return Plugin_Handled;
}
public Action:find(client, args)
{
    if (args != 1)
    {
        ReplyToCommand(client, "usage: find <anystring>");
        return Plugin_Handled;
    }
    decl String:argument[255];
    GetCmdArg(1, argument, 255);
    new Handle:myProf = CreateProfiler();
    new IDX, Float:Times;
    for(new j = 1;j<1001;j++)
    {
        StartProfiling(myProf);
        for(new i = 1;i<1001;i++)
        {
            IDX = get_weapon_index(argument);
        }
        StopProfiling(myProf);
        Times += GetProfilerTime(myProf);
    }
    Times /= 1000.0;
    CloseHandle(myProf);
    ReplyToCommand(client, "Returned index: %i, HPT needed in seconds: %f",IDX,Times);
    return Plugin_Handled;
} 


results:

] find ak47
Returned index: 0, HPT needed in seconds: 0.000074
] hash ak47
Returned index: 0, HPT needed in seconds: 0.000111
] find knife
Returned index: 25, HPT needed in seconds: 0.001484
] hash knife
Returned index: 25, HPT needed in seconds: 0.000247
] find hegrenade
Returned index: 11, HPT needed in seconds: 0.000700
] hash hegrenade
Returned index: 11, HPT needed in seconds: 0.000203

While ak47 and m4a1 are propably the most used weapons in the game, this would surely prove counterproductive.
Looking at how fast the original lookup by string compare is executed, I think this function is not worth optimizing.
Unless you or somebody else knows a faster way to produce string hashes/checksums.

[p3tsin]

Originally Posted by Timiditas While ak47 and m4a1 are propably the most used weapons in the game, this would surely prove counterproductive.

Both methods are totally fine, as long as you're not calling the function tens of thousands of times per second. A delay of 0.000002 seconds isn't really that noticeable

Originally Posted by Timiditas Looking at how fast the original lookup by string compare is executed, I think this function is not worth optimizing.

I just remembered tries, they suit your case perfectly. Probably a lot faster than any self written function too. Link to API page.

[Timiditas]

Interesting results

findtrie        ak47                0.000160
find            ak47                0.000074
hash            ak47                0.000109

findtrie        knife            0.000148
find            knife            0.001566
hash            knife            0.000246

findtrie        hegrenade        0.000151
find            hegrenade        0.000730
hash            hegrenade        0.000196

findtrie        NOTINARRAY    0.000131
find            NOTINARRAY    0.001527
hash            NOTINARRAY    0.000283

[psychonic]

I do similar to what you're doing in my SuperLogs plugins (probably for similar reason).
I semi-recently switched from custom hashing to using tries. I didn't do as extensive benchmarking as you, but a couple small tests did show some improvement in speed and using them also inherently cleaned up some of the code. I would recommend them if you're not already convinced by your benchmarks.

[Timiditas]

Yes, propably. I have to allocate the weapons to integers to calculate points as well as adress client arrays (accuracy stats for each weapon). A lookup is done each clients death, each time a bullet is fired and each time a bullet hits a player.
Sure, this isn't quite your average OnGameFrame-clog, but meh...

I need it for n1g-css-stats/Dignatio. That plugin needs a clean sweep badly.

I was not just convinced of the tries, so I ran a final test, considering all 26 weapon strings.
This is the result of the 26 weapons, averaged:
Find: 0,000834769
Trie: 0,000167346
Hash: 0,000164885

The older string compare is totally out of the game. My hash/checksum whatever you want to call it is faster than the tries on the first half, but slower on the second half, while the tries seem to stay at the same speed over the whole weaponlist.

It propably won't make any difference wether to choose tries or hashing, speedwise; at least in this special case because its all limited to 26 slots at any time.
So I've chosen to use the hash function and move the most common weapons to the first half of the array.
As well because I can work with the *return* of get_weapon_hash directly, compared to GetTrieValue.

More detailed results and the used code to benchmark is in attachment.
The zip has the results as XLS, saved with Excel 2002/Office XP.
Now go and blame me for not using Open Office.