-
Notifications
You must be signed in to change notification settings - Fork 12
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
speed of copying with iterators #29
Comments
I simply mean:
( -> has 1 fragment)
( -> has 2 fragment2) |
Thanks for bringing this to my attention. |
By the way... At first I thought there is a bug here: ring-span-lite/include/nonstd/ring_span.hpp Line 982 in b8135cd
? Basically: What if you increment beyond the unsigned max and get wrap around? But that can never happen, right? (Because the iterator protocol says: iter somewhere in the range, or one beyond the range.) And also interesting: a begin() iterator that you store to a variable auto it = rs.begin(); "moves along" with push_backs to rs. |
And here's some "fast" code for you to experiment with: template<typename OutputIt>
OutputIt copy(const const_iterator &beg, const const_iterator &end, OutputIt d_first ) {
assert(this == beg.m_rs);
assert(this == end.m_rs);
if (beg == end) { // necessary, since otherwise below, would result in b == e, which is not distinguishable from a completely full ring
return d_first;
}
auto b = m_data + normalize_(m_front_idx + beg.m_idx);
auto const e = m_data + normalize_(m_front_idx + end.m_idx);
if (e <= b) {
auto const edge = m_data + m_capacity;
d_first = std::copy(b, edge, d_first);
b = m_data;
}
return std::copy(b, e, d_first);
} only 2 calls to |
And this, when copying from ring_span into ring_span: public:
template<typename TOther>
typename ring_span<TOther>::iterator copy(const const_iterator &beg, const const_iterator &end, ring_span<TOther> &other, typename ring_span<TOther>::iterator d_first ) {
assert(this == beg.m_rs);
assert(this == end.m_rs);
assert(&other == d_first.m_rs);
assert(end - beg <= other.size());
if (beg == end) { // necessary, since otherwise below, would result in b == e, which is not distinguishable from a completely full ring
return d_first;
}
auto b = m_data + normalize_(m_front_idx + beg.m_idx);
auto const e = m_data + normalize_(m_front_idx + end.m_idx);
auto b_o = other.m_data + normalize_(other.m_front_idx + d_first.m_idx);
if (e <= b) {
auto const edge = m_data + m_capacity;
copy_to_lim(b, edge, b_o, other);
b = m_data;
}
copy_to_lim(b, e, b_o, other);
return std::next(d_first, end - beg);
}
private:
template<typename TOther>
void copy_to_lim(pointer b, const pointer lim, pointer &b_o, ring_span<TOther> &other) {
auto const numTillLim = lim - b;
auto const numTillEdge_o = other.m_data + other.m_capacity - b_o;
if (numTillLim > numTillEdge_o) {
std::copy(b, b + numTillEdge_o, b_o);
b += numTillEdge_o;
b_o = other.m_data;
}
b_o = std::copy(b, lim, b_o);
} I just hope there's no bug, in there. haha |
This sounds to me like a case of "piecewise contiguous iterators," which also comes up with FWIW, simply adding a Consider whether the right API might be (extremely bikesheddable names):
and whether "rotate" is even possible, if you have a custom popper that you don't know what it does. I haven't thought about this at all. Or alternatively, probably better:
|
FWIW I can't recommend playing around in implementation-details, but this indeed looks like it could be made a segmented iterator. If you really want to, you can look at |
Thanks for those pointers. Reasons: a) I won't invest in segmented_iterator as I'm not on libc++, but on libstdc++. b) I want indices or iterators into the ring, that remain fixed... that don't "magically" shift with push_back. Related: Personally I think that I don't agree with the design decision made here, of having iterators do magic on deferences (the obtained value is shifted along). Look what happens in this code: ring-span-lite/include/nonstd/ring_span.hpp Line 966 in b8135cd
You call I would change that, to have Why do I say all this? Well... Image a relativly large ring (many items). I want a writer, and a delayed reader, who can at his leisure read blocks (copy them), (also hopefully without needing all that much locking). Currently there's no proper index or iterator mechanism, to do this; as currently push_backs, would cause dereferences to shift along ("behind my back" -- I'm joking ... this is all design decision and usecase stuff.) Yes, there is a potential problem with my approach, namely that too slow reads, will cause the writer to overwrite ranges that the slow reader has not yet read. That's particular to my usecase and I need to work with code, to come up with a good solution. so far with ...my thoughts... |
Thanks for providing insight into this background :) |
Is this not "slow(ish)", when using the standard copying mechanisms:
std::copy(rs.cbegin(), rs.cend(), out_it)
??
It'll call this unnecessary code on each iterator-dereference:
ring-span-lite/include/nonstd/ring_span.hpp
Line 968 in b8135cd
which calls the slowish
ring-span-lite/include/nonstd/ring_span.hpp
Line 836 in b8135cd
on each dereference!!!
Should
ring
andring_span
not have some facilities to speed up copying?The text was updated successfully, but these errors were encountered: