BG Development


  Reply to this topicStart new topicStart Poll

> Rust: оптимиране на функция без излишни алокации
FidelDahan
Публикувано на: 28-12-2021, 16:37
Quote Post



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

Мнения: 2428
Регистриран на: 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"

PMEmail Poster
Top
FidelDahan
Публикувано на: 28-12-2021, 18:32
Quote Post



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

Мнения: 2428
Регистриран на: 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% по-бавно icon_lol.gif
PMEmail Poster
Top
Bender++
Публикувано на: 28-12-2021, 22:36
Quote Post



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

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



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

Проблема ти е, че
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


--------------------
Ваксините са лъжа и НЕ работят! Не на ковид фашизма!
PMEmail Poster
Top
FidelDahan
Публикувано на: 29-12-2021, 15:15
Quote Post



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

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



Благодаря много Bender icon_smile.gif И аз предполагах, че превръщането във hex алоцира нещо. Ще експериментирам с твоя код довечера icon_smile.gif
PMEmail Poster
Top
SuN
Публикувано на: 29-12-2021, 23:41
Quote Post


Group Icon
Име:
Група: Администратор
Ранг: Почетен член

Мнения: 12051
Регистриран на: 27.01.05



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

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

Това мнение е било редактирано от SuN на 29-12-2021, 23:42


--------------------
Само аз не троля.
Всички коментари са плод на художествена измислица и нямат общо с действителни и недействителни лица, събития и факти.
PMEmail Poster
Top
Bender++
Публикувано на: 30-12-2021, 19:46
Quote Post



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

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



QUOTE (SuN @ 29-12-2021, 23:41)
Ако от името на функцията не става ясно, че прави мизерии зад гърба ти, то или използваш грешната абстракция (езика в случая) или решаваш грешния проблем.

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

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


--------------------
Ваксините са лъжа и НЕ работят! Не на ковид фашизма!
PMEmail Poster
Top
SuN
Публикувано на: 31-12-2021, 00:31
Quote Post


Group Icon
Име:
Група: Администратор
Ранг: Почетен член

Мнения: 12051
Регистриран на: 27.01.05



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

Това мнение е било редактирано от SuN на 31-12-2021, 00:32


--------------------
Само аз не троля.
Всички коментари са плод на художествена измислица и нямат общо с действителни и недействителни лица, събития и факти.
PMEmail Poster
Top
1 потребители преглеждат тази тема в момента (1 гости, 0 анонимни потребители)
Потребители, преглеждащи темата в момента:

Topic Options Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2019 | BG Development | All Rights Reserved
RSS 2.0