Ugens mest nørdede opgave

  • var også ugens ubetinget sjoveste, i en arbejdsuge, der for mit vedkommende har været præget af bugfixing og oprydning i bugreports, da vi nærmer os afslutningen på næste release.  Så hvis der skullle sidde nogle med-nørder derude, vil jeg da gerne dele ugens nørdede opgave:

Man har et stykke JavaScript med en meget lang række af eller, eller, eller... betingelser i en if: 

if (zipCode == 10001 || zipCode == 10020 || .... osv.

Når dette gives til Mozillas JavaScript-engine, fejler sidstnævnte med en StackOverflowError i forbindelse med at transformere parse-træet til en række instruktioner til JavaScript-fortolkeren."Synderen" er følgende stykke kode i funktionen generateICode

     case Token.AND :            
     case Token.OR : {  
          stackDelta = 1;
          iCodeTop = generateICode(child, iCodeTop);                
          iCodeTop = addIcode(Icode_DUP, iCodeTop);               
          itsStackDepth++;
          if (itsStackDepth > itsData.itsMaxStack)                   
               itsData.itsMaxStack = itsStackDepth;               
          int afterSecondJumpStart = iCodeTop;
          int jump = (type == Token.AND) ? Token.IFNE : Token.IFEQ;
          iCodeTop = addForwardGoto(jump, iCodeTop);               
          itsStackDepth–;
          iCodeTop = addToken(Token.POP, iCodeTop);               
          itsStackDepth–;
          child = child.getNext();
          iCodeTop = generateICode(child, iCodeTop);               
          resolveForwardGoto(afterSecondJumpStart, iCodeTop);
          break;           
     }

Oplagt nok laves der et rekursivt kald for hhv. venstre og højre undertræ i en eller-betingelse. Ved tilstrækkeligt mange under-betingelser, vokser stack'en sig så stor, at den overskrider det for applikationen satte maksimum.  Hvad gør man så? Man må jo folde rekursionen ud. Da ||-operatoren i JavaScript associerer til venstre, vil et træ bestående af a || b || c || d || ... være skævt mod højre, dvs. at det er det sidste rekursive kald til generateICode(child, iCodeTop), vi skal have foldet ud, så vi kører en løkke indenfor case Token.OR så længe højre barn også er en OR.  Derved får man noget i stil med:

     case Token.AND :
     case Token.OR : {
          stackDelta = 1;
          Node myChild = child; 
          Node myNode = node; 
          do {
               iCodeTop = generateICode(myChild, iCodeTop); 
               iCodeTop = addIcode(Icode_DUP, iCodeTop); 
               itsStackDepth++;
               if (itsStackDepth > itsData.itsMaxStack) 
                    itsData.itsMaxStack = itsStackDepth; 
               int jump = (type == Token.AND) ? Token.IFNE : Token.IFEQ;
               iCodeTop = addForwardGoto(jump, iCodeTop); 
               itsStackDepth–;
               iCodeTop = addToken(Token.POP, iCodeTop); 
               itsStackDepth–;
               myNode = myChild.getNext();
               myChild = myNode.getFirstChild();
          while (myNode.type == node.type);
          iCodeTop = generateICode(myNode, iCodeTop);
          break;
     }

Men hvis man kigger nærmere på forskellen mellem ovenstående og den originale kode, så vil man bemærke, at der i den originale kode var en linje til sidst med
                 resolveForwardGoto(afterSecondJumpStart, iCodeTop);

Det er fordi, man først efter at have genereret kode for hele betingelsen ved, hvor langt, man skal hoppe for at komme ud af betingelsen. Det ved vi jo ikke noget om, mens vi er i den nye løkke, fordi vi ikke har genereret kode for hele betingelsen endnu. Altså må vi samle de jumps op, der skal rettes til, når vi er færdige. 

Den endelige kode ser derfor således ud:

     case Token.AND :
     case Token.OR : {
          stackDelta = 1;
          Node myChild = child; 
          Node myNode = node; 
          List jumpsToFix = new ArrayList();
          do {
               iCodeTop = generateICode(myChild, iCodeTop); 
               iCodeTop = addIcode(Icode_DUP, iCodeTop); 
               itsStackDepth++;
               if (itsStackDepth > itsData.itsMaxStack) 
                    itsData.itsMaxStack = itsStackDepth; 
               jumpsToFix.add(iCodeTop);
               int jump = (type == Token.AND) ? Token.IFNE : Token.IFEQ;
               iCodeTop = addForwardGoto(jump, iCodeTop); 
               itsStackDepth–;
               iCodeTop = addToken(Token.POP, iCodeTop); 
               itsStackDepth–;
               myNode = myChild.getNext();
               myChild = myNode.getFirstChild();
          while (myNode.type == node.type);
          iCodeTop = generateICode(myNode, iCodeTop);
          for (int afterSecondJumpStart : jumpsToFix) {
               resolveForwardGoto(afterSecondJumpStart, iCodeTop);
          } 
          break;
     }

Et voilà: Var det ikke sjovt? I hvert fald for en nørd som mig ![Eksternt billede](http://www.version2.dk/uploads/smil3dbd4d6422f04.gif" alt=")

Kommentarer (6)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Henrik Jacobsen

Nice... omend jeg som gammel OS- og compiler-hacker er svær at imponere. Men det er vel ikke en løsning på det oprindelige problem - andet end på meget langt sigt - at vise hvordan Mozillas Java-engine skulle ha' set ud for at kunne køre din kode? Der er jo lige nogle ganske få millioner klienter der skal opdateres, når Mozilla teamet har implementeret din ændring. Eller der der noget jeg helt har misforstået?

mvh Henrik

  • 0
  • 0
Jacob Christian Munch-Andersen

Jeg vil da lige bemærke at i JavaScript sammenhænge er det bedste for den samlede ydelse ofte at få koden til at fylde så lidt som muligt, eftersom det giver mindre download tid. I det her tilfælde vil du spare meget plads ved at fylde værdierne på en liste og iterere igennem den. Den bedste pladsoptimering for store mængder data opnår man som regel ved at sammenskrive hele molevitten til en streng i et til formålet defineret format.

Hvis selve tjekket af om det er et legalt postnummer også skal gå hurtigt kan du "vende arrayet om" ved at gøre værdierne til nøgler i et nyt array eller objekt.

At omtalte JavaScript motor kunne være skrevet smartere er sikkert korrekt, men det samme kan helt sikkert siges om din postnummer kode.

  • 0
  • 0
Kim Dalsgaard

Hvis man anvender jQuery vil det blive noget med

if ($.inArray(zipCode, targetZipCodes) > -1) {
...
}

hvor targetZipCodes = [10001, 10020, ... ]

Vil man have ekstra fart på kunne man skrive en $.inSortedArray plug-in til jQuery.

  • 0
  • 0
Anne-Sofie Nielsen

Jeg kan se, at der er indtil flere venlige mennesker, som gerne vil fortælle mig, hvordan JavaScriptet skulle være skrevet.

Derfor bliver jeg nødt til at klargøre, at JavaScript-koden ikke er min: Jeg laver et værktøj, som kunderne anvender på sider, der kan indeholde vilkårlig JavaScript. Zip code script'et kommer fra en side, som en kunde havde brug for at anvende værktøjet på.

Det er altså IKKE en mulig løsning at bede om en ændring af JavaScriptet - selvom det selvfølgelig havde været den bedste løsning, hvis det havde kunnet lade sig gøre.

Jeg håber i øvrigt ikke, at der har siddet en halvsnalret JavaScript-programmør et sted og hånd-skrevet 400 (eller hvor mange det nu var) gange eller-eller-eller. Formodentlig er det maskin-genereret?

  • 0
  • 0
Anne-Sofie Nielsen

Men det er vel ikke en løsning på det oprindelige problem - andet end på meget langt sigt - at vise hvordan Mozillas Java-engine skulle ha' set ud for at kunne køre din kode? Der er jo lige nogle ganske få millioner klienter der skal opdateres, når Mozilla teamet har implementeret din ændring.

Nej, vi kører med en hjemme-patchet udgave af Mozillas JavaScript-engine, da vi i nogle tilfælde er nødt til at lave rettelser, som alle måske ikke vil have - og ikke kan vente på, at der måske først om laaaang tid bliver releaset en ny udgave med ændringer, der for os kan være kritiske.

Så det er ikke en akademisk øvelse; det er et spørgsmål om at løse kundernes problemer NU.

  • 0
  • 0
Log ind eller Opret konto for at kommentere