Ускорить цикл for


#1

И снова здраствуйте, сейчас мне нужно как можно лучше оптимизировать(ускорить?) данный код:

for (index,value) in vector.iter().enumerate() {
     if value == "1.0" {
          do_something(index);
      }
}

Сейчас я получаю такой результат по времени: 114 миллисикунд когда длинна вектора равна 14.Но размер вектора может быть в разы больше и хотелось бы узнать, как можно это все ускорить, и возможно ли это вообще?


#2

Нужен полностью код бенчмарков + параметры запуска. И параметры твоего железа не помешали бы, раз конкретное время работы указываешь.

UPD: В общем-то, это ж просто цикл с условием - без знания дополнительной информации по задче с точки зрения кода хз что тут особо улучшать.


#3

Сейчас просто использую крейт time для того что бы засечь время со старта и конца вычислений, в основном результат именно 100-120 миллисекунд.
Параметры такие:
– CPU: Intel Core i5-4460 @ 4x 3.4GHz
– GPU: GeForce GTX 760
– RAM: 8GB


#4

На всякий случай, дежурный вопрос: с --release флагом запускаешь же, да?


#5

Да с релиз и еще немного погуглил и решил LTO в релизе включить.
Задача в том что бы определить есть ли нужное value в векторе и если есть то добавить его в hashmap, точнее его индекс


#6

Руками такие мелкие вещи замерять черевато, для этого есть штуки вроде


#7

В ручном цикле тогда вряд ли смыл особый есть, можно взять https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.position, но думаю что на скорости работы оно не скажется.


#8

bencher показал результат в 117,27 миллисекунд


#9

А ты уверен что у тебя проблема в for? и как он у тебя формируется?
У меня получились следующие цифры:

for test                time:   [30.951 ns 31.011 ns 31.119 ns]                      
                        change: [-98.483% -98.448% -98.410%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 15 outliers among 100 measurements (15.00%)
  3 (3.00%) low severe
  1 (1.00%) high mild
  11 (11.00%) high severe

Меня смущает, то что ты написал:

if value == "1.0" {

Хотя тут у тебя явно должно быть:

if value == &"1.0" {

Мой вектор:

 let vector = vec![
    "1.0", "2.0", "3.0", "4.0", "5.0", "6.0", "7.0", "8.0", "9.0", "10.0", "11.0", "12.0",
    "13.0", "14.0",
];

#10

Я тестировал библиотекой criterion.rs, которую выше @ozkriff рекомендовал.

Мой код:

#[macro_use]
extern crate criterion;

use criterion::Criterion;

fn test_for() -> usize {
    let vector = vec![
        "1.0", "2.0", "3.0", "4.0", "5.0", "6.0", "7.0", "8.0", "9.0", "10.0", "11.0", "12.0",
        "13.0", "14.0",
    ];
    let mut result: usize = 0;
    for (index, value) in vector.iter().enumerate() {
        if value == &"1.0" {
            result += index;
        }
    }
    return result;
}

fn criterion_benchmark(c: &mut Criterion) {
    c.bench_function("for test", |b| b.iter(|| test_for()));
}

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

У тебя либо ошибка в тестирование, либо проблема в другом месте, но 114 ms это слишком много для массива с 14тью элементами


#11

Поэтому и задал вопрос как ускорить, сам не знаю почему так долго выполняется, да и тот код привел как пример, у меня там немного по другому, там tuple Enum матчится


#12

А что метод do_something делает? мне кажется в нем у тебя проблема. For в любом случае работать должен быстро, проблема либо в итерации(ты на каждой итерации что то сложное делаешь), либо замеры не правильно делаешь. попробуй все таки протестировать библиотекой которую выше привели. :wink:


#13

https://play.rust-lang.org/?version=stable&mode=release&edition=2015&gist=7969e36dfefc40c8366243909960be7f

там скорее всего чтото в дусомсинг


#14

Во-первых, надо выкладывать полный код бенчей.
Во-вторых, бенч функции test_for не имеет смысла, т.к. внутри нее идет создание vec!, что есть затратная операция, ибо приходится аллоцировать память в хипе. Функция, которую ты бенчишь, должна быть максимально короткой и делать только то, что ты бенчишь. Т.е. она должна по ссылке принимать уже сформированный массив (ну или слайс), и возвращать result: usize.
В-третьих, ты должен сказать нам порядок размера твоего массива, для которого ты пишешь эту функцию. Если это… 1000 элементов и вызываешь эту функцию раз в секунду, забей на оптимизацию. Если это 1М элементов и будешь вызывать каждую миллисекунду, то это уже хороший кандидат на оптимизацию.
В-четвертых, почему это массив строк, да которые еще и выглядят как флоаты?
В-пятых, будут ли флоаты отсортированы? Каков порядок элементов?

3 пункт очень важен. Если у тебя там 100 элементов, то не стоит тратить на эту “оптимизацию” время.


#15

Я бы к этому вопросу подошёл вот так:
https://play.rust-lang.org/?version=stable&mode=release&edition=2015&gist=854695818058ca1ce6a916c6e357f0ef

А дальше уже можно разбираться что и почему тормозит, и каковы будут последствия в разных условиях.

Кстати, для меня оказалось сюрпризом, что один println! томозит как три десятка аллокаций: век живи - век учись…


#16

Это плохой бенч. Смотри в сторону стандартного бенчмаркинга или Criterion. Следует прогревать кеши перед замерами, замерять не 1 итерацию, а несколько итераций, с одними и теми же аргументами. Смысла в println! внутри бенчмарка нет. Инициализация вектора сделана неправильно, let v: Vec<String> = (0..n).map(|n| format!("{}.0", n + 1)).collect(); - это означает, что в нем только 1 элемент, а надо протестировать отсутствие элемента, когда все элементы - “1.0”… и т.д. Ну и дождаться от автора поста ответов на уже предоставленную информацию.


#17

Я bencher’ом тестировал. do_something(index) кладет в HashMap индекс этого value


#18

Если быть точным, то вот что выполняется:

            match value {
                Operation::MakeLabel(label_id) => {
                    labeled.insert(label_id, index);
                },
                _operation => {}
            };

@kpp дело в том что вектор может быть размером от нуля до нескольких тысяч, хотя возможно и не стоит сильно беспокоиться о такой скорости в 0.1c ибо эта программа просто для себя, но все же хотелось бы что бы все было побыстрее


#19

На основе того что было выше накидал дуболомный вариант с HashMap, который и вектор внутри себя выделяет, и HashMap выделяет, и еще строчку клонирует при сохранении:

$ cat Cargo.toml:

[package]                                          
name = "criterion_test"                            
version = "0.1.0"                                  
authors = ["Andrey Lesnikov <ozkriff@gmail.com>"]  
edition = "2018"                                   

[dependencies]                                     

[dev-dependencies]                                 
criterion = "0.2"                                  

[[bench]]                                          
name = "my_benchmark"                              
harness = false                                    

$ cat benches/my_benchmark.rs:

#[macro_use]                                       
extern crate criterion;                            

use std::collections::HashMap;                     

use criterion::Criterion;                          

fn f() -> u64 {                                    
    let vector = vec![                             
        "1.0", "2.0", "3.0", "4.0", "5.0", "6.0", "7.0", "8.0", "9.0", "10.0", "11.0", "12.0",         
        "13.0", "14.0",                            
    ];                                             
    let mut map: HashMap<usize, String> = HashMap::new();                                              
    for (index, value) in vector.iter().enumerate() {                                                  
        if value == &"1.0" {                       
            map.insert(index, value.to_string());  
        }                                          
    }                                              
    map.len() as _                                 
}                                                  

fn criterion_benchmark(c: &mut Criterion) {        
    c.bench_function("fib 20", |b| b.iter(|| f()));                                                    
}                                                  

criterion_group!(benches, criterion_benchmark);    
criterion_main!(benches);                          
$ cargo bench                                      
    Finished release [optimized] target(s) in 0.09s
     Running target/release/deps/criterion_test-b6d4e6c476bc742b                                       

running 0 tests                                    

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out                             

     Running target/release/deps/my_benchmark-a2c6c11db5814243                                         
Gnuplot not found, disabling plotting              
fib 20                  time:   [222.39 ns 226.60 ns 231.63 ns]                                        
                        change: [+0.1911% +1.9279% +3.9791%] (p = 0.04 < 0.05)                         
                        Change within noise threshold.                                                 
Found 11 outliers among 100 measurements (11.00%)  
  11 (11.00%) high severe                          

time: [222.39 ns 226.60 ns 231.63 ns]

И время тут измеряется наносекундами все еще.

Это абсурдно долго для просто цикла с парочкой выделений памяти. Поэтому, собственно, пытаемся получить от тебя полный код того как ты меряешь, потому что 90% что у тебя ошибка в подходе к измерению времени, т.е. это все совсем не вопрос оптимизации кода.


UPD: Даже если внутри тестируемой функции взять и выделить вектор из десяти тысяч строк, речь все равно идет и us, т.е. микросекундах:

let vector: Vec<&str> = ["1.0", "2.0", "3.0"].into_iter().cycle().map(|s| *s).take(10_000).collect();

time: [625.98 us 634.95 us 649.10 us]


#20

Полный код такой:


    pub fn sort_lables(hashmap: &mut HashMap<usize,usize>, operations: Vec<Operation>)
    {
        for (index,value) in operations.iter().enumerate() {
            match value {
                Operation::MakeLabel(label_id) => {
                    hashmap.insert(label_id, index);
                },
                _operation => {}
          };
         }
    }