---

Hvorfor performer detectByReverse en faktor 2-3 bedre end
detectByLinear i nedenstående:

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class DetectBadChars {

   static String badChars = "<\"&'/>\\";

   public void testInit() throws Exception {

      StringBuffer s = new StringBuffer();

      for(int i=0; i<10000; i++) {
         s.append("a");
      }
      s.append("\\");
      String v = s.toString();

      long now = System.currentTimeMillis();
      for(int i=0; i<1000;i++) {
         boolean hit = detectByLinear(v);
         if(!hit)
            throw new Exception("Not detected by linear");
      }
      long linear = System.currentTimeMillis() - now;

      System.out.println("Linear run: "+linear+" ms");

      now = System.currentTimeMillis();
      for(int i=0; i<1000;i++) {
         boolean hit = detectByReverse(v);
         if(!hit)
            throw new Exception("Not detected by reverse");
      }
      long reverse = System.currentTimeMillis() - now;

      System.out.println("Reverse run: "+reverse+" ms");
   }

   public static boolean detectByLinear(String data) {
      for(int i=0;i<data.length();i++) {
         if(badChars.indexOf(data.charAt(i)) != -1) {
            return true;
         }
      }
      return false;
   }

   public static boolean detectByReverse(String data) {
      for(int i=0;i<badChars.length();i++) {
         if(data.indexOf(badChars.charAt(i)) != -1) {
            return true;
         }
      }
      
      return false;
   }
}

---

usenet@kikobu.com skrev den 01-05-2006 11:24:
> Hvorfor performer detectByReverse en faktor 2-3 bedre end
> detectByLinear i nedenstående:

Godt spørgsmål. Den er måske blevet hotspotoptimeret.

Får du samme resultater hvis du bytter om på de to måleløkker?

--
Thorbjørn

---

Yeps. Samme resultat. Jeg prøvede med en random genereret streng, og
så er faktor forskellen nede på omkring 1.5.

      int gap = 90 - 65;
      Random random = new Random();

      StringBuffer s = new StringBuffer();

      for(int i=0; i<20000; i++) {
         s.append((char)(random.nextInt(gap)+65));
         if(i == 10000)
            s.append("\\");
      }

      String v = s.toString();


Mvh.

Morten

---

Det må være fordi at der er et lille overhead i indexOf metoden. Den
initialiserer en variabel og et par andre småting. detectByReverse
bruger badChars.length() indexOf kald, hvor detectByLinear bruger
data.length().

---

usenet@kikobu.com wrote:
> Hvorfor performer detectByReverse en faktor 2-3 bedre end
> detectByLinear i nedenstående:

Det giver meget bedre vilkår for optimering i både compile og
JIT når du med nogle få iterationer løber badChars igennem,
i stedet for mange flere iterationer for at komme igennem hver
char af data.

Så det er ikke så mærkeligt. Men det har nok mere at gøre med
din kode, end selve String.indexOf; men meget færre kald af en
metode vil tendere til at gå hurtigere, også selv om den internt
har brug for at løbe samme antal char[] elementer igennem.

I øvrigt er det ganske tænkbart at en konret JVM/JIT vælger at
implementere "passende" udvalg af java.lang klasserne som f.eks
nogle String metoder uden at køre igennem bytekode hele tiden.