daphne-project / daphne-project/daphne

Data structures for boolean matrices

Open
#39 1 comment 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.