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
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.