O seară blândă de februarie, ora 18:13. Soarele se retrage discret după coama muntelui. Spot se delectează cu resturile unui păstrăv prăjit la proțap. În șapte ore 49ers și Chiefs joacă în Super Bowl. Lichidul de culoarea apusului strălucește în pahar. Timpul se dilată, nepăsător la umbrele care încep să ia contur.
Aud un mieunat subțire: "Ai promis..." Bat speriat în retragere, dar între mine și ușă se interpune un monstru cu blană neagră. Grivei mârâie: "Ar fi vremea, nu crezi? Avem timp destul până la meciul ăla plictisitor." Replic tăios: "Challenge-ul s-a terminat pe 31 ianuarie și, în plus, nu mă mai ocup cu așa ceva de multă vreme."
Grivei e de neclintit - la propriu și la figurat, nu de alta dar iarna asta a ajuns la nord de 100kg. Încerc să-i explic conceptul de Super Bowl party, dar nu pare interesat. Ca să ajung la sticla de coniac trebuie să negociez... La 18:19 ajungem la un acord: voi folosi rust nu java, am voie să folosesc biblioteci externe, nu voi scrie SIMD direct, voi evita pe cât posibil unsafe, vom testa local nu în cloud.
Pe 1 ianuarie 2024 Gunnar Morling a lansat o provocare numită 1brc - The one billion row challenge. Nu intenționam să mă leg la cap cu astfel de jocuri, dar la Bobotează, după un pahar de zmeurată, am spus că...
Problema e simplă: se dă un fișier text (cu un miliard de linii) ce conține temperaturi pentru un set de stații meteo, cu fiecare linie de forma nume_stație;temperatură. Stația este un string UTF de maxim 100 de octeți, iar temperatura este un număr cu exact o cifră zecimală, cuprins între -99.9 și 99.9 Exemplu:
Brisbane;24.0
San Antonio;19.3
Milwaukee;33.7
Baku;-4.0
Chișinău;10.8Se cere un program java cât mai rapid, care citește fișierul, calculează pentru fiecare stație valoarea minimă, medie și maximă a temperaturii și apoi tipărește rezultatele sortate alfabetic. Nu voi respecta regulile ad-literam, dar vreau să văd ce efort îți trebuie să scoți o performanță decentă în rust.
După aproape opt ani de HFT am o idee despre ceea ce înseamnă viteza în software, deci nu îmi fac iluzii de mărire. Când vorbim de performanță, clasicul You can write Fortran în any language devine You can write C în any language. Promit că nu voi scrie C în rust ok, poate un pic...
Mașina mea de zi cu zi (4 cpu cores, 2 threads per core, 32 GB RAM) va fi utilizată pentru benchmarking. Pentru măsurări cât mai precise voi utiliza hyperfine, iar pentru evaluări rapide comanda timeit din nushell.
Spot a făcut deja download la programul care generează fișierul pentru test, soluția de referință și soluția câștigătoare. Fișierul de intrare e uriaș are 13GB. Soluția de referință rulează în 3min 33sec 431ms 557µs 891ns. Grivei zâmbește: "Nimic spectaculos aici, probabil că pot scrie ceva mai rapid în awk."
Din păcate, entuziasmul nostru dispare mai repede decât jumările din farfuria lui Grivei. Programul câștigător java, copilul virtual al câtorva minți iscusite de pe mapamond, e mai rapid decât Verstapen la Monza:
Time (mean ± σ): 2.748 s ± 0.053 s
Range (min … max): 2.679 s … 2.852 s"Au folosit unsafe și graalVM", oftez trist, sperând să scap din încurcătură. Grivei se uită la mine cu milă: "Situația e albastră, vom avea serios de lucru." Facem o căutare online...
Olandezul Ragnar Groot Koerkamp vine cu un program rust, care mă face să mă gândesc că poate e vremea să aplic pentru social security. Din fericire, soluția lui(probabil cea mai rapidă) nu se compilează pe mașina mea (versiunea mea de rust nightly nu se potrivește cu cea cerută de program) așa că alegem ca țintă soluția rust a lui Marko Topolnik, cea mai iute care se compilează și rulează pe mașina mea.
Time (mean ± σ): 4.370 s ± 0.019 s
Range (min … max): 4.337 s … 4.408 sPoate pentru că sunt la al doilea pahar de coniac sau poate pentru că țin cu 49ers în Super Bowl, privindu-l în ochi pe Spot afirm curajos: asta pot și eu. Spot nu zice nimic, doar zâmbetul îl trădează: "Îți va părea rău... ."
Vom începe cu cea mai leneșă soluție posibilă. Andrew Gallant aka BurntSushi, unul din programatorii mei favoriți, îmi va fi de mare ajutor azi - indirect bineînțeles. Grivei e nemulțumit, dar așa ne-a fost înțelegerea. Voi folosi crate-ul creat de el să parsez fișierul de intrare. Prima noastră încercare arată cam așa:
use csv::ReaderBuilder;
use std::{collections::HashMap, env::args, error::Error};
#[derive(Debug, PartialEq)]
struct CityData {
min_tmp: f32,
max_tmp: f32,
tot_tmp: f32,
count: i64,
}
impl Default for CityData {
fn default() -> Self {
CityData {
min_tmp: 101.0,
max_tmp: -101.0,
tot_tmp: 0.0,
count: 0,
}
}
}
impl CityData {
#[inline(always)]
pub fn update(&mut self, value: f32) {
self.count += 1;
self.tot_tmp += value;
if value < self.min_tmp {
self.min_tmp = value
}
if value > self.max_tmp {
self.max_tmp = value
}
}
}
fn simple() -> Result<(), Box> {
let input = &args().nth(1).unwrap_or("measurements.txt".to_string());
println!("Using {}", &input);
let mut rdr = ReaderBuilder::new().delimiter(b';').from_path(input)?;
let mut data: HashMap =
HashMap::with_capacity_and_hasher(4096, Default::default());
for result în rdr.records() {
let record = result?;
let name = record[0].to_owned();
let value: f32 = record[1].parse().unwrap();
data.entry(name).or_default().update(value);
}
let mut sdata = data
.into_iter()
.map(|(k, v)| {
format!(
"{}={:.1}/{:.1}/{:.1}, ",
&k,
v.min_tmp,
v.tot_tmp / v.count as f32,
v.max_tmp
)
})
.collect::>();
sdata.sort_unstable();
sdata.iter().for_each(|e| println!("{}", e));
Ok(())
}
fn main() {
if let Err(err) = simple() {
println!("Error running simple program: {}", err);
}
}
Spot compilează, rulează și apoi așteptăm 2min 16sec 800ms 839µs 234ns până când rezultatul apare pe ecran. Timpul nu este de loc impresionant, dar Grivei punctează repede câteva modificări simple, care vor duce la o performanță superioară:
Înlocuim float cu întregi, fiindcă plaja de valori și precizia datelor de intrare sunt limitate;
Parsăm la nivel binar, deși vom avea puțin mai mult de lucru, fiindcă va trebui să transformăm octeții în numere întregi și caractere;
Schimbăm funcția de hashing cu una mai rapidă - tot webul sugerează cea din crate-ul rustc_hash;
unsafe, dar nu e nimic serios, fiindcă șirul de octeți conține doar valori UTF corecte.use csv::{ByteRecord, ReaderBuilder};
use rustc_hash::FxHashMap as HashMap;
use std::{env::args, error::Error};
#[derive(Debug, PartialEq)]
struct CityData {
min_tmp: i16,
max_tmp: i16,
tot_tmp: i64,
count: i64,
}
impl Default for CityData {
fn default() -> Self {
CityData {
min_tmp: 10100i16,
max_tmp: -10100i16,
tot_tmp: 0,
count: 0,
}
}
}
impl CityData {
#[inline(always)]
pub fn update(&mut self, value: i16) {
self.count += 1;
self.tot_tmp += value as i64;
self.min_tmp = self.min_tmp.min(value);
self.max_tmp = self.max_tmp.max(value);
}
}
fn improved() -> Result<(), Box> {
let input = &args().nth(1).unwrap_or("measurements.txt".to_string());
let mut rdr = ReaderBuilder::new().delimiter(b';').from_path(input)?;
println!("Using {}", &input);
let mut data: HashMap, CityData> =
HashMap::with_capacity_and_hasher(4096, Default::default());
for result in rdr.byte_records() {
let record: ByteRecord = result?;
let name = record[0].to_owned().into_boxed_slice();
let value: i16 = parse(&record[1]);
data.entry(name).or_default().update(value);
}
let mut sdata = data
.into_iter()
.map(|(k, v)| {
format!(
"{}={:.1}/{:.1}/{:.1}, ",
unsafe { std::str::from_utf8_unchecked(&k) },
v.min_tmp as f64 / 10.0,
((v.tot_tmp as f64) / (v.count as f64)).round() / 10.0,
v.max_tmp as f64 / 10.0
)
})
.collect::>();
sdata.sort_unstable();
sdata.iter().for_each(|e| println!("{}", e));
Ok(())
}
#[inline]
fn parse(mut s: &[u8]) -> i16 {
let neg = if s[0] == b'-' {
s = &s[1..];
-1
} else {
1
};
let (d2, d1, dec) = match s {
[c, b'.', d] => (0, c - b'0', d - b'0'),
[b, c, b'.', d] => (b - b'0', c - b'0', d - b'0'),
_ => panic!("Unknown number {:?}", std::str::from_utf8(s).unwrap()),
};
let v = d2 as i16 * 100 + d1 as i16 * 10 + dec as i16;
v * neg
}
fn main() {
if let Err(err) = improved() {
println!("Error running improved: {}", err);
}
}
Rezultatele nu întârzie, dar nu sunt spectaculoase: 1min 41sec 457ms 836µs 546ns. Nu vreau să recunosc că sunt în criză de idei, așa că devin foarte preocupat de paharul de coniac de pe masă.
Noroc cu Spot, care, fără șovăire, preia inițiativa. "Mai sunt multe de făcut" replică sec. Grivei se uită le el cu admirație. "Dacă mapăm fișierul în memorie, sigur vom câștiga timp". Sunt total de acord, avem încă o linie de cod unsafe, dar, din nou, este ceva tolerabil.
"Apoi, va trebui să parsăm fișierul manual" - afirmă el hotărât. "Nu are rost, Spot, nu vom câștiga mare lucru, dacă nu folosim SIMD." "Credeam că ești fan BurntShusi" îmi răspunde laconic. Grivei nu pierde vremea, adaugă la proiect biblioteca memchr scrisă de BurntSushi: It provides heavily optimized routines for string search primitives.
Golesc paharul de coniac, dintr-o înghițitură - am scăpat de codat SIMD în seara asta. Codul devine mai urât, dar mai facem un pas în direcția bună.
Spot vrea să continue, dar Grivei latră de parcă o haită de lupi s-ar fi afișat neinvitată la petrecerea noastră de Super Bowl: "Rayon, rayon". "Da, Grivei, ai dreptate, am uitat să paralelizăm întreaga operațiune".
Ideea lui Grivei îmi dă un pic de lucru, va trebui să sparg fișierul în bucăți egale și să le pasez la câte un thread pentru procesare. Codul e simplu, dar trebuie scris cu atenție. În plus, la sfârșit va trebui să comasăm rezultatele.
Spot intră pe fir: "Sunt două posibile abordări: poți sparge fișierul în multe bucăți mici sau în exact opt bucăți (numărul de threaduri disponibile în sistem). Trebuie să aflăm care este varianta mai bună." Pentru implementarea noastră rezultatele sunt aceleași cu ambele abordări. Vom merge cu varianta a doua fiindcă ne scapă de un extra-parametru - dimensiunea feliilor în care să rupem fișierul.
Modificările esențiale din cod sunt listate mai jos:
fn mempar() -> Result<(), Box> {
let input = &args().nth(1).unwrap_or("measurements.txt".to_string());
let file = File::open(input)?;
let mmap = unsafe { MmapOptions::new().map(&file)? };
let cores: usize = std::thread::available_parallelism().unwrap().into();
let chunks_count = cores;
let chunk_size = mmap[..].len() / cores;
let mut chunks: Vec<(usize, usize)> = Vec::with_capacity(chunks_count);
let mut start = 0;
for _ în 0..chunks_count {
let end = (start + chunk_size).min(mmap.len());
let next_nl = match memchr::memchr(b'\n', &mmap[end..]) {
Some(v) => v,
None => {
assert_eq!(end, mmap.len());
0
}
};
let end = end + next_nl;
chunks.push((start, end));
start = end + 1;
}
let parts: Vec<_> = chunks
.par_iter()
.map(|(from, to)| process(&mmap[*from..*to]))
.collect();
let res: HashMap<&[u8], CityData> = parts.into_iter().fold(Default::default(), |mut a, b| {
for (k, v) în b {
a.entry(k).or_default().join(&v);
}
a
});
let mut sdata = res
.par_iter()
.map(|(k, v)| {
format!(
"{}={:.1}/{:.1}/{:.1}, ",
unsafe { std::str::from_utf8_unchecked(&k) },
v.min_tmp as f64 / 10.0,
((v.tot_tmp as f64) / (v.count as f64)).round() / 10.0,
v.max_tmp as f64 / 10.0
)
})
.collect::>();
sdata.sort_unstable();
sdata.iter().for_each(|e| println!("{}", e));
Ok(())
}
fn process<'a>(data: &'a [u8]) -> HashMap<&'a [u8], CityData> {
let mut res: HashMap<&'a [u8], CityData> =
HashMap::with_capacity_and_hasher(1024, Default::default());
let mut it = memchr2_iter(b';', b'\n', data);
let mut from = 0;
loop {
match it.next() {
Some(sep) => {
let name = &data[from..sep];
let eol = it.next().unwrap_or(data.len());
let temp = parse(&data[(sep + 1)..eol]);
res.entry(name).or_default().update(temp);
from = eol + 1;
}
None => {
break;
}
}
}
res
} Rulăm cu hyperfine:
Time (mean ± σ): 7.309 s ± 0.054 s
Range (min … max): 7.257 s … 7.440 sÎn sfârșit, ceva cu care ne-am putea lăuda.
... continuarea articolului va fi publicată în următorul număr al revistei.
de Ovidiu Mățan
