search

flintlib / flint

FLINT (Fast Library for Number Theory)
http://www.flintlib.org
GNU Lesser General Public License v3.0
403 stars 235 forks source link

Allow aliasing in all mpn multiplication functions #1940

Open fredrik-johansson opened 2 months ago

fredrik-johansson commented 2 months ago

The hardcoded assembly versions do so, the FFT versions ought to do so automatically, and at intermediate sizes we could probably afford to stick in some pointer comparison and allocate temporary memory when needed.

albinahlback commented 2 months ago

Hmm, not all functions allow aliasing. Whenever there is a loop involved, I believe it does not support aliasing (or it may do up to some specific iteration).

albinahlback commented 2 months ago

Generally, I think it is a bad idea performance-wise to try to allow aliasing for low-level multiplication functions.

fredrik-johansson commented 2 months ago

The point is that for small n, the hardcoded functions do support aliasing, so there is no performance hit on the mpn level. But functions like fmpz_mul and arf_mul currently waste time comparing pointers, allocating temp space and copying data since they don't know about this.

Similarly, functions like fmpz_mul waste memory handling aliasing for FFT-size operands.

albinahlback commented 1 month ago

I don't recall if the Arm semi-hardcoded multiplication routines allow for aliasing, but I'm pretty sure there is ranges there where aliasing is not allowed.