On 26/08/25 06:19, Alexei Starovoitov wrote:
On Mon, Aug 25, 2025 at 10:30 AM Nandakumar Edamana
<nandakumar@xxxxxxxxxxxxxxxx> wrote:
This commit addresses a challenge explained in an open question ("How
can we incorporate correlation in unknown bits across partial
products?") left by Harishankar et al. in their paper:
https://arxiv.org/abs/2105.05398
Either drop this paragraph or add the details inline.
Okay, I'll drop it from the commit message and add it to the code like
this, since it's useful information:
diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
index c98aa148e666..4c82f3ede74e 100644
--- a/kernel/bpf/tnum.c
+++ b/kernel/bpf/tnum.c
@@ -116,7 +116,7 @@ struct tnum tnum_xor(struct tnum a, struct tnum b)
return TNUM(v & ~mu, mu);
}
-/* Perform long multiplication, iterating through the trits in a:
+/* Perform long multiplication, iterating through the bits in a using
rshift:
* - if LSB(a) is a known 0, keep current accumulator
* - if LSB(a) is a known 1, add b to current accumulator
* - if LSB(a) is unknown, take a union of the above cases.
@@ -132,6 +132,11 @@ struct tnum tnum_xor(struct tnum a, struct tnum b)
* xx 00 11
* ------ ------ ------
* ???? 0011 1001
+ *
+ * Considering cases LSB(a) = known 0 and LSB(a) = known 1 separately and
+ * taking a union addresses a challenge explained in an open question ("How
+ * can we incorporate correlation in unknown bits across partial
products?")
+ * left by Harishankar et al. in their paper:
https://arxiv.org/abs/2105.05398
*/
struct tnum tnum_mul(struct tnum a, struct tnum b)
{
When LSB(a) is uncertain, we know for sure that it is either 0 or 1,
from which we could find two possible partial products and take a
union. Experiment shows that applying this technique in long
multiplication improves the precision in a significant number of cases
(at the cost of losing precision in a relatively lower number of
cases).
This commit also removes the value-mask decomposition technique
employed by Harishankar et al., as its direct incorporation did not
result in any improvements for the new algorithm.
Please rewrite commit using imperative language.
This will be my new message:
bpf: Improve the general precision of tnum_mul
Drop the value-mask decomposition technique and adopt straightforward
long-multiplication with a twist: when LSB(a) is uncertain, find the
two partial products (for LSB(a) = known 0 and LSB(a) = known 1) and
take a union.
Experiment shows that applying this technique in long multiplication
improves the precision in a significant number of cases (at the cost
of losing precision in a relatively lower number of cases).
Using uppercase for the character after "bpf: " this time, just to be
consistent with other commits.
Similar changes for PATCH 2/2.
"trit" is not used anywhere in the code.
Use "ternary digit" instead.
Changing it to "bits" since other comments in the file already use it to
mean trit (also, "digit" could be confused for a decimal thing). With
another clarification, "iterating through the trits in a" now becomes
"iterating through the bits in a using rshift". Hope it's okay.
I'll send v6 after waiting for a while for further feedback, if any.
Keep acks when respining.
Sorry, I didn't get this. Is this something I need to do?
--
Nandakumar
