Bit-packed GF2

[amirebrahimi]

Hi Matt,

We've been using GF2 for a project and it's been quite useful, but have since needed to move to bit-packing for performance reasons. Is this something you've ever thought about adding or would want to have included in the package (only for GF2 specifically). We have a few routes we can move forward with, such as rolling our own package or possibly contributing some work back to Galois, so I figured I'd ask.

Cheers,
Amir

[mhostetter]

Hey Amir, thanks for reaching out. I did something similar with bit-packing GF(2) arrays in the past. What kinds of operations do you desire with a bit-packed array? Simple addition and multiplication? Or more complex things like matrix multiplication?

I can see a use-case here. There would probably need to be a separate class, perhaps GF2BitPacked or GF2Packed? Supporting addition and multiplication is easy, but some other operations are trickier and would require custom ufuncs. I think adding something like this could be useful to the library.

[amirebrahimi]

@mhostetter, I've started work on this now. Here is a first pass:
main...amirebrahimi:galois:main

If anything feels off with the direction please direct me towards any classes / functionality I might not know about.

[amirebrahimi]

One thing I am wondering is how to restrict this support, so only GF2 can be allowed to have bitpacked=True.

[amirebrahimi]

After working on this a bit more I'm now playing a game of whack-a-mole with numpy functions. So, I think I'm going to go the route of restricting this class to only allow operations that benefit from being bit-packed (e.g. addition/element-wise multiplication and possibly matmul with different bit-packed axes). Then, there can be follow-up ticket(s) to expand scope to a more implicit bitpacked data structure that will expand and pack as necessary.

[mhostetter]

Thanks for your work on this. I feel there are a lot of details to discuss and think through. Would it be best to open a PR (target release/0.4.x) and we can comment on them iteratively there? You can mark as "draft", if you'd like.

[amirebrahimi]

Sure thing, please take a look at #583.

[amirebrahimi]

Sounds good. We haven't started on this work yet, so we are open to any pointers you wish to provide.