[Alg] Custom Hash functie: gericht op snelheid*

[Verwijderd]

Hallo,

Ik probeer momenteel een functie te maken die sneller is dan de bestaande MD5 hash functie (als ik mij niet vergis is dit één van de snellere). De reden hiervoor is dat ik hash tables wil maken maar dat MD5 nog te langzaam is. Een verminderde veiligheid en een acceptabel aantal collisions zijn geen probleem. Het is idee is puur om een hele snelle lookup table te krijgen.

Dit is mijn pseudocode:

code:

Array convert => a=1, b=2, c=3 en zo voort tot en met z=26

String to_be_hashed_string
integer index

for loop ( i = 0 ; i <= length ( to_be_hashed_string) ; ++i )
  index += pow ( convert[substring(to_be_hashed_string, i, 1)], i )
end for

print index

Bij elke iteratie zal 'i' 1 omhoog gaan, door het gebruik van exponenten (pow) worden de enorme aantallen collisions tegen gegaan die er normaal zouden zijn bij het enkel optellen van de a <=> z cijfers.

Dus even meerdere malen getest maar wat blijkt: mijn functie is veel trager. Ik heb weliswaar in PHP getest, dus wellicht dat daar de built-in functies het verschil maken in snelheid.

MD5 hash functie
Resultaat: c18427314aa891c19a3c4e388211eb94
Duratie: 1.8 microseconden

Mijn custom hash functie
Resultaat: 1.6514813305334E+29
Duratie: 7.1 microseconden

Weet iemand een implementatie die potentieel sneller zou kunnen zijn voor in ieder geval PHP, C++ of Perl is wat mij betreft ook prima.

[ Voor 12% gewijzigd door Verwijderd op 29-05-2012 00:48 ]

[Verwijderd]

MD5 is een trage hashfunctie, en is ook niet ontworpen om snel te zijn.
Maar er zijn zat snelle hashfuncties te vinden op het internet, je moet ze misschien even vertalen naar PHP code. En de ene functie is de andere niet, als je een beperkt aantal mogelijkheden hebt qua invoer, kun je met een generator aan de gang, en dat zorgt sowieso voor een enorm snelle oplossing.

[RobIII]

Verwijderd schreef op dinsdag 29 mei 2012 @ 00:40:
MD5 hash functie
Duratie: 1.8 microseconden

Mijn custom hash functie
Duratie: 7.1 microseconden

Dat is geen meting (even aangenomen dat dit een enkele meting is dan; ik zie er verder niets over terug).
Voor 'tzelfde geld was je OS even bezig met who-knows-what. Als je dit meet dan doe je dat over vele iteraties, niet een enkele call (en neem dit dan even mee).

Voor een vergelijk van een aantal hashfuncties, collisions, snelheid kun je hier eens kijken.

Verder ben ik vooral eens benieuwd naar waarom een van de vele (andere dan MD5) hashfuncties niet voor je voldoet. Heb je die al overwogen? Of ben je, misschien, 't wiel opnieuw aan 't uitvinden?

[ Voor 88% gewijzigd door RobIII op 29-05-2012 01:07 ]

[.oisyn]

En hoeveel significante cijfers kan een floating point getal op kan slaan, denk je? Je hashfunctie is dus nogal bogus, de eerste paar tekens hebben totaal geen betekenis omdat de orde van grootte van de laatste paar tekens significant veel groter is.

RobIII schreef op dinsdag 29 mei 2012 @ 00:55:
Als je dit meet dan doe je dat over vele iteraties, niet een enkele call (en neem dit dan even mee).

Nou ben ik wel benieuwd hoe je tot die conclusie komt, want ik lees iets dergelijks niet terug in de topicstart. Sterker nog, hij zegt:

Dus even meerdere malen getest maar wat blijkt: mijn functie is veel trager.

[ Voor 49% gewijzigd door .oisyn op 29-05-2012 01:11 ]

[RobIII]

.oisyn schreef op dinsdag 29 mei 2012 @ 01:09:
Nou ben ik wel benieuwd hoe je tot die conclusie komt, want ik lees iets dergelijks niet terug in de topicstart. Sterker nog, hij zegt:

Ik las dat als:

code:

function HashA() {
...
}

function HashB() {
...
}

Time HashA('Hello world');
Time HashB('Hello world');

En daarna 't script 5 keer runnen.

Maar goed, ik kan me vergissen. Daarom schreef ik ook:

RobIII schreef op dinsdag 29 mei 2012 @ 00:55:
(even aangenomen dat dit een enkele meting is dan; ik zie er verder niets over terug).

Wat betreft de hashfunctie van TS: die is inderdaad redelijk nutteloos. Vandaar ook mijn linkje naar een post die wat uitgebreider is dan een Wikipedia linkje met een "list of hashfunctions".

[ Voor 38% gewijzigd door RobIII op 29-05-2012 01:20 ]

[.oisyn]

Dus je kunt wel een artikel uit je mouw schudden over statistiek, maar geeneen over het doen van aannames?

[ Voor 8% gewijzigd door .oisyn op 29-05-2012 01:21 ]

[Soultaker]

Er zijn al zoveel snelle, niet-cryptografische hashfunctions. FNV, SuperFastHash, Murmur, Jenkins, SpookyHash, CityHash en dat is nog maar een kleine greep uit het aanbod dat me in het hoofd schiet.

Een CRC32 checksum werkt ook uitstekend als een hashfunctie; dat is vooral een interessante optie als je processoren met SSE 4.2 support target want die hebben native support voor het berekenen van CRC32 checksums. Op die processoren denk ik dat je weinig beters kunt verzinnen, mits 32 bits output voldoende is.

Verwijderd schreef op dinsdag 29 mei 2012 @ 00:48:
MD5 is een trage hashfunctie, en is ook niet ontworpen om snel te zijn.

Dat is een misvatting. MD5 is wél ontworpen om snel te zijn; daar worden cryptografische hashfuncties op geselecteerd. MD5 moest echter ook cryptografisch secure zijn, en daarom is het minder snel dan de niet-cryptografische hash functies die ik hierboven noemde. Op zichzelf is MD5 (of oudere en nog snellere varianten als MD4) daarom niet direct ongeschikt, maar functies die onveilig mogen zijn zullen in de praktijk altijd sneller zijn.

[ Voor 26% gewijzigd door Soultaker op 29-05-2012 03:03 ]

[Voutloos]

Linkje met wat hash algo's en benchmarks: http://programmers.stacke...s-and-speed/145633#145633

[.oisyn]

Was al gepost.
Desalniettemin, ik denk dat zolang je je hash algoritme in PHP implementeert je nooit de snelheid van de built-in MD5 kunt toppen. Al helemaal omdat de echt snelle implementaties gestoeld zijn op specifieke CPU instructies. Kwa algoritmische complexiteit valt er niets te winnen, ze zijn allemaal wel O(n).

[ Voor 66% gewijzigd door .oisyn op 29-05-2012 13:59 ]

[Mental]

Stukje proza wat hier blijkbaar relevant is: http://blogs.yourdiscover...ther-of-all-fuck-ups.html

[Verwijderd]

Thanks allemaal. Het is niet te geloven hoe traag PHP kan zijn, als het gaat om niet built-in functies. Afhankelijk van onze gekozen talen voor het systeem dat we gebruiken moest ik kiezen tussen PHP en Perl, dat wordt dus Perl.

[.oisyn]

Ik denk niet dat Perl in dat opzicht zoveel sneller is hoor.

[Verwijderd]

Het ding was een beetje dat ik geen PHP built-in functies wil gebruiken, omdat die an sich al te langzaam zijn voor mij. De built-in functies zijn niet te verslaan met custom functies.

Bij Perl zijn het juist die CPAN packages die juist wel vergelijkbaar zijn in snelheid, daarom redeneerde ik dat daar potentieel meer te winnen valt.

[.oisyn]

Ah, fair enough. Eventueel zou je nog kunnen overwegen om een PHP module te maken waar je favo hash functie native in geïmplementeerd is.