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

BG Development · За реклама · За контакти

Помощ

Търсене

Потребители

Календар

Правила

Здравей! ( Включване | Регистриране )

BG Development Форуми -> Програмиране -> Други

Rust: оптимиране на функция без излишни алокации

Абонирай се за темата | Изпрати адреса на темата на приятел | Принтирай темата

FidelDahan

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

Име:
Група: Потребител
Ранг: Почетен член

Мнения: 2429
Регистриран на: 12.06.08

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

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

Име:
Група: Потребител
Ранг: Почетен член

Мнения: 2429
Регистриран на: 12.06.08

Открих грешките, явно байтовете трябва се преобразуват допълнително като шестнадесеттичен стринг. И буфера е 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

Име:
Група: Потребител
Ранг: Редовен член

Мнения: 359
Регистриран на: 18.04.21

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

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

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] // моята

Това мнение е било редактирано от Bender++ на 28-12-2021, 22:41

--------------------

Ваксините са лъжа и НЕ работят! Не на ковид фашизма!
Слава на Цар Путин! Долу украинските фашисти!
Слава на героите - Z V

FidelDahan	Публикувано на: 29-12-2021, 15:15
Име: Група: Потребител Ранг: Почетен член Мнения: 2429 Регистриран на: 12.06.08	Благодаря много Bender И аз предполагах, че превръщането във hex алоцира нещо. Ще експериментирам с твоя код довечера

SuN	Публикувано на: 29-12-2021, 23:41
Име: Група: Администратор Ранг: Почетен член Мнения: 12323 Регистриран на: 27.01.05	Ако от името на функцията не става ясно, че прави мизерии зад гърба ти, то или използваш грешната абстракция (езика в случая) или решаваш грешния проблем. И понеже съм минал примерите от официалната книжка, чувствам се достатъчно уверен да изкажа това мнение. Това мнение е било редактирано от SuN на 29-12-2021, 23:42 -------------------- Само аз не троля. Всички коментари са плод на художествена измислица и нямат общо с действителни и недействителни лица, събития и факти.

Bender++

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

Име:
Група: Потребител
Ранг: Редовен член

Мнения: 359
Регистриран на: 18.04.21

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

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

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

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

--------------------

SuN	Публикувано на: 31-12-2021, 00:31
Име: Група: Администратор Ранг: Почетен член Мнения: 12323 Регистриран на: 27.01.05	Дали е очевидно може да се спори. На пръв поглед този съкратен запис на няколко операции напомня много на джаваскрипт, само че компилиран. Даже неефикасно заделя памет. Липсва само един колекционер на боклуци. Дано в случая само за примера е сбито, а не просто да се създават уроци с такива примери. Това мнение е било редактирано от SuN на 31-12-2021, 00:32 -------------------- Само аз не троля. Всички коментари са плод на художествена измислица и нямат общо с действителни и недействителни лица, събития и факти.

0 потребители преглеждат тази тема в момента (0 гости, 0 анонимни потребители)

Потребители, преглеждащи темата в момента:

« Предишна тема | Други | Следваща тема »

BG Development Форуми -> Програмиране -> Други