Troubles with kernels

[Waldek Hebisch]

It was already discussed that there is no consisent and reasonably
computable order on kernels. Example by Kurt Pagani from February
2 2017 shows that this may lead to user-visible troubles. Recently
Qian reported that this leads to bugs during integration.

Core of the problem is that due to failure of order our kernel
machinery may consider two kernels as unequal, even though
they should be equal. Attached patch modifies KERNEL so
that it does not depend on order for kernel equality.
It still uses order to find positions in kernel cache.
With the patch all test pass but testsuite takes almost
two times longer than current version. More visible
slowdown is on formal derivatives:

f := operator 'f
D(f(x), x, 655)

currently takes 8.22 sec on my machine. After kernel patch
it was much longer (I did not wait long enough to know how
much longer).

The patch fixes problem reported by Kurt and hopefully
should fix some integration problems (of course there
are several problem with integration and most are
not coused by wrong handling of kernels).

ATM I am testing this patch, I particular I am looking
for possible troubles. This patch passed testsuite, but
earlier version failed, at least one of failures in
earlier version looks like unwarrented assumption in
algebra, so it is possible that this version also
causes trouble in some obscure cases. Of course,
I would like to avoid slowdown, but ATM is is not
clear how much can be done in kernel code.
Probably most of work on avoiding slowdown should
be outside kernel...

--
Waldek Hebisch

[Qian Yun]

I did not give the patch a full test, but the logic in the patch
looks very reasonable to me.

About performance (50% slower?), do you think it is acceptable?

Most time spent on Kernel should be in "linearSearch".
And since Kernel doesn't have order, I wonder if it is possible to
using some kind of hashtable to store all cached kernels.

- Qian

[Bill Page]

Waldek wrote:

> It still uses order to find positions in kernel cache.

Although order is at least to some extent arbitrary, it is still
necessary for the ordering to be consistent during a session to
satisfy category 'Comparable'.

On Thu, Aug 26, 2021 at 5:22 AM Qian Yun <oldk...@gmail.com> wrote:
>
> Most time spent on Kernel should be in "linearSearch".
> And since Kernel doesn't have order, I wonder if it is possible to
> using some kind of hashtable to store all cached kernels.

Of course hash and order are not compatible but it might be possible
to maintain a duplicate cache.

[Waldek Hebisch]

On Thu, Aug 26, 2021 at 05:21:56PM +0800, Qian Yun wrote:
> I did not give the patch a full test, but the logic in the patch
> looks very reasonable to me.
>
> About performance (50% slower?), do you think it is acceptable?

We need to do something. As I wrote, I noticed unsoundness of
kernel order several years ago. However, it looked like
theoretical problem, rare enough that it would get
unnoticed in practice. And we had visible problems to
fix. So other things got done and this one waited.

But other things improved. And examples by Kurt and
expecially your recent example shows that problem is
more serious than what I thought before.

Main speed loss shows in 'mapleok.input'. Profiling shows
significant slowdown in 'normalize' and in limit code.
In both cases it is desirable to rewrite code limiting use
of kernels.

There are also possiblities to somewhat limit linear
search. OTOH it is not clear if limiting search will
give visible gain: in profile main cost is aritmetic
which happens only after other things like operator
and number of arguments match.

> Most time spent on Kernel should be in "linearSearch".
> And since Kernel doesn't have order, I wonder if it is possible to
> using some kind of hashtable to store all cached kernels.

Hashing kernels is almost as tricky as defining order.
Consider "sin(1 + sqrt(2))" and "sin(-1/(1 - sqrt(2)))".
They should give the same kernel. Building hash function
from part we need hash function which produces the same
value for "1 + sqrt(2)" and "-1/(1 - sqrt(2))". Simple
way to get such function is to use homomorphizm. But
there are no homomorphizms from field into smaller field.
The best scheme that I found out is to build tower of
finite fields, and compute algebraic expressions inside
appropriate extention of "PF(p)" for some choice of "p".
But this is rather complicated scheme and there is still
trouble that during evaluation we can get 0/0 errors.

Another trouble is that we can attach arbitrary data to
operators. Currently we require equality function,
but would also need hash functions. Or (as we do now)
go back to linear search for any problematic cases.
--
Waldek Hebisch

[Waldek Hebisch]

On Thu, Aug 26, 2021 at 09:07:58AM -0400, Bill Page wrote:
> Waldek wrote:
>
> > It still uses order to find positions in kernel cache.
>
> Although order is at least to some extent arbitrary, it is still
> necessary for the ordering to be consistent during a session to
> satisfy category 'Comparable'.

On kernels, once kernel is in cache order is determined by
position, so it is consistent. Beyond kernels it quickly
gets unsound. I am affraid that we either need to declare
that "Comparable" is unsound (that is useful for ordering
printouts, but not much more) or drop "Comparable" from
"Expression" and similar domains.

BTW: When kernel is not in the cache, our code uses order
to find position. But if ordering predicate gives wrong
results we still insert kernel somewhere, possibly in
"wrong" position.

--
Waldek Hebisch

[Qian Yun]

Hi Waldek,

I can not reproduce the slowdown in the following example
after applying your patch. Did I miss something here?

On 8/24/21 8:48 PM, Waldek Hebisch wrote:

> two times longer than current version. More visible
> slowdown is on formal derivatives:
>
> f := operator 'f
> D(f(x), x, 655)
>
> currently takes 8.22 sec on my machine. After kernel patch
> it was much longer (I did not wait long enough to know how
> much longer).

About the performance in KERNEL, it seems that simply inline
function "height" can give a noticeable boost.

- Qian