Løsning: Nu med C

lør maj 16, 2009 (Rolf)

Inden du kommer for langt: Se først opgaven!!!

Brainer - billede

Den var svær den sidste – men den blev rimelig godt knækket på DTU Fotonik af Henning Engelbrecht Larsen. Rigtig rigtig flot! Morten gennemgår svaret her:

Afhængig af arkitektur og calling conventions overføres argumenter til en C funktion enten på stakken eller i registre. Hvis x overføres via register er det sædvanligvis ikke muligt at tage adressen af registeret. Compileren vil derfor gemme argumentet på stakken, hvilket giver en skrivning til hukommelsen. Her finder du årsagen til performance problemet i funktionen fra sidst.

Det andet problem hænger sammen med at compilere er smarte – det meste af tiden i hvert fald. Desværre kan en optimerende compiler finde på at konkludere således: ”Eftersom programmøren beder om en pointer til en 8-bit værdi, er der jo ingen grund til at skrive samtlige 32 bit ud på stakken”. Herefter er det nemt at regne ud at resten af koden ikke kommer til at virke som forventet.

Det kan selvfølgelig argumenteres at dette må være en fejl i compileren eftersom udtrykket &x i sig selv skal give en pointer til en korrekt 32-bit værdi; men det ændrer ikke på at man bevæger sig langs kanten af sproget og derfor fra tid til anden kan støde ind i problemer. I så tilfælde gælder som altid, at det er ligegyldigt hvem der har skylden så længe der ikke er smør på brødet.

Der er i øvrigt flere der har gættet på endianness som et muligt problem. I netop dette tilfælde, da samme tabel bruges til alle fire bytes, vil endianness ikke være et problem. Havde vi brugt forskellige tabeller havde dette naturligvis også været et problem.

Til slut et forslag til en bedre måde at skrive den funktion på:

#include <stdint.h>
const uint8_t lookup_table[256] = { };
uint32_t better_translate(uint32_t x)
{
  uint32_t ret;
  ret = lookup_table[x & 0xff]
  | (((uint32_t) lookup_table[(x>>8) & 0xff] ) << 8) 
  | (((uint32_t) lookup_table[(x>>16) & 0xff] ) << 16)
  | (((uint32_t) lookup_table[(x>>24) & 0xff] ) << 24);
  return ret;
}

Konklusion: Koder du “ude på kanten”, må du være forberedt på problemer. Ryk lidt tilbage i stolen og kod lidt mere defensivt – det svarer sig i længden.

Hvad mener du?