Raph Levien este cunoscut pentru implementarea ultra-eficientă a celui mai rapid motor de randare a glifurilor, folosind un design SIMD foarte ingenios bazat pe Rust. Munca sa m-a inspirat cu adevărat când proiectam un GPU SIMD la Bestechnics în 2023. Ulterior, Ralf Levien a lucrat și la o versiune GPU a acestei randări a glifurilor.
Așadar, când am dat peste ultima sa prezentare despre „Cum a câștigat Rust: căutarea unui software performant și fiabil”, am decis să dedic o oră timp urmăririi prezentării și să captez orice informații utile.
Partea intensă (cunoscută și sub numele de zona de înec) începe în jurul minutei 55:00, cu un slide intitulat Sosul secret al ruginii: un tip mai precis.
La 56:50, Raph spune „Aici intră în joc tipul afin; vrei să modelezi (clonabilitatea) ca «există o singură instanță a acestui lucru»; iar tipul îți permite să specifici cu atenție, în semnătura funcției, cum va fi gestionată această proprietate; Și voi sări peste ultimul exemplu, dar e distractiv, nu-i așa…”
Nu pretind în niciun caz că sunt expert în Rust și recunosc că am o ușoară preferință pentru Go - așadar, întrebarea este, pot înțelege ce înseamnă cu adevărat tipul afin? Și poate fi explicat în cuvinte simple, fără a fi nevoie să mă înec într-un ocean de cunoștințe?
O altă întrebare, care este subliniată în comentariile de pe YouTube: se pare că tipul de returnare pentru ultima funcție ar trebui să fie Cow<'a, [T]> în loc de Cow<&'a [T]>. Sincer, asta mi se pare chiar mai complicat decât algoritmii cuantici. Dar poate că nu trebuie să fie așa!
Așadar, haideți să aruncăm o privire mai atentă la aceste exemple de „sos secret de tip mai precis”:
fn α(l: &[T]) → Vec<T> : alocă întotdeauna, intrarea neafectată
fn β( l: Vec<T> ) → Vec<T> : consumă intrarea și reutilizează alocarea.
fn δ(l: &mut Vec<T> ): fără alocare, doar mută vectorul de intrare
fn ω( l: &'a [T]) → Cow<'a,[T]>: ar putea aloca; se evită alocarea dacă se duplică doar la capete
Prima provocare: Medicamente generice
Link to heading
Prima problemă de verificat în șablonul generic T? Funcționează cu adevărat? Pot fi compilate aceste funcții ca atare? Să încercăm cu cea mai simplă versiune a funcției:
// fails with: error cannot find type T in this scope
fn α( l: &[T] ) -> Vec<T> { vec![] }
Evident, acest lucru nu funcționează și eșuează cu eroarea nu se poate găsi tipul T în acest domeniu. Dacă sunteți familiarizat cu C++, v-ați aștepta ca tipul T să fie declarat cu numele funcției, așadar declararea α<T> în loc de α.
// all right with the T declaration
fn α<T>( l: &[T] ) -> Vec<T> { vec![] }
Funcționează bine în felul acesta! Dar când se adaugă o implementare de bază (care se convertește doar în vec, fără a elimina duplicatele), compilatorul eșuează și spune legatura de trăsătură T: Clone nu este satisfăcută
// fails with: the trait bound `T: Clone` is not satisfied
fn α<T>( l: &[T] ) -> Vec<T> { l.to_vec() }
Din fericire, Rust are o documentație foarte bună despre generic și trăsături, iar după o citire de 10 minute, devine evident că trebuie să schimbăm α<T> către α<T: Clone> ca mijloc de exprimare a legăturii de trăsătură a tipului T.
// all right with the trait bound
fn α<T: Clone>( l: &[T] ) -> Vec<T> { l.to_vec() }
Următorul pas este implementarea unei soluții pentru eliminarea duplicatelor. Pentru aceasta, o abordare este utilizarea unui HashSet. Mai întâi, matricea este convertită într-un iterator (let iterator: std::slice::Iter<T> = l.iter();), apoi construim un set hash din acest iterator (HashSet::from_iter(iterator)), și în final convertim setul hash într-un vector set.into_iter().collect().
//Fails with: the trait bound `T: Eq` is not satisfied
use std::collections::HashSet;
fn α<T: Clone>( l: &[T] ) -> Vec<T> {
let array_iterator: std::slice::Iter<T> = l.iter();
let hash_set: HashSet<&T> = HashSet::from_iter(array_iterator);
hash_set.into_iter().collect()
}
Fără nicio surpriză, acest lucru eșuează! Și este normal, pentru că dacă ați fi petrecut cele 10 minute citind documentația Rust trăsătură, ați fi știut că HashSet necesită probabil ceva care poate „compara” elementele de tip T. Asta face trăsătura Eq - așa că, haideți să o adăugăm la legătura trăsăturii (din α<T: Clone> către α<T: Clone + Eq> ):
//Fails with: the trait bound `T: Hash` is not satisfied
use std::collections::HashSet;
fn α<T: Clone + Eq>( l: &[T] ) -> Vec<T> {
let array_iterator: std::slice::Iter<T> = l.iter();
let hash_set: HashSet<&T> = HashSet::from_iter(array_iterator);
hash_set.into_iter().collect()
}
Tot eșuează, iar motivul este că am uitat să menționăm că tipul T trebuie să poată fi convertit într-o valoare hash. Asta face trăsătura Hash. Deci, să schimbăm de la α<T: Clone + Eq> către α<T: Clone + Eq + Hash>
//Fails with: a value of type `Vec<T>` cannot be built from an iterator over elements of type `&T`
use std::collections::HashSet;
fn α<T: Clone + Eq + std::hash::Hash>( l: &[T] ) -> Vec<T> {
let array_iterator: std::slice::Iter<T> = l.iter();
let hash_set: HashSet<&T> = HashSet::from_iter(array_iterator);
hash_set.into_iter().collect()
}
Aici intervine partea interesantă a clonabilității: setul hash este o structură care conține pointeri către elementele care se aflau inițial în listă și care au fost transmise prin valoare (mai exact, matricea a fost transmisă prin pointer, iar matricea conținea elemente referențiate prin valoare). Așadar, trebuie să-i spunem setului hash să facă o copie a acelor elemente, ceea ce se poate face adăugând cloned() înainte de ultima colecție (colecția este folosită pentru a transforma iteratorul într-o colecție vectorială).
// all right!
use std::collections::HashSet;
fn α<T: Clone + Eq + std::hash::Hash>( l: &[T] ) -> Vec<T> {
let array_iterator: std::slice::Iter<T> = l.iter();
let hash_set: HashSet<&T> = HashSet::from_iter(array_iterator);
hash_set.into_iter().cloned().collect()
}
Și voila, suntem gata cu primul exemplu de funcție:
fn main() {
println!("{:?}", α(&["A","A","B","D"]));
println!("{:?}", α(&[1,1,2,4]));
}
Sincer, este atât complex, cât și necomplex. Complex pentru că compilatorul impune reguli stricte, care trebuie declarate explicit, nu derivate implicit, ceea ce îngreunează curba de învățare. Nu complex, pentru că odată ce ai petrecut „10 minute” citind documentul, ei bine, ar trebui să fie mai ușor. Poate că problema nu este că durează 10 minute să citești documentul, ci mai degrabă că durează 10 ore să înțelegi ce este scris. Este un sentiment de deja vu…
Mai am o întrebare despre clonabilitate. Am putea returna un vector care conține doar referințe la elementele transmise în matrice? La prima vedere, ar trebui doar să schimbăm Vec cătreVec<&T>` … și să gestioneze corect constrângerile de tip afin? Să încercăm:
// All right - works fine
use std::collections::HashSet;
fn α<T: Clone + Eq + std::hash::Hash>( l: &[T] ) -> Vec<&T> {
let array_iterator: std::slice::Iter<T> = l.iter();
let hash_set: HashSet<&T> = HashSet::from_iter(array_iterator);
hash_set.into_iter().collect()
}
Ei bine, asta funcționează! Și nicio plângere legată de durata de viață? Adică, nu suntem oare în cazul în care împrumutăm elementele, astfel încât durata de viață ar trebui verificată? Problema este că funcția noastră „main” este prea simplă? Deci, haideți să încercăm ceva mai complex:
// fails with expected named lifetime parameter
fn limited_lifetime() -> vec<&str> {
let l = ["A","A","B","D"];
α(&l)
}
fn main() {
let v = limited_lifetime();
println!("{:?}",v);
}
De data aceasta, eșuează: compilatorul se plânge că lipsește un parametru lifetime, așa că hai să petrecem acele 10 minute suplimentare citind documentația Rust despre Validarea referințelor cu Lifetimes. La prima vedere, trebuie doar să adăugăm ‘a ?
// fais with: mismatched types; expected `&[str]`, found `&[&str; 4]`
fn limited_lifetime<'a>() -> Vec<&'a str> { ... }
Dar nu, asta nu funcționează. Să încercăm să convertim „str imuabil” într-un „Șir” dinamic:
// fails with: cannot return value referencing local variable `l`
fn limited_lifetime<'a>() -> Vec<&'a String> {
let l = ["A".into(),"A".into(),"B".into(),"D".into()];
α(&l)
}
Ok, aceasta este de fapt eroarea la care ne așteptam - verificatorul de împrumuturi funcționează într-adevăr. Dar, așadar, cum putem spune compilatorului că dorim ca proprietatea acelor variabile alocate local să fie transferată? Pentru a realiza acest lucru, trebuie să informăm compilatorul că dorim ca matricea l să fie alocată pe heap. Și pentru aceasta, trebuie să folosim un vec în loc de matrice.
// this works
fn β<T: Clone + Eq + std::hash::Hash>( l: Vec<T> ) -> Vec<T> {
let hash_set: HashSet<_> = l.into_iter().collect();
hash_set.into_iter().collect()
}
fn limited_lifetime<'a>() -> Vec<&'a str> {
let l2 = vec!["A","B","B","D"];
β(l2)
}
fn main() {
println!("{:?}",limited_lifetime());
}
Această versiune funcționează de fapt deoarece noua funcție β preia un vector de elemente și returnează același element în loc de un pointer către acestea. Deci, elementele sunt clonate. Ce se întâmplă dacă, în schimb, dorim ca funcția β să returneze un pointer către elementele de intrare?
A treia provocare: Clonare la scriere
Link to heading
Îți amintești de „Vaca” din ultima funcție omega?
fn ω( l: &’a [T]) → Cow<&’a [T]>
„Cow” este de fapt o enumerare. Poate conține fie o referință imuabilă (împrumutată), fie o clonă mutabilă a acesteia. De exemplu:
use std::borrow::Cow;
fn trim_input(input: &str) -> Cow<str> {
if input.ends_with(' ') {
Cow::Owned(input.trim_end().to_string())
}
else Cow::Borrowed(input)
}
Deci, trebuie să scriem Cow<'a [T]> sau Cow<&'a [T]>? Ei bine, la prima vedere, deoarece intrarea este un pointer & cu o durată de viață 'a către un obiect de tip [T], ieșirea este, de asemenea, un pointer către un obiect de același tip. Diferența este că Cow<> reprezintă, de asemenea, pointer. Deci, da, înseamnă că răspunsul corect ar trebui să fie Cow<'a, [T]>.
fn ω<'a, T>( l: &'a [T]) -> Cow<'a, [T]> where [T]: ToOwned { Cow::Borrowed(l) }
Partea interesantă aici este că, în Rust, tablourile au o lungime fixă la momentul compilării. Deci, cum am putea, la momentul execuției, să alocăm un nou tablou cu o dimensiune dinamică? Ei bine, se pare că, conform acestui comentariu de supraîncărcare a stivei, nu este posibil. Poate că Ralf a vrut să folosească un vec în schimb?
fn ωx<'a, T: Clone + Eq + std::hash::Hash>( l: &'a Vec<T>) -> Cow<'a, Vec<T>> {
let hash_set: HashSet<_> = l.into_iter().collect();
if hash_set.len()==l.len() {
return Cow::Borrowed(l);
}
let own_copy = hash_set.into_iter().cloned().collect();
return Cow::Owned(own_copy);
}
Sincer, trebuie să recunosc că m-am înecat în sintaxa „fn ω<‘a, T>(l: &‘a [T]) -> Cow<‘a, [T]> where [T]: ToOwned { Cow::Borrowed(l) }”, care ar trebui să însemne pur și simplu „o clonă a aceluiași cuvânt”.
Dacă considerăm că &'a T poate fi rescris ca Ptr<'a,T>, atunci putem rescrie funcția și ca:
fn ω<'a, T>( l: Ptr<'a, [T]>) -> Cow<'a, [T]> where [T]: ToOwned { Cow::Borrowed(l) }
Dacă omitem faptul că T este un array, codul de mai sus poate fi rescris ca
fn ω<'a, T: ToOwned>( l: Ptr<'a, T>) -> Cow<'a, T> { Cow::Borrowed(l) }
Atunci ce zici de rescrierea tipului ca o expresie bazată pe macro, mai degrabă decât ca o sintaxă?
fn ω<'a, T>( l: Ptr<'a, T> ) -> !Cow(l) { Cow::Borrowed(l) }
Permițând rescrierea, macrocomanda !Cow(l) poate implicita faptul că tipul T trebuie legat de trăsătura ToOwned. Gândind în acest fel, am putea anticipa că ``așiTsunt tipuri generice care nu trebuie specificate explicit atunci când se utilizează trăsăturaPtr`.
fn ω( l: Ptr ) -> !Cow(l) { Cow::Borrowed(l) }
Ce este derutant atunci faptul că specificăm atât tipul la momentul compilării, cât și implementarea la momentul execuției fără nicio distincție. Dar poate despre asta este vorba, de fapt, despre rust?
Cred că „ingredientul secret” al lui Ralf este ceva ce ar putea dura o oră pentru a fi explicat și care ar putea avea propriul set de slide-uri - nu doar 3 minute într-o prezentare de o oră. Ar merita, de asemenea, să avem o perspectivă critică asupra lui; poate că nu este totul atât de plăcut în el? Poate că există un pic de inginerie excesivă care deconectează destui dezvoltatori? Și poate că asta se înțelege prin „distracție”? În fine, voi încerca să lucrez la câteva slide-uri pentru o prezentare de o oră în următoarele săptămâni.
Revenind la provocarea calculului cuantic - întrebarea este dacă avem nevoie de un nivel similar de complexitate pentru ca sistemele de calcul cuantic să funcționeze? Poate aceasta este provocarea actuală? Deși aparent complecși, algoritmii cuantici sunt destul de simpli în comparație cu această sintaxă barbară. Poate că trebuie să gândim cu un pas înainte pentru a rezolva provocarea „utilității” calculului cuantic? Și că, fără această complexitate suplimentară, vom putea totuși să facem doar calcule de bază?
Presupunând că totul se rezumă la semantica obiectelor pe care vrem să le manipulăm, poate că trebuie să ne dăm seama că există un nivel de abstractizare logică deasupra qubiților, ceea ce nu este încă evident, deoarece industria încă se luptă să facă qubiții să se comporte corect.