include: interval_set: Relax requirements and enhance performance of interval sets#60250
include: interval_set: Relax requirements and enhance performance of interval sets#60250
Conversation
aainscow
force-pushed
the
interval_set_enhancements
branch
from
ef9cb0a to
14c5386
Compare
|
jenkins test make check |
|
jenkins test make check |
1 similar comment
|
jenkins test make check |
|
This pull request has been automatically marked as stale because it has not had any activity for 60 days. It will be closed if no further activity occurs for another 30 days. |
aainscow
force-pushed
the
interval_set_enhancements
branch
from
14c5386 to
0134c8e
Compare
|
Updated to latest version of changes. I am basing this on top of the legacy_ec changes, as that is the priority order of the deliver. If this gets reviewed quickly and I get a request, I can re-order the commits. Please only review the interval set changes here. |
| const_iterator &operator*() { | ||
| return *this; | ||
| } | ||
| constexpr bool contains(K _off, K _len) const { |
There was a problem hiding this comment.
unorthodox naming convention
There was a problem hiding this comment.
The intent was something analagous to map::contains().
Happy to change to a better, more conventional name.
| auto start = range_start(); | ||
| auto end = range_end(); | ||
|
|
||
| /* Only loop over the overlapping range of a */ |
aainscow
force-pushed
the
interval_set_enhancements
branch
from
0134c8e to
d9c8e93
Compare
aainscow
force-pushed
the
interval_set_enhancements
branch
from
14920d0 to
055f85a
Compare
src/include/interval_set.h
Outdated
|
|
||
| /** This insert method adds an interval into the interval map, with some | ||
| * caveats and restrictions. Inserts must be new interval or append to | ||
| * an existing interval. Adding an unsupported interval will result in an |
There was a problem hiding this comment.
s/an unsupported interval/an interval that intersects existing one/ ?
| * caveats and restrictions. Inserts must be new interval or append to | ||
| * an existing interval. Adding an unsupported interval will result in an | ||
| * assert firing. | ||
| * |
There was a problem hiding this comment.
"This function is intended for cases where intervals are required to never to overlap."
?
There was a problem hiding this comment.
Will reword comment with the above recommendations
| * @param len - the length of the interval being added. | ||
| * @param pstart (optional) returns the start of the resulting interval | ||
| * @param plen (optional) returns the length of the resulting interval. | ||
| */ |
| } else { | ||
| T old_len = 0; | ||
| T new_end = end; | ||
| for (;p != m.end() && end >= p->first; p = m.erase(p)) { |
There was a problem hiding this comment.
Are we updating _size accordingly? I don't see it.
Update:
I see it now. old_len accumulates size that is in erased intervals.
src/include/interval_set.h
Outdated
| //cout << "insert " << start << "~" << len << endl; | ||
| T new_len = len; | ||
| auto p = find_adj_m(start); | ||
| auto o = std::pair(start, len); |
| // For some maps, inserting here corrupts p, so we need | ||
| // to insert, then recover p, so that we can delete it if needed. | ||
| p = m.insert(p, std::pair(end, pend-end)); | ||
| --p; |
There was a problem hiding this comment.
return;?
There is noting to do beyond this point, right?
There was a problem hiding this comment.
Agreed. I will add.
There was a problem hiding this comment.
Doing so caused this test to fail:
// erase overlapping start by 1
{
ISet iset1, iset2;
iset1.union_insert(3, 4);
iset1.erase(1, 3);
iset2.union_insert(4, 3);
ASSERT_EQ(iset1, iset2);
}
error:
Expected equality of these values:
iset1
Which is: { (3, 0), (4, 3) }
iset2
Which is: { (4, 3) }
So I have reverted this.
These new utilities add the ability to: get_lower_range: Return the lowest interval iterator which covers the specified range get_start_off(): return the first offset in the interval. get_end_off(): Return the end offset of the last interval contains(): Return true if specified is entirely contained within the interval map. Signed-off-by: Alex Ainscow <[email protected]>
…within range. Determine, for a particular interval iterator, whether the specified range is entirely contained inside the interval. Signed-off-by: Alex Ainscow <[email protected]>
Signed-off-by: Alex Ainscow <[email protected]>
…rely contained within the set. Signed-off-by: Alex Ainscow <[email protected]>
…llow more flexibility. The old insert was restrictive in ranges that could be added in. The new interface allows for a range to be added, whether it extends or joins other intervals. Also change a number of interfaces to use the new insert. Signed-off-by: Alex Ainscow <[email protected]>
The old erase would only allow intervals which exist to be erased. It is often useful to erase any interval, even if it does not exist or partially overlaps one or many intervals. Signed-off-by: Alex Ainscow <[email protected]>
… a specified alignment Signed-off-by: Alex Ainscow <[email protected]>
Signed-off-by: Alex Ainscow <[email protected]>
Signed-off-by: Alex Ainscow <[email protected]>
Signed-off-by: Alex Ainscow <[email protected]>
A reviewer (see github) was concerned that the policing provided by insert() may have been required for some applications of insert_set. As such, I have re-instated the old insert method and instead refactored "union_insert". IU have also enhanced the comments. Signed-off-by: Alex Ainscow <[email protected]>
Here we duplicate all the original tests which used "insert" to verify they also pass with "union_insert". All new tests are modified to use "union_of" and "union_insert" Signed-off-by: Alex Ainscow <[email protected]>
|
jenkins test make check |
Signed-off-by: Alex Ainscow <[email protected]>
aainscow
force-pushed
the
interval_set_enhancements
branch
from
b5369d9 to
adaafdd
Compare
|
jenkins test make check |
|
jenkins test make check arm64 |
|
jenkins test make check |
|
jenkins test make check arm64 |
aainscow
added
the
no-backport-required
3 participants
These commits enhance the insert/erase function of interval sets. The main intent is to enhance flexibility to callers, but in many cases, performance is likely also improved. Where performance is not improved, there should be no performance reduction.
There is also a new "align" method which allows for all intervals within a set to be aligned to an arbitrary alignment. This will be consumed by the new optimised erasure code.
Contribution Guidelines
To sign and title your commits, please refer to Submitting Patches to Ceph.
If you are submitting a fix for a stable branch (e.g. "quincy"), please refer to Submitting Patches to Ceph - Backports for the proper workflow.
When filling out the below checklist, you may click boxes directly in the GitHub web UI. When entering or editing the entire PR message in the GitHub web UI editor, you may also select a checklist item by adding an
xbetween the brackets:[x]. Spaces and capitalization matter when checking off items this way.Checklist
Show available Jenkins commands
jenkins retest this pleasejenkins test classic perfjenkins test crimson perfjenkins test signedjenkins test make checkjenkins test make check arm64jenkins test submodulesjenkins test dashboardjenkins test dashboard cephadmjenkins test apijenkins test docsjenkins render docsjenkins test ceph-volume alljenkins test ceph-volume toxjenkins test windowsjenkins test rook e2e