Оптимизируем кодирование u128 в base62

[lebedec]

Если гонитесь за скоростью, попробуйте ещё убрать аллокацию вектора. На большом количестве вызовов, должно быть ощутимо быстрее.

let mut b62_str = [b'0'; U128_BASE62_ENCODED_LEN];
...
unsafe { String::from(std::str::from_utf8_unchecked(&b62_str)) }

[gpaw]

+1, но немного дополню. можно сделать такое решение - буфер, сочетающий в себе данные на стеке и аллокацию из кучи -

pub struct TinyBuffer<T: Copy, const S: usize> {
    /// небольшой буфер, используемый по умолчанию, чтобы избежать лишнего обращения к аллокатору
    tiny: [MaybeUninit<T>; S],
    /// количество элементов буфера
    length: usize,
    /// вместимость текущей ячейки
    capacity: usize,
    /// указатель на первый элемент буфера
    pointer: *mut T,
}

[rsk]

не совсем понял насчет "убрать аллокацию", можно убрать инициализацию вектора это да, будет немного быстрее, если вы имеете ввиду передавать в функцию буфер для заполнения, то можно, но не подойдет для моего случая

[Biga]

Компиляторы в некоторых случаях умеют превращать деление на константу в умножение и сдвиг. (https://libdivide.com)

[kovserg]

Они содержат только буквы и цифры, поэтому их можно выделять двойным кликом

Если набирать с экрана то лучше убрать не однозначные символы O0o 1liI B8, если по телефону то независимым от больших и маленьких букв сделать. А вот для выделения курсором можно unicode использовать база резко увеличиться :)

Посмотрим на скорость алгоритма, результат бенчмарка

А для чего вам скорость или весь текст состоит из идентификаторов? Или это по тестам оказалось самым узким местом?

ps: Т.к. используются случайные числа, можно получать случайные слова, которые могут оскорбить случайных пользователей. Были инциденты.

[Quartz32]

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

[rsk]

Если набирать с экрана то лучше убрать не однозначные символы O0o 1liI
B8, если по телефону то независимым от больших и маленьких букв сделать.
А вот для выделения курсором можно unicode использовать база резко
увеличиться :)

да, есть в планах использование двух типов идентификаторов, глобально уникальные как описано в статье, а также локально уникальные, например, 5-ти символьные base32 строки (см. Crockford's Base32)

А для чего вам скорость или весь текст состоит из идентификаторов? Или это по тестам оказалось самым узким местом?

ради эстетики, слишком уж медленно было и хорошо поддается оптимизации

[gpaw]

спасибо, схоронил ) немного оффтопик, но - по опыту, раст прямо-таки создан для различного рода оптимизаций. сейчас пишу имплементацию сопоставлений unicode для своей бд, так на нормализации добился до 40% прироста по сравнению с ICU4X.

приятно увидеть людей со схожими взглядами на код )

[pfffffffffffff]

А можно ссылку на приложение заметок?

[rsk]

не знаю можно ли здесь оставлять ссылки на свои проекты, но все есть в профиле, называется heaplist.app

[Gorthauer87]

А чем не устроил base58?

[rsk]

Хм, заставили призадуматься, действительно u128 кодированное в base58 тоже помещается в 22 символа. В свою защиту скажу base62 проще, более однозначный алфавит. Ну а если идти по пути уменьшения алфавита, тогда можно использовать base57, тоже будет 22 символа. Спасибо подумаю над этим.

[aiscy]

Рассмотрите еще newbase60.

[NooneAtAll3]

Посмотрим на сгенерированный компилятором Rust ассемблер:

__umodti3
__udivti3

а вы оптимизацию точно включали?
компиляторы давным-давно умеют деление на константу превращать в умножение

если компилятору не доверяем, то используйте fastdiv/fastdivide/strength_reduce либы (и "заранее расчитайте" нужную константу с помощью const)

[rsk]

да, все бенчмарки были в релиз-билде, как описано в статье оптимизация выполена за счет перехода от деления 128-битных чисел к делению 64-битных

fastdiv еще не пробовал, потестирую, спасибо