[PATCH] optimize and simplify variables$SMP

[Qian Yun]

The original version is verbose and allocates memory unnecessarily.

The new version is much better.

It saves 1.66% of memory for mapleok.input.
The difference in CPU time is indistinguishable because of
fluctuations in measurement.

- Qian

[Waldek Hebisch]

Looks OK, go on.

BTW: If you are looking at single percent savings I have noticed
that in mapleok prifile BASTYPE-;~=;2SB;1 takes 2.2% self time.
AFAICS replacing '... ~= ...' in triage by 'not(... = ...)'
should give percent or two of speedup.

> diff --git a/src/algebra/multpoly.spad b/src/algebra/multpoly.spad
> index 85c1d335..10ffdc0a 100644
> --- a/src/algebra/multpoly.spad
> +++ b/src/algebra/multpoly.spad
> @@ -618,37 +618,26 @@ SparseMultivariatePolynomial(R : Join(SemiRng, AbelianMonoid),
> -- p case R => p
> -- leadingCoefficient p.ts
>
> - mymerge : (List VarSet, List VarSet) ->List VarSet
> - mymerge(l : List VarSet, m : List VarSet) : List VarSet ==
> - empty? l => m
> - empty? m => l
> - first l = first m =>
> - empty? rest l =>
> - setrest!(l, rest m)
> - l
> - empty? rest m => l
> - setrest!(l, mymerge(rest l, rest m))
> - l
> - first l > first m =>
> - empty? rest l =>
> - setrest!(l, m)
> - l
> - setrest!(l, mymerge(rest l, m))
> - l
> - empty? rest m =>
> - setrest!(m, l)
> - m
> - setrest!(m, mymerge(l, rest m))
> - m
> -
> - variables p ==
> - p case R => empty()
> - lv : List VarSet := empty()
> - q := p.ts
> - while not zero? q repeat
> - lv := mymerge(lv, variables leadingCoefficient q)
> - q := reductum q
> - cons(p.v, lv)
> + myinsert(v : VarSet, l : List VarSet) : List VarSet ==
> + empty? l => [v]
> + first l = v => l
> + v < first l => cons(v, l)
> + setrest!(l, myinsert(v, rest l))
> + l
> +
> + -- helper that accumulates variables directly into the list 'acc'
> + collect_variables(p : %, acc : List VarSet) : List VarSet ==
> + p case R => acc
> + -- since traversing 'p' tends to encounter decreasing values,
> + -- 'myinsert' uses '<' to exploit this locality.
> + acc := myinsert(p.v, acc)
> + q := p.ts
> + while not zero? q repeat
> + acc := collect_variables(leadingCoefficient q, acc)
> + q := reductum q
> + acc
> +
> + variables p == reverse! collect_variables(p, empty())
>
> mainVariable p ==
> p case R => "failed"


--
Waldek Hebisch

[Qian Yun]

On 6/28/26 10:11 PM, Waldek Hebisch wrote:
> On Sun, Jun 28, 2026 at 08:16:49PM +0800, Qian Yun wrote:
>> The original version is verbose and allocates memory unnecessarily.
>>
>> The new version is much better.
>>
>> It saves 1.66% of memory for mapleok.input.
>> The difference in CPU time is indistinguishable because of
>> fluctuations in measurement.
>
> Looks OK, go on.
>
> BTW: If you are looking at single percent savings I have noticed
> that in mapleok prifile BASTYPE-;~=;2SB;1 takes 2.2% self time.
> AFAICS replacing '... ~= ...' in triage by 'not(... = ...)'
> should give percent or two of speedup.
>

Or implement ~=$EXPR instead of indirect call?

The ~=$BASTYPE is the default implementation of hundreds of domains.

I'll take a closer look at that.

- Qian

[Qian Yun]

This is a followup patch.

It optimizes kernels$EXPR, via variables$SMP.

For mapleok.input, it saves additionally 1.74% memory.

- Qian

[Waldek Hebisch]

AFAICS you declare 2 argument variables as export of
MaybeSkewPolynomialCategory. There are 24 domains of this category,
but you provide implementation only for one domain. We should also
provide implementation for other domains, say give default
implementation in the category using variables and merging.

> diff --git a/src/algebra/fspace.spad b/src/algebra/fspace.spad
> index cda59470..a6df8af6 100644
> --- a/src/algebra/fspace.spad
> +++ b/src/algebra/fspace.spad
> @@ -1047,7 +1047,7 @@ FunctionSpace2(R : Comparable, K : KernelCategory(%)) : Category ==
> par : % -> %
>
> mainKernel x == mainVariable(x)$QF
> - kernels(x : %) : List(K) == variables(x)$QF
> + kernels(x : %) : List(K) == variables(numer x, denom x)
> univariate(x : %, k : K) == univariate(x, k)$QF
> isPlus x == isPlus(x)$QF
> isTimes x == isTimes(x)$QF
> diff --git a/src/algebra/multpoly.spad b/src/algebra/multpoly.spad
> index 10ffdc0a..62a232e1 100644
> --- a/src/algebra/multpoly.spad
> +++ b/src/algebra/multpoly.spad
> @@ -639,6 +639,11 @@ SparseMultivariatePolynomial(R : Join(SemiRng, AbelianMonoid),

>
> variables p == reverse! collect_variables(p, empty())
>

> + variables(p, q) ==
> + acc := collect_variables(p, empty())
> + acc := collect_variables(q, acc)
> + reverse! acc
> +

> mainVariable p ==
> p case R => "failed"

> p.v
> diff --git a/src/algebra/polycat.spad b/src/algebra/polycat.spad
> index 05c40029..2df824f5 100644
> --- a/src/algebra/polycat.spad
> +++ b/src/algebra/polycat.spad
> @@ -222,6 +222,9 @@ MaybeSkewPolynomialCategory(R : Join(SemiRng, AbelianMonoid),
> variables : % -> List(VarSet)
> ++ variables(p) returns the list of those variables actually
> ++ appearing in the polynomial p.
> + variables : (%, %) -> List(VarSet)
> + ++ variables(p, q) returns the list of those variables actually
> + ++ appearing in the polynomial p and q.
> if R has SemiRing then
> primitiveMonomials : % -> List %
> ++ primitiveMonomials(p) gives the list of monomials of the
> diff --git a/src/algebra/rf.spad b/src/algebra/rf.spad
> index 5472143c..6aed739d 100644
> --- a/src/algebra/rf.spad
> +++ b/src/algebra/rf.spad
> @@ -92,16 +92,7 @@ PolynomialCategoryQuotientFunctions(E, V, R, P, F):
> v := x::P::F
> ((numer f) v) / ((denom f) v)
>
> - mymerge : (List V, List V) ->List V
> - mymerge(l : List V, m : List V) : List V==

> - empty? l => m
> - empty? m => l

> - first l = first m => cons(first l, mymerge(rest l, rest m))
> - first l > first m => cons(first l, mymerge(rest l, m))
> - cons(first m, mymerge(l, rest m))
> -
> - variables f ==
> - mymerge(variables numer f, variables denom f)
> + variables f == variables(numer f, denom f)
>
> isPower f ==
> (den := denom f) ~= 1 =>


--
Waldek Hebisch

[Qian Yun]

On 6/29/26 7:25 AM, Waldek Hebisch wrote:
> On Mon, Jun 29, 2026 at 07:07:00AM +0800, Qian Yun wrote:
>> This is a followup patch.
>>
>> It optimizes kernels$EXPR, via variables$SMP.
>>
>> For mapleok.input, it saves additionally 1.74% memory.
>
> AFAICS you declare 2 argument variables as export of
> MaybeSkewPolynomialCategory. There are 24 domains of this category,
> but you provide implementation only for one domain. We should also
> provide implementation for other domains, say give default
> implementation in the category using variables and merging.
>

I don't want to use "removeDuplicates merge(p, q)",
so I want to add a new function "merge_unique" in aggcat.spad.

It is like "merge", but discard same elements.

Is that OK?

- Qian

[Waldek Hebisch]

Yes.

--
Waldek Hebisch