LINUX.ORG.RU
Форум — Development  

t1ha (Fast Positive Hash) реализован на Rust

 , , t1ha


1

5

Flier Lu переложил реализацию t1ha (Fast Positive Hash) на Rust.

Библиотека t1ha предоставляет несколько предельно быстрых переносимых хэш-функций (в тестах опережает StadtX, xxHash, mum-hash, metro-hash, CityHash и т.д.).

Проект на Rust интересен тем, что реализация достаточно тщательная. Поэтому внутри можно подсмотреть, как из C/C++ на Rust перекладываются связанные с производительностью трюки.

Репозиторий на GitHub

Перемещено jollheef из opensource

anonymous

Последнее исправление: Virtuos86 (всего исправлений: 2)
← IDE - ?
Как в GitLab скрыть от группы свой репозитарий? →
  1 2 3 4 5
Ответ на: комментарий от Pacmu3ka

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

anonymous
()
Ответ на: комментарий от turtle_bazon

Да синтаксис это вообще последнее дело в языке, ИМХО.

вот и программируй на brainfuck тогда!

anonymous
()

Осточертели уже новости про переписывание! Какой-то онанизм. Нет, ну пусть себе переписывают, но зачем это тащить на публику? То с питона на си, то с си на раст..

Пользователям от программ в основном нужны а) функциональность б) производительность

Причем переписывание ради производительности принимается только с оговоркой, если предыдущая реализация реально тормозит и это мешает. Множество небольших программ прекрасно работают вообще на языках со сборкой мусора и это ОК.

Здесь нет не увеличения скорости (скорее всего, иначе об этом надо было написать в новости), ни нового функционала. Ну и нафига оно?

Crocodoom ★★★★★
()
Ответ на: комментарий от vasya_pupkin

Кто-то сдал курсач?

Вот +100500. Реализовать уже реализованное — годился для студенческих работ, и то не для всех. Для диплома уже требуется какая-то новизна! А обсуждать такую поделку всерьез на техническом форуме... Извините

Crocodoom ★★★★★
()
Ответ на: комментарий от Crocodoom

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

q0tw4 ★★★★
()
Последнее исправление: q0tw4 (всего исправлений: 1)
Ответ на: комментарий от mx__

Сравнил производительность оригинального кода на C и реализации на Rust.

Сравнил производительность оригинального кода на C и реализации на Rust.

Оригинальная C/C++ версия замеряет такты CPU и пересчитывает скорость на заданные гигагерцы (по умолчанию 3 ГГц) выдавая по «make bench» знатную портянку. Rust-версия бенчмарка не считает такты CPU, а делает замеры исключительно по «wall clock».

Поэтому для получения сравнимых цифр я выключил speed-step в BIOS и запускал оригинальный бенчмарк t1ha с опцией «-GHz=2.1» (что соответствует актуальной частоте на моём ноуте).

Вывод оригинальной C/C++ версии: 

$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

$ make && ../test —GHz=2.1

Preparing to benchmarking...
 - running on CPU#1
 - use RDPMC_40000001 as clock source for benchmarking
 - assume it cheap and stable
 - measure granularity and overhead: 54 cycles, 0.0185185 iteration/cycle

Bench for tiny keys (7 bytes):
t1ha2_atonce            :     17.266 cycle/hash,  2.467 cycle/byte,  0.405 byte/cycle,  0.851 GB/s @2.1GHz 
t1ha2_atonce128*        :     40.594 cycle/hash,  5.799 cycle/byte,  0.172 byte/cycle,  0.362 GB/s @2.1GHz 
t1ha2_stream*           :     80.688 cycle/hash, 11.527 cycle/byte,  0.087 byte/cycle,  0.182 GB/s @2.1GHz 
t1ha2_stream128*        :    101.562 cycle/hash, 14.509 cycle/byte,  0.069 byte/cycle,  0.145 GB/s @2.1GHz 
t1ha1_64le              :     19.219 cycle/hash,  2.746 cycle/byte,  0.364 byte/cycle,  0.765 GB/s @2.1GHz 
t1ha1_64be              :     19.234 cycle/hash,  2.748 cycle/byte,  0.364 byte/cycle,  0.764 GB/s @2.1GHz 
t1ha0                   :     16.109 cycle/hash,  2.301 cycle/byte,  0.435 byte/cycle,  0.913 GB/s @2.1GHz 
t1ha0_32le              :     21.234 cycle/hash,  3.033 cycle/byte,  0.330 byte/cycle,  0.692 GB/s @2.1GHz 
t1ha0_32be              :     23.234 cycle/hash,  3.319 cycle/byte,  0.301 byte/cycle,  0.633 GB/s @2.1GHz 
xxhash32                :     18.922 cycle/hash,  2.703 cycle/byte,  0.370 byte/cycle,  0.777 GB/s @2.1GHz 
xxhash64                :     25.062 cycle/hash,  3.580 cycle/byte,  0.279 byte/cycle,  0.587 GB/s @2.1GHz 
StadtX                  :     19.250 cycle/hash,  2.750 cycle/byte,  0.364 byte/cycle,  0.764 GB/s @2.1GHz 
HighwayHash64_pure_c    :    516.231 cycle/hash, 73.747 cycle/byte,  0.014 byte/cycle,  0.028 GB/s @2.1GHz 
HighwayHash64_portable  :    493.000 cycle/hash, 70.429 cycle/byte,  0.014 byte/cycle,  0.030 GB/s @2.1GHz 
HighwayHash64_sse41     :     68.375 cycle/hash,  9.768 cycle/byte,  0.102 byte/cycle,  0.215 GB/s @2.1GHz 
HighwayHash64_avx2      :     62.594 cycle/hash,  8.942 cycle/byte,  0.112 byte/cycle,  0.235 GB/s @2.1GHz 

Bench for large keys (16384 bytes):
t1ha2_atonce            :   3550.000 cycle/hash,  0.217 cycle/byte,  4.615 byte/cycle,  9.692 GB/s @2.1GHz 
t1ha2_atonce128*        :   3556.000 cycle/hash,  0.217 cycle/byte,  4.607 byte/cycle,  9.676 GB/s @2.1GHz 
t1ha2_stream*           :   3711.000 cycle/hash,  0.227 cycle/byte,  4.415 byte/cycle,  9.271 GB/s @2.1GHz 
t1ha2_stream128*        :   3746.000 cycle/hash,  0.229 cycle/byte,  4.374 byte/cycle,  9.185 GB/s @2.1GHz 
t1ha1_64le              :   3539.000 cycle/hash,  0.216 cycle/byte,  4.630 byte/cycle,  9.722 GB/s @2.1GHz 
t1ha1_64be              :   4812.000 cycle/hash,  0.294 cycle/byte,  3.405 byte/cycle,  7.150 GB/s @2.1GHz 
t1ha0                   :   1305.626 cycle/hash,  0.080 cycle/byte, 12.549 byte/cycle, 26.352 GB/s @2.1GHz 
t1ha0_32le              :   7428.000 cycle/hash,  0.453 cycle/byte,  2.206 byte/cycle,  4.632 GB/s @2.1GHz 
t1ha0_32be              :   7641.000 cycle/hash,  0.466 cycle/byte,  2.144 byte/cycle,  4.503 GB/s @2.1GHz 
xxhash32                :   8204.000 cycle/hash,  0.501 cycle/byte,  1.997 byte/cycle,  4.194 GB/s @2.1GHz 
xxhash64                :   4120.000 cycle/hash,  0.251 cycle/byte,  3.977 byte/cycle,  8.351 GB/s @2.1GHz 
StadtX                  :   3664.000 cycle/hash,  0.224 cycle/byte,  4.472 byte/cycle,  9.390 GB/s @2.1GHz 
HighwayHash64_pure_c    :  49083.252 cycle/hash,  2.996 cycle/byte,  0.334 byte/cycle,  0.701 GB/s @2.1GHz 
HighwayHash64_portable  :  43452.427 cycle/hash,  2.652 cycle/byte,  0.377 byte/cycle,  0.792 GB/s @2.1GHz 
HighwayHash64_sse41     :   6429.570 cycle/hash,  0.392 cycle/byte,  2.548 byte/cycle,  5.351 GB/s @2.1GHz 
HighwayHash64_avx2      :   4550.001 cycle/hash,  0.278 cycle/byte,  3.601 byte/cycle,  7.562 GB/s @2.1GHz

Rust-бенчмарк компилировался и работал минут 10. Портянку он выдает еще больше и трудно читаемую. Поэтому вот небольшая вырезка характерных моментов: 

$ rustc --version
rustc 1.35.0-nightly (f22dca0a1 2019-03-05)

$ RUSTFLAGS="-C target-cpu=native" cargo +nightly bench

…
t1ha2/t1ha2_atonce/7    time:   [11.464 ns 11.466 ns 11.468 ns]                                  
                        thrpt:  [582.14 MiB/s 582.23 MiB/s 582.31 MiB/s]
…
t1ha2/t1ha2_atonce/16384                                                                             
                        time:   [1.7373 us 1.7375 us 1.7378 us]
                        thrpt:  [8.7807 GiB/s 8.7818 GiB/s 8.7829 GiB/s]

…
t1ha2/t1ha2_stream128/7 time:   [48.680 ns 48.686 ns 48.694 ns]                                     
                        thrpt:  [137.10 MiB/s 137.12 MiB/s 137.14 MiB/s]
…
t1ha2/t1ha2_stream128/16384                                                                             
                        time:   [1.9996 us 1.9998 us 2.0000 us]
                        thrpt:  [7.6293 GiB/s 7.6301 GiB/s 7.6308 GiB/s]

Итого, в этих характерных точках, с приведением к Гигабайтам в секунду (я предполагаю что в Rust-бенчмарке попутаны биты и байты при выводе результатов): 

t1ha2_atonce / 7 байт:
   Rust: 0.582 GB/s
  C/C++: 0.851 GB/s 
 
t1ha2_atonce / 16 Кбайт:
   Rust: 8.781 GB/s 
  C/C++: 9.692 GB/s

t1ha2_ stream128 / 7 байт:
   Rust: 0.137 GB/s
  C/C++: 0.145 GB/s
 
t1ha2_ stream128 / 16 Кбайт:
   Rust: 7.630 GB/s
  C/C++: 9.185 GB/s

Я не поленился и глянул код генерируемый компилятором Rust. Субъективно его качество соответствует результатам выше, т. е. на 10% медленнее C/C++. Причем пока rustc в сравнении с gcc/clang довольно плохо разворачивает граф переходов и не делает каких-то оптимизаций.

Тем не менее, это очень неплохой результат (в частности недостижимый для Java).

Deleted
()

Ну и замечательно.

bbk123 ★★★★★
()
Ответ на: комментарий от anonymous

вот и программируй на brainfuck тогда!

Мсье не понимает, что в языке кроме синтаксиса ещё куча вещей присутствует?

turtle_bazon ★★★★★
()
Ответ на: комментарий от kto_tama

У каждого первого языка синтаксис - адский, пока ты хотя бы не попытаешься онять что он значит.

anonymous
()

а есть ли реализация на голом СТАРОМ js?
есть у меня имплементация murmurhash с поддержкой шестого осла, которая работает очень быстро. но нет предела совершенству - былобы здорово заполучить реализацию и этой функции. поиском не находится

и да, в некоторых крайне специфичных проектах мне всееще актуален ie6 и производительность.

genryRar ★★
()
Последнее исправление: genryRar (всего исправлений: 1)
Ответ на: Сравнил производительность оригинального кода на C и реализации на Rust. от Deleted

довольно плохо разворачивает граф переходов и не делает каких-то оптимизаций.

Ну это как раз может измениться со временем. Если у самих руки не дойдут, то думаю, пуллреквесты на эту тему они принимать согласятся.

q0tw4 ★★★★
()
Ответ на: комментарий от genryRar

а есть ли реализация на голом СТАРОМ js?

Это примерно не возможно, точнее не возможно с адекватной эффективностью.

Внутри t1ha используется «широкое» (aka алгебраическое) умножение uint64 * uint64 => uint128. А Java (и производных от него «языках программирования») отсутствует тип uint64 (беззнаковое 64-битное целое), поэтому в компиляторах не предусмотрена генерация код с использованием соответствующих инструкций CPU.

Короче - Quod licet Iovi, non licet bovi.

Deleted
()
Ответ на: комментарий от Deleted

понятно, спасибо

А Java (и производных от него «языках программирования»)

чушь какаято, бро.
хотя в целом да, int64+ в яваскрипт так и не завезли насколько я знаю.

genryRar ★★
()
Ответ на: комментарий от turtle_bazon

Я другой мсье, но понимаю, что синтаксис всё равно присутствует в каждой строчке.

Всё это Луговский-стайл «синтаксис неважен» идет от теоретиков, которые языки обсуждают, а не с кодом работают.

anonymous
()
Ответ на: комментарий от genryRar

хотя нет, я не прав - недавно завезли bigint правда доступен он только в свежей лисе и хроме, такчто считай что ПОКАЧТО нету

genryRar ★★
()
Ответ на: комментарий от q0tw4

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

Да Васина либа должна завернуть вашу ошибку в Box<Error> и выкинуть наружу. Ну тогда это будет аналог dynamic_cast.

Если тип ошибок который могут возвращать каллбэки известен зарание то васина либа может выкидывать enum из условно InternalError и CallbackError.

anonymous
()
Ответ на: комментарий от anonymous

Само собой такой подход безопаснее, а то вдруг Вася вызвал меня в другом потоке. Но блин, есть же случаи, когда всё однопоточно и хочется просто развернуть стек не спрашивая Васиного разрешения.

q0tw4 ★★★★
()
Ответ на: комментарий от anonymous

Есть мнение, что 128-битный вариант t1ha на голову превосходит SipHash.

По скорости - безусловно t1ha быстрее в 5-10 раз.

По качеству - аналогично (t1ha проходит все самые строгие тесты).

По стойкости - у меня есть своё мнение, но очень хочется увидеть независимый криптоанализ. На всякий, пока никто не нашел ничего плохого ни в цикле сжатия t1ha, ни в финальном перемешивании (#1, #2).

Deleted
()
Ответ на: комментарий от Cycle_A

Растишка 

> rustc -C debuginfo=2 -C opt-level=0 hello.rs
> du --apparent-size --bytes hello
2427576 hello
> rustc -C debuginfo=0 -C opt-level=3 hello.rs
> du --apparent-size --bytes hello
2415608 hello

Сишка 

> gcc -Og -g3 hello.c
> du --apparent-size --bytes a.out
42224   a.out
> gcc -O3 hello.c
> du --apparent-size --bytes a.out
16568   a.out
> gcc -s -O3 hello.c
> du --apparent-size --bytes a.out
14360   a.out
Система. 
Linux pc 4.20.6-arch1-1-ARCH #1 SMP PREEMPT Thu Jan 31 08:22:01 UTC 2019 x86_64 GNU/Linux
> rustc --version
rustc 1.33.0 (2aa4c46cf 2019-02-28)
> gcc --version
gcc (GCC) 8.2.1 20181127

У меня почему-то большие цифры.

Растишка 

> ldd hello
        linux-vdso.so.1 (0x00007ffd78fca000)
        libdl.so.2 => /usr/lib/libdl.so.2 (0x00007faec8e06000)
        librt.so.1 => /usr/lib/librt.so.1 (0x00007faec8dfc000)
        libpthread.so.0 => /usr/lib/libpthread.so.0 (0x00007faec8ddb000)
        libgcc_s.so.1 => /usr/lib/libgcc_s.so.1 (0x00007faec8dc1000)
        libc.so.6 => /usr/lib/libc.so.6 (0x00007faec8bfd000)
        /lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007faec8e79000)
Сишка 
> ldd a.out 
        linux-vdso.so.1 (0x00007ffef9ffd000)
        libc.so.6 => /usr/lib/libc.so.6 (0x00007f24ff3ef000)
        /lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007f24ff5f5000)

baist ★★
()
Ответ на: комментарий от Cycle_A

Плюсишка 

> cat hello.cpp 
#include <iostream>

int main()
{
    std::cout << "Hello, world!";
    return 0;
}
rust-and-c > g++ -s -O3 hello.cpp
rust-and-c > du --apparent-size --bytes a.out
14376   a.out
rust-and-c > ldd a.out 
        linux-vdso.so.1 (0x00007ffe6ebf5000)
        libstdc++.so.6 => /usr/lib/libstdc++.so.6 (0x00007f6a023cc000)
        libm.so.6 => /usr/lib/libm.so.6 (0x00007f6a02247000)
        libgcc_s.so.1 => /usr/lib/libgcc_s.so.1 (0x00007f6a0222d000)
        libc.so.6 => /usr/lib/libc.so.6 (0x00007f6a02069000)
        /lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007f6a0259d000)

Странно. Либ больше но размер тот же.

baist ★★
()
Последнее исправление: baist (всего исправлений: 1)
Ответ на: Сравнил производительность оригинального кода на C и реализации на Rust. от Deleted

А у тебя для растишки релизная сборка или отладочная? Они обычно сильно отличаются по скорости. По умолчанию в cargo идет отладочная.

dave ★★★★★
()
Последнее исправление: dave (всего исправлений: 2)
Ответ на: комментарий от baist

Странно. Либ больше но размер тот же.

man динамическая vs статическая линковка и rust no-std

anonymous
()
Ответ на: комментарий от genryRar

хотя нет, я не прав - недавно завезли bigint правда доступен он только в свежей лисе и хроме, такчто считай что ПОКАЧТО нету

На всякий поясню почему в Java/JavaScript «нет и не будет», а не «покачто».

Алгебраически полноценное умножение двух чисел дает результат удвоенной разрядности (точнее говоря разрядность результата равна сумме разрядностей множителей). Именно такое «широкое» умножение используется в t1ha (причины пока оставим за скобками).

Технически у CPU есть специальная инструкция для выполнения такого широкого умножения (на x86 это разновидность mul, на ARM/MIPS есть mulh для до-вычисления старшей половины результата). Соответственно t1ha работает быстро если компилятор задействует такие инструкции, а не занимается ерундой.

Все актуальные/хорошие компиляторы C/C++ (а также Rust) умеют такое, либо оптимизируя операции с __uint128, либо предоставляя intrinsic-и emul() или mulh(). А для старых/плохих компиляторов t1ha реализует нужное «широкое» через переносимые операции. Это примерно в 3-6 раз медленнее и для этого нужна поддержка беззнаковых 64-битных целых. Если же нет 128-битных операций и нет беззнаковых 64-битных целых (только со знаком или только 32-битные), то «широкое» умножение все-рано можно реализовать. Однако оно будет выполняться еще в 2-8 раз медленнее (суммарно в 10-50 раз медленнее).

Так вот, в Java (и JavaScript) нет беззнаковых 64-битных целых и нет их «широких» умножений. Теоретически можно использоваться BigInteger, но вместо _одной_ инструкции умножения в ~100 раз больше.

С другой стороны, так и должно быть - Java НЕ должна быть быстрой, если вспомнить её исходное предназначение (и всех потомков).

Deleted
()
Ответ на: комментарий от baist

У меня почему-то большие цифры.

Rust линкует свою стандартную библиотеку статически, C и C++ - динамически. Такая линковка по-умолчанию обусловлена отсутсвием стабильного ABI (разные версии компилятора будут генерить разный, несовместимы друг с другом код).

Но если если сильно нужно, см. этот пост.

anonymous
()
Ответ на: комментарий от Crocodoom

И, самое смешное, что переписали на какой-то унылый Rust, а не на популярный и опенсорсный нынче C#/.NET Core.

menangen ★★★★★
()
Ответ на: комментарий от anonymous 
> rustc -C debuginfo=0 -C opt-level=z -C relocation-model=static -C prefer-dynamic hello.rs
> du --apparent-size --bytes hello
16712   hello
> strip hello
> du --apparent-size --bytes hello
14032   hello
baist ★★
()

на Rust.

А почему не на Haskell?

Odalist ★★★★★
()
Ответ на: комментарий от Crocodoom

Пользователям от программ в основном нужны а) функциональность б) производительность

ты забыл еще один пункт:

в) стабильность.

Раст это дает?

Odalist ★★★★★
()
Ответ на: Сравнил производительность оригинального кода на C и реализации на Rust. от Deleted

Я не поленился и глянул код генерируемый компилятором Rust.

Но ты поленился осилить LORCODE. Так что, шел бы ты лесом, диванный аналитик.

Odalist ★★★★★
()
Ответ на: комментарий от Manhunt

Тихо, сейчас его «поделка» и «диванная аналитика» станут внезапно нужны xD

theNamelessOne ★★★★★
()
Ответ на: комментарий от anonymous

Можно подумать, если бы не с автором - ответ был бы адекватен.

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

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

Manhunt ★★★★★
()
Последнее исправление: Manhunt (всего исправлений: 1)
Ответ на: комментарий от baist

Асмишка 

$ cat hw.s

                .data

.type hw, @object
hw:
        .ascii  "Hello, world\n"
        .set    hs, .-hw

                .text

.global _start
.type _start, @function

.type write, @function

.type exit, @function

_start:
                leaq    hw(%rsi), %rsi
                movq    $hs, %rdx
                callq   write
                xorq    %rdi, %rdi
                callq   exit

# sys_write(1, message, size)
write:
                movq    $1,  %rax
                movq    $1,  %rdi
                syscall
                retq

# sys_exit(%rdi)
exit:
                movq    $60, %rax
                syscall
                retq
Изменения в скрипте линкера (link.ld) 
+  /DISCARD/ : { *(.note.gnu.property) }
Сборка 
as hw.s -o hw.o
ld -s -T link.ld hw.o -o hw
и 
du --apparent-size --bytes hw
528     hw

kostyarin_ ★★
()
Ответ на: комментарий от WatchCat

Спасибо! :3

Лень, нетерпение и самомнение, браток.

perl5_guy ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
  1 2 3 4 5
← IDE - ?
Development
Как в GitLab скрыть от группы свой репозитарий? →