Grep -v? Nee, -L!

Idee 1/2 maart, tekst 4 en 5 maart 2013

Promotie

Mijn nieuwste verzinsel ter promotie van mijn site is een etalagefunctie. Daarin verschijnen steeds andere markante zinsnedes uit bestaande artikelen, met daaronder een hyperlink met de titel erin.

Het idee is belangstelling te wekken. Waarschijnlijk tevergeefs. Maar ik vond en vind het leuk, het programmeren, het markeren en het zien verschijnen. Laat mij maar genieten; zolang verder niemand er last van heeft, is het niet erg.

Realisatie

De functie is georganiseerd is drie stappen:

Markeren

Het markeren doe ik met de hand. Achteraf bij al wat oudere artikelen, of meteen, of toch achteraf, bij nieuwere. Ik breng in de HTML een commentaar aan (tussen <!-- en -->, dus) met een herkenbare unieke string voor het tekstfragment, en een iets andere erna.

Opzoeken

Algoritme

Een in C geschreven programma dat via crontab eenmaal per etmaal draait, of op afroep als ik dat leuk of nodig vind, zoekt alle HTML-bestanden van de hele site af – waarvan de padnamen worden aangeleverd door find met wat grep-filtering erachter). Het programma noteert de taalcode (uit bijvoorbeeld: <html lang=nl> bij een pagina in het Nederlands), de titel (tussen <h1> en </h1>, hoewel ik ook van de <title> had kunnen uitgaan), en alle eventuele tekst die tussen de markeringen blijkt te staan.

Die teksten, steeds met een voorbereide hyperlink eronder, worden verzameld in HTML-bestanden per taal. Ze zijn niet rechtstreeks bereikbaar voor websitebezoekers, maar alleen via het selectieprogramma. Daarover meer in het volgende hoofdstukje.

Performance

Deze opzoekstap is niet bedoeld om superefficiënt te zijn, omdat hij toch niet vaak hoeft te draaien. De stap doet het zware werk (stelde ik me voor, toen ik de getrapte opzet bedacht), zodat de volgende stap efficiënt en snel kan zijn. Dat moet wel, omdat die selectiestap steeds opnieuw door bezoekers kan worden geactiveerd, zonder dat ik daar controle over heb. Daar kan dus in theorie een zware belasting van de webserver door ontstaan.

Merkwaardig genoeg echter kost de opzoekstap slechts ongeveer een zesde van een seconde, ondanks het gebruik van een zeer bescheiden virtuele server, waarop slechts een deel van de capaciteit van een van de fysieke processorkernen beschikbaar is.

In die uiterst korte tijd van ca. 160 milliseconden (doorlooptijd! de echte CPU-tijd is maar zo’n 60 ms) is dan bijna 8 megabyte aan HTML-code in 1099 bestanden doorgeworsteld. Ik vraag me af hoe het mogelijk is dat moderne computers soms vele minuten over een taak doen, bijvoorbeeld over het starten van een Windows-systeem. Hoe kan dat als deze ogenschijnlijk heftige sequentiële zoektaak zo extreem snel gaat?

Selecteren

Het selectieprogramma doet in essentie met een door de vorige stap voorbereid bestand, wat dit en dit doen met de sitemap: ze selecteren daaruit met behulp van een randomiser bij elke aanroep andere entries.

Er is een voorziening om te garanderen dat bij één aanroep dezelfde entry nooit meer dan eens geselecteerd wordt: een simpel tabelletje waarin wordt bijgehouden wat al eerder gevonden was. Met een noodrem natuurlijk: als er minder entries zijn voorbereid dan worden aangevraagd, dan moet het zoeken ooit wel een keer ophouden.

Ook deze selectiefunctie blijkt zeer snel te werken en de webserver nauwelijks te belasten. C, CGI, Apache en FreeBSD vormen samen een flitsend team, met mijzelf als teamleider. Maar vergeet niet de hardware en virtualisatierealisatie van Tilaa.nl.

Welke nog niet en dus nog?

Richting een algoritme

Ik wilde wel eens weten in welke HTML-bestanden ik de bedoelde zinsnedemarkeringen al had aangebracht, en in welke nog niet zodat ik dat alsnog zou kunnen doen. Daartoe bakte ik een shellscriptje met daarin:

fgrep -rl "Destaque Rudhar.com" $HOMEBASE |
   grep -v -f ~/bin/nodestaq-stop | sort

Ik zoek dus recursief (-r) alle bestanden door vanaf de begindirectory van de webbestanden van de site. ‘Recursief’ wil in dit verband zeggen dat ook alle bestanden in subdirectories worden meegenomen. De optie -l wil zeggen dat ik niet de door grep gevonden tekststrings wil zien, maar juist en alleen de bestandsnamen (padnamen) van de bestanden waarin iets gevonden is.

Performance

Daarna filter ik met een pipe (‘|’) een heleboel patronen, paden en bestanden eruit waarin die markeringen sowieso niet thuishoren. Daaronder bijvoorbeeld jpg-, wav- en mp3-bestanden. Het geheel is dus nogal inefficiënt: er wordt heel veel data doorzocht waarvan te voren bekend is dat er niks interessants in gevonden kan worden, met daarna nog eens een uitfiltering (die vooral interessant bij de volgende stap: de omkering).

Grep kan bij mijn weten niet de optie -r combineren met bestandsnamen of bestands­naam­patronen, zodat je het bereik van de zoekactie zou kunnen beperken. Als argument van grep dienen in dit geval een of meer directory’s, die startpunt zijn voor de recursieve zoekactie door de hiërarchische boom.

Ik had het script ook achterstevoren kunnen zetten: eerst de output van find filteren, en via xargs vervolgens grep alleen in de juiste bestanden laten zoeken. Dat ziet er dan zo uit:

find $HOMEBASE -type f | grep -v -f ~/bin/nodestaq-stop |
   xargs fgrep -l "Destaque Rudhar.com" | sort

Maar dat is ook niet efficiënt, omdat mijn stoplist vrij lang is, 130 regels. Voor elke aan grep aangeboden regel moeten al die 130 reguliere expressies worden doorlopen, om te zien of er reden is om het zoekpad voor de volgende stap te skippen. Dat kost ook tijd. (Als er eenmaal een reden is gevonden, hoeft weliswaar de rest niet meer bekeken te worden, maar dan nog.)

Meetwaarden (beide met alvast de omkering waar ik zo op kom): 1,15 seconden zuivere CPU-tijd voor de tweede methode, tegen 1,28 bij de eerste. Niet de moeite van het optimaliseren waard dus, zeker gezien het zeer incidentele gebruik van het script.

Meten is weten.

Omkeren

Tot zover keek ik dus waar de markeringen van zinsnedes wél in mijn HTML voorkomen. Werkt prima. Maar eigenlijk wilde ik weten waar ze nog níét voorkomen, maar eventueel wel zinvol toe te voegen zijn.

Simpel, dacht ik, ik draai gewoon de grep om, met de bekende omdraaioptie -v die ik hierboven ook al toepaste om bestandsnamen uit te sluiten van zoekacties.

Maar het bleek niet te werken. HTML-bestanden waarvan ik wist dat er markeringen in stonden, verschenen in de oorspronkelijke lijst (correct), maar óók in de lijst nadat ik -v had toegevoegd. Hoe kon dat?

Dus maar eens testen met een eenvoudig voorbeeld en de handleiding nauwkeurig lezen. Zoek op man grep.

Wat blijkt? De optie -v keert inderdaad om: “Invert the sense of matching, to select non-matching lines.

Er staat “lines”, niet “files”. In plaats van dat de regels mét markering eruit zouden komen (als ik niet met -l om alleen filenamen gevraagd had), komen de regels zónder markering eruit. In beide gevallen zou er dus uitvoer zijn. En de optie -l betekent:

Suppress normal output; instead print the name of each input file from which output would normally have been printed.

In mijn voorbeeld is er zowel met als zonder -v wel uitvoer, dus geeft -l altijd uitvoer. Dat zou alleen niet zo zijn bij een HTML-bestand waarin alleen maar regels met een markering stonden en geen andere regels.

De optie -v keert wel om, maar niet op de manier die ik nodig heb. Gelukkig is er ook een optie die wel doet wat ik wil. Die optie kende ik niet van mijn vroegste kennismaking met Unix, tussen 1985 en 1990. Bestond die toen nog niet of heb ik haar gewoon nooit opgemerkt? Weet ik niet, ga ik niet nazoeken.

De omschrijving van de optie -L verschilt maar in één woord, namelijk “no”, van die van -l:

Suppress normal output; instead print the name of each input file from which no output would normally have been printed.

Inderdaad blijkt dit de oplossing: in het script dat bestanden vindt waarin wél markeringen staan, niet -v toevoegen, maar -l vervangen door -L.

Kast

Unix is case-sensitive: hoofdletters (uit de bovenkast) hebben een andere betekenis dan kleine letters (uit de onderkast). Puristen schrijven daarom commandonamen zoals grep altijd met een kleine letter, ook in lopende tekst aan het begin van een zin. Ik dacht dat dat ook geldt voor man-pages, maar het blijkt niet zo te zijn. O nee, alleen soms niet, zoals hier op het web; maar vaak ook wel, zoals in de commandoregel van FreeBSD 8.3:

grep searches the named input FILEs (or standard input if no files are named, or the file name - is given) for lines containing a match to the given PATTERN. By default, grep prints the matching lines.

Kleuren: Neutraal Raar Geen voorkeur Pagina opnieuw laden