<bgdev />^free

Забелязах много интересен феномен,който не мога да си го обясня:

Вариант 1:

fn solve_part_one_1(input: &mut [i32]) -> Option<i32> {
    input.sort_unstable();

    let mut ones = 0;
    let mut threes = 1; 
    let mut prev = 0;

    for &i in input.iter() {
        let diff = i - prev;
        if diff == 1 {
            ones += 1;
        } else if diff == 3 {
            threes += 1;
        }

        prev = i;
    }

    if cfg!(debug_assertions) {
        println!("O:{}; T: {}; Result: {}", ones, threes, ones * threes);
    }

    Some(ones * threes)
}

Вариант 2:

fn solve_part_one_2(input: &mut [i32]) -> Option<i32> {
    input.sort_unstable();

    let mut sums = [0, 0, 1];
    let mut prev = 0;

    for &i in input.iter() {
        let diff = (i - prev) as usize;
        if diff <= 3 {
            sums[diff-1] += 1;
            prev = i;
        }
    }

    if cfg!(debug_assertions) {
        println!("O:{}; T: {}; Result: {}", sums[0], sums[2], sums[0] * sums[2]);
    }

    Some(sums[0] * sums[2])
}

Та това което не мога да си обясня е, защо вариант 1 се изпълнява за 2800 наносекунди, а вариант 2 - само за 1500. Защо така ?

Компилатора на Ръст е смотан?

По-малко сравнения? По-малък шанс за branch misprediction?

П.П. Двете програми не са еквивалентни.

|

По-малко сравнения? По-малък шанс за branch misprediction?

П.П. Двете програми не са еквивалентни.

Аз на пръв поглед без да бенчмарквам бих предположил,че трябва да са точно обратните резултати,а именно там където се ползва [] оператора да е по-бавно,въпреки,че паметта е алокирана на едно място

saruman

|

По-малко сравнения? По-малък шанс за branch misprediction?

П.П. Двете програми не са еквивалентни.

Аз на пръв поглед без да бенчмарквам бих предположил,че трябва да са точно обратните резултати,а именно там където се ползва [] оператора да е по-бавно,въпреки,че паметта е алокирана на едно място

Това всъщност показва, че компилатора на Ръст е доста добър.

|

saruman

|

По-малко сравнения? По-малък шанс за branch misprediction?

П.П. Двете програми не са еквивалентни.

Аз на пръв поглед без да бенчмарквам бих предположил,че трябва да са точно обратните резултати,а именно там където се ползва [] оператора да е по-бавно,въпреки,че паметта е алокирана на едно място

Това всъщност показва, че компилатора на Ръст е доста добър.

Стига ве,и само заради branch prediction-а ли да прави такива разлики,забележи че долу ползва даже <= оператор,ако ползва само < още би трябвало да падне времето

saruman

|

saruman

|

По-малко сравнения? По-малък шанс за branch misprediction?

П.П. Двете програми не са еквивалентни.

Аз на пръв поглед без да бенчмарквам бих предположил,че трябва да са точно обратните резултати,а именно там където се ползва [] оператора да е по-бавно,въпреки,че паметта е алокирана на едно място

Това всъщност показва, че компилатора на Ръст е доста добър.

Стига ве,и само заради branch prediction-а ли да прави такива разлики,забележи че долу ползва даже <= оператор,ако ползва само < още би трябвало да падне времето

Какво значение има дали ще е <= или <?

Е как какво,първото ти прави < и след това ==,това са две операции,а второто само <

saruman

Е как какво,първото ти прави < и след това ==,това са две операции,а второто само <

Струва ми се, че Иванушка Пъдаря ще ти се кара, че не знаеш асемблерските инструкции. :)

|

saruman

Е как какво,първото ти прави < и след това ==,това са две операции,а второто само <

Струва ми се, че Иванушка Пъдаря ще ти се кара, че не знаеш асемблерските инструкции. :)

Мълча позорно,признавам

https://stackoverflow.com/questions/12135518/is-faster-than

По-важното е,че ако я нямаше тая тема,щях да си продължавам да си живея в заблуда,че едното е по-бързо от другото :(

saruman

Стига ве,и само заради branch prediction-а ли да прави такива разлики,забележи че долу ползва даже <= оператор,ако ползва само < още би трябвало да падне времето

да, само заради него е. обаче и на правец 16 дето няма конвеери мисля че "аритметичния" вариант ще е по-бърз, но няма да е с толкова много. ифа дори на платформа без конвеери монвеери е няколко операции и замяната му с аритметична операция (индексиране) още от фортранските времена си е била далавера. компилаторите от много отдавна като компилират switch гледат дали клоновете са последователни числа, и ако да компилират аритметично, без ифове.

На мен това diff-1 изобщо не ми харесва помеже може да доведе до array under/overflow. Ако разбирач правилно, че usize e unsigned, аз бих го написал като ... mut prev = 1 извън цикъла, и в цикъла prev = i + 1, индекса diff

П.П. всъщност най-добре е просто масива да се направи с 4 елемента.

|

На мен това diff-1 изобщо не ми харесва помеже може да доведе до array under/overflow.

ами не може, ако можеше ръста няма да го компилира. и да, точно защото е без знак, ако е негативно ще стане просто голямо число.

Дон Реба

|

На мен това diff-1 изобщо не ми харесва помеже може да доведе до array under/overflow.

ами не може, ако можеше ръста няма да го компилира. и да, точно защото е без знак, ако е негативно ще стане просто голямо число.

затова съм написал under/overflow.

деа, май си прав, какво става при нула? защо ръста го позволява?

Пусни един С декомпилатор. Защото Branchless Programming: Why "If" is Sloowww... and what we can do about it!

Дон Реба

деа, май си прав, какво става при нула? защо ръста го позволява?

Нямам идея, не трябва ли да го позволява?

не трябва, идеята е че ръста по време на компилация трябва да го види като грешка, но не го вижда, а и програмата не гърми, така че нещо недоглеждам

Дон Реба

не трябва, идеята е че ръста по време на компилация трябва да го види като грешка, но не го вижда, а и програмата не гърми, така че нещо недоглеждам

Хмм, толкова ли му е добър статичния анализ? Чувал съм, че Ръст се опитва да осигури някаква коректност at compile time, но е ясно и че не всичко може да се направи тогава.

Това означава ли, че всеки достъп до елемент на масив трябва да е guard-нат от екплицитна проверка дали индекса е в размерите на масива?

Масивите имат bound checks. Ако индекса е извън границите на масива ще се паникьоса и умре в рънтайм. Обаче ако LLVM се усети, че индекса винаги ще е в границата на масива, то тогава ще махне bounds check-a като dead code.

Отделно debug билдовете се инструментират от компилатора с проверки за over/under flow. Което ти позволява да хванеш разни тъпи грешки. Обаче в release mode ги няма тези проверки, защото доста забавят.