amarao (amarao_san) wrote,
amarao
amarao_san

Category:

fast random

Когда-то Олег мне подсказал функцию быстрого псевдорандома:

        factor ^= factor << 13;
        factor ^= factor >> 17;
        factor ^= factor << 5;

Когда я был в недрах piston'а и очень далеко от criterion'а, я не мог её проверить. Сейчас (научившись работать criterion'ом и cargo asm'ом) я могу с уверенностью сказать, что функция эта много медленее, чем кажется. Причина - она не конвейеризируется. Если тело цикла большей частью состоит из рандома (и записи оного), то мы получаем, что каждая следующая строка зависит от предыдущей, и это полностью тормозит конвейер (за вычетом инструкций цикла).

По моим замерам одна инструкция примерно на 70% быстрее, чем три (т.е. трёхкратная разница), и ~25x кратная по сравнению с отсутствием математики (но тут могут быть какие-то ещё спецоптимизации).

Я планирую попробовать сделать рандом конвейеризируемым.

Мораль: viva Criterion.

Tags: rust
Subscribe

  • systemd-networkd, netlink и arp флуд

    Нереально странный баг пофикшен с помощью eBPF затычки. Для меня большой неожиданностью является реакция на него.…

  • Rust soundness

    Каждый раз, когда я сталкиваюсь с маленькими "но" в Rust'е, это ощущение тщательной продуманности. Например, простейшие fold-функции для итераторов:…

  • still_ntp

    В ходе локального мозгового штурма у меня родилась суперидея. Надо написать ntp сервер, который может отдавать указанную дату. Т.е. сказали при…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments