[PATCH] optimize "weight" in BasicOperator

[Qian Yun]

This patch optimizes "weight" related stuff in BasicOperator.

Before this patch, each comparison in BOP (which is common
since Kernel comparison requires it) need to get '%weight'
property which can be costly since it needs to traverse
the whole property list and do allocation because of "failed".

I have a test file that contains 81907 expressions, reading
them requires ~46s and 15.8GB, after patch requires ~44s
and 15.0GB.

- Qian

[Waldek Hebisch]

On Mon, Jul 20, 2026 at 08:26:17PM +0800, Qian Yun wrote:
> This patch optimizes "weight" related stuff in BasicOperator.
>
> Before this patch, each comparison in BOP (which is common
> since Kernel comparison requires it) need to get '%weight'
> property which can be costly since it needs to traverse
> the whole property list and do allocation because of "failed".

In cases that are performance critical and where representation
of actual type does not contain Lisp NIL we could use internal
function that returns Lisp NIL. We do such things in rare
cases but most of the time I consdered speed gain to be too
small to justify more complicated code.

For "popular" properties that mostly have default values
we could have a single field with bits working as flags
to singal if property has default value or it should be
searched for on property list.

In general I try to limit number of fields in various
data structures. Namely, bigger data structures need
more space in caches which tends to decrease chache
hit ratio, consequently leading to slowdown. In
case of operators this probably is not a big deal
as there should be rather small number of operator
nodes (due to kernel caching operators are shared).

> I have a test file that contains 81907 expressions, reading
> them requires ~46s and 15.8GB, after patch requires ~44s
> and 15.0GB.

If you want go on. AFAICS you are looking here at rather small
gains, which is worthwile but can use a lot of effort (also
to verify that actually there is a gain overall).

> diff --git a/src/algebra/jet.spad b/src/algebra/jet.spad
> index 5096d602..2f991db3 100644
> --- a/src/algebra/jet.spad
> +++ b/src/algebra/jet.spad
> @@ -2165,8 +2165,7 @@ JetBundle(IVar : LS, DVar : LS) : Cat == Def where
> display(jop, opdisp)
> tmp : None := coerce(jv)$NoneFunctions1(%)
> jop := setProperty(jop, "%symbol"::SY, tmp)$BOP
> - tmp := coerce(weight(jv))$NoneFunctions1(NNI)
> - jop := setProperty(jop, "%weight"::SY, tmp)$BOP
> + jop := weight(jop, weight(jv))$BOP
> tmp := coerce(type(jv))$NoneFunctions1(SY)
> jop := setProperty(jop, "%jet"::SY, tmp)$BOP
> arg : L EI := concat!([opname::EI, index(jv)::EI], _
> @@ -2304,8 +2303,7 @@ IndexedJetBundle(x, u, p, n, m) : Cat == Def where
> display(jop, opdisp)
> tmp : None := coerce(jv)$NoneFunctions1(%)
> jop := setProperty(jop, "%symbol"::SY, tmp)$BOP
> - tmp := coerce(weight(jv))$NoneFunctions1(NNI)
> - jop := setProperty(jop, "%weight"::SY, tmp)$BOP
> + jop := weight(jop, weight(jv))$BOP
> tmp := coerce(type(jv))$NoneFunctions1(SY)
> jop := setProperty(jop, "%jet"::SY, tmp)$BOP
> if getNotation() = Multi then
> diff --git a/src/algebra/op.spad b/src/algebra/op.spad
> index 3c88b165..e6334429 100644
> --- a/src/algebra/op.spad
> +++ b/src/algebra/op.spad
> @@ -10,6 +10,7 @@ BasicOperator() : Exports == Implementation where
> O ==> OutputForm
> P ==> AssociationList(Symbol, None)
> L ==> List Record(key : Symbol, entry : None)
> + N ==> NonNegativeInteger
> SEX ==> InputForm
>
> Exports ==> OrderedSet with
> @@ -89,7 +90,9 @@ BasicOperator() : Exports == Implementation where
>
> Implementation ==> add
> -- if narg < 0 then the operator has variable arity.
> - Rep := Record(opname : Symbol, narg : SingleInteger, props : P)
> + -- property WEIGHT allows one to change the ordering around
> + -- by default, every operator has weight 1
> + Rep := Record(opname : Symbol, narg : SingleInteger, weight : N, props : P)
>
> import from P
> import from SingleInteger
> @@ -99,24 +102,24 @@ BasicOperator() : Exports == Implementation where
> -- some internal properties
> LESS? := "%less?"::Symbol
> EQUAL? := "%equal?"::Symbol
> - WEIGHT := '%weight
> DISPLAY := '%display
> SEXPR := '%input
>
>
> - oper : (Symbol, SingleInteger, P) -> %
> + oper : (Symbol, SingleInteger, N, P) -> %
>
> is?(op, s) == name(op) = s
> name op == op.opname
> properties op == op.props
> setProperties(op, l) == (op.props := l; op)
> - operator s == oper(s, -1::SingleInteger, table())
> - operator(s, n) == oper(s, n::Integer::SingleInteger, table())
> + operator s == oper(s, -1::SingleInteger, 1, table())
> + operator(s, n) == oper(s, n::Integer::SingleInteger, 1, table())
> property(op, name) == search(name, op.props)
> assert(op, s) == setProperty(op, s, NIL$Lisp)
> has?(op, name) == key?(name, op.props)
> - oper(se, n, prop) == [se, n, prop]
> - weight(op, n) == setProperty(op, WEIGHT, n pretend None)
> + oper(se, n, w, prop) == [se, n, w, prop]
> + weight op == op.weight
> + weight(op, n) == (op.weight := n; op)
> nullary? op == zero?(op.narg)
> unary? op == ((op.narg) = 1)
> nary? op == negative?(op.narg)
> @@ -142,30 +145,25 @@ BasicOperator() : Exports == Implementation where
> convert(n)@Integer :: NonNegativeInteger
>
> copy op ==
> - oper(name op, op.narg,
> + oper(name op, op.narg, op.weight,
> table([[r.key, r.entry] for r in entries(properties op)@L]$L))
>
> -- property EQUAL? contains a function f: (BOP, BOP) -> Boolean
> -- such that f(o1, o2) is true iff o1 = o2
> op1 = op2 ==
> (EQ$Lisp)(op1, op2) => true
> - name(op1) ~= name(op2) => false
> op1.narg ~= op2.narg => false
> + op1.weight ~= op2.weight => false
> + name(op1) ~= name(op2) => false
> set(keys properties op1) ~=$Set(Symbol) set(keys properties op2) => false
> (func := property(op1, EQUAL?)) case None =>
> ((func@None) pretend ((%, %) -> Boolean)) (op1, op2)
> true
>
> --- property WEIGHT allows one to change the ordering around
> --- by default, every operator has weight 1
> - weight op ==
> - (w := property(op, WEIGHT)) case "failed" => 1
> - (w@None) pretend NonNegativeInteger
> -
> -- property LESS? contains a function f: (BOP, BOP) -> Boolean
> -- such that f(o1, o2) is true iff o1 < o2
> op1 < op2 ==
> - (w1 := weight op1) ~= (w2 := weight op2) => w1 < w2
> + op1.weight ~= op2.weight => op1.weight < op2.weight
> op1.narg ~= op2.narg => op1.narg < op2.narg
> name(op1) ~= name(op2) => name(op1) < name(op2)
> n1 := #(k1 := set(keys(properties op1))$Set(Symbol))


--
Waldek Hebisch

[Qian Yun]

As shown in the patch, currently weight is only used in JetBundle.

Is this usage critical or replaceable?

On the other hand, is it worth to make BOP into SCACHE?

- Qian

[Waldek Hebisch]

On Wed, Jul 22, 2026 at 09:09:01PM +0800, Qian Yun wrote:
> As shown in the patch, currently weight is only used in JetBundle.
>
> Is this usage critical or replaceable?

IIUC JetBundle really needs weight-s. At first glance I see
no easy way to replace it. OTOH this is isolated use which
does not matter much for rest of algebra.

> On the other hand, is it worth to make BOP into SCACHE?

I do not think so. Operators mostly appear in kernels.
So kernel caching effectively works as cache for operators.

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/98b36e16-4ac7-4481-8c1d-1020b3f43c53%40gmail.com.

--
Waldek Hebisch