Panic! At the 0xC0D3

Сижу вот изучаю Rust
Как вы, наверное, знаете, в C/C++ есть switch, который работает для чисел
И компилятор там всеми силами пытается его соптимайзить, фигачит jump table какой-то или около того
В Rust есть по сути тоже самое, но еще и со строками (match str), и возник вопрос, а как оно там, собственно, оптимизируется

Короче - сам поиск примерно никак, используется линейный поиск, но оптимизируется сравнение строк.
Единственное, если размер строк разный, то он сделает jump table по их размеру (по сути, как с обычными числами)

А вот со сравнением строк уже интереснее. Да да, это скорее всего уже не сам раст, сколько llvm, но все равно интересно
1) Если строки <8 байт, то строка запишется как число, и компилятор просто прочитает строку как число и сделает сравнение
2) Если строки <16 байт, то сделает два сравнения (два числа 8 байт)
3) Если строки <32(?) байта, то фиганет SIMD сравнение (строки все еще числа)
4) Иначе, вызовет какую-то функцию сравнения длинных строк, которая, думаю, использует какие-то идеи из 1-3

Обидно конечно, что он не оптимайзит для длинных строк ничего. В моем случае (см картинку) очевидно, что можно понять, какая именно строка нужна по первому символу даже, и дальше сделать всего-лишь 1 проверку.
May be one day я решусь залезть в llvm...

Так что если вдруг кто-то решит переписать ejudge на раст, то придется и для него кодогенерировать бор для команд...

godbolt.org

Compiler Explorer - Rust (rustc 1.55.0)

// Type your code here, or load an example.
pub fn some(s: &str) -> i32 {
match s {
"asomessmesomdsomesomesomesomessmesomdsomesomesome" => 0,
"bothrothrothrothrothrothrothrothrothrothrothrothr" => 1,
"cstufstufstufstufstufstuf…

👍1

www.tgoop.com/paniccode/8

388 viewsLev Iskandarov, edited  Sep 12, 2021 at 22:18

Сижу вот изучаю Rust
Как вы, наверное, знаете, в C/C++ есть switch, который работает для чисел
И компилятор там всеми силами пытается его соптимайзить, фигачит jump table какой-то или около того
В Rust есть по сути тоже самое, но еще и со строками (match str), и возник вопрос, а как оно там, собственно, оптимизируется

Короче - сам поиск примерно никак, используется линейный поиск, но оптимизируется сравнение строк.
Единственное, если размер строк разный, то он сделает jump table по их размеру (по сути, как с обычными числами)

А вот со сравнением строк уже интереснее. Да да, это скорее всего уже не сам раст, сколько llvm, но все равно интересно
1) Если строки <8 байт, то строка запишется как число, и компилятор просто прочитает строку как число и сделает сравнение
2) Если строки <16 байт, то сделает два сравнения (два числа 8 байт)
3) Если строки <32(?) байта, то фиганет SIMD сравнение (строки все еще числа)
4) Иначе, вызовет какую-то функцию сравнения длинных строк, которая, думаю, использует какие-то идеи из 1-3

Обидно конечно, что он не оптимайзит для длинных строк ничего. В моем случае (см картинку) очевидно, что можно понять, какая именно строка нужна по первому символу даже, и дальше сделать всего-лишь 1 проверку.
May be one day я решусь залезть в llvm...

Так что если вдруг кто-то решит переписать ejudge на раст, то придется и для него кодогенерировать бор для команд...

BY Panic! At the 0xC0D3