ABONAMENTE VIDEO REDACȚIA
RO
EN
NOU
Numărul 147
Numărul 146 Numărul 145 Numărul 144 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 141
Abonament PDF

Rust și coniac (II)

Romulus Pașca
Software Developer & Trainer @ Haqr Studio



PROGRAMARE

Continuarea articolului. Prima parte a fost publicată ediția anterioară, nr. 140/februarie

Pe culmile disperării

Încerc să-l mituiesc pe Spot cu o farfurie de lapte, Super Bowl-ul va începe în câteva ore și vreau să visez puțin la 85 Bears. De fapt, m-aș mulțumi și cu varianta lor din 2006. "Te credeam programator serios", spune Spot lingându-se pe bot. "Chiar și cu noua funcție de hashing, dicționarul e tot încet". Mă apăr cu disperare: "Sub nici o formă nu mă apuc să scriu la ora asta mapuri. E mult prea complicat."

Spot continuă netulburat: "Nu ai nevoie de un map propriu zis. Problema noastră nu necesită ștergere de chei. Ceea ce ne trebuie e mai mult un fel de memory arena decât un map." Arenă sau tabelă de dispersie, că să scap de bestiile astea, n-am de ales, trebuie să o scriu. Grivei dă din coadă fericit: "Structurile de date sunt partea ta favorită din programare."

Visând la Devin Hester (tocmai inclus în Hall of Fame) din vremurile când Chicago avea echipă decentă de fotbal, mă apuc de lucru. Rezultatul este chiar elegant cu toate că trebuie să modific și structura CityData, noroc că parametrii de lifetime sunt ușor de mulțumit.

Capacitatea arenei trebuie să fie putere a lui doi - operația de modulo este mult mai rapidă în acest caz. În plus, îi adaug o interfață frumoasă de iterator, așa de amorul artei.

#[repr(C, align(64))]
#[derive(Debug, Default)]
struct CityData<'this> {
    name: &'this [u8],
    min_tmp: i16,
    max_tmp: i16,
    tot_tmp: i64,
    count: i64,
}

impl<'this> Display for CityData<'this> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "{}={:.1}/{:.1}/{:.1}, ",
            self.name_as_str(),
            self.min_tmp as f64 / 10.0,
            ((self.tot_tmp as f64) / (self.count as f64)).round() / 10.0,
            self.max_tmp as f64 / 10.0
        )
    }
}

impl<'this> CityData<'this> {
    #[inline(always)]
    pub fn new(name: &'this [u8], value: i16) -> Self {
        Self {
            name,
            min_tmp: value,
            max_tmp: value,
            tot_tmp: value as i64,
            count: 1,
        }
    }
    #[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);
    }
    #[inline(always)]
    fn join(&mut self, rhs: &CityData) {
        self.count += rhs.count;
        self.tot_tmp += rhs.tot_tmp;
        self.min_tmp = self.min_tmp.min(rhs.min_tmp);
        self.max_tmp = self.max_tmp.max(rhs.max_tmp);
    }
    pub fn name_as_str(&self) -> &'this str {
        unsafe { std::str::from_utf8_unchecked(self.name) }
    }
}

enum ArenaEntry<'this> {
    Vacant,
    Occupied(CityData<'this>),
}

const CAPACITY: usize = 32768;

struct CityDataArena<'this> {
    arena: Vec>,
}

impl<'this> Default for CityDataArena<'this> {
    fn default() -> Self {
        let mut arena = Vec::with_capacity(CAPACITY);
        for _ în 0..CAPACITY {
            arena.push(ArenaEntry::Vacant);
        }
        Self { arena }
    }
}

impl<'this> CityDataArena<'this> {
    #[inline(always)]
    pub fn update(&mut self, data: &'this [u8], value: i16) {
        let mut hasher = FxHasher::default();
        hasher.write(data);
        let hash = hasher.finish();

        let mut pos = (hash & ((CAPACITY - 1) as u64)) as usize;
        loop {
            let ArenaEntry::Occupied(slot) = &mut self.arena[pos] else {
                let cd = CityData::new(data, value);
                self.arena[pos] = ArenaEntry::Occupied(cd);
                break;
            };
            if slot.name == data {
                slot.update(value);
                break;
            }
            pos = (pos + 1) & (CAPACITY - 1);
        }
    }
}

impl<'this> IntoIterator for CityDataArena<'this> {
    type Item = CityData<'this>;
    type IntoIter = CityDataArenaIter<'this>;

    #[inline(always)]
    fn into_iter(self) -> Self::IntoIter {
        let iter = self.arena.into_iter();
        CityDataArenaIter { iter }
    }
}
struct CityDataArenaIter<'this> {
    iter: IntoIter>,
}

impl<'this> Iterator for CityDataArenaIter<'this> {
    type Item = CityData<'this>;

    #[inline(always)]
    fn next(&mut self) -> Option {
        loop {
            let Some(entry) = self.iter.next() else {
                return None;
            };
            match entry {
                ArenaEntry::Vacant => continue,
                ArenaEntry::Occupied(cd) => return Some(cd),
            }
        }
    }
}

Arena propusă de Spot merge șnur, mai câștigăm o secundă, dar tot suntem departe de ținta de patru secunde.

  Time (mean ± σ):      6.129 s ±  0.049 s
  Range (min … max):    6.078 s …  6.238 s

Idei periculoase

"Am terminat, nu mai vreau să aud de nici o linie de CSV". Grivei nu pare convins: "Știi că e chiar amuzant să te murdărești uneori?" "Spune-i asta lui Spot". Din păcate, sunt în minoritate din nou fiindcă Spot îl susține: "Prinsul de șoareci, crezi că e muncă de birou?"

Mai sunt câteva lucruri care le-am putea face, dar toate sunt puțin forțate.

Primul pas e simplu. Un motiv pentru care un program rust poate fi mai încet decât unul C/C++ este faptul că rust verifica aproape totdeauna accesul la elementele unui vector. Totuși, acest lucru se poate evita, daca în loc de v[i] scriem v.get_unchecked(i).

Codul arată oribil, dar mai stoarcem un pic de timp. Spot se uita la mine ciudat „De ce nu folosești get_unchecked în CityDataArena?”. Mă bucur să am și eu o dată ultimul cuvânt: "Fiindcă dimensiunea arenei este predefinită, compilatorul de rust poate să optimizeze accesul la elementele ei fără ajutor din partea noastră."

Al doilea pas e complicat. Comanda perf se plânge de eficiența cu care convertim informația despre temperatură în valori întregi. Ideal ar fi să folosim un cod cu cât mai puține instrucțiuni alternative, branchless, dacă se poate. Aparent există programatori, care au reușit asta folosind magie. (Vezi soluția java câștigătoare.) La magie pe biți, mă refer. Nu am intenția de a-i imita (deși le admir cu desăvârșire arta), voi încerca doar niște modificări la limita bunului simț. Prima din ele este să trec de la codul în stil funcțional la unul pur imperativ. A doua este să abuzez de get_unchecked:

#[inline(always)]
fn gfst(temp: &[u8], i: usize) -> u8 {
    unsafe { *temp.get_unchecked(i) }
}

#[inline]
fn parse1(temp: &[u8]) -> i16 {
    let mut i = 0;
    let sign = if gfst(temp, i) == b'-' {
        i += 1;
        -1
    } else {
        1
    };
    let mut value: i16 = (gfst(temp, i) - b'0') as i16;
    i += 1;
    if temp[i] == b'.' {
        i += 1;
    } else {
        value = 10 * value + (gfst(temp, i) - b'0') as i16;
        i += 2;
    }
    sign * (10 * value + (gfst(temp, i) - b'0') as i16)
}

#[inline]
pub fn parse2(s: &[u8]) -> i16 {
    let len = s.len();
    let sign = if gfst(s, 0) == b'-' { -1 } else { 1 };
    let b = ((len >= 4) as i16) * (gfst(s, len - 4) as i16 - (b'0' as i16));
    let c = gfst(s, len - 3) - b'0';
    let d = gfst(s, len - 1) - b'0';
    let v = b * 100 + c as i16 * 10 + d as i16;
    sign * v
}

A doua opțiune fiind mai ilizibilă este evident și mai rapidă. Mai fac o modificare inspirată din blogul lui Ragnar și codul lui Marko. Stațiile lor se pot identifica folosind doar primii și ultimii opt octeți din nume. Rescriem funcția de hashing folosind această informație.

fn hash_baby(name: &[u8]) -> u64 {
    let seed: u64 = 0x51_7c_c1_b7_27_22_0a_95;
    let rot_dist = 17;
    let len = name.len();
    let block = if len >= 8 {
        u64::from_le_bytes(name[len - 8..len].try_into().unwrap())
    } else {
        let mut buf = [0u8; 8];
        buf[..len].copy_from_slice(&name[..len]);
        u64::from_le_bytes(buf)
    };
    let mut hash = block;
    hash *= seed;
    hash = hash.rotate_left(rot_dist);
    hash
}

Ultimii pași îi fac cu strângere de inimă. Deși inteligibili, pentru a-i duce la capăt trebuie să arunc un ochi la soluțiile lui Ragnar Groot Koerkamp și Marko Topolnik. Rulăm pentru ultima oară.

  Time (mean ± σ):      5.173 s ±  0.070 s
  Range (min … max):    5.099 s …  5.351 s      

Time (mean ± σ): 5.173 s ± 0.070 s
Range (min … max): 5.099 s … 5.351 s

Grivei mârâie satisfăcut: "Ai pierdut. Te-ai lăudat degeaba". Mă apăr: "Eu cred că a fost o luptă strânsă, am fost destul de aproape..." Aștept zadarnic un cuvânt de încurajare de la Spot. Replica lui doare: A miss is as good as a mile.

Epilog

Grivei doarme liniștit pe prag. El zice că mă apară - trebuie să îl cred pe cuvânt. Spot e de mult culcușit sub un calorifer fierbinte. San Francisco 49ers au luptat cu dăruință și curaj - meciul a ajuns în prelungiri, dar până la urmă au fost orbiți de aura de invincibilitate a lui Patrick Mahomes.

Închid ochii cu Nicolae Steinhardt în gând: "Asta-i singura noastră datorie sfântă: de ne este dat să cădem, să fie-n zori."

  git add .
  git commit -m '1brc'
  git push

Codul sursă îl găsiți pe Codeberg.

Conferință TSM

NUMĂRUL 147 - Automotive

Sponsori

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

Romulus Pașca a mai scris