Skip to content

Give til::bitmap custom allocator support and add til::pmr::bitmap#8787

Merged
2 commits merged intomainfrom
dev/duhowett/bitmap-with-allocator-magic
Jan 19, 2021
Merged

Give til::bitmap custom allocator support and add til::pmr::bitmap#8787
2 commits merged intomainfrom
dev/duhowett/bitmap-with-allocator-magic

Conversation

@DHowett
Copy link
Member

@DHowett DHowett commented Jan 14, 2021 •
edited
Loading

til::details::bitmap<Allocator> will use Allocator for its
dynamic_bitset, and it will use a rebound allocator for its run storage.

Allocator should be an allocator type storing unsigned long long, the
backing store type for dynamic_bitset.

I've introduced a type alias, til::bitmap, which papers over the
allocator choice for all existing code. I've also introduced a second
type alias, til::pmr::bitmap, which lets a consumer use the C++
polymorphic allocator system.

I chatted with @miniksa about whether to keep the "full" allocator
version in details or not. We decided that for the simplicity of the
til namespace, we would. If anybody has a compelling reason to use
til::details::bitmap<Allocator> directly, we can re-evaluate this
decision.

@DHowett
Add custom allocator support to til::bitmap
3a076ab 
til::details::bitmap<Allocator> will use Allocator for its
dynamic_bitset, and it will use a rebound allocator for its run storage.

Allocator should be an allocator type storing `unsigned long long`, the
backing store type for dynamic_bitset.

I've introduced a type alias, `til::bitmap`, which papers over the
allocator choice for all existing code. I've also introduced a second
type alias, `til::pmr::bitmap`, which lets a consumer use the C++
polymorphic allocator system.
DHowett
DHowett commented Jan 14, 2021
View reviewed changes
src/inc/til/bitmap.h Outdated
_rc(sz),
_bits(_sz.area()),
_runs{}
_bits(_sz.area(), fill ? std::numeric_limits<unsigned long long>::max() : 0, _alloc),
Copy link
Member Author

@DHowett DHowett Jan 14, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

functional change, but minor. instead of using set_all to fill all the bits, we are constructing the dynamic_bitset with 0xffffffffffffffff stored in its blocks. It has the same effect!

@DHowett DHowett changed the title Add custom allocator support to til::bitmap Give til::bitmap custom allocator support and add til::pmr::bitmap Jan 14, 2021
@DHowett
Copy link
Member Author

DHowett commented Jan 14, 2021

I had to reindent the file because of namespace nesting. Review with whitespace hidden.

@miniksa miniksa mentioned this pull request Jan 15, 2021
Closed
6 tasks
@DHowett DHowett added the Needs-Second It's a PR that needs another sign-off label Jan 18, 2021
@DHowett DHowett mentioned this pull request Jan 18, 2021
Merged
6 tasks
@DHowett DHowett added the AutoMerge Marked for automatic merge by the bot when requirements are met label Jan 19, 2021
@ghost
Copy link

ghost commented Jan 19, 2021

Hello @DHowett!

Because this pull request has the AutoMerge label, I will be glad to assist with helping to merge this pull request once all check-in policies pass.

p.s. you can customize the way I help with merging this pull request, such as holding this pull request until a specific person approves. Simply @mention me (@msftbot) and give me an instruction to get started! Learn more here.

@ghost ghost merged commit 2919d96 into main Jan 19, 2021
@ghost ghost deleted the dev/duhowett/bitmap-with-allocator-magic branch January 19, 2021 18:24
mpela81 pushed a commit to mpela81/terminal that referenced this pull request Jan 28, 2021
@DHowett @mpela81
Give til::bitmap custom allocator support and add til::pmr::bitmap (m…
bb51c1a 
…icrosoft#8787)

`til::details::bitmap<Allocator>` will use `Allocator` for its
`dynamic_bitset`, and it will use a rebound allocator for its run storage.

Allocator should be an allocator type storing `unsigned long long`, the
backing store type for `dynamic_bitset`.

I've introduced a type alias, `til::bitmap`, which papers over the
allocator choice for all existing code. I've also introduced a second
type alias, `til::pmr::bitmap`, which lets a consumer use the C++
polymorphic allocator system.

I chatted with @miniksa about whether to keep the "full" allocator
version in `details` or not. We decided that for the simplicity of the
`til` namespace, we would. If anybody has a compelling reason to use
`til::details::bitmap<Allocator>` directly, we can re-evaluate this
decision.
lhecker added a commit that referenced this pull request May 14, 2021
@lhecker @miniksa
Introduce til::rle - a run length encoded vector
ba58564 
* #8000 - Supports buffer rewrite work. A re-use of `til::rle` will be
  useful as a column counter as we pursue NxM storage and presentation.
* #3075 - The new iterators allow skipping forward by multiple units,
  which wasn't possible under `TextBuffer-/OutputCellIterator`.
  Additionally it also allows a bulk insertions.
* #8787 and #410 - High probability this should be `pmr`-ified
  like `bitmap` for things like `chafa` and `cacafire`
  which are changing the run length frequently.

* [x] Closes #8741
* [x] I work here.
* [x] Tests added.
* [x] Tests passed.

- [x] Ran `cacafire` in `OpenConsole.exe` and it looked beautiful
- [x] Ran new suite of `RunLengthEncodingTests.cpp`

Co-authored-by: Michael Niksa <[email protected]>
lhecker added a commit that referenced this pull request May 14, 2021
@lhecker @miniksa
Introduce til::rle - a run length encoded vector
997fedd 
## Summary of the Pull Request

Introduces `til::rle`, a vector-like container which stores elements of
type T in a run length encoded format. This allows efficient compaction
of repeated elements within the vector.

## References

* #8000 - Supports buffer rewrite work. A re-use of `til::rle` will be
  useful as a column counter as we pursue NxM storage and presentation.
* #3075 - The new iterators allow skipping forward by multiple units,
  which wasn't possible under `TextBuffer-/OutputCellIterator`.
  Additionally it also allows a bulk insertions.
* #8787 and #410 - High probability this should be `pmr`-ified
  like `bitmap` for things like `chafa` and `cacafire`
  which are changing the run length frequently.

## PR Checklist

* [x] Closes #8741
* [x] I work here.
* [x] Tests added.
* [x] Tests passed.

## Validation Steps Performed

* [x] Ran `cacafire` in `OpenConsole.exe` and it looked beautiful
* [x] Ran new suite of `RunLengthEncodingTests.cpp`

Co-authored-by: Michael Niksa <[email protected]>
@lhecker lhecker mentioned this pull request May 14, 2021
Merged
6 tasks
lhecker added a commit that referenced this pull request May 14, 2021
@lhecker @miniksa
Introduce til::rle - a run length encoded vector
e55a1ea 
## Summary of the Pull Request

Introduces `til::rle`, a vector-like container which stores elements of
type T in a run length encoded format. This allows efficient compaction
of repeated elements within the vector.

## References

* #8000 - Supports buffer rewrite work. A re-use of `til::rle` will be
  useful as a column counter as we pursue NxM storage and presentation.
* #3075 - The new iterators allow skipping forward by multiple units,
  which wasn't possible under `TextBuffer-/OutputCellIterator`.
  Additionally it also allows a bulk insertions.
* #8787 and #410 - High probability this should be `pmr`-ified
  like `bitmap` for things like `chafa` and `cacafire`
  which are changing the run length frequently.

## PR Checklist

* [x] Closes #8741
* [x] I work here.
* [x] Tests added.
* [x] Tests passed.

## Validation Steps Performed

* [x] Ran `cacafire` in `OpenConsole.exe` and it looked beautiful
* [x] Ran new suite of `RunLengthEncodingTests.cpp`

Co-authored-by: Michael Niksa <[email protected]>
lhecker added a commit that referenced this pull request May 14, 2021
@lhecker @miniksa
Introduce til::rle - a run length encoded vector
4b0eeef 
## Summary of the Pull Request

Introduces `til::rle`, a vector-like container which stores elements of
type T in a run length encoded format. This allows efficient compaction
of repeated elements within the vector.

## References

* #8000 - Supports buffer rewrite work. A re-use of `til::rle` will be
  useful as a column counter as we pursue NxM storage and presentation.
* #3075 - The new iterators allow skipping forward by multiple units,
  which wasn't possible under `TextBuffer-/OutputCellIterator`.
  Additionally it also allows a bulk insertions.
* #8787 and #410 - High probability this should be `pmr`-ified
  like `bitmap` for things like `chafa` and `cacafire`
  which are changing the run length frequently.

## PR Checklist

* [x] Closes #8741
* [x] I work here.
* [x] Tests added.
* [x] Tests passed.

## Validation Steps Performed

* [x] Ran `cacafire` in `OpenConsole.exe` and it looked beautiful
* [x] Ran new suite of `RunLengthEncodingTests.cpp`

Co-authored-by: Michael Niksa <[email protected]>
DHowett added a commit that referenced this pull request May 18, 2021
@DHowett
Squashed commit of the following:
8250eba 
commit 4b0eeef
Author: Leonard Hecker <[email protected]>
Date:   Fri May 14 23:56:08 2021 +0200

    Introduce til::rle - a run length encoded vector

    ## Summary of the Pull Request

    Introduces `til::rle`, a vector-like container which stores elements of
    type T in a run length encoded format. This allows efficient compaction
    of repeated elements within the vector.

    ## References

    * #8000 - Supports buffer rewrite work. A re-use of `til::rle` will be
      useful as a column counter as we pursue NxM storage and presentation.
    * #3075 - The new iterators allow skipping forward by multiple units,
      which wasn't possible under `TextBuffer-/OutputCellIterator`.
      Additionally it also allows a bulk insertions.
    * #8787 and #410 - High probability this should be `pmr`-ified
      like `bitmap` for things like `chafa` and `cacafire`
      which are changing the run length frequently.

    ## PR Checklist

    * [x] Closes #8741
    * [x] I work here.
    * [x] Tests added.
    * [x] Tests passed.

    ## Validation Steps Performed

    * [x] Ran `cacafire` in `OpenConsole.exe` and it looked beautiful
    * [x] Ran new suite of `RunLengthEncodingTests.cpp`

    Co-authored-by: Michael Niksa <[email protected]>
ghost pushed a commit that referenced this pull request May 20, 2021
@lhecker @miniksa
Introduce til::rle - a run length encoded vector (#10099)
a8e4bed 
## Summary of the Pull Request

Introduces `til::rle`, a vector-like container which stores elements of
type T in a run length encoded format. This allows efficient compaction
of repeated elements within the vector.

## References

* #8000 - Supports buffer rewrite work. A re-use of `til::rle` will be
  useful as a column counter as we pursue NxM storage and presentation.
* #3075 - The new iterators allow skipping forward by multiple units,
  which wasn't possible under `TextBuffer-/OutputCellIterator`.
  Additionally it also allows a bulk insertions.
* #8787 and #410 - High probability this should be `pmr`-ified
  like `bitmap` for things like `chafa` and `cacafire`
  which are changing the run length frequently.

## PR Checklist

* [x] Closes #8741
* [x] I work here.
* [x] Tests added.
* [x] Tests passed.

## Validation Steps Performed

* [x] Ran `cacafire` in `OpenConsole.exe` and it looked beautiful
* [x] Ran new suite of `RunLengthEncodingTests.cpp`

Co-authored-by: Michael Niksa <[email protected]>
This pull request was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@carlos-zamora carlos-zamora carlos-zamora approved these changes

@miniksa miniksa miniksa approved these changes

@zadjii-msft zadjii-msft Awaiting requested review from zadjii-msft

@leonMSFT leonMSFT Awaiting requested review from leonMSFT

@PankajBhojwani PankajBhojwani Awaiting requested review from PankajBhojwani

Assignees

@miniksa miniksa

Labels

AutoMerge Marked for automatic merge by the bot when requirements are met Needs-Second It's a PR that needs another sign-off

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@DHowett @carlos-zamora @miniksa