1BRC - JavaScript / Node.js
Hur matchar modern JavaScript mot klassisk JavaScript, vad gäller exekveringstid för 1BRC (1 Billion Row Challenge)?
I denna artikel implementerar jag två lösningar, dels med moderna förtecken via användning av await och dels enligt
klassisk continuation-style med event-handlers. Vilken vinner, tror du?
En så kallad disruptiv uppfinning, innebär ett nytillskott till en marknad eller annan form av intressegruppering, som i grunden förändrar spelreglerna, spelplanen och vilka aktörer som blir ledande.
Man kan utan tvekan hävda att när Ryan Dahl presenterade Node.js för första gången år 2009, så var det innovativt men också disruptivt. Jag länkar till hans presentation den 8 november 2009, här nedan. Den är väl värd att se, än idag.
Fram till denna tidpunkt var JavaScript ett språk man programmerade i av ren nödvändighet, men begränsade sig i den utsträckning det var möjligt. Många ansåg (undertecknad inkluderad) att JavaScript inte var att betrakta som ett riktigt programspråk.
Ryan hade från andra källor spanat in hur vitalt det var att implementera storskalig in- och ut- hantering via asynkron och icke-suspenderande operationer (asynchronous and non-blocking I/O). Av det skälet, letade han efter ett enkel-trådat (single-threaded) språk som gick att bygga ut. JavaScript var perfekt i denna roll.
Starkt förenklat, består JavaScripts VM av två centrala komponenter. Dels en execution stack, som fungerar på liknande sätt som i andra stack-baserade språk. Dvs varje anropad funktion beskrivs med en stack-post, som har plats för lokala variabler, argument samt återhopps information. När en funktion anropas läggs en stack-post överst på stacken och när anropet är klart tas posten bort. När stacken blir tom slutar programmet.
Dels, en call-back queue. Till varje händelse (event) såsom tangentbordsklick, musrörelse, eller HTTP anrop med flera, går det att knyta en funktion (call-back). När en (knuten) händelse uppstår läggs att anrop sist i kön. Först när stacken är tom, hämtas nästa funktion (event call-back) från kön och exekveras. Först när kön är tom avslutas programmet.
Eftersom JavaScript var skapat enbart för att exekvera i en webbläsare, krävdes en stor anpassning för att hantera vanligt förekommande uppgifter för ett program som exekverar på en server (eller laptop), såsom hantering av filer, processer, signaler med mera. Resultatet blev en smart kombination av tre separata beståndsdelar.
- Google V8 JavaScript Engine
- C biblioteket libuv för avancerad händelse hantering (event loop)
- Linux system-anrop (egentligen POSIX)
Kopplingen till systemanropen, kan man fortfarande se i dokumentationen, för till exempel open() respektive
stat(). Två systemanrop i Linux, som är mer eller mindre direkt replikerade i Node.js Core API.
OK, vad hände sen då? Ett system för att söka, hantera och installera Node.js program från en central plats, skapades av Isaac Z. Schlueter ett år senare och lade grunden för att snabbt sprida bibliotek och program. Han skapade NPM (Node Package Manager). I början brukade han hävda att NPM stod för Npm is not a Package Manager. Plankat från GNU, som ju står för Gnu is Not Unix.
Plötsligt såg världen en stor mängd program, bibliotek och ramverk som var visslande snabba, vilket givetvis lockade till sig fler intressenter och det blev, vad som brukar kallas, en snöbollseffekt.
Snabbspolar vi drygt tio år senare, så har verktyg och metodik för utveckling av webbapplikationer i grunden fullständigt förändrats; och det helt till det bättre.
Populariteten för språket JavaScript har också ändrats, eftersom många nya programmerare kom in och började efterfråga funktionalitet som fanns i andra språk. Idag, så utgör Modern JavaScript (eller ECMAScript (ES) som det formellt heter) ett mycket angenämt språk att programmera i.
Mycket av just den utvecklingen har vi sett under de senaste fem, sex åren, med start i ES2015 och en ny specifikation/version varje år. Vi har fått lambdauttryck, destrukturering av sammansatta data, array streams, promises, async functions och mycket mer.
Google har varit snabba med att följa nya specifikationer och implementerat dessa i V8 för att göra dessa tillgängliga i webbläsaren Chrome. Eftersom även Node.js använder V8, så har man kunnat hålla sig uppdaterad med ES utveckling på såväl server-sidan som klient-sidan.
Modern JavaScript - await
Begreppet async funktioner kom i ES2017 och fick omgående genomslag bland JS utvecklare. Skälet är att det förenklade
implementation av asynkron kod kolossalt. Vilket är poängen med denna artikel.
Inledningsvis, behövde man först deklarera en funktion som async. I denna funktion kunde man sen anropa andra
funktioner, vilka returnerade en så kallas promise, genom att placera nyckelordet await framför.
async function do_something_clever() {
... await promise_returning_function() ...
}Helt magiskt väntande programmet där, tills ett resultat fanns tillgängligt. Rent tekniskt så utgör en async funktion en så kallad co-routine och varje anrop till await utgörs av en så kallad suspension-point. I senare versioner av JS/ES relaxerades kravet på att omgärda await med ett async block, utan det gick att använda await direkt. Vilket också är fallet i koden nedan.
Om du följt denna artikel-serie, så börjar du känna igen i de olika stegen. Öppna filen, läs rad för rad, splittra raden på semi-kolon, aggregera temperatur kopplat till stationsnamn, samt skriv ut resultatet sorterat på stationsnamnen. Koden nedan är skriven i modern JavaScript och är också enkel att följa.
import {createReadStream} from 'node:fs';
import * as readline from 'node:readline/promises';
const start_time = process.hrtime();
const data = new Map();
const filename = process.argv[2] || '../../../data/weather-data-1M.csv';
console.log('filename: %s\n----', filename);
const fileStream = createReadStream(filename);
const rl = readline.createInterface({
input: fileStream,
crlfDelay: Infinity,
});
for await (const line of rl) {
let [name, temp] = line.split(';');
temp = parseFloat(temp);
const next = {count: 1, sum: temp, min: temp, max: temp};
const a = data.get(name);
if (!!a) {
next.count = 1 + a.count;
next.sum += a.sum;
next.min = Math.min(temp, a.min);
next.max = Math.max(temp, a.max);
}
data.set(name, next);
}
const sortable = [...data.entries()];
sortable.sort((a, b) => a[0].localeCompare(b[0]))
sortable.forEach(([name, aggr]) => {
console.log('%s: %f C, %f/%f (%d)', name,
(aggr.sum / aggr.count).toFixed(1),
(aggr.min).toFixed(1),
(aggr.max).toFixed(1),
aggr.count)
})
console.log('----')
const [secs, nano] = process.hrtime(start_time);
const elapsed = (secs + nano * 1E-9).toFixed(3)
process.stderr.write('[js await] elapsed ' + elapsed + ' seconds, ' + filename + '\n')Classic JavaScript - event
Här skulle vi ha kunnat stanna. Men det finns en sida till av detta, och det är klassisk JavaScript, eller mer exakt Classic Node.js. Det innebär att all asynkron kod fortsätter i en registrerad funktion. Vilken kallas för call-back, eftersom JSVM anropar tillbaka till den funktionen när en operation är klar. Från denna funktion kan man sen starta en ny asynkron operation med en ny call-back, och ännu nästlad funktion, med mera. Ett annat ord för detta är continuation. Dvs var koden fortsätter.
I version 2 av lösningen nedan, registrerar vi händelselyssnare (event call-backs) för händelsen att det
har lästs in en textrad (line), samt händelsen att filen är klar, dvs stängs (close). I den förstnämnda
sker temperatur aggregeringen. I den sistnämnda sker sortering och utskrift. Koden inuti respektive call-back
är identiskt med motsvarande kod i version 1.
import {createReadStream} from 'node:fs';
import * as readline from 'node:readline/promises';
const start_time = process.hrtime();
const data = new Map();
const filename = process.argv[2] || '../../../data/weather-data-1M.csv';
console.log('filename: %s\n----', filename);
const fileStream = createReadStream(filename);
const rl = readline.createInterface({
input: fileStream,
crlfDelay: Infinity,
});
rl.on('line', line => {
let [name, temp] = line.split(';');
temp = parseFloat(temp);
const next = {count: 1, sum: temp, min: temp, max: temp};
const a = data.get(name);
if (!!a) {
next.count = 1 + a.count;
next.sum += a.sum;
next.min = Math.min(temp, a.min);
next.max = Math.max(temp, a.max);
}
data.set(name, next);
});
rl.on('close', () => {
let sortable = [...data.entries()];
sortable.sort((a, b) => a[0].localeCompare(b[0]))
sortable.forEach(([name, aggr]) => {
console.log('%s: %f C, %f/%f (%d)', name,
(aggr.sum / aggr.count).toFixed(1),
(aggr.min).toFixed(1),
(aggr.max).toFixed(1),
aggr.count)
})
console.log('----')
const [secs, nano] = process.hrtime(start_time);
const elapsed = (secs + nano * 1E-9).toFixed(3)
process.stderr.write('[js await] elapsed ' + elapsed + ' seconds, ' + filename + '\n')
});
rl.on('error', err => {
console.error('ooops:', err);
});Exekvering
Ok, är det då någon skillnad i exekveringstid mellan de två lösningsversionerna? Låt oss kika efter. Jag kör programmen på liknande sätt som tidigare.
$ node --version
v18.13.0
$ node calculate-average-await.js ../../../data/weather-data-100K.csv > /dev/null
[js await] elapsed 0.217 seconds, ../../../data/weather-data-100K.csv
$ node calculate-average-events.js ../../../data/weather-data-100K.csv > /dev/null
[js await] elapsed 0.139 seconds, ../../../data/weather-data-100K.csvTabell nedan visar tiden för respektive version och antalet textrader. Här framgår tydligt att den klassiska versionen (Events) är snabbare. Exekveringstiden ligger i intervallet 2/3 till 3/4 av motsvarande tid för den moderna versionen (Await).
| # | Rows | Await | Events | Events/Await [%] |
|---|---|---|---|---|
| 1 | 100.000 | 0.22 | 0.14 | 64 |
| 2 | 1.000.000 | 1.29 | 0.89 | 69 |
| 3 | 10.000.000 | 12.34 | 8.48 | 69 |
| 4 | 100.000.000 | 140.77 | 106.78 | 76 |