mhostetter / galois

A performant NumPy extension for Galois fields and their applications
https://mhostetter.github.io/galois/
MIT License
328 stars 30 forks source link

Creating Reed Solomon code is slower than in Sage #571

Closed luan-xiaokun closed 3 days ago

luan-xiaokun commented 1 month ago

Thanks for the very useful library!

I am struggling to use Sage's Reed Solomon code. Although it has linting issue and more difficult to use than Galois (thanks again), I noticed that it is faster than Galois though, my tests are as follows:

import galois
rs = galois.ReedSolomon(2**16 - 1, 3)
# time python test1.py
# 32.38 user 2.56 system 98% cpu 41.630 total
from sage.all import *
F = GF(Integer(2**16))
rs = codes.GeneralizedReedSolomonCode(F.list()[1:2**16], 3)
# time python test2.py
# 0.50 user 0.11 system 99% cpu 0.619 total

I wonder why there is such a difference, is it something related to JIT? I'm a newbie in terms of symbolic computation (and Sage and Galois), any explanation or link to references would be much appreciated.

mhostetter commented 4 days ago

You are timing everything for galois. There is the JIT compilation of the finite field(s) and their lookup tables (for fast execution). Sage is pre-compiled, where galois is just-in-time compiled. I wouldn't expect them to be the same.

Also, creation time should matter less than encode/decode times.

luan-xiaokun commented 3 days ago

Hi @mhostetter, thank you for the explanation!

That makes a lot of sense, especially about the JIT compilation in galois versus Sage's pre-compilation.