1BRC - Python vs. Perl

Hur matchar Python jämfört med Perl, när det kommer till 1BRC? I denna artikel, implementerar jag en lösning till 1BRC (1 Billion Row Challenge) dels i Python och dels i Perl och mäter tiden för att behandla olika filstorlekar. Vem vinner, tror du?

Om du är ny här, så länkar jag till tidigare artiklar i denna serie, sist i denna artikel. Den första i serien, går igenom programmeringsuppgiften och visar en lösning i Java. Den andra artikeln, visar en enkel lösning i C++, medan den tredje går igenom en betydligt mer ambitiös och optimerad C++ version.

Program Design

I korthet, går det ut på att läsa en textfil med namn på väderstationer och tillhörande temperatur separerade av semikolon och ett sådant par per rad. Temperaturen för respektive väderstation ska aggregeras till medelvärde samt lägsta och högsta temperatur. Resultatet ska skrivas sorterat på stationsnamnen i alfabetisk ordning.

Jag har ju tidigare visat kod i både Java och C++. Denna gång tänkte jag jämföra både kod och förfluten tid mellan en version i Python och en i Perl.

Programspråken

Perl började utvecklades i slutet 1980-talet av Larry Wall, som en slags hybrid av shell-script, AWK och C. Målsättningen var och är att tillhandahålla ett snabbt skript-språk för textbehandling. Vilket också dess akronym står för, nämligen Practical Extraction and Report Language.

Under 1990-talet blev Perl kolossalt populärt och kom att användas i många olika typer av tillämpningar, från rena system-administrativa uppgifter till rent finansiella applikationer. Man brukade skämta om att nästa finanskris, skulle vara orsakat av en bug i något Perl program.

Under årens lopp har jag skrivit många Perl program av varierande storlek och syfte. Till exempel implementerade och driftsatte jag en av Sveriges första internet-bokhandlar, våren 1995. Många år senare konsultade jag för en av våra affärsbanker avseende ett stort Perl system för kreditkortshantering. Har också byggt en hel del monitoreringslösningar för företag och myndigheter, där Perl var en vital komponent.

Python började utvecklas under första halvan av 1990-talet av Guido van Rossum. Även om det inte har explicit kommunicerats, så kan man tydligt se att Python var tänkt som en utmanare till Perl och utgör i många stycken dess anti-tes. Man kan ana att Guido måste ha avskytt Perl. 😉

Varför då, undrar du kanske? Jo, devisen för Perl är att det finns alltid ytterligare ett sätt att lösa det aktuella problemet på. Medan i Python är det tvärtom, det finns i regel ett kanoniskt sätt att lösa ett visst problem på och man benämner det oftast som att det är pythonic.

Namnet för Python är en del av titeln Monty Python's Flying Circus, som var namnet på en brittisk serie med korta, ofta surrealistiska, humor-sketcher vilka sändes under 1970-talet. Den mest kända medlemmen i gruppen är John Cleese, känd för bl.a. Pang i bygget och otaliga komedifilmer. Guido var/är en stor beundrare av Monty Python.

Under 1970-talet var jag tonåring och Monty Python var en självklar del av kultur-konsumtionen. För ett antal år sedan implementerade jag ett ramverk för REST web services i C++, kallat Just RESTing och med en blå norsk papegoja som logotyp. Ni som kan er Monty Python kopplar... 😀 Jag länkar till dess GitHub repo sist i denna artikel.

Python

OK, först ut är versionen i Python. Signifikant för detta språk är att det använder indentering för att definiera block-strukturen. Dvs ett block utgörs av ett block-huvud, såsom en if-sats, vilken avslutas med ett kolon (:). Block-innehållet är sen indraget ett eller flera blank-tecken. Det måste vara exakt lika många blanka, annars blir det syntax-fel. Vanligtvis indenterar man tre eller fyra blanka. Det är möjligt att använda TAB tecken, men det är som att be om trubbel, eftersom en TAB och BLANK är två helt olika ASCII tecken.

Programmet börjar med att ta in namnet på datafilen från kommando-raden och öppnar denna med den fiffiga with-satsen. Filen öppnas och knyts till en variabel (f) och när blocket är till ända, så stängs filen automatiskt.

with open(filename, encoding='utf-8') as f:
    ...do something with f...

Den här mekanismen lånar drag av C++ RAII, som är ett vanligt idiom där destruktorn automatiskt städar undan en resurs, så som stänger en fil eller återlämnar ett minnesblock.

struct Resource {
   Resource(Params p) {...allocate...}
   ~Resource() {...deallocate...}
   ...
};
void do_something() {
  auto r = Resource{...};
  ...
} //dispose r here

Liknande har vi Java med try-closable satsen, där ett objekt vars klass har en close() metod anropas i slutet.

var f = Files.newBufferedReader(filename);
try (f) {
    ...read from file...
} //close f here

Python har ett elegant inbyggt sätt att läsa radvis, med sin for-loop. För varje inläst rad, strippas NEWLINE bort och splittras runt semi-kolon. Resultatet tilldelas var sin variabel via destructuring.

for line in file:
    station, temperature = line.strip().split(';')

Destructuring är populärt och finns i många programspråk numera, såsom JavaScript och Perl. Men det finns också i C++, vilket är otippat eftersom språket började utvecklas 1979.

struct Record {
  std::string  name;
  double       temperature;
};

auto parse(std::string const& line) -> Record;

void do_something() {
    auto csv = ...get it...
    auto [name, temp] = parse(csv);
    ...
}

Temperaturerna aggregeras i en hash-tabell (data), som i Python kallas för dictionary. Om det redan finns ett entry för stationsnamnet, så uppdateras detta annars så skapas ett nytt.

next  = {'count': 1, 'sum': temperature, 'min': temperature, 'max': temperature}
entry = data.get(station)
if entry:
    next['count'] = 1 + entry['count']
    next['sum']   = temperature + entry['sum']
    next['min']   = min(temperature, entry['min'])
    next['max']   = max(temperature, entry['max'])
data[station] = next

Sista delen är att skriva ut den aggregerade information, sorterad på stationsnamnen. Här görs en datatyps-transformation; från dict till list, sortera, och sen från list till dict.

for entry in dict(sorted(data.items())).items():

Det är lite kul med detta, eftersom det här sättet att byta fram och åter av datatyper, kallas för att göra en Schwartzian transform. Det är uppkallat efter Perl-gurun Randal Schwartz, som demonstrerade idiomet först. Jag länkar längst ned till en Wikipedia-artikel, där du kan läsa mera.

Här är programmet i sin helhet. Själva körningen gör jag efter att beskrivit Perl programmet, vilket kommer härnäst.

import time, sys

start_time = time.time()
filename   = '../../data/weather-data-100K.csv'
if len(sys.argv) > 1:
    filename = sys.argv[1]
print('filename:', filename, '\n----')

data = {}
with open(filename, encoding='utf-8') as file:
    for line in file:
        station, temperature = line.strip().split(';')
        temperature = float(temperature)
        next  = {'count': 1, 'sum': temperature, 'min': temperature, 'max': temperature}
        entry = data.get(station)
        if entry:
            next['count'] = 1 + entry['count']
            next['sum']   = temperature + entry['sum']
            next['min']   = min(temperature, entry['min'])
            next['max']   = max(temperature, entry['max'])
        data[station] = next

for entry in dict(sorted(data.items())).items():
    station, a = entry
    print('{}: {:+.1f} C, {:+.1f}/{:+.1f} ({})'.format(
        station, a['sum'] / a['count'], a['min'], a['max'], a['count']))

print('------')
end_time     = time.time()
elapsed_time = end_time - start_time
print('[python] elapsed {:.2f} seconds, {}'.format(elapsed_time, filename), file=sys.stderr)

Perl

Perl och Python har en hel del likheter, ungefär som AIK och Djurgården 😉. Båda är dynamiskt typade, dvs en variabel kan referera vad som helst. De har ungefär samma uppsättning datatyps-kategorier, i form av skalära respektive sammansatta datatyper.

Den primära skalära datatypen i Perl är text, även om dess VM gör ett bra jobb att differentiera mellan text och tal. I Python så görs det en klar skillnad mellan text, heltal och flyttal. Det finns speciella funktioner för datatyps-konverteringar, vilket inte är fallet i Perl.

Perl har två primära sammansatta datatyper, nämligen array och hash. Den första kallas i andra språk för lista och den andra för tabell, hash-tabell, map, eller som i Python dictionary. Perl är en aningen mer typad är Python, genom att variabler har ett kategori-prefix.

En skalär variabel inleds med dollar ($), en array med snabel-a (@) och en hash med procent (%). I exemplet nedan ser vi

$filename - scalar
@ARGV - array
%data - hash

Perl och Python delar den egenskapen att man kan skapa en variabel, genom att börja använda den. Emellertid, kan man också deklarera en scoped/local variabel genom my-satsen. Det sistnämnda är definitivt att föredra, vilket jag gör i min kod nedan.

Både Perl och Python har syntax för en villkorlig sats. Detta innebär att man skriver en sats, som exempelvis en tilldelning eller print-sats och sen villkorar denna med ett test-suffix. I kodensnutten nedan tar vi filnamnet, bara om det finns ett dylikt på kommandoraden. Perl har både if och unless, medan Python bara har if. Unless uttolkas som negationen av if. På svenska typ; såvida inte.

$filename = $ARGV[0] if (@ARGV);

Ett typiskt Perl idiom är open-or-die, som vi ser nedan. Det innebär att antingen gick det bra att öppna filen, eller också bryter vi programmet med en felutskrift. Här ser vi också en detalj i syntaxen att det inte behövs parenteser runt argumenten till ett funktionsanrop. Något som fanns tidigare i Python, men togs bort i och med version 3, till förtret för många när det begav sig.

open my $file, '<', $filename or die "cannot open $filename: $!";

Att läsa radvis i Perl görs med en syntax som kanske inte är fullständigt kristallklar. Uttrycket <$file> läser nästa rad från filen ifråga och detta tilldelar vi till en loop-lokal variabel. Eftersom raden, precis som i Python, innehåller radslut (NEWLINE), så kapar vi bort denna med funktionen chomp.

while (my $line = <$file>) {
    chomp $line;
    ...

Även Perl har möjlighet till destructuring, vilket vi utnyttjar när vi splittrar en inläst rad.

my ($station, $temperature) = split ';', $line;

Efter detta, uppdaterar vi vår aggregerade datastruktur och Perl sköter diskret om att skapa eventuella nya data-element.

$data{$station}{count}++;
$data{$station}{sum} += $temperature;
...

Till sist, skriver vi ut resultatet, genom att begära ut alla stationsnamn, sortera dessa och sen plocka ut den data vi är intresserad av.

foreach my $station (sort keys %data) {
    my $cnt = $data{$station}{count};
    my $avg = $data{$station}{sum} / $cnt;
    ...
    printf "%s: %.1f, %.1f/%.1f (%d)\n", $station, $avg, $min, $max, $cnt;
}

Här kommer Perl programmet i sin helhet.

use strict;
use warnings;
use Time::HiRes qw(gettimeofday tv_interval);

my $start_time = [ gettimeofday ];
my $filename   = '../../data/weather-data-100K.csv';
$filename      = $ARGV[0] if (@ARGV);
print "filename: $filename\n----\n";

my %data;
open my $file, '<', $filename or die "cannot open $filename: $!";
while (my $line = <$file>) {
    chomp $line;
    my ($station, $temperature) = split ';', $line;

    $data{$station}{count}++;
    $data{$station}{sum} += $temperature;
    if (!defined $data{$station}{min} || $temperature < $data{$station}{min}) {
        $data{$station}{min} = $temperature;
    }
    if (!defined $data{$station}{max} || $temperature > $data{$station}{max}) {
        $data{$station}{max} = $temperature;
    }
}
close $file;

foreach my $station (sort keys %data) {
    my $cnt = $data{$station}{count};
    my $avg = $data{$station}{sum} / $cnt;
    my $min = $data{$station}{min};
    my $max = $data{$station}{max};
    printf "%s: %.1f, %.1f/%.1f (%d)\n", $station, $avg, $min, $max, $cnt;
}

print '----\n';
my $end_time     = [ gettimeofday ];
my $elapsed_time = tv_interval($start_time, $end_time);
print STDERR "[perl] elapsed $elapsed_time seconds, $filename\n";

Exekvering

Båda programmen skriver ut förfluten tid på stderr, medan resten av utskrifterna går till stdout. Det medger att jag kan skicka det sistnämnda till /dev/null, så bara det förstnämnda syns som utskrift.

$ python3 --version
Python 3.11.6
$ python3 calculate-average.py ../../data/weather-data-1M.csv > /dev/null
[python] elapsed 1.69 seconds, ../../data/weather-data-1M.csv
$ 
$ perl --version
This is perl 5, version 36, subversion 0 (v5.36.0) built for x86_64-linux-gnu-thread-multi
$ perl calculate-average.pl ../../data/weather-data-1M.csv > /dev/null
[perl] elapsed 1.872438 seconds, ../../data/weather-data-1M.csv

Varje körning upprepas några gånger och jag redovisar den kortaste tiden i tabellen nedan.

Rows	Python [secs]	Perl [secs]
100.000	0.18	0.16
1.000.000	1.61	1.34
10.000.000	22.68	13.61
100.000.000	229.48	191.34

Vi har en klar vinnare, och det är Perl 🏆. I samtliga fall, är Perl klart snabbare än Python.