Projects / binmat

Storing binary (boolean) matrices where each element is a byte (or worse, a 32 or 64 bit integer) is incredibly inefficient and wasteful, both in time and space. For example, a 10k square matrix requires 400Mb of RAM if stored as 32 bit int values. Binmat is a library that bit-packs these matrices so that this 10k square matrix requires just 12.5Mb (the minimum space possible). More than that, binmat takes advantage of extremely fast bit-operations when multiplying matrices. The usual series of multiplications and additions required to compute each element are replaced by bitwise AND and OR operations. Furthermore, on 64-bit hardware each bitwise operation can replace up to 64 multiplications or additions, reducing operations that can take hundreds of clock cycles down to just a single cycle. This gives rise to some very considerable performance increases, especially when taking the power of a matrix. Binary exponentiation is implemented to further improve the performance of higher matrix powers.

Tags | lib Matrix |
---|---|

Licenses | GPLv3 |

Operating Systems | Linux |

Implementation | C |

Tweet