AT Blog

Ditmaal een voorbeeld van een goedbedoelde optimalisatie techniek die geen verbetering maar een verslechtering opleverde. De optimalisatie houdt in dat je het aantal keer dat een for-loop moet worden opgebouwd minimaliseert. Dit speelt vooral wanneer je loops in loops codeert, zoals de twee loops uit mijn vorige blog. Hier als opfrisser de geoptimaliseerde code.

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

Als we kijken naar de buitenste for-loop dan wordt voor elke bug een for-loop opgestart die de toegewezen medewerker opspeurt. De binnenste for-loop wordt dus voor elke bug opgebouwd en dit opbouwen kost CPU cycles. Er valt winst te behalen als we dit opbouwen kunnen verminderen.

In ons geval zal MAX_EMPLOYEES meestal vele malen kleiner zijn dan MAX_BUGS. Het zou in ons geval dus lonen om de twee for-loops om te draaien. Dan hoeft er namelijk nog maar MAX_EMPLOYEES keer een for-loop te worden opgebouwd. Oftewel de code wordt als volgt:

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

Je zal helaas merken dat de code langzamer draait dan de voorgaande versie. In mijn geval 2 seconden langzamer. Dit komt omdat bug_assignee[bug_number] nu in elke iteratie van de binnenste loop een ander array element aanwijst. Bij de vorige bleef deze constant tijdens de binnenste loop en hierdoor maak je efficiënter gebruik van je CPU registers.

Dit was niet wat ik beloofd had, namelijk een optimalisatie die ervoor zorgt dat de code minder dan 1 seconde nodig heeft. Ik ga dat echter nu nog niet verklappen. Maar ik zal jullie ook niet achterlaten met een slechter werkende code. Er valt namelijk nog wel een seconde winst te behalen door op te merken dat het doel is om alleen voor medewerkers die niet in dienst zijn de bugs te tonen. We hoeven dus niet voor iedere medewerker de lijst van bugs langs te lopen. Als we de code aanpassen als volgt:

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

Dan wordt de code er zeker niet leesbaarder op maar haal ik wel een winst van 1 seconde ten opzichte van de geoptimaliseerde code aan het begin van deze blog. Wellicht dat bovenstaande aanpassing jullie al op een idee brengt om de code nog sneller te maken....

Debian

In het Debiankamp vraagt Thomas Hood zich af of Bash scripts kunnen/moeten worden geëlimineerd (link). Hij geeft een aantal redenen die al snel van tafel worden geveegd. De enige reden die overblijft is dat Dash (Debian Amquist Shell) minder afhankelijkheden heeft. Men vindt dit niet voldoende om Bash in de ban te doen.

Manjul Apratim merkt op dat Sid (unstable) eigenlijk erg bruikbaar is en vraagt zich af wat het verschil is tussen Sid en de stabiele versie van Debian. Daarnaast vraagt ie zich af waarom Sid nog steeds erg achter loopt met betrekking tot GNOME (link). Jonathan Nieder geeft aan dat unstable vooral betekent dat afhankelijkheden van pakketten wellicht nog niet bestaan. Er mag in principe geen instabiele software aan Sid worden toegevoegd. In dat opzicht is Sid dus vaak goed bruikbaar. Josselin Mouette maakt duidelijk dat GNOME 3 wel al in de experimentele versie zit. Echter, het kan pas in Sid worden opgenomen wanneer "alle" pakketten waaruit GNOME 3 bestaat in Sid kunnen worden opgenomen. Aangezien GNOME 3 uit heel veel pakketten bestaat duurt dit allemaal wat langer.

De database die de tijdzones bijhoudt is uitgezet (link). Dit kan grote gevolgen hebben voor localisatie van de tijd op Linux systemen. Maar men maakt zich er niet zo druk over aangezien er al een backup is gemaakt en de database op een andere locatie alweer online is (link).

Eric Dorland maakt bekend dat hij automake versie 1.7 zal verwijderen (link). Paul Wise vraagt waarom dan niet eerst versie 1.4 wordt verwijderd. Eric durft daar niet aan omdat er wellicht gebruikers zijn die nog oude software willen bouwen die alleen te bouwen is met automake versie 1.4.

Marco d'Itri vraagt zich af hoe complex het zal zijn om het idee van Fedora om alle software naar /usr te verplaatsen ook in Debian te implementeren (link) (link). Het doel van de directories /bin, /sbin, en /lib is om software te bevatten die vervolgens kan worden gebruikt om /usr te mounten. Het idee is om deze taak over te hevelen naar de initrd (initiele ramdisk). Men geeft aan dat er een hoop voorwaarden zijn maar deze lijken vooralsnog niet onoverkomelijk.

Fedora

Bij Fedora maakt Kevin Fenzy bekend dat iedere gebruiker van het Fedora Account System (FAS) zijn of haar wachtwoord moet wijzigen en een nieuwe publieke SSH sleutel moet uploaden (link). De reden is niet dat de systemen van Fedora zijn gehackt maar is in navolging van het grote aantal recente inbraken op andere belangrijke systemen (e.g. linuxfoundation.org, kernel.org, mysql.net). Men heeft weinig problemen met het wijzigen van het wachtwoord, maar het wijzigen van de sleutels vindt men meer problematisch. Dit aangezien vele één sleutel gebruiken voor meerdere diensten. Dit vereist dan dat men meerdere sleutels moet gaan beheren.

Daniel Drake geeft aan dat er nogal een verschil zit tussen de fontgroottes van Fedora 14 en Fedora 16. Hij vraagt zich af waardoor dit komt (link). Het blijkt dat deze hardcoded in GNOME zitten (link). Dit is zo gedaan omdat men niet kan vertrouwen op de schermresolutie in dotch per inch (DPI) die Xorg aangeeft. Dit komt weer omdat de correcte DPI niet eenduidig kan worden berekend omdat hardware leveranciers niet altijd correct de beeldscherm afmeting doorgeven (link).

Er wordt natuurlijk nog flink ontwikkeld aan systemd en dit levert de nodige discussies op. Meestal gaat dit over hoe het een en ander moet via systemd. Maar er wordt bijvoorbeeld ook gediscussieerd over de opstarttijd van CD (live) van een Fedora 16 en in vergelijking met Knoppix (link). Lennart Poettering geeft aan dat het wel een beetje appels met peren vergelijken is aangezien Fedora 16 veel enterprise software bevat en opstart terwijl Knoppix veel minder opstart. Desalniettemin is het interessant om te kijken wat er geoptimaliseerd kan worden. Het blijkt dat sommige hardware probes op andere hardware probes staan te wachten die eigenlijk niet afhankelijk zijn van elkaar. Hierdoor duurt het opzetten van bijvoorbeeld LVM erg lang dat wacht totdat alle hardware probes klaar zijn (link).

Ook bij Fedora wordt er druk gediscussieerd over het verplaatsen van /bin, /sbin, en /lib naar /usr en wat voor impact het heeft (link). Algemeen ziet iedereen deze opzet wel zitten. Deze opzet maakt het mogelijk om /usr bijvoorbeeld read-only te mounten en het root filesysteem read-writable. Daarnaast kan dan makkelijk het OS gedeeld worden over meerdere machines door /usr te exporteren.