BG Development Форуми [Powered by Invision Power Board]

Версия, подходяща за принтиране
Кликни тук, за да видиш темата в оригиналният и вид

BG Development Форуми > Други > Rust: оптимиране на функция без излишни алокации

Публикувано от: FidelDahan 28-12-2021, 16:37

Хей хо :-) започнах да уча Rust и се опитвам да направя функция която приема стринг и го хешира многократно чрез SHA-1. Ползвам struct Sha1 от библиотеката https://docs.rs/rust-crypto/0.2.36/crypto/sha1/index.html който имплементира trait https://docs.rs/rust-crypto/0.2.36/crypto/digest/trait.Digest.html:

main.rs:

CODE

use std::str::from_utf8;
use crypto::digest::Digest;
use crypto::sha1::Sha1;

fn sha1(input: &str) -> String {
      let mut hasher: Sha1 = Sha1::new();
      hasher.input_str(input);
      return hasher.result_str();
}

fn hash_repeatedly(input: &str, times: usize) -> String {
      assert!(times > 0);
      let mut current: String = sha1(input);
      for _ in 1..times {
            current = sha1(current.as_str());
      }
      return current;
}

fn main() {
      const INPUT: &'static str = "hello world";
      let hash2r: String = hash_repeatedly(INPUT, 1000);
      println!("hash2r={}", hash2r);

}

Може ли hash_repeatedly() да се пренапише по по-ефективен начин, така че да не се получава излишно алоциране на памет? Примерно това в момента се случва 1000 пъти вътре във sha1():

let mut hasher: Sha1 = Sha1::new();

Опитах да го пренапиша използвайки функции в Sha1, които раотят с байтове вместо стрингове и reset()-ване на Sha1 за всеки междинен хеш вместо алоциране на нов Sha1:

CODE

fn hash_optimized(input: &str, times: usize) -> String {
      assert!(times > 0);

      let mut hasher: Sha1 = Sha1::new();
      let buffer: &mut [u8] = &mut [0; 40];

      hasher.input(input.as_bytes());
      hasher.result(buffer);
      hasher.reset();

      for _ in 1..times {
            hasher.input(buffer);
            hasher.result(buffer);
            hasher.reset();
      }

      return from_utf8(buffer).expect("Error: UTF").to_string();
}

Но дава грешка когато се опитам да го превърна накрая байтовете обратно в стринг:

CODE

thread 'main' panicked at 'Error: UTF: Utf8Error { valid_up_to: 0, error_len: Some(1) }'

Искам максимално да го оптимирам, защото после в експеримента тази функция ще се изпълнява за милиарди входни данни. Някакви идеи?

ПП: в случай че някой иска да го пробва, това е cargo.toml:

CODE

[package]
name = "myhash"
version = "0.1.0"
edition = "2021"

[dependencies]
rust-crypto = "^0.2"

Публикувано от: FidelDahan 28-12-2021, 18:32

Открих грешките, явно байтовете трябва се преобразуват допълнително като шестнадесеттичен стринг. И буфера е 20 вместо 40 байта (160 бита за изхода на SHA-1).

QUOTE

fn hash_optimized(input: &str, times: usize) -> String {
assert!(times > 0);

let mut hasher: Sha1 = Sha1::new();
let mut buffer: [u8; 20] = [0; 20]; // 20 bytes capacity to accommodate the SHA-1 output, which is specified as 160 bits

hasher.input(input.as_bytes());
hasher.result(&mut buffer);
hasher.reset();

for _ in 1..times {
hasher.input(from_utf8(hex::encode(buffer).as_bytes()).expect("Error: UTF").as_ref());
hasher.result(&mut buffer);
hasher.reset();
}

return from_utf8(hex::encode(buffer).as_bytes()).expect("Error: UTF").to_string();
}

Обаче резултата е че "оптимизираната" ми функция върви 5% по-бавно

Публикувано от: Bender++ 28-12-2021, 22:36

Най-накрая още някой да подхване ръст

Проблема ти е, че

CODE

hex::encode

алокира памет. А пък

CODE

from_utf()

валидира байтаррея и пак алокира нов стринг. С минимална промяна могат да се избегнат 2те излишни алокации и валидацията и става по-бързо:

CODE

pub fn hash_optimized_2(input: &str, times: usize) -> String {
assert!(times > 0);

let mut hasher: Sha1 = Sha1::new();
let mut raw_out = [0; 20];
let mut hex_out = [0; 40];

hasher.input(input.as_bytes());
hasher.result(&mut raw_out);
hasher.reset();
as_hex(&raw_out, &mut hex_out);

for _ in 1..times {
hasher.input(&hex_out);
hasher.result(&mut raw_out);
hasher.reset();
as_hex(&raw_out, &mut hex_out);
}

return from_utf8(&hex_out).expect("Error: UTF").to_string();
}

fn as_hex(src: &[u8; 20], dst: &mut [u8; 40]) {
const HEX: [u8; 16] = [
b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7', b'8', b'9', b'a', b'b', b'c', b'd', b'e',
b'f',
];

for idx in 0..src.len() {
let hi = (src[idx] >> 4) as usize;
let lo = (src[idx] & 0x0F) as usize;

dst[idx * 2] = HEX[hi];
dst[idx * 2 + 1] = HEX[lo]
}
}

Benchmark:

CODE

use criterion::{black_box, criterion_group, criterion_main, Criterion};
use rs::{hash_optimized, hash_optimized_2, hash_repeatedly};

criterion_group!(benches, benchmark);
criterion_main!(benches);

pub fn benchmark(c: &mut Criterion) {
c.bench_function("A", |b| {
b.iter(|| black_box(hash_repeatedly(black_box("hello world"), black_box(1000))))
});

c.bench_function("B", |b| {
b.iter(|| black_box(hash_optimized(black_box("hello world"), black_box(1000))))
});

c.bench_function("C", |b| {
b.iter(|| black_box(hash_optimized_2(black_box("hello world"), black_box(1000))))
});
}

Results:

CODE

A time: [191.26 us 191.49 us 191.72 us] // оригиналната версия
B time: [228.07 us 228.34 us 228.62 us] // след "оптимизацията"
C time: [154.22 us 154.47 us 154.73 us] // моята

Публикувано от: FidelDahan 29-12-2021, 15:15

Благодаря много Bender

И аз предполагах, че превръщането във hex алоцира нещо. Ще експериментирам с твоя код довечера

Публикувано от: SuN 29-12-2021, 23:41

Ако от името на функцията не става ясно, че прави мизерии зад гърба ти, то или използваш грешната абстракция (езика в случая) или решаваш грешния проблем.

И понеже съм минал примерите от официалната книжка, чувствам се достатъчно уверен да изкажа това мнение.

Публикувано от: Bender++ 30-12-2021, 19:46

QUOTE (SuN @ 29-12-2021, 23:41)

Е то е очевидно какво прави - щом връща owned обект, в случая String, то няма как да не алокира памет

Публикувано от: SuN 31-12-2021, 00:31

Дали е очевидно може да се спори. На пръв поглед този съкратен запис на няколко операции напомня много на джаваскрипт, само че компилиран. Даже неефикасно заделя памет. Липсва само един колекционер на боклуци.

Дано в случая само за примера е сбито, а не просто да се създават уроци с такива примери.