celestiaorg / rsmt2d

Go implementation of two dimensional Reed-Solomon merkle tree data availability scheme.
Apache License 2.0
162 stars 80 forks source link

Proposal: use light-weight bitmask instead of gonums's mat.Dense #22

Closed liamsi closed 3 years ago

liamsi commented 3 years ago

This float64 slice https://github.com/lazyledger/rsmt2d/blob/ef1d6c54461edaa428b5720835b6b522c18defff/extendeddatacrossword.go#L52-L63 is used to initialize a dense matrix: https://github.com/lazyledger/rsmt2d/blob/ef1d6c54461edaa428b5720835b6b522c18defff/extendeddatacrossword.go#L82

It looks like this could be vastly improved by using some form of 2d-bitmask to look up if a cell in a row or column is present or not, or if a row / column is incomplete. So instead of 64 bits per element, we could reduce that to 1 bit per element.

We can either look for a small library out there to use or we can write this our selves.

liamsi commented 3 years ago

This is how this could look like: https://github.com/lazyledger/rsmt2d/blob/9454d9b9c7ed4d9cf5fcbb3ffe3121ab304d9585/bit_matrix.go#L17-L30 used here: https://github.com/lazyledger/rsmt2d/blob/9454d9b9c7ed4d9cf5fcbb3ffe3121ab304d9585/extendeddatacrossword.go#L50

The branch can be found here (it is lacking tests and ideally we'd have benchmarks before, see: #23): https://github.com/lazyledger/rsmt2d/compare/ismail/draft_refactor