The fastest string Contains/IndexOf (very very fast)

Discussion in 'Scripting' started by n0mad, Mar 6, 2012.

  1. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    UPDATE : the cake is a lie !
    see this post, thanks to the below discussion, this method is faster in a very particular case (and as a matter of fact I was always falling into that case), which itself can be treated as fast with an alternate better fitting solution (see NPFS3000 post).
    So this thread still have the fastest solution, but it's not in this OP ^^

    _______________________________

    Hello,

    Vet coders will undoubtedly know this, but this is something I found a while ago after trying to milk the fastest possible string Contains. So it might help some people who didn't come to be aware of that.
    In Unity, String comparisons and operations are much needed for animationClip-heavy games, or even just for complicated state machines. Actually, the default string.Contains() or IndexOf() are horribly slow.

    But it comes to a simple option to make it far much faster. Just ignoring culture and casing by turning it to an IndexOf test, while putting "System.StringComparison.OrdinalIgnoreCase" in the function (as Contains() doesn't have this option afaik). Unless you have tons of different state names / animationClips, you don't need to separate them by case. So here we go.


    Test 1 (native Contains method) :

    Code (csharp):
    1. for (int i = 0; i < 100000; i++)
    2. return _clipName.Contains("VeryLongName");
    Test 2 (Contains OrdinalIgnoreCase method) :

    Code (csharp):
    1. for (int i = 0; i < 100000; i++)
    2. return _clipName.IndexOf("VeryLongName", System.StringComparison.OrdinalIgnoreCase) != -1;

    Test 1 : 16 ms.
    Test 2 : 4 ms.

    So "emulating" a Contains() by using an IndexOf with OrdinalIgnoreCase is 400% faster than the builtin Contains().

    Remember it's tested on a PC (Intel i7 920), so you can expect 10 to 30 times longer durations on mobile.
    Last edited: Mar 7, 2012
  2. Cbp

    Cbp

    New Member

    Joined:
    Jul 8, 2011
    Messages:
    4
  3. justinlloyd

    justinlloyd

    Member

    Joined:
    Aug 5, 2010
    Messages:
    1,657

    Not enough to be significant and if that is the code he used to test, then it is wrong.
  4. justinlloyd

    justinlloyd

    Member

    Joined:
    Aug 5, 2010
    Messages:
    1,657
    I am sure there is a mistake in here, but this is my code and my results:
    Code (csharp):
    1.  
    2. using System;
    3. using System.Collections.Generic;
    4. using System.Linq;
    5. using System.Text;
    6. using System.Diagnostics;
    7.  
    8. namespace ConsoleApplication1
    9. {
    10.     class Program
    11.     {
    12.         static string _clipNameShort = "VeryShortName";
    13.         static string _clipNameLong = "VeryLongName";
    14.         static bool _resultBool;
    15.         static int _resultIndex;
    16.  
    17.         static void Main(string[] args)
    18.         {
    19.             const int PermittedRuns = 10000000;
    20.             Stopwatch sw;
    21.  
    22.             sw = Stopwatch.StartNew();
    23.             for (int i = 0; i < PermittedRuns; i++)
    24.             {
    25.                 _resultBool = _clipNameShort.Contains("VeryLongName");
    26.             }
    27.  
    28.             sw.Stop();
    29.             Console.WriteLine(String.Format("Short Time Contains Not Found= {0:N0}", sw.ElapsedMilliseconds));
    30.  
    31.  
    32.             sw = Stopwatch.StartNew();
    33.             for (int i = 0; i < PermittedRuns; i++)
    34.             {
    35.                 _resultBool = _clipNameLong.Contains("VeryLongName");
    36.             }
    37.  
    38.             sw.Stop();
    39.             Console.WriteLine(String.Format("Long Time Contains Found = {0:N0}", sw.ElapsedMilliseconds));
    40.  
    41.  
    42.             sw = Stopwatch.StartNew();
    43.             for (int i = 0; i < PermittedRuns; i++)
    44.             {
    45.                 _resultIndex = _clipNameShort.IndexOf("VeryLongName");
    46.             }
    47.  
    48.             sw.Stop();
    49.             Console.WriteLine(String.Format("Short Time IndexOf Not Found = {0:N0}", sw.ElapsedMilliseconds));
    50.  
    51.  
    52.             sw = Stopwatch.StartNew();
    53.             for (int i = 0; i < PermittedRuns; i++)
    54.             {
    55.                 _resultIndex = _clipNameLong.IndexOf("VeryLongName");
    56.             }
    57.  
    58.             sw.Stop();
    59.             Console.WriteLine(String.Format("Long Time IndexOf Found = {0:N0}", sw.ElapsedMilliseconds));
    60.  
    61.             sw = Stopwatch.StartNew();
    62.             for (int i = 0; i < PermittedRuns; i++)
    63.             {
    64.                 _resultBool = _clipNameShort.IndexOf("VeryLongName", System.StringComparison.OrdinalIgnoreCase) != -1;
    65.             }
    66.  
    67.             sw.Stop();
    68.             Console.WriteLine(String.Format("Short Time IndexOf Ignore Case Not Found = {0:N0}", sw.ElapsedMilliseconds));
    69.  
    70.             sw = Stopwatch.StartNew();
    71.             for (int i = 0; i < PermittedRuns; i++)
    72.             {
    73.                 _resultBool = _clipNameLong.IndexOf("VeryLongName", System.StringComparison.OrdinalIgnoreCase) != -1;
    74.             }
    75.  
    76.             sw.Stop();
    77.             Console.WriteLine(String.Format("Long Time IndexOf Ignore Case Found = {0:N0}", sw.ElapsedMilliseconds));
    78.  
    79.         }
    80.     }
    81. }
    82.  
    And the results:
    Code (csharp):
    1.  
    2. Short Time Contains Not Found= 573
    3. Long Time Contains Found = 611
    4. Short Time IndexOf Not Found = 975
    5. Long Time IndexOf Found = 1,041
    6. Short Time IndexOf Ignore Case Not Found = 1,461
    7. Long Time IndexOf Ignore Case Found = 819
    8.  
    The results are interesting, and in complete conflict with the OP, so I am curious to know what the OP is seeing and what deviation from expected results of the 400% speedup I am getting. :)

    @n0mad: Can you post the full block of code you used to test the speed?
    Last edited: Mar 6, 2012
  5. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    Hello and thanks for your interest :)
    The full block are just in the OP, I intended to strip it from any "noise" by only limiting it to function, not attribution.

    I put a System.Diagnostics.Stopwatch before the test, and read the result after the loop.

    Full code would be :
    Test 1 :
    Code (csharp):
    1.  
    2. string _clipName = "s_LP";
    3. sw = new Stopwatch();
    4. sw.Start();
    5. for (int i = 0; i < 100000; i++)
    6.   _clipName.Contains("VeryLongName");
    7. sw.Stop();
    8. Debug.Log(sw.ElapsedMilliseconds);
    Test 2 :
    Code (csharp):
    1.  
    2. string _clipName = "s_LP";
    3. sw = new Stopwatch();
    4. sw.Start();
    5. for (int i = 0; i < 100000; i++)
    6.   _clipName.IndexOf("VeryLongName", System.StringComparison.OrdinalIgnoreCase) != -1;
    7. sw.Stop();
    8. Debug.Log(sw.ElapsedMilliseconds);

    I ran the tests several times, and results are always the same. It's interesting to see that you have different results though ?
    Also, @Cbp, I insist on using OrdinalIgnoreCase, if it's not specified, speed is the same for IndexOf and Contains.

    edit : what's more intriguing about your results Justin is that ignoring case should always be faster, in theory ?

    p.s : _clipName in my tests would be any incoming clip, and never contained "VeryLongName" in any case. I didn't think it would have its importance, but it seems it has after your results.
    Last edited: Mar 6, 2012
  6. Cbp

    Cbp

    New Member

    Joined:
    Jul 8, 2011
    Messages:
    4
    ignoring case Will always be slower, since it has to make both strings to uppercase and then compare them, each char is compared with it's byte value, and therefore the comparison will be the same speed as case sensitive matching.

    the indexOf only return the first match and should return as soon as this happens, so it does not need to compare the rest of the string, and will be faster, im not total sure it does this tho.
  7. npsf3000

    npsf3000

    Member

    Joined:
    Sep 19, 2010
    Messages:
    3,747
    Code (csharp):
    1.  
    2.         static void Main(string[] args)
    3.         {
    4.             bool result;
    5.             string _clipName = "NeryLongNamee";  //vary the length of this
    6.  
    7.             int iterations = 1000000;
    8.  
    9.             var sw = new Stopwatch();
    10.  
    11.             sw.Start();
    12.             for (int i = 0; i < iterations; i++)
    13.                 result = _clipName.Contains("VeryLongName");
    14.             sw.Stop();
    15.  
    16.             Console.WriteLine(sw.ElapsedMilliseconds);
    17.  
    18.             sw = new Stopwatch();
    19.  
    20.             sw.Start();
    21.             for (int i = 0; i < iterations; i++)
    22.                 result = _clipName.IndexOf("VeryLongName", System.StringComparison.OrdinalIgnoreCase) != -1;
    23.             sw.Stop();
    24.  
    25.             Console.WriteLine(sw.ElapsedMilliseconds);
    26.  
    27.             Console.ReadLine();
    28.         }
    29.  
    After 30s of experimentation I deduced the following:

    If the string we are searching is longer than the string we are looking for, IndexOf is much faster. If it is the same it's a bit slower. If it's shorter than it's much slower.

    For example searching the string "NeryLongNamwe" 1Mn times Contains takes 60ms while indexof takes 160!


    Want the best performance? Add in a short circuit:

    Code (csharp):
    1. result = _clipName.Length < "VeryLongName".Length ? false : _clipName.Contains("VeryLongName");
    Fastest in all tests.
  8. justinlloyd

    justinlloyd

    Member

    Joined:
    Aug 5, 2010
    Messages:
    1,657
    Well their string search code uses those there fancy algorithms. The more variation of letters being searched, the faster. The longer the string being searched for, the faster. The longer the string being searched through, the faster (in terms of relative comparison.) IIRC .NET uses something like KMP or Boyer-Moore -- too lazy to look it up at this time. KMP is an algorithm that almost all programmers eventually discover independently and still one of the fastest general purpose string search algorithms.
  9. angrypenguin

    angrypenguin

    Member

    Joined:
    Dec 29, 2011
    Messages:
    5,193
    I know that you need to use strings for animationClips and so on, but I still don't see this having a huge impact. The string based stuff doesn't have to happen every frame, does it? The only reliance on strings is when you need to change the state of animation(s) on an object, right?
  10. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    @NPSF3000 : thanks for the tip ! That's a very good idea :)

    @Cbp : I tested the stuff and yes, ignoring case is effectively a bit slower .... I was misguided by some other dev blogs who ran some similar tests than the one I posted in the OP :/

    @angrypenguin : string searching can be very intensive for complex state machines and AIs. For example, in my fight AI, some behaviors cannot be calculated without scanning opponent's potential actions, all depending on a lot of potential parameters. I already organized them with enums, but there are tons of different action names, so besides the basic "action family" sorting, I still have to make the AI analyze action names if I want it to be accurate enough for a hardcore audience.
    This routine is run every 1 to 2 seconds for performance optim, but ideally I'd like it to run every 100 ms (which is the average hardcore fighting gamer reaction time). In the end, this can lead into some serious string work, so milking for the best optimization possible is necessary, to avoid interference with all the already CPU consuming tasks (like drawcall, engine, player input responsivity).

    ______________________

    Ok I ran some deeper tests too, and it seems that NPSF3000 conclusion is the right one, but OrdinalIgnoreCase does have some faster cases :

    Not found, short pattern (< 10 chars) :
    - short pattern searched in long string; pattern not found : IndexOf slightly faster than Contains
    - short pattern searched in short string; pattern not found : IndexOf equal to Contains, IndexOf OrdinalIgnoreCase faster than both

    Found, short pattern (< 10 chars) :
    - short pattern searched in long string; pattern found : IndexOf equal to Contains
    - short pattern searched in short string; pattern found : IndexOf slightly faster than Contains

    Not found, long pattern (> 20 chars) :
    - long pattern searched in long string; pattern not found : IndexOf slightly faster than Contains, IndexOf OrdinalIgnoreCase faster than both
    - long pattern searched in short string; pattern not found : IndexOf equal to Contains, IndexOf OrdinalIgnoreCase much faster than both (the 400% case, but well searching a long pattern in a short string is automatically false by definition)

    Found, long pattern (> 20 chars) :
    - long pattern searched in long string; pattern found : IndexOf slightly faster than Contains.

    In all the cases where OrdinalIgnoreCase wasn't specified, it was twice slower than IndexOf/Contains default methods.
    Where OrdinalIgnoreCase is faster, it's only 20% faster.

    Conclusion : I should delete the OP asap :p IndexOf and Contains are generally prefered to OrdinalIgnoreCase.
    Initially my tests were run on any incoming animation name, and it was always returning the 400% faster result. This can be explained by the fact that all my anim names are using short names, except some special ones, which are the ones containing the patterns I search.
    So my case was very, very specific, and lead to think that OrdinalIgnoreCase would be more performant as I would always fall in the case "long pattern in short string", but NPSF3000 got a far better solution posted above.

    My apologies for the misguiding results in the OP ! And thank you all for having taken the time to try it yourself and correct me ;-) Now I should spread the info into all those blogs I saw a while ago having the same results as in the OP ...
    Last edited: Mar 7, 2012
  11. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    Additionally, while we're at string operations optimization, I also found a script on Stackoverflow that is faster than the base string.Replace().
    Once again, I tested it and it was faster, but I may have fallen into another ultra specific case as the one above.
    So if anybody is interested in testing it, or just using it, here it is :

    Code (csharp):
    1.  static public string Replace(string original, string pattern, string replacement, int stringBuilderInitialSize)
    2.     {
    3.         if (original == null)
    4.         {
    5.             return null;
    6.         }
    7.  
    8.         if (String.IsNullOrEmpty(pattern))
    9.         {
    10.             return original;
    11.         }
    12.  
    13.  
    14.         int posCurrent = 0;
    15.         int lenPattern = pattern.Length;
    16.         int idxNext = original.IndexOf(pattern, StringComparison.OrdinalIgnoreCase);
    17.         StringBuilder result = new StringBuilder(stringBuilderInitialSize < 0 ? Math.Min(4096, original.Length) : stringBuilderInitialSize);
    18.  
    19.         while (idxNext >= 0)
    20.         {
    21.             result.Append(original, posCurrent, idxNext - posCurrent);
    22.             result.Append(replacement);
    23.  
    24.             posCurrent = idxNext + lenPattern;
    25.  
    26.             idxNext = original.IndexOf(pattern, posCurrent, StringComparison.OrdinalIgnoreCase);
    27.         }
    28.  
    29.         result.Append(original, posCurrent, original.Length - posCurrent);
    30.  
    31.         return result.ToString();
    32.     }
  12. angrypenguin

    angrypenguin

    Member

    Joined:
    Dec 29, 2011
    Messages:
    5,193
    Are you dynamically adding new states to these state machines/AIs?

    Even if you are, if performance is key then I'd strongly consider running some kind of pre-pass to convert all of those strings into ints (or similar) for use once the real-time part has started. If performance is important, why work with strings at all?
  13. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    There are 510 animations per character, dynamically converting them at launch would take forever.
    And because there are 510 to 700 anim names per char, I on't have any other choice but to work with strings.
    I'm not even overdoing the number of different anims, it's just the base 4 punches/kicks types (Light/Fierce), declined into basic fighting game moves (close, far, crouch, jump, specials, hit, crouch hit, etc).

    Plus, now that my engine is written, I would have to convert tons and tons of string tests to enums. It's impossible.

    The other reason why I chosed strings over enums is that they let me use concatenation for simpler action triggering routines.
    Last edited: Mar 7, 2012
  14. steego

    steego

    Member

    Joined:
    Jul 15, 2010
    Messages:
    183
    Maybe the Rabin-Karp algorithm is a better choice for you if what you actually need is a multi pattern search. Wikipedia has a list of string search algorithms that you can take a look at to see if there might be a better choice for you.
  15. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    Thanks for the tip, that's a great link !
  16. fholm

    fholm

    Member

    Joined:
    Aug 20, 2011
    Messages:
    1,690
    I am curious, no matter what your results were, what n0mad ment by this:

  17. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    I ment this :


  18. fholm

    fholm

    Member

    Joined:
    Aug 20, 2011
    Messages:
    1,690
    Wait, you did one animation for "punch jump" and one for "punch standing"? or am I miss understanding something? having 500+ animations seems... excessive to say the least.
  19. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    Exactly ;-)

    - (Light | Fierce) + (stand | crouch | jump | closeStand) + (Punch | Kick)
    - combos (average of 3 anims x 6 x 8 Martial Arts, as seen in the latest post of Kinetic Damage's thread, there's 10 min of video)
    - specials (4 per 8 Martial Arts, each containing 2 - 15 different animations, sometimes more)
    - grabs (1 per Art, with (launchGrab | DoGrab | FailGrab) + (enemyGrabReaction | enemyGrabRejection))
    - and hit animations : (Light | Fierce | Falling) + (stand | crouch | jump) + (direction of hit : top | left | right | down), plus other misc anims like standing up/stun/etc, all divived into separate splits to enable refactoring.

    And they're all different, so I couldn't use Anim Mixing (or it would have been situational, so I ran for a full non-mixing, non-anim-reusing approach).

    These are not special at all, it's the basis for all 1vs1 fighting games.

    edit : I just counted, there are 1694 AnimationClips in total.
    Last edited: Mar 7, 2012
  20. Tseng

    Tseng

    Member

    Joined:
    Nov 29, 2010
    Messages:
    1,215
    1. What kind of situation are you exactly taking about or what do the (productive, not just some test code for synthetical tests) code looks like? In which situation you need to compare many strings and for what reasons. If you don't mind posting an actuall piece of code you currently use in your project here, so we can have a look at it.

    Maybe HashTables/Dictionary could be an alternative to whatever you are attempting to do. The Hash tabels usually store only the hash as a key. So if you search inside this HashTable/Dictionary, your input string will be calculated into a hash and only the hash will be compared with the keys in the HashTable

    2. If your AI code is that time critical, you shouldn't use Enums neither. Enums are also quite slow, compared to let's say an int and constants. Of course with int + constants you have to be bit more careful, because it's possible to accidently have invalid values there.

    Code (csharp):
    1.  
    2. public enum {
    3.    State1,
    4.    State2,
    5.    State3
    6. }
    7. // you can do
    8. public class StateConstants {
    9.     public const STATE1 = 0;
    10.     public const STATE2 = 1;
    11.     public const STATE3 = 2;
    12. }
    13.  
    14. ...
    15. int state = STATE3; // at compile time the STATE3 willl be replaced with 2, so there won't be any method or variable access in the final IL code
    16.  
    The const values will be replaced (at compile time) with the values. So it's same as if you do
    Code (csharp):
    1.  
    2.   if(state==2)
    3.      ....
    4.  
    just that it's more readable for you.
    Last edited: Mar 7, 2012
  21. fholm

    fholm

    Member

    Joined:
    Aug 20, 2011
    Messages:
    1,690
    Tseng: Enums are not slow, they are compiled to their native type.
  22. Tseng

    Tseng

    Member

    Joined:
    Nov 29, 2010
    Messages:
    1,215
    After having a second look on it you're right. Guess my mind got somewhat tainted by Java, which I also use (I do Android Apps too) and in Java there is a difference in enum vs. constants (aka static final int/string/whatever).

    Can be quite confusing when you switch back and forth from a well designed language (C#) to an outdated one with some major design flaws (Java)... Like inner/outer class concept of Java which is... really stupid :p
  23. George Foot

    George Foot

    New Member

    Joined:
    Feb 22, 2012
    Messages:
    399
    If you have a lot of processing you want to avoid at load time, push it back into the editor rather than forwards into the runtime. Make an editor script that does all the work and stores the results ready for the game's use, or better, hook up an AssetPostProcessor to rebuild your lookup tables when new animations are imported.
  24. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    I can't post any code that would make sense here, I'm afraid, as it's more of a succession of routines (mainly in my AI) that in a whole package is triggered every second. It's very basic, like for the AI :
    - scan for opponent possible moves
    - check if those moves are doable in the opponent's actual situation (= state machine reader)
    - scan for AI possible moves + check if doable
    - analyze the gathered infos (names -> get moves property from a Dictionary)
    - decide which strategy to adopt (offense, defense, preparation, and some more advanced stuff like move planning ahead of time according to analysis of the fight so far)
    - trim the best move to adopt according to strategy
    - do the action

    this list is just a very simplified overview of what a basic fighting AI has to do in order to stay interesting for hardcore gamers. Actually I'm performing a lot more "getMovePropertyBasedOnActionName" than that, of course.

    Yes, I chosed the Dictionary storing :)
    I even created an Editor class that autocreates data classes, scanning for each move's range, duration, launchTime, etc, and then hardwrite them into the class, to avoid the most runtime calculations possible. Those Editor scans are using a realtime (simulation + estimation + calculation) of important positions for each animation's important bones at important given times, on FBX import.

    edit :



    Haha yes, precisely this, you beat me to it ;-)

    Besides, I've also hardwritten all the moves other Dictionaries manually, like damage, hitStun, etc. So there is absolutely no calculation at all at runtime, only Dictionary lookup, hence the huge importance of string use.

    (But the thread is being derailed a bit here I guess)
    Last edited: Mar 7, 2012
  25. angrypenguin

    angrypenguin

    Member

    Joined:
    Dec 29, 2011
    Messages:
    5,193
    I never suggested converting them to enums, I suggested converting them to ints. This wouldn't noticeably add to your load time, but as George Foot says it can be pushed back even further to the Editor anyway. Or it can be cached.

    My point is, if you're dealing with performance critical code, instead of spending ages optimising string performance, I'd design up front to avoid strings like plague in the first place. In my experience, the only time a string absolutely needs to be a string is when the user can read or write it. And even then, if things are performance critical I'd do a bit of extra work on the back end so that humans can read strings but the computer does its legwork with something more lightweight.

    For instance, programatically create a Dictionary<int, string> where each unique string is mapped to a different integer. From then on, your code can refer to the ints instead of the strings. Your string compare algorithm then gets replace with an integer equality check. Looking up the int for a string later on would be slow, but that would be exceedingly rare after startup. It does make your code a little more cryptic, but if it's truly performance critical then that's probably a price worth paying.

    Edit: I wouldn't say that the thread is getting derailed. The fastest string comparison is, after all, not having to compare strings in the first place. ;)

    Edit edit: My experience with character animation is limited to relatively simple scenarios, so I'm curious as to why you've hand-animated every animation combination instead of using blending.
    Last edited: Mar 8, 2012
  26. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    Because I wanted each animation to have a very different feel from each other to really make each martial art feel unique :)
    (vids in my sig, "giant thread", first page, first vid, for ex)
    + I needed very precise movements
    Last edited: Mar 8, 2012