/ Forside / Teknologi / Udvikling / Java / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Java
#NavnPoint
molokyle 3688
Klaudi 855
strarup 740
Forvirret 660
gøgeungen 500
Teil 373
Stouenberg 360
vnc 360
pmbruun 341
10  mccracken 320
Hvordan er switch strukturen implementeret~
Fra : Thorbjørn Ravn Ander~


Dato : 02-03-01 10:21


Hejsa.

Jeg skal lave en switch med 250 indgange, og jeg blev i tvivl om hvordan
det er implementeret. Hele ideen med en switch er at jeg selv slipper
for at kode en række ineffektive if-then-elsif, men jeg vil jo gerne
have at det blvier compileret til noget der er smartere end det.

Jeg er ikke på hjemmebane i Java Byte Code så jeg er ikke meget for
henvisninger til javap.

Nogen der tilfældigvis véd det?
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear

 
 
Morten Jensen (02-03-2001)
Kommentar
Fra : Morten Jensen


Dato : 02-03-01 11:33

Thorbjørn Ravn Andersen wrote:

> Hejsa.
>
> Jeg skal lave en switch med 250 indgange, og jeg blev i tvivl om hvordan
> det er implementeret. Hele ideen med en switch er at jeg selv slipper
> for at kode en række ineffektive if-then-elsif, men jeg vil jo gerne
> have at det blvier compileret til noget der er smartere end det.
>
> Jeg er ikke på hjemmebane i Java Byte Code så jeg er ikke meget for
> henvisninger til javap.
>
> Nogen der tilfældigvis véd det?

Switch bliver compileret til noget smartere end if-elseif. Switch har jo
den optimeringsfordel, at den arbejder med konstanter, så compileren kan
udregne resultaterne af alle case's med det samme.

(og jeg har checket det med javap) :)

--
CAPUT A/S Morten Jensen Phone +45 70 12 24 42
Nygade 6 Senior Developer Fax +45 70 11 24 42
DK-1164 Kbh K jensen@caput.com http://www.caput.com


Thorbjørn Ravn Ander~ (02-03-2001)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 02-03-01 13:40

Morten Jensen wrote:

> Switch bliver compileret til noget smartere end if-elseif. Switch har jo
> den optimeringsfordel, at den arbejder med konstanter, så compileren kan
> udregne resultaterne af alle case's med det samme.
>
> (og jeg har checket det med javap) :)

Det er jo godt nok

Kan du ikke være en lille smule mere præcis?

--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear

Morten Jensen (02-03-2001)
Kommentar
Fra : Morten Jensen


Dato : 02-03-01 14:50

Thorbjørn Ravn Andersen wrote:

> Morten Jensen wrote:
>
>> Switch bliver compileret til noget smartere end if-elseif. Switch har jo
>> den optimeringsfordel, at den arbejder med konstanter, så compileren kan
>> udregne resultaterne af alle case's med det samme.
>>
>> (og jeg har checket det med javap) :)
>
> Det er jo godt nok
>
> Kan du ikke være en lille smule mere præcis?

Det er ikke noget, som jeg ved noget specielt om, men jeg kan da vise,
hvordan jeg kom frem til ovenstående konklusion.

Jeg lavede en klasse med følgende to funktioner:

public void switchtest(int i)
{
switch(i)
{
case 0:
i++;
break;
case 1:
i++;
break;
case 2:
i++;
break;
}
}

public void iftest(int i)
{
if(i == 0)
i++;
else if(i == 1)
i++;
else if(i == 2)
i++;
}

Med javap -c <klasse> fik jeg følgende resultat for de to funktioner:

Method void iftest(int)
0 iload_1 // Hent variable 1 (metodeparameteren)
1 ifne 10 // Hvis den ikke er 0 gå til 10
4 iinc 1 1 // Læg 1 til variable 1
7 goto 29 // Gå til 29
10 iload_1 // Hent variable 1
11 iconst_1 // Hent konstanten 1
12 if_icmpne 21 // Hvis ikke ens, gå til 21
15 iinc 1 1 // Læg 1 til variable 1
18 goto 29 // Gå til 29
21 iload_1 // Hent variable 1
22 iconst_2 // Hent konstanten 2
23 if_icmpne 29 // Hvis ikke ens, gå til 21
26 iinc 1 1 // Læg 1 til variable 1
29 return // Return

Method void switchtest(int)
0 iload_1 // Hent variable 1 (metodeparameteren)
1 tableswitch 0 to 2: default=46
    0: 28 // Hvis 0 gå til 28
    1: 34 // Hvis 1 gå til 34
    2: 40 // Hvis 2 gå til 40
28 iinc 1 1 // Læg 1 til variable 1
31 goto 46 // Gå til 46
34 iinc 1 1 // Læg 1 til variable 1
37 goto 46 // Gå til 46
40 iinc 1 1 // Læg 1 til variable 1
43 goto 46 // Gå til 46
46 return // Return

Som man kan se, så skal iftest hele tiden hente variable, hente
konstanter og sammenligne, så hvis det er den sidste case man er
interesseret i, så skal den igennem en del.

Det kommer selvfølgelig altsammen an på hvordan jvm'en har implementeret
tableswitch instruktionen.

--
CAPUT A/S Morten Jensen Phone +45 70 12 24 42
Nygade 6 Senior Developer Fax +45 70 11 24 42
DK-1164 Kbh K jensen@caput.com http://www.caput.com


Thorbjørn Ravn Ander~ (02-03-2001)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 02-03-01 15:29

Morten Jensen wrote:

> Method void switchtest(int)
> 0 iload_1 // Hent variable 1 (metodeparameteren)
> 1 tableswitch 0 to 2: default=46
> 0: 28 // Hvis 0 gå til 28
> 1: 34 // Hvis 1 gå til 34
> 2: 40 // Hvis 2 gå til 40

> Det kommer selvfølgelig altsammen an på hvordan jvm'en har implementeret
> tableswitch instruktionen.

Takker. Det var lige præcis den information jeg var ude efter.

Nu har jeg char's som indeks, så hop-tabellen kan så blive lidt
halvstor. Det er bare ok. Hastighed er vigtigere end pladsforbrug.

--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear

Bertel Lund Hansen (02-03-2001)
Kommentar
Fra : Bertel Lund Hansen


Dato : 02-03-01 14:56

Thorbjørn Ravn Andersen skrev:

>det er implementeret. Hele ideen med en switch er at jeg selv slipper
>for at kode en række ineffektive if-then-elsif, men jeg vil jo gerne
>have at det blvier compileret til noget der er smartere end det.

Det gør det. En switch opretter en tabel over mulige værdier
parret med adressen på det ønskede stykke program. Der skal kun
foretages en lynhurtig søgning i et regelmæssigt array.

If aner ikke hvilken type undersøgelse der skal til ved hver
betingelse.

(Helt principielt. Jeg ved ikke noget konkret om Javas
kompilering)


Thorbjørn Ravn Ander~ (02-03-2001)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 02-03-01 15:25

Bertel Lund Hansen wrote:

> (Helt principielt. Jeg ved ikke noget konkret om Javas
> kompilering)

Hvilket var det jeg helt specifikt spurgte til...

--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear

Ulrik Magnusson (03-03-2001)
Kommentar
Fra : Ulrik Magnusson


Dato : 03-03-01 15:47

Thorbjørn Ravn Andersen wrote:

> Jeg skal lave en switch med 250 indgange, og jeg blev i tvivl om hvordan
> det er implementeret. Hele ideen med en switch er at jeg selv slipper
> for at kode en række ineffektive if-then-elsif, men jeg vil jo gerne
> have at det blvier compileret til noget der er smartere end det.
>
> Jeg er ikke på hjemmebane i Java Byte Code så jeg er ikke meget for
> henvisninger til javap.

ok

> Nogen der tilfældigvis véd det?

I hvert fald er svaret - som er blevet præsenteret - at switch er hurtigere
end if--then-else med det yderligere kuriosum, at det er mest effektivt,
hvis konstanterne ligger tæt på hinanden - altså:

switch( n )
{
case 0: //...
case 1: //...
case 2: //...
case 3: //...
}

er hurtigere end
switch( n )
{
case 1: //...
case 10: //...
case 100: //...
case 1000 //...
}

Ulrik Magnusson

--
DEUTSCH: You two have some sick sex thing?
BARTON: Sex?! He's a MAN! We WRESTLED!
Barton Fink - Joel and Ethan Coen, 1991
Visit my home page: http://www.geocities.com/ulrikm



Soren 'Disky' Reinke (05-03-2001)
Kommentar
Fra : Soren 'Disky' Reinke


Dato : 05-03-01 09:06

> I hvert fald er svaret - som er blevet præsenteret - at switch er
hurtigere
> end if--then-else med det yderligere kuriosum, at det er mest effektivt,
> hvis konstanterne ligger tæt på hinanden - altså:

Hvorfor det ?

--
With many Thanks
Soren ' Disky ' Reinke ICQ #1413069 remove 'ihsyd' when email replying
Please visit my Freshwater Aquaria Webpage
http://www.disky-design.dk/fish



Ulrik Magnusson (05-03-2001)
Kommentar
Fra : Ulrik Magnusson


Dato : 05-03-01 17:45

Soren 'Disky' Reinke wrote:

> > I hvert fald er svaret - som er blevet præsenteret - at switch er
> hurtigere
> > end if--then-else med det yderligere kuriosum, at det er mest effektivt,
> > hvis konstanterne ligger tæt på hinanden - altså:
>
> Hvorfor det ?

fordi

case 100 kode1
case 101 kode2

kan laves som et array:

start = 100

array[0] = kode1
array[1] = kode 2

match( konstant )//null ved ikke-match
{
return array[konstant - start]
}

hvis de ikke ligger tæt, skal man bruge en tabel, til at slå det op ( for ikke
at spilde plads):

case 100 kode1
case 1000 kode2
=>
table.put( 100, kode1 );
table.put( 1000, kode2 );

match( konstant )//null ved ikke-match
{
return table.get( konstant );
}

En fornuftig compiler vil oversætte følgende:

case 101: kode1
case 103: kode2

til:
start = 101;
array[0] = kode1
array[1] = null
array[2] = kode2

med

return array[konstant - start] som match funktion

Ulrik Magnusson

--
"hvorfor er det stadig tilladt at høre klassisk musik ?"
'Mickey', dk.politik.indvandring
Visit my home page: http://www.geocities.com/ulrikm



Ulrik Magnusson (05-03-2001)
Kommentar
Fra : Ulrik Magnusson


Dato : 05-03-01 17:49

Ulrik Magnusson wrote:

> Soren 'Disky' Reinke wrote:
>
> > > I hvert fald er svaret - som er blevet præsenteret - at switch er
> > hurtigere
> > > end if--then-else med det yderligere kuriosum, at det er mest effektivt,
> > > hvis konstanterne ligger tæt på hinanden - altså:
> >
> > Hvorfor det ?

[snip - array og tabel]

Tabelopslag svarer i øvrigt til lookupswitch i bytecode og arrayopslag
til tableswitch.

Ulrik Magnusson

--
"hvorfor er det stadig tilladt at høre klassisk musik ?"
'Mickey', dk.politik.indvandring
Visit my home page: http://www.geocities.com/ulrikm



Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste