AT Blog

In een vorige blog heb ik laten zien dat de volgorde van if-statements van invloed kan zijn op de prestaties van je programma. Dat dit op meerdere manieren tot uiting kan komen in je code wil ik graag illustreren aan de hand van een ander praktijkvoorbeeld. De volgende code is onderdeel van een routine die een lijst van bugs moet tonen die toegewezen zijn aan medewerkers die niet meer in dienst zijn.

for ( bug_number = 0; bug_number < MAX_BUGS; bug_number++ )
{
  for ( employee_id = 0; employee_id < MAX_EMPLOYEES; employee_id++ )
  {
    if( ( employee_employed[employee_id] == false ) && (employee_id == bug_assignee[bug_number]) )
    {
      printf("Bug %d assigned to non employed person\n", bug_number);
    }
  }
}

De code is geschreven op basis van een zogenaamde "user story" en is recht toe recht aan geprogrammeerd.

De code doet precies wat de gebruiker wilde, het was echter erg traag. Gemiddeld moest de gebruiker 30 seconden wachten op het eerste resultaat. De routine waarin bovenstaande for-loop zat had een aandeel van 28 seconden. Dit was onacceptabel. Het resultaat mocht niet langer dan 10 seconden op zich laten wachten. Laten we eens kijken of we dit kunnen bereiken.

Allereerst neem ik de if-statement onder de loep. In een volgend blog zal ik de code verder analyseren en optimaliseren. De if-statement bevat twee condities, namelijk:

employee_employed[employee_id] == false

en

employee_id == bug_assignee[bug_number]

De condities zijn verbonden via && oftewel een logische AND. Dit betekent dat de gecombineerde conditie alleen slaagt als beide condities waar zijn. Als één van beide condities onwaar is, zal de gecombineerde conditie ook onwaar zijn. Wanneer de conditie voor de && faalt, zal dus de gecombineerde conditie ook falen. Het programma hoeft de conditie na de && dan ook niet te evalueren. Dit wordt door de meeste programmeertalen ondersteund; men noemt dat lazy evaluation. Dit stelt ons in staat om dit stukje code te optimaliseren door hier ook een frequentie-analyse te doen.

De buitenste loop itereert over de lijst van bugs, terwijl de binnenste loop itereert over de lijst van medewerkers. In de binnenste loop gaan we op zoek naar de medewerker die is toegewezen aan de bug en controleren we of de medewerker nog in dienst is. Nu is het zo dat elke bug altijd is toegewezen aan maximaal één medewerker. Oftewel de conditie employee_id == bug_assignee[bug_number] zal in de binnenste loop maar één keer slagen. Er zijn meerdere medewerkers inmiddels niet meer in dienst. Dit betekent dat de conditie employee_employed[employee_id] == false veel vaker slaagt. Dit heeft tot gevolg dat tijdens de binnenste loop een aantal keer onnodig alle twee de condities worden geëvalueerd. Namelijk voor die situaties waarbij de medewerker niet meer in dienst is en hij of zij niet aan de bug is toegewezen. Dit kunnen we voorkomen door de condities om te draaien.

...
if( (employee_id == bug_assignee[bug_number]) && (employee_employed[employee_id] == false) )
...

Deze simpele aanpassing leverde in dit geval een winst op van bijna 23 seconden en voldeed daarmee aan de wensen van de gebruiker.

Er is echter nog veel meer winst te behalen. Het lukte mij om de routine te herschrijven zodat deze minder dan één seconde nodig had. Ik zal hier in een volgend blog verder op ingaan.

In het Debiankamp vraagt Christoph Anton Mitterer zich af of Debian's kernel gevolgen ondervindt van de kernel.org hack (link). Ben Hutchings laat weten dat hij de ondertekeningen controleert en dat de sleutels niet op kernel.org staan. Naar zijn inziens is de code dus niet gecompromitteerd.

Jon Dowland vraagt zich af of ondersteuning voor encrypted filesystemen niet gebruikersvriendelijker kan (link). Nu is het zo dat je tijdens installatie de optie hebt voor encryptie van het volledige filesysteem. Hij wil graag dat er ook een optie komt om alleen de home directory te versleutelen. Men heeft hier bedenkingen bij, aangezien het de gebruiker wellicht een vals gevoel van veiligheid geeft. Sommige gevoelige informatie zoals sleutels in het geheugen of bijvoorbeeld printjobs onder /var/spool/cups worden dan niet versleuteld. Wanneer de gebruiker zijn systeem laat "hibernaten" worden deze gegevens onversleuteld naar de swapruimte geschreven.

Stefano Zacchiroli (de huidige Debian projectleider) geeft een verslag van zijn presentatie op de GNU Hackers Meeting (GHM) in Parijs (link). Hij heeft daar lang gepraat met Steve White over Debians procedure om bugs door te spelen naar de originele ontwikkelaars (upstream). Veel eindgebruikers melden bugs bij Debian aan die niet door de packager maar door de originele ontwikkelaar moeten worden opgelost. Steve White kwam met het voorstel om het bug tracking systeem en/of het package tracking systeem van Debian aan te passen, zodat upstream ontwikkelaars makkelijker hun software in Debian in de gaten kunnen houden. Hiermee een betere link leggende tussen de eindgebruikers en de originele ontwikkelaars (link).

Didier Raboud geeft een verslag van de Mobile UX discussie sessie (Birds Of a Feather (BoF)) (link). Belangrijkste conclusie is dat er veel initiatieven zijn om Debian op Mobiele platformen (denk aan smartphones en tablets) te krijgen, maar dat deze nu verdeeld zijn over meerdere groepen. Er moet een overkoepelende organisatie komen waardoor de inzet beter kan worden gecoördineerd.

Bij Fedora is er wat ophef ontstaan over het openssh pakket dat in Rawhide (ontwikkelversie van Fedora) na een update niet meer werkte (link). Men vraagt zich af hoe het kan dat een pakket door de tests is gekomen en zo in Rawhide is opgenomen. Jan F. Chadima geeft eerlijk toe dat hij de oorzaak van het probleem is (link). Hij gebruikt wel degelijk tests om het pakket te controleren en begrijpt niet waarom de tests bij hem slaagden terwijl na installatie de software niet werkte. Het is duidelijk dat Rawhide een ontwikkelversie is en stuk kan gaan. Maar men vindt dat er toch beter getest moet worden voordat het wordt opgenomen in Rawhide. Men heeft goede hoop dat testen via het autoQA project dit soort problemen in de toekomst kan voorkomen.

Matyas Selmeci wil graag weten hoe hij prioriteiten in packages kan verwerken zodat yum op bepaalde machines selectief pakketten installeert (link). Richard Hughes raadt hem zif aan en raakt daarmee een gevoelige snaar. Het programma zif is net als yum een package manager. Zif gebruikt echter andere regels om te bepalen welk pakket moet worden geïnstalleerd dan de regels die yum gebruikt. Men vindt dit onacceptabel en men heeft liever dat verbeteringen worden aangedragen bij yum. Daarnaast is men erg sceptisch of zif wel beter is in het afhandelen van pakket-afhankelijkheden dan yum. Hierover blijft Richard Hughes helaas stil. Kevin Kofler legt uit dat de logica in yum om een pakket te kiezen zo complex is geworden, dat het als een random algoritme moet worden beschouwd. De nieuwe package manager zif probeert dit te verbeteren (link).

Tom Callaway laat weten dat de Fedora Packaging Guidelines zijn geactualiseerd (link). Ten behoeve van hardening is een sectie Position Independent Executable (PIE) toegevoegd. Dit maakt het voor aanvallers moeilijker om vooraf te bepalen waar bepaalde code in het geheugen wordt geplaatst. Als dit wel bekend is, kunnen ze ervoor zorgen dat hun eigen code wordt uitgevoerd via een zogenaamde return-to-libc aanval. Daarnaast is er een voorbeeld toegevoegd waarbij expliciete afhankelijkheden zijn toegestaan en md5-peslyak is toegevoegd waarin bundelen van bibliotheken wel is toegestaan.

Paul Wouters doet een oproep om dns-trigger te testen (link). Dit pakket maakt het mogelijk om een (desktop)gebruiker te waarschuwen wanneer DNS niet te vertrouwen is via DNSSEC.