Rendered at 20:53:11 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
guyomes 6 hours ago [-]
One book cited several times in the preprint of OP is the volume 2 of the famous book series of Knuth, The Art of Computer Programming, notably its section 4.6.4. For readers interested in this kind of results, it is a really interesting gathering of classical theorems and useful tricks to evaluate quickly polynomials.
emil-lp 12 hours ago [-]
I read your arxiv paper yesterday (or was it the day before).
Do you think this can be used to speed up the algebraic method for k-path?
If so, you should enter next years PACE challenge.
thomasahle 10 hours ago [-]
I'm not sure, since we only do univariate polynomials and k-path has lots of variables, right?
But maybe this work can inspire looking for other small, constant factor saving circuits for different classes of polynomials. Would be cool!
pvillano 14 hours ago [-]
This is super cool. I learned a lot playing with the demo. I only knew Horner and Estrin, but I think I've gotten a grasp on most of them.
One small change I'd recommend is for the graph visualization, have a separate source node for each x, x^2, x^4 used. A single x source clutters the graph and hides the structure.
thomasahle 14 hours ago [-]
Thank you! It was a lot of fun to make the website and see all the methods in practice after having just looked at the theory for a long time :D
> have a separate source node for each x, x^2, x^4 used
I forgot that the purpose of your site is comparing the number of mults. A more compatible idea is to rearrange the nodes so that any repeated squaring is always in a single row at the top. The graph would have the same nodes and connectivity, but a more structured flow. If I ever make my own comparison of polynomial evaluation strategies I'll do manual layout.
For completeness: To apply my original idea to R&W9 you would have 5 nodes labeled x, each with one arrow out, two nodes labeled x^2, each with no arrows in and one arrow out, one node labeled x^4 with no arrows in and one arrow out, one node labeled x^8 with no arrows in and one arrow out. Three missing mults, but way fewer crossings, not what you want.
IsTom 12 hours ago [-]
Pretty cool, especially in finite fields. Though coefficients seem to blow up pretty quick in Q?
thomasahle 11 hours ago [-]
It's the blessing and the course of a polynomial inverse: the inverse is the same degree as the polynomial, so its largest coeffecient is large and blows up.
Knuth-Eve and Pan use the root of a degree d polynomial, which is slightly less big, but still inpractical.
voxelghost 18 hours ago [-]
It keeps flipping back to 'monic' from e.g. 'ln(1+x)' when switching between algorithms, and then seems to lock to 'monic'? (Am I missing something?)
Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?
gowld 18 hours ago [-]
"monic" is a separate switch from the example functions radio-selector. Enabling "monic" removes the leading coefficient.
thomasahle 15 hours ago [-]
[dead]
throwaway81523 15 hours ago [-]
If you're going to preprocess the polynomial, maybe you want to evaluate it at many different points. But then why not use the FFT?
thomasahle 14 hours ago [-]
FFT multipoint evaluation is great when you know all the evaluation points in advance. However, for many practical applications the input is only streamed to you. E.g. a polynomial hash for a hashmap. Or preprocessing the taylor approximation of exp(x) for a standard library.
1 days ago [-]
vlovich123 18 hours ago [-]
Would this be applicable to fast hashes like WyHash and xxh3 or are those not using polynomials? Is this mainly for faster cryptographic hashes?
thomasahle 15 hours ago [-]
WyHash and xxh3 are not polynomial, in fact this is one of the issues we try to solve in the paper.
Many "practical" hashes use heuristics instead of real field multiplications to be faster. But it means they are vulnerable to adversarial inputs. That means, it's possible to design a set of keys that have much higher probability (under random hash seeds/keys) to collide than you'd expect under a correct hash function.
It is applicable to fast universal hashes like Poly1305 and Polymur (the latter of which I'm the author). However it's not clear to me whether this work improves over the state of the art for that purpose, see some questions here: https://www.reddit.com/r/programming/comments/1wbgcke/comput....
This purpose is however much easier/flexible than actual polynomial equivalence since the requirement here is only that the polynomial is injective, not identical.
WyHash and xxh3 do not have polynomial structures.
adrian_b 15 hours ago [-]
It is applicable, but it is not useful.
Universal hashes use the input text as the set of coefficients.
This method requires additional preprocessing of the coefficients, before starting to evaluate the polynomial. That preprocessing would slow the hashing algorithm more than what is gained during evaluation.
This method is useful only when with a given polynomial, i.e. set of polynomial coefficients, you want to evaluate that polynomial many times, so the cost of the preprocessing is amortized.
However, this application is very important because most functions are approximated either with polynomials or with rational functions, so this method can accelerate the evaluation of all such approximated functions.
thomasahle 14 hours ago [-]
> This method requires additional preprocessing of the coefficients, before starting to evaluate the polynomial. That preprocessing would slow the hashing algorithm more than what is gained during evaluation.
There is no preprocessing at hash time in either use.
Universal hashing: the message words are the parameters of the chain, a_i and b_i
in P_i = a_i + (b_i + y)(P_{i−1} + u), not coefficients of a target polynomial.
Distinct messages give distinct polynomials, which is all a universal hash needs;
the decoder never runs. Same as Bernstein's BRW.
k-independent hashing: the key should be a uniformly random monic polynomial of
degree k. Our parameterisation is a bijection onto those polynomials, with the
rational preprocessing as its inverse, so uniformly random gate constants give a
uniformly random polynomial. You draw the ⌊k/2⌋+1 constants and evaluate; the
coefficients are never computed. That is why the paper needs bijective rather than
just injective constructions, and the Section 5 speedups are for the whole hash.
Preprocessing only appears when a fixed polynomial (a Taylor approximation, a
secret-sharing polynomial) is evaluated at many points, and then it runs once.
adrian_b 13 hours ago [-]
There are many kinds of universal hashing, many of which are not based on polynomial evaluation.
However, the most common kinds of universal hashing, i.e. those which are used for computing message authentication codes (MAC) in the TLS and SSH protocols (using poly1305 or GCM), are based on polynomial evaluation, where the message is the sequence of coefficients of the polynomial and the secret key of the MAC is the value at which the polynomial is evaluated.
The polynomial corresponding to a MAC is evaluated only once at the sender and once at the receiver, usually in a single pass over the data, simultaneously with its encryption or decryption. Frequently the reading or writing of the data from/to the main memory limits the throughput of the MAC computation (caches do not help, because the data is not reused), in which case a better algorithm than Horner cannot provide significant speed-ups.
Besides their application in MACs, which is ubiquitous now in Internet communication, I consider the other applications of universal hashing as minor, because the "universality" property of such hashes seldom provides any substantial benefit over alternative hash functions that do not have this property, but which guarantee other more useful properties. (The "universality" property is just a statistical property of a family of hash functions, while instantiated universal hashes may happen to be quite bad hash functions. For instance, in AES-GCM it is possible to choose by bad luck a secret key for which some reordered messages have the same hash value with the original message, so tampering with the message remains undetected. Fortunately, the adversary cannot guess when the sender has chosen a bad secret key, in order to try to alter the message.)
thomasahle 11 hours ago [-]
> the "universality" property of such hashes seldom provides any substantial benefit over alternative hash functions that do not have this property
Do you mean hashes like xxh3?
We have a section in the paper showing for a bunch of these that they collide much more often than universal hashes on bad inputs.
adrian_b 10 hours ago [-]
No, though even a hash like xxh3 can be useful when speed is more important than collision resistance.
There are many hashes that use more thorough mixing functions than can be achieved with one or a few arithmetic operations (like in universal hashes), thus for them the collision probability reaches the limit imposed by the length of the hash value. Modern CPUs have various instructions that can be exploited in mixing functions that have about the same speed as simpler arithmetic operations, but which achieve a better mixing.
An example is the Alred construction (Joan Daemen & Vincent Rijmen, in 2005-02), which was inspired by the old CBC-MAC algorithm, but it is much more efficient (in this construction, the hash mixing function is derived from the internal mixing function used in some block cipher function, for example the AES block cipher function, so it can be implemented with the AES round function instructions of x86-64 and Aarch64, which are very fast in modern processors; this hash function uses the AES instructions but it is several times faster than the AES encryption/decryption algorithms, which are already very fast).
Another example is any hash function that has the structure used in the Jutla authentication method (Charanjit Singh Jutla @ IBM, patent filed on 2000-04-14; many other patents were filed on variants of this, but now they are expired or invalid; in this method, the input text is partitioned in blocks with the length equal to the hash length, then a parallel mixing function transforms each input text block into a scrambled text, in a different space of values, then in the transformed space a simple additive function, even the simplest, which is bitwise addition modulo 2, can be used to reduce the transformed message to a single intermediate hash value, and finally the inverse of the mixing function is applied to the intermediate hash value to produce the final hash value by going back to the original space of values; this makes the computation of the hash parallelizable, thus very fast; an LFSR, i.e. linear-feedback shift register, is used to generate a non-repeating sequence that is added to each block, both before and after applying the mixing transformation, to make the hash depend on the order of the input blocks, i.e. this is equivalent with using a different mixing function for each block; there are universal hashes based on scalar products which have the same structure like this, but the difference is that they use a simple multiplication instead of a complex mixing function).
Another example is the HighwayHash, developed at Google in 2016, and optimized for SIMD instructions of AVX2 or SSE4.1 or IBM POWER VSX or Arm Aarch64.
Such hash functions were developed first in cryptographic contexts, i.e. as keyed hash functions, a.k.a. message-authentication codes.
Nonetheless, because modern CPUs now include a lot of instructions for the acceleration of cryptographic algorithms, such hash functions can be used now for any other hashing applications, because on modern CPUs they can be as fast or even faster than traditional hash functions with simple arithmetic operations.
thomasahle 6 hours ago [-]
It's true that you can use AES instructions now on some computers, bit I honestly don't see why you'd use a heuristic hash (even if cryptographic) when you can get provable guarantees with k-wise independent hashing. Our paper makes these even faster than they already were.
See section 5.7 and 5.8 in the paper for experiments against other hashes.
vlovich123 4 hours ago [-]
You benchmarked a really old heuristic hash in Murmur and xxh64. xxh3 is ~1.6x to 1.8x faster than xxh64 - extrapolating that to 5.7 in your paper puts it at ~18-27% faster. WyHash and UMash sometimes report faster numbers.
Even xxh3 isn't the cutting edge - gxhash (~1.8x faster) and aesni (~1.5x faster) use AES instructions. Compared to your approach that perf disparity should grow to ~30-40%.
Hopefully that answers your question about why someone might still choose to use heuristic hashing rather than k-wise independent hashing when collision resistance isn't critical.
huhtenberg 11 hours ago [-]
* "monic" = the leading coefficient is 1
NooneAtAll3 10 hours ago [-]
> non-monic input costs 1 extra scalar multiplication
I guess that's covered
aetherspawn 19 hours ago [-]
I guess it’s not faster than using a table for CRC8?
thomasahle 14 hours ago [-]
In CRC8 you interpret the input as coefficients of a polynomial, and take mod `x⁸ + x² + x + 1`.
The problem we solve here is a bit different: You know the coefficients in advance, and want to preprocess the polynomial to make it fast to evaluate.
However, in section "5.9 Injective Polynomial Hashing" we actually study the problem of universal hashing, which is a lot more like CRC8.
From the abstract, a name that many on HN would recognize:
> We also give an injective polynomial construction for universal hashing that uses N multiplications to hash 2N values with a single random key. This improves the best previous construction by Daniel J. Bernstein (this http URL).
It's a very nice construction (based on Rabin & Winograd's polynomial multiplication method) for building universal hashes with n/2+O(logn) multiplications.
The annoying part is that it's a tree structure, which is not usually what you want in a fast hash that you're folding over a data stream. Some papers like https://eprint.iacr.org/2017/328.pdf try to fix this, but there are a lot of annoying trade-offs.
It takes advantage of FMA (fused multiply add), has good numeric stability and uses pipelining optimally.
A while ago I suggested using Estrin's method in Boost, for functions like std::exp. There's some interesting discussions here: https://github.com/boostorg/math/issues/924 if you are interested in all the practical details.
However, for finite fields (e.g. used for hashing and cryptography) multiplication is much more expensive than addition, which is the main use of this algorithm.
LegionMammal978 15 hours ago [-]
Yeah, I just recently learned about Estrin's method when fooling around with some polynomial approximations. I'd been scaling the output by a sqrt term to get better accuracy at small degrees, but it turned out that polynomials of very large degrees can be calculated in the same time as a single correctly-rounded sqrt, especially when fma is available. Seemingly, the only real cost is the added register pressure.
The length of an expression when written out can definitely be deceiving when pipelining is added to the mix.
adrian_b 15 hours ago [-]
In modern computers, the throughput of an execution unit is the same for multiplications and additions, but multiplication frequently has a greater latency, by 1 or 2 clock cycles.
Many CPUs, like the AMD Zen CPUs, have more execution units that can do additions, than those that can do multiplications. So the aggregated throughput over all execution units can be higher for additions than for multiplications.
For example, for floating-point numbers, the AMD Zen CPUs have 4 vector execution units, where all 4 can do additions, but only 2 of them can do multiplications or fused multiply-add operations. So Zen CPUs can do up to 4 additions + 2 multiplications per clock cycle (when 2 multiplication-addition pairs are fused).
Someone 13 hours ago [-]
> Many CPUs, like the AMD Zen CPUs, have more execution units that can do additions, than those that can do multiplications
And the reasons for that it takes way more transistors to implement a fast rabbit^W multiplier than to implement a fast adder, so adding an execution unit that cannot multiply is easier to warrant than adding one that can.
nraynaud 17 hours ago [-]
Just a few years ago, mults were slower, but I think now (Intel i9) mult, add and fma are the same.
The answer's all over the place with each successive CPU generation. Originally Intel CPUs had adds faster than multiplies, then both went through the FMA unit so they were the same, then they added a fast FP adder, etc. And current timings on uops.info now show FP fma 4c and mul 3c over two multiply units, and add 2c over two separate addition units.
gigatexal 18 hours ago [-]
I think multiplications are faster to do in computer land than adds? I too am curious.
hyperhello 18 hours ago [-]
Also could use analysis of dependencies to see what can happen in parallel. Or for that matter, some real benchmarks.
Do you think this can be used to speed up the algebraic method for k-path?
If so, you should enter next years PACE challenge.
But maybe this work can inspire looking for other small, constant factor saving circuits for different classes of polynomials. Would be cool!
One small change I'd recommend is for the graph visualization, have a separate source node for each x, x^2, x^4 used. A single x source clutters the graph and hides the structure.
> have a separate source node for each x, x^2, x^4 used
Do you mean a graph like this R&W? https://thomasahle.com/fast-polynomials/#ex=bessel&mode=Q&me... there are nodes labeled x2, x4, x8; but it's the output of multiplications, and we want to make the number of mults visually clear.
For completeness: To apply my original idea to R&W9 you would have 5 nodes labeled x, each with one arrow out, two nodes labeled x^2, each with no arrows in and one arrow out, one node labeled x^4 with no arrows in and one arrow out, one node labeled x^8 with no arrows in and one arrow out. Three missing mults, but way fewer crossings, not what you want.
Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?
Many "practical" hashes use heuristics instead of real field multiplications to be faster. But it means they are vulnerable to adversarial inputs. That means, it's possible to design a set of keys that have much higher probability (under random hash seeds/keys) to collide than you'd expect under a correct hash function.
We actually analyze both WyHash and xxh3 in this setting in section "Adversarial inputs for heuristic hashes" - https://arxiv.org/pdf/2609.06022#page=165
This purpose is however much easier/flexible than actual polynomial equivalence since the requirement here is only that the polynomial is injective, not identical.
WyHash and xxh3 do not have polynomial structures.
Universal hashes use the input text as the set of coefficients.
This method requires additional preprocessing of the coefficients, before starting to evaluate the polynomial. That preprocessing would slow the hashing algorithm more than what is gained during evaluation.
This method is useful only when with a given polynomial, i.e. set of polynomial coefficients, you want to evaluate that polynomial many times, so the cost of the preprocessing is amortized.
However, this application is very important because most functions are approximated either with polynomials or with rational functions, so this method can accelerate the evaluation of all such approximated functions.
There is no preprocessing at hash time in either use.
Universal hashing: the message words are the parameters of the chain, a_i and b_i in P_i = a_i + (b_i + y)(P_{i−1} + u), not coefficients of a target polynomial. Distinct messages give distinct polynomials, which is all a universal hash needs; the decoder never runs. Same as Bernstein's BRW.
k-independent hashing: the key should be a uniformly random monic polynomial of degree k. Our parameterisation is a bijection onto those polynomials, with the rational preprocessing as its inverse, so uniformly random gate constants give a uniformly random polynomial. You draw the ⌊k/2⌋+1 constants and evaluate; the coefficients are never computed. That is why the paper needs bijective rather than just injective constructions, and the Section 5 speedups are for the whole hash.
Preprocessing only appears when a fixed polynomial (a Taylor approximation, a secret-sharing polynomial) is evaluated at many points, and then it runs once.
However, the most common kinds of universal hashing, i.e. those which are used for computing message authentication codes (MAC) in the TLS and SSH protocols (using poly1305 or GCM), are based on polynomial evaluation, where the message is the sequence of coefficients of the polynomial and the secret key of the MAC is the value at which the polynomial is evaluated.
The polynomial corresponding to a MAC is evaluated only once at the sender and once at the receiver, usually in a single pass over the data, simultaneously with its encryption or decryption. Frequently the reading or writing of the data from/to the main memory limits the throughput of the MAC computation (caches do not help, because the data is not reused), in which case a better algorithm than Horner cannot provide significant speed-ups.
Besides their application in MACs, which is ubiquitous now in Internet communication, I consider the other applications of universal hashing as minor, because the "universality" property of such hashes seldom provides any substantial benefit over alternative hash functions that do not have this property, but which guarantee other more useful properties. (The "universality" property is just a statistical property of a family of hash functions, while instantiated universal hashes may happen to be quite bad hash functions. For instance, in AES-GCM it is possible to choose by bad luck a secret key for which some reordered messages have the same hash value with the original message, so tampering with the message remains undetected. Fortunately, the adversary cannot guess when the sender has chosen a bad secret key, in order to try to alter the message.)
Do you mean hashes like xxh3? We have a section in the paper showing for a bunch of these that they collide much more often than universal hashes on bad inputs.
There are many hashes that use more thorough mixing functions than can be achieved with one or a few arithmetic operations (like in universal hashes), thus for them the collision probability reaches the limit imposed by the length of the hash value. Modern CPUs have various instructions that can be exploited in mixing functions that have about the same speed as simpler arithmetic operations, but which achieve a better mixing.
An example is the Alred construction (Joan Daemen & Vincent Rijmen, in 2005-02), which was inspired by the old CBC-MAC algorithm, but it is much more efficient (in this construction, the hash mixing function is derived from the internal mixing function used in some block cipher function, for example the AES block cipher function, so it can be implemented with the AES round function instructions of x86-64 and Aarch64, which are very fast in modern processors; this hash function uses the AES instructions but it is several times faster than the AES encryption/decryption algorithms, which are already very fast).
Another example is any hash function that has the structure used in the Jutla authentication method (Charanjit Singh Jutla @ IBM, patent filed on 2000-04-14; many other patents were filed on variants of this, but now they are expired or invalid; in this method, the input text is partitioned in blocks with the length equal to the hash length, then a parallel mixing function transforms each input text block into a scrambled text, in a different space of values, then in the transformed space a simple additive function, even the simplest, which is bitwise addition modulo 2, can be used to reduce the transformed message to a single intermediate hash value, and finally the inverse of the mixing function is applied to the intermediate hash value to produce the final hash value by going back to the original space of values; this makes the computation of the hash parallelizable, thus very fast; an LFSR, i.e. linear-feedback shift register, is used to generate a non-repeating sequence that is added to each block, both before and after applying the mixing transformation, to make the hash depend on the order of the input blocks, i.e. this is equivalent with using a different mixing function for each block; there are universal hashes based on scalar products which have the same structure like this, but the difference is that they use a simple multiplication instead of a complex mixing function).
Another example is the HighwayHash, developed at Google in 2016, and optimized for SIMD instructions of AVX2 or SSE4.1 or IBM POWER VSX or Arm Aarch64.
Such hash functions were developed first in cryptographic contexts, i.e. as keyed hash functions, a.k.a. message-authentication codes.
Nonetheless, because modern CPUs now include a lot of instructions for the acceleration of cryptographic algorithms, such hash functions can be used now for any other hashing applications, because on modern CPUs they can be as fast or even faster than traditional hash functions with simple arithmetic operations.
See section 5.7 and 5.8 in the paper for experiments against other hashes.
Even xxh3 isn't the cutting edge - gxhash (~1.8x faster) and aesni (~1.5x faster) use AES instructions. Compared to your approach that perf disparity should grow to ~30-40%.
Hopefully that answers your question about why someone might still choose to use heuristic hashing rather than k-wise independent hashing when collision resistance isn't critical.
I guess that's covered
However, in section "5.9 Injective Polynomial Hashing" we actually study the problem of universal hashing, which is a lot more like CRC8.
> We also give an injective polynomial construction for universal hashing that uses N multiplications to hash 2N values with a single random key. This improves the best previous construction by Daniel J. Bernstein (this http URL).
It's a very nice construction (based on Rabin & Winograd's polynomial multiplication method) for building universal hashes with n/2+O(logn) multiplications.
The annoying part is that it's a tree structure, which is not usually what you want in a fast hash that you're folding over a data stream. Some papers like https://eprint.iacr.org/2017/328.pdf try to fix this, but there are a lot of annoying trade-offs.
A famous fast hash is NH, which is just:
where `a_i` are random keys. No modulus needed. The issue is that you need as many random keys as the length of the input.Our construction (section 5.9 Injective Polynomial Hashing) shows that you can do something a bit similar with polynomials:
this is a lot simpler than Bernstein's, and is still n/2 multiplications.It takes advantage of FMA (fused multiply add), has good numeric stability and uses pipelining optimally.
A while ago I suggested using Estrin's method in Boost, for functions like std::exp. There's some interesting discussions here: https://github.com/boostorg/math/issues/924 if you are interested in all the practical details.
However, for finite fields (e.g. used for hashing and cryptography) multiplication is much more expensive than addition, which is the main use of this algorithm.
The length of an expression when written out can definitely be deceiving when pipelining is added to the mix.
Many CPUs, like the AMD Zen CPUs, have more execution units that can do additions, than those that can do multiplications. So the aggregated throughput over all execution units can be higher for additions than for multiplications.
For example, for floating-point numbers, the AMD Zen CPUs have 4 vector execution units, where all 4 can do additions, but only 2 of them can do multiplications or fused multiply-add operations. So Zen CPUs can do up to 4 additions + 2 multiplications per clock cycle (when 2 multiplication-addition pairs are fused).
And the reasons for that it takes way more transistors to implement a fast rabbit^W multiplier than to implement a fast adder, so adding an execution unit that cannot multiply is easier to warrant than adding one that can.
https://stackoverflow.com/a/39135689