iotaledger / iota / 17901950127

push

github

feat(consensus): compress ancestor and ack references into a single vector (#8585)

# Description of change
Compresses the ancestor and acknowledgements vectors into a single
reference vector with overlap indices. Using the following layout.

```
references: Vec<BlockRef>, // layout: |ancestors|overlap|acks|ancestor[0]?|
overlap_start_index:u8, // bounded by committee size (<=256)
overlap_end_index: u8, // same bound as above
```
`ancestors -> &references[..overlap_end_index]`
`acks -> &references[overlap_start_index..]`
- ancestor[0] is the first ancestor supplied during block header
creation and is also the first reference in references.
- it is not added in the overlap part of references, but is added to the
end of the vectors if it is acknowledged.
- ancestors - non overlapping ancestors excluding ancestor 0
- overlap - ancestor and ack overlap without ancestor 0
- acks - non overlapping acks

This implementation adds a bit of computational overhead during block
header creation. But compresses to a single shared reference vector with
2 bytes for the indices as overhead and a single BlockRef duplication.
It keeps access to `ancestors` / `acknowledgements` in a single
continuous array in memory.

## Links to any relevant issues

Closes #8151 

## How the change has been tested

- [x] Basic tests (linting, compilation, formatting, unit/integration
tests)
- [x] Patch-specific tests (correctness, functionality coverage)
- [x] I have added tests that prove my fix is effective or that my
feature works
- [x] I have checked that new and existing unit tests pass locally with
my changes

132 of 132 new or added lines in 1 file covered. (100.0%)

229529 of 349205 relevant lines covered (65.73%)

2389279.07 hits per line