Sha512 - wydajność

0

Potrzebuję w javie maksymalnie szybko przehashować wiele razy pewne dane.
Z javowych rozwiązań najszybsze jest Apache Commons Codec.
Czy ktoś zna jakąś inną opcję żeby to jeszcze przyspieszyć? Wykorzystanie jakiegoś innego języka na JVM może albo zawołanie jakiegoś C? Ktoś walczył z czymś takim kiedyś?

3

Robiłeś jakieś benchmarki? Na pewno hashowanie jest problemem? Jeśli Hashujesz stringi w Javie, to, niech mnie ktoś poprawi, trzeba je skonwertować do bajtów, i to może być bardziej kosztowne, niż sam hash.

1

Jak kolega wyżej wspomniał, zrób benchmark, spróbuj profilować aplikację żeby wychwycić co jest najwęższym gardłem.
Możesz też poeksperymentować z flagami:

-Xcomp
-Xbatch
-XX:CompileThreshold
0

Zależy jak dużo masz tych danych. Wywołując kod natywny przez JNA/JNI należy liczyć się z narzutem rzędu 5-10 ns.
Ale kod natywny może być znacząco szybszy zwłaszcza w takich zadaniach jak hashowanie / szyfrowanie, które często mają wspomaganie sprzętowe, a nawet jeśli nie, to SSE/AVX potrafi robić niezłe cuda (a JVM cały czas nie umie w te klocki).

https://software.intel.com/en-us/articles/intel-sha-extensions

1
daniel_96 napisał(a):

wiele razy

Ile razy? Podejrzewam, że mowa tutaj o 10 - 100k iteracji na każdym z elementów?

0
qbns napisał(a):
daniel_96 napisał(a):

wiele razy

Ile razy? Podejrzewam, że mowa tutaj o 10 - 100k iteracji na każdym z elementów?

Dla jednego dużego requestu mowa o milionach iteracji

2

Jeśli naprawdę Ci na tym zależy i masz konkretny biznesowy problem do rozwiązania, to co powiesz na takie podejście:

  • postaw sobie dedykowany serwis do takiego haszowania i z dżawy wołaj ten serwis
  • skorzystaj z zabawek typu NVIDIA CUDA do obliczeń tych milionów haszy
0
daniel_96 napisał(a):

Potrzebuję w javie maksymalnie szybko przehashować wiele razy pewne dane.
Z javowych rozwiązań najszybsze jest Apache Commons Codec.
Czy ktoś zna jakąś inną opcję żeby to jeszcze przyspieszyć? Wykorzystanie jakiegoś innego języka na JVM może albo zawołanie jakiegoś C? Ktoś walczył z czymś takim kiedyś?

jakiej jakości muszą być te hashe? Jakich kodeków z appache commons uzywałeś?

0
slsy napisał(a):
daniel_96 napisał(a):

Potrzebuję w javie maksymalnie szybko przehashować wiele razy pewne dane.
Z javowych rozwiązań najszybsze jest Apache Commons Codec.
Czy ktoś zna jakąś inną opcję żeby to jeszcze przyspieszyć? Wykorzystanie jakiegoś innego języka na JVM może albo zawołanie jakiegoś C? Ktoś walczył z czymś takim kiedyś?

jakiej jakości muszą być te hashe? Jakich kodeków z appache commons uzywałeś?

Nie rozumiem pytania o jakość.
Używam DigestUtils.sha512Hex
Jest to szybsze niż Guava i inne javowe opcje na hashowanie, ale nadal biznesowo za wolne

2
  1. Aż boję się pytać, bo przewiduje że używacie tego SHA w jakiś bardzo zły sposób ;)
  2. Jak ma być szybko to musisz to robić przez jakąś natywną libkę, może polyglot z GraalVM ci pomoże w integracji.
0
Shalom napisał(a):
  1. Aż boję się pytać, bo przewiduje że używacie tego SHA w jakiś bardzo zły sposób ;)
  2. Jak ma być szybko to musisz to robić przez jakąś natywną libkę, może polyglot z GraalVM ci pomoże w integracji.

My używamy go bo takie ktoś z jednego ministerstwa wymyślił rozwiązanie

1
daniel_96 napisał(a):

Nie rozumiem pytania o jakość.

Chodzi mi o użycie innego algorytmu np. tych używanych do hash map; przykładowo: murmur3 albo FNV. Jeśli to musi być SHA512 to jedynie co zostaje to mierzenie CPU i szukanie wolnych miejsc np. za pomocą tego https://www.jetbrains.com/help/idea/async-profiler.html , lub użycie natywnego rozwiązania.

2
daniel_96 napisał(a):

Używam DigestUtils.sha512Hex

Nie wiem co dokładnie robisz, ale to powyżej to wygląda na najgłupsze możliwe podejście do problemu...
Jak masz wielokrotnie zrobić tego Hasha to powinieneś naturalnie odpalać sha512 (byte[] -> byte[]).
Żadne stringi w trakcie-dopiero na sam koniec, po ostatniej iteracji robimy konwersje do hex.

0
jarekr000000 napisał(a):
daniel_96 napisał(a):

Używam DigestUtils.sha512Hex

Nie wiem co dokładnie robisz, ale to powyżej to wygląda na najgłupsze możliwe podejście do problemu...
Jak masz wielokrotnie zrobić tego Hasha to powinieneś naturalnie odpalać sha512 (byte[] -> byte[]).
Żadne stringi w trakcie-dopiero na sam koniec, po ostatniej iteracji robimy konwersje do hex.

Spróbowałem i po takim wielokrotnym hashowaniu na byte[] po konwersji do stringa na sam koniec dostaje inny hash niz jak hashuje stringa.
Oczywiście nie rozumiem dlaczego.

2
daniel_96 napisał(a):
jarekr000000 napisał(a):
daniel_96 napisał(a):

Używam DigestUtils.sha512Hex

Nie wiem co dokładnie robisz, ale to powyżej to wygląda na najgłupsze możliwe podejście do problemu...
Jak masz wielokrotnie zrobić tego Hasha to powinieneś naturalnie odpalać sha512 (byte[] -> byte[]).
Żadne stringi w trakcie-dopiero na sam koniec, po ostatniej iteracji robimy konwersje do hex.

Spróbowałem i po takim wielokrotnym hashowaniu na byte[] po konwersji do stringa na sam koniec dostaje inny hash niz jak hashuje stringa.
Oczywiście nie rozumiem dlaczego.

Bo na koniec trzeba jeszcze ogarnąć przesunięcia i kodowanie za pomocą Hex.encodeHex(TWOJA_TABLICA_BAJTÓW)

2

Spróbowałem i po takim wielokrotnym hashowaniu na byte[] po konwersji do stringa na sam koniec dostaje inny hash niz jak hashuje stringa.

Ta, tym razem dostajesz dobrą wartość :D Bo jeśli ty hashowałeś wielokrotnie za każdym razem zamieniajac to na hexy, to zupełnie nie to co trzeba robiłeś. Zamiana na hexy to jak kodowanie czegoś w base64, robi się tak żeby wygodnie się czytało, bo wszystko jest printable. Ale jeśli masz wielokrotnie hashować, to musisz hashować bajty a nie ich wersje zakodowaną jako hexy, base64 czy cokolwiek innego.

4

Tu jeszcze jeden hint - istnienie flagi USE_SHA512_INTRINSICS_OPTION wskazuje, że SHA512 może byc mocno zoptymalizowane juz w JDK ... i korzystanie z biblioteki tylko to spowolni. (Trzeba sprawdzić).
https://github.com/openjdk/jdk/blob/6bab0f539fba8fb441697846347597b4a0ade428/src/hotspot/cpu/ppc/macroAssembler_ppc_sha.cpp
https://github.com/openjdk/jdk/blob/6bab0f539fba8fb441697846347597b4a0ade428/src/hotspot/cpu/x86/macroAssembler_x86_sha.cpp

0
Koziołek napisał(a):
daniel_96 napisał(a):
jarekr000000 napisał(a):
daniel_96 napisał(a):

Używam DigestUtils.sha512Hex

Nie wiem co dokładnie robisz, ale to powyżej to wygląda na najgłupsze możliwe podejście do problemu...
Jak masz wielokrotnie zrobić tego Hasha to powinieneś naturalnie odpalać sha512 (byte[] -> byte[]).
Żadne stringi w trakcie-dopiero na sam koniec, po ostatniej iteracji robimy konwersje do hex.

Spróbowałem i po takim wielokrotnym hashowaniu na byte[] po konwersji do stringa na sam koniec dostaje inny hash niz jak hashuje stringa.
Oczywiście nie rozumiem dlaczego.

Bo na koniec trzeba jeszcze ogarnąć przesunięcia i kodowanie za pomocą Hex.encodeHex(TWOJA_TABLICA_BAJTÓW)

Mimo tego wynik jest inny.
A co do sugestii innego kolegi że to jest wynik prawidłowy- nie neguje jej, ale wynikiem pożądanym przez ministerstwo jest jednak taki hash po stringach.
Dzisiaj potestuje te flagę o ktorej pisze Jarek

2

Ministerstwo zawsze ma racje!

Edit: a może ty kodzisz te tokeny, które trzeba będzie wpisywać, żeby obejrzeć sobie legalnie porno?

6

Napisałem mały benchmark:
https://github.com/jarekratajski/sha512test
https://github.com/jarekratajski/sha512test/blob/master/src/jmh/java/pl.setblack.sha512/ShaBenchmark.java

Odpalilem to na brudno (na komputerze, na którym cały czas pracowałem) i wyszło tak:

VM version: JDK 13.0.2, OpenJDK 64-Bit Server VM, 13.0.2+8
Benchmark                   Mode  Cnt   Score   Error  Units
ShaBenchmark.apacheSha512  thrpt   15  18.493 ± 0.440  ops/s
ShaBenchmark.jvmSha512     thrpt   15  23.425 ± 0.151  ops/s
ShaBenchmark.jvmShaBC512   thrpt   15  13.959 ± 0.086  ops/s

jvmSha512 to wbudowana implementacja (wychodzi najlepiej)
jvmShaBC512 to BouncyCastle
apacheSha512 to ta z apache codecs

Testowałem na grupuie 128 tablic bajtów (byte[][]). 1024 iteracje na każdym elemencie (element to tablica bajtów). Sekwencyjnie (bez użycia wątków, oczywiście każdy hash z grupy można spokojnie w osobnym wątku liczyć).
Wynik oznacza, że w najlepszym przypadku, na tej maszynie, wychodzi 23.425 (op/s) * 128 * 1024 = 3,070,361.6 czyli 3 miliony hashowań na sekunde (na jednym wątku).

To nie jest to dokładnie to samo zagadnienie, które podał OP. Bo tam jest dodatkowo dziwaczne konwertowanie na hex repeatX( Sha512 -> toHex) - nie uwzględniłem tego toHex.
IMO jeśli zrobić toHex z tablicy bajtów na tablicę bajtów to powinno być niewiele wolniejsze. (na pewno operowanie na stringach jest niewskazane, bo funkcje kryptograficzne operują na tablicach bajtów byte[] więc mamy niepotrzebne konwersje wtedy).

0

hm..., to jak się pozbyć tego "dziwacznego konwertowania"?
Jeśli to w ogóle możliwe w tym przypadku.

Poprawny hash wg wymogów zwraca np.

private MessageDigest md= MessageDigest.getInstance("SHA-512");

private String getHash(String input) {
        for (int i = 0; i < 5000; i++) {
            input = Hex.encodeHexString( md.digest( input.getBytes(StandardCharsets.UTF_8) ) );
        }
        return input;
    }

przy czym jeśli zrobić konwertowanie tylko na końcu, to oczywiście jest inny wynik (nieprawidłowy w tym przypadku)

private String getHash(String input) {
        byte[] next = input.getBytes(StandardCharsets.UTF_8);
        for (int i = 0; i < 5000; i++) {
            next = md.digest( next );
        }
        return Hex.encodeHexString( next );
    }

btw: u mnie wychodzi, że jednak DigestUtils z commons coodec (v1.13) jest szybsze.
Z tym, że tam problem ten sam, każdorazowe konwertowanie na Stringa, znacznie wydłuża :(

1

Skoro tworzenie stringów jest wolne to możesz napisać własną funkcję, która robi to co Hex.encodeHexString, tylko dla byte[] -> byte[]. Z innej strony: jaki jest sens liczenia tego hasha w ten sposób tj. 5000 razy?

0

Tylko jak się zabrać za napisanie własnej Hex.encodeHexString? Nie wiem co na co mam konwertować :(
Może jakaś wskazówka/link?
Co do hashowania 5K razy, to tak jak w tym wątku było wspominane. To narzucony wymóg biznesowy, służy prawdopodobnie temu aby ew złamanie wymagało więcej mocy obliczeniowej i czasu.

2

Nie trzeba pisać własnej:
https://commons.apache.org/proper/commons-codec/apidocs/org/apache/commons/codec/binary/Hex.html#encode-byte:A-

Ewentualnie - można zobaczyć jak jest zrobiona.
(btw. to zadanie na poziomie programisty z 2 godzinami doświadczenia... )

2

Wystarczy lekko przerobić kod z apache commons:

    private static final char[] DIGITS_LOWER = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd',
            'e', 'f' };

   protected static char[] encodeHex(final byte[] data, final char[] toDigits) {
        final int l = data.length;
        final char[] out = new char[l << 1];
        // two characters form the hex value.
        for (int i = 0, j = 0; i < l; i++) {
            out[j++] = toDigits[(0xF0 & data[i]) >>> 4];
            out[j++] = toDigits[0x0F & data[i]];
        }
        return out;
    }

na:

 private static final byte[] DIGITS = "0123456789abcdef".getBytes(StandardCharsets.US_ASCII);
   public static byte[] encodeHex(byte[] data) {
        final int l = data.length;
        final var out = new byte[l << 1];

        for (int i = 0, j = 0; i < l; i++) {
            out[j++] = DIGITS[(0xF0 & data[i]) >>> 4];
            out[j++] = DIGITS[0x0F & data[i]];
        }
        return out;
    }
0

@slsy, @jarekr000000 wielkie dzięki
Pewnie pomimo większego doświadczenia niż 2h, to z przeróbką miałbym kłopot :P
Nie znam się na tego typu konwersjach, ani kryptografii :(

odpowiedziałem już powyżej w komentarzach

Dodam tylko, że użycie użycie DigestUtils.sha512, ma tą istotną zaletę, że można uruchomić równolegle.
MessageDigest się sypie, bo chyba nie jest thread safe.
A na tym zysk jest znaczny tj ok 50%, choć to pewnie istotnie zależy od infrastruktury tj lb procesorów i rdzeni.
Porównywałem tylko lokalnie na pc, na wsadzie z 10K danych do zahashowania.

1

Jeszcze sprawdziłem kod. Okazuje się, że DigestUtils używa pod spodem MessageDigest, więc mierzenie wydajności jest bez sensu, bo testujesz tą samą implementację. To co może zwiększać CPU to fakt, że za każdym wywołaniem DigestUtils.sha512 wywoływany jest kod, który szuka implementacji przy użyciu refleksji i innych jvmowych czarów. Z doświadczenia wiem, że tego typu kod może ładnie zjadać CPU. Inna sprawa, że na pewno znalazłbyś to miejsce przy użyciu profilera np. wbudowanego w IntelliJ async-profilera działającego na unixach. Możesz popróbować z klonowaniem globalnego MessageDigest, zgaduję, że sam koszt jest niski w porównaniu do tworzenia nowego tak jak to się dzieje w DigestUtils

private MessageDigest md= MessageDigest.getInstance("SHA-512");

private String getHash(String input) {
        final var localMd = (MessageDigest) md.clone();
        byte[] next = input.getBytes(StandardCharsets.UTF_8);
        for (int i = 0; i < 5000; i++) {
            next = localMd .digest( next );
        }
        return Hex.encodeHexString( next );
    }

ewentualnie MessageDigest per thread, ale to już czarna magia, która chyba nie jest konieczna

0

mierzenie wydajności jest bez sensu

Zyski czasowe, które podawałem nie dotyczyły bezpośredniego porównania MessageDigest vs DigestUtils.sha512.
To 5% procent zysku to było na zastąpieniu Hex.encode przez Twojego .encodeHex, oba z MessageDigest :)
Natomiast 50% zysk na DigestUtils wynikał bardziej z samego zrównoleglenia niż z DigestUtils, choć może to nie do końca jasno napisałem.

Możesz popróbować z klonowaniem globalnego MessageDigest

I to jest genialne!
Dzięki, temu na MesageDigest poszło też równolegle :)
I co najlepsze zysk jest o kolejne 50% :D (vs rownolegle z DigestUtils, oba z Twoim .encodeHex)
I jak puszcze oba szeregowo to MessageDigest też jest szybsze.

Myślę, że to jest zgodne z Twoim tokiem myślenia i benchmarkiem, który @jarekr000000 zrobił.
Początkowo mi opcja z DigestUtils szybciej działała, ale to pewnie przez to, że było jeszcze na Stringach.

Dzięki !!!

1 użytkowników online, w tym zalogowanych: 0, gości: 1