ABONAMENTE VIDEO REDACȚIA
RO
EN
NOU
Numărul 143
Numărul 142 Numărul 141 Numărul 140 Numărul 139 Numărul 138 Numărul 137 Numărul 136 Numărul 135 Numărul 134 Numărul 133 Numărul 132 Numărul 131 Numărul 130 Numărul 129 Numărul 128 Numărul 127 Numărul 126 Numărul 125 Numărul 124 Numărul 123 Numărul 122 Numărul 121 Numărul 120 Numărul 119 Numărul 118 Numărul 117 Numărul 116 Numărul 115 Numărul 114 Numărul 113 Numărul 112 Numărul 111 Numărul 110 Numărul 109 Numărul 108 Numărul 107 Numărul 106 Numărul 105 Numărul 104 Numărul 103 Numărul 102 Numărul 101 Numărul 100 Numărul 99 Numărul 98 Numărul 97 Numărul 96 Numărul 95 Numărul 94 Numărul 93 Numărul 92 Numărul 91 Numărul 90 Numărul 89 Numărul 88 Numărul 87 Numărul 86 Numărul 85 Numărul 84 Numărul 83 Numărul 82 Numărul 81 Numărul 80 Numărul 79 Numărul 78 Numărul 77 Numărul 76 Numărul 75 Numărul 74 Numărul 73 Numărul 72 Numărul 71 Numărul 70 Numărul 69 Numărul 68 Numărul 67 Numărul 66 Numărul 65 Numărul 64 Numărul 63 Numărul 62 Numărul 61 Numărul 60 Numărul 59 Numărul 58 Numărul 57 Numărul 56 Numărul 55 Numărul 54 Numărul 53 Numărul 52 Numărul 51 Numărul 50 Numărul 49 Numărul 48 Numărul 47 Numărul 46 Numărul 45 Numărul 44 Numărul 43 Numărul 42 Numărul 41 Numărul 40 Numărul 39 Numărul 38 Numărul 37 Numărul 36 Numărul 35 Numărul 34 Numărul 33 Numărul 32 Numărul 31 Numărul 30 Numărul 29 Numărul 28 Numărul 27 Numărul 26 Numărul 25 Numărul 24 Numărul 23 Numărul 22 Numărul 21 Numărul 20 Numărul 19 Numărul 18 Numărul 17 Numărul 16 Numărul 15 Numărul 14 Numărul 13 Numărul 12 Numărul 11 Numărul 10 Numărul 9 Numărul 8 Numărul 7 Numărul 6 Numărul 5 Numărul 4 Numărul 3 Numărul 2 Numărul 1
×
▼ LISTĂ EDIȚII ▼
Numărul 140
Abonament PDF

Rust și coniac (I)

Romulus Pașca
Software Developer & Trainer @ Haqr Studio



PROGRAMARE

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.

Provocarea

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.8

Se 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...

Ștacheta

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 s

Poate 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... ."

La lucru

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ă:

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.

Conferință

NUMĂRUL 142 - Robotics & AI

Sponsori

  • Accenture
  • BT Code Crafters
  • Accesa
  • Bosch
  • Betfair
  • MHP
  • BoatyardX
  • .msg systems
  • Yardi
  • P3 group
  • Ing Hubs
  • Colors in projects

INTERVIURI VIDEO

Romulus Pașca a mai scris