[PATCH] Optimize 'shiftCache$SCACHE'

[Qian Yun]

The current algorithm of assigning position to elements
of cache array is not optimal, the conflict is frequent
and 'shiftCache' is called very often.

Because the machine integer is as large as 2^62,
we can utilize that more. Even with DIFF==>2^44,
we can fit 250k kernels within machine integer range.

Also we can distribute the positions more evenly.

As a test result, for 10k integrals generating 38228
kernels, before the patch, 'shiftCache' is called 3773
times, after patch, it is 18 times.

- Qian

[Waldek Hebisch]

On Sat, Jul 18, 2026 at 08:38:49PM +0800, Qian Yun wrote:
> The current algorithm of assigning position to elements
> of cache array is not optimal, the conflict is frequent
> and 'shiftCache' is called very often.
>
> Because the machine integer is as large as 2^62,
> we can utilize that more. Even with DIFF==>2^44,
> we can fit 250k kernels within machine integer range.

2^44 is way too big. We still support 32-bit machines. And
some implementation use more tags bits, so range of machine
integers may be smaller.

> Also we can distribute the positions more evenly.
>
> As a test result, for 10k integrals generating 38228
> kernels, before the patch, 'shiftCache' is called 3773
> times, after patch, it is 18 times.

My feeling was that calls to 'shiftCache' do not matter much.
I do not rememeber to see it as significant postion in profile.
However, if you can make choice of numbers smarter, then it
would be good. I would expect that current DIFF, that is
1024 should be able to decrease number of calls to 'shiftCache'
compared to number of kernels inserted into the cache much more
than factor of about 10 that you see.

> diff --git a/src/algebra/kl.spad b/src/algebra/kl.spad
> index d2a2187d..0c144869 100644
> --- a/src/algebra/kl.spad
> +++ b/src/algebra/kl.spad
> @@ -23,7 +23,7 @@ CachableSet : Category == SetCategory with
> ++ of S, once they have been entered in the cache.
> SortedCache(S : CachableSet) : Exports == Implementation where
> N ==> NonNegativeInteger
> - DIFF ==> 1024
> + DIFF ==> 2^44
>
> Exports ==> with
> clearCache : () -> Void
> @@ -47,8 +47,8 @@ SortedCache(S : CachableSet) : Exports == Implementation where
> ++ if f(x, y) is 0 or "failed" if no such y exists.
>
> Implementation ==> add
> - shiftCache : (N, N) -> Void
> - insertInCache : (N, S, N) -> S
> + shiftCache : () -> Void
> + insertInCache : (N, S) -> S
> expandCache : (S) -> Void
> insertBefore : (N, S) -> Void
>
> @@ -76,12 +76,10 @@ SortedCache(S : CachableSet) : Exports == Implementation where
> cache_use := cache_use + 1
> void
>
> - shiftCache(l, n) ==
> - k : Integer
> - vscan := cache
> - for k in l..(cache_use - 1) repeat
> - x := vscan(k)
> - setPosition(x, n + position x)
> + shiftCache() ==
> + for k in 0..(cache_use - 1) repeat
> + x := cache(k)
> + setPosition(x, DIFF * (k + 1))
> void
>
> clearCache() ==
> @@ -176,15 +174,16 @@ SortedCache(S : CachableSet) : Exports == Implementation where
> setPosition(x, (position qelt(vscan, m - 1)) + DIFF)
> insertAtEnd(x)
> return x
> - pos : N :=
> - l < 0 => 0
> - position qelt(vscan, l)
> - insertInCache((l+1)::N, x, pos)
> + insertInCache((l+1)::N, x)
>
> - insertInCache(before, x, pos) ==
> + insertInCache(before, x) ==
> + pos : N :=
> + before = 0 => 0
> + position cache(before - 1)
> y := cache(before)
> if ((pos+1) = position y) then
> - WITHOUT_INTERRUPTS(shiftCache(before, DIFF))$Lisp
> + WITHOUT_INTERRUPTS(shiftCache())$Lisp
> + if before ~= 0 then pos := position cache(before - 1)
> setPosition(x, pos + (((position y) - pos)::N quo 2))
> WITHOUT_INTERRUPTS(insertBefore(before, x))$Lisp
> x


--
Waldek Hebisch

[Qian Yun]

On 7/18/26 8:58 PM, Waldek Hebisch wrote:
> On Sat, Jul 18, 2026 at 08:38:49PM +0800, Qian Yun wrote:
>> The current algorithm of assigning position to elements
>> of cache array is not optimal, the conflict is frequent
>> and 'shiftCache' is called very often.
>>
>> Because the machine integer is as large as 2^62,
>> we can utilize that more. Even with DIFF==>2^44,
>> we can fit 250k kernels within machine integer range.
>
> 2^44 is way too big. We still support 32-bit machines. And
> some implementation use more tags bits, so range of machine
> integers may be smaller.
>
>> Also we can distribute the positions more evenly.
>>
>> As a test result, for 10k integrals generating 38228
>> kernels, before the patch, 'shiftCache' is called 3773
>> times, after patch, it is 18 times.
>
> My feeling was that calls to 'shiftCache' do not matter much.
> I do not rememeber to see it as significant postion in profile.
> However, if you can make choice of numbers smarter, then it
> would be good. I would expect that current DIFF, that is
> 1024 should be able to decrease number of calls to 'shiftCache'
> compared to number of kernels inserted into the cache much more
> than factor of about 10 that you see.

Just tested, for DIFF==>1024, the count only drops from 3773 to 2025.

Even for 32-bit machines, 64-bit multiplication is much cheaper
than thousands of memory access.

- Qian