Large FreeAlgebraImpl's are very slow

[aklitzke]

I sometimes work with FreeAlgebraImpl's of degree up to 256. I've noticed that even just creating this ring is very slow .. up to 30s or longer.

Is this expected? Or is there perhaps some big-o problem that could be fixed?

        const ELEMENTS: usize = 256;
        let base_ring = Zn::<256>::RING;
        let x_pow_rank = vec![base_ring.neg_one(); ELEMENTS];
        let ring = FreeAlgebraImpl::new(base_ring, x_pow_rank, default_memory_provider!());
        let can_secret: Vec<_> = (0..ELEMENTS)
                .map(|_| ring.base_ring().random_element(rand::random::<u64>))
                .collect();
        // takes 30 seconds+
        ring.from_canonical_basis(can_secret.into_iter())

[FeanorTheElf]

No, that's certainly not expected. I think the problem is that I did not specialize the default implementation, and thus from_canonical_basis() computes the sum a0 + a1 * g + a2 * g^2 + .... I'll fix it soon (hopefully tomorrow).

Of course, there is also the second bug that you should not be able to get Fp::<256>::RING, since Z/256Z is not a field...

[aklitzke]

you should not be able to get Fp::<256>::RING, since Z/256Z is not a field...

Ope, that's actually just a typo on my end while putting together the example. Should be Zn, not Fp. Though I have seen the performance problem with base rings like Fp::<3329> as well

[FeanorTheElf]

Ok good, I just checked and you indeed cannot get a Fp::<256>::RING.

On the other issue: The current implementation of from_canonical_basis() is certainly very inefficient, and I will fix this. Nevertheless, your example runs in about a second on my laptop (which is clearly still too much), so I wonder if there is anything else that I am missing. Anyway, I will fix the obvious problem, and if it is still slow for you we can investigate further.

[FeanorTheElf]

I published version 1.5.3 that replaced the inefficient implementation. Could you check whether it is still slow in your setting?

[aklitzke]

Much much faster! Thanks a bunch!