daphne-project / daphne-project/daphne
Data structures for boolean matrices
- Dominant language
- C++
- Stars
- 81
- Forks
- 83
- PR merge metrics
- No merged PRs in 30d
Description
In GitLab by @pdamme on May 10, 2021, 22:22
**Motivation**
Matrices of boolean values are promising because they
1. allow a compact representation using only a single bit per value, thereby saving space at any level of the memory hierarchy
2. allow a highly efficient processing using full-word scalar (or even SIMD) instructions to process multiple values at once
At the same time, boolean matrices do occur in typical ML algorithms and DB processing models, e.g., as the result of elementwise comparisons, which must also be further processed.
While our current implementations of data structures and kernels are mostly generic w.r.t. the value type by means of a template parameter, they can hardly treat `bool` efficiently, because they implicitly assume byte-aligned types. Thus, support for boolean matrices must be implemented explicitly.
Supporting boolean matrices has two aspects:
1. data structures (this issue)
2. algorithms/kernels (issue #40).
**Data structures for boolean matrices**
As a first step, our matrix data structures (`DenseMatrix` and `CSRMatrix`) need to be adapted to efficiently support `bool` as the value type. This could best be done by writing specializations of both classes for `bool` as the value type.
For `DenseMatrix`, the values should be stored densely packed with 1 bit per value. That way, a size reduction of 8x compared to a 1-byte value type is possible. For `CSRMatrix`, the non-zero values would not need to be stored at all, since they are obviously all 1, i.e., the data structure itself would be organized differently internally. In any case, the new specializations should provide direct access to the underlying arrays, but also correctly support the generic `get`/`set`/`append` interface as well.
Contributor guide
Assessment
This issue has not been assessed yet.