API for bulk data operations

[mtnpke]

Hi,

thanks for this nice project! It was really easy to integrate and use and was the only circular buffer API that fulfilled my needs of being able to bulk resize.

Regarding bulk insertion and removal operations, I was wondering if there would be an option to offer some kind of higher-level API. You offer the segment views, but it is a bit clunky to put in user code and requires some knowledge of the internals of the buffer. I haven't found a better way, but of course it might also be that I just missed it.

For example, to insert a block of data, I currently use:

// add `std::span<std::byte> data` to the end of `circular::span<std::byte> q`
auto copyDestFirstSeg{q.first_unused_segment()};
auto copyDestLastSeg{q.last_unused_segment()};
q.expand_back(data.size());
const auto bytesInFirstSeg{std::min(data.size(), copyDestFirstSeg.size())};
const auto bytesInLastSeg{data.size() - bytesInFirstSeg};
std::copy_n(data.begin(), bytesInFirstSeg, copyDestFirstSeg.begin());
if (bytesInLastSeg > 0) {
    std::copy_n(data.begin() + bytesInFirstSeg, bytesInLastSeg, copyDestLastSeg.begin());
}

Could operations like this be added to the buffer or maybe as a free-standing function? I can imagine it is quite common to want to do this with a circular buffer and I guess it is also the reason you provide the segment queries in the first place.

[breese]

Does q.push_back(data.begin(), data.end()) serve your purposes?

[mtnpke]

Heh, I coincidentally just had a look at that as well. API-wise, I think it's fine, but the implementation would have to be changed to something like the snippet above instead of n calls to push_back(value) (EDIT: for performance reasons). If I'm not mistaken, std::copy_n should boil down to a memcpy for contiguous iterators.

This would still leave the question of bulk value extraction, though.

[breese]

If performance is a concern, then it may indeed be a good idea to have free-standing bulk functions for insertion and removal.

[mtnpke]

Is there a downside to making push_back have better performance?

[breese]

Larger binaries.

[mtnpke]

I've checked with an (admittedly naive) implementation and it's still small enough to get inlined in a release build, but of course it's arguably larger and I don't have a strong opinion here - in the end it just needs to work :)

Original function:

Modified function:

Would you still consider a free-standing function a possible part of your library or should I just add it to my user code?

[breese]

Does your implementation assume random-access iterators?

I am interested in having these bulk functions as part of the library.

[mtnpke]

I haven't put a lot of time into it since it was just for a quick assessment (i.e., I'm not sure this is even correct - for sure there is some error handling missing in case the iterator distance exceeds the capacity of the ring buffer), but right now a forward iterator should suffice:

template <typename T, std::size_t E>
template <typename InputIterator>
TRIAL_CXX14_CONSTEXPR
void span<T, E>::push_back_seg(InputIterator first,
                           InputIterator last) noexcept(std::is_nothrow_copy_assignable<value_type>::value)
{
    static_assert(std::is_copy_assignable<T>::value, "T must be CopyAssignable");

    const auto allocSize{static_cast<std::size_t>(distance(first, last))};

    const auto oldNext{member.next};
    expand_back(allocSize);

    const auto bytesInFirstSeg{std::min(allocSize, capacity() - oldNext)};
    const auto bytesInLastSeg{allocSize - bytesInFirstSeg};
    std::copy_n(first, bytesInFirstSeg, member.data + oldNext);
    advance(first, bytesInFirstSeg);
    std::copy_n(first, bytesInLastSeg, member.data);
}

I guess the performance gain will be most apparent with contiguous iterators since it then boils down to a memcpy/memmove. For non-contiguous ones, I'd have to benchmark. It might be a bit faster because the resizing of the container is done as one operation, but I wouldn't count on it in an optimized build.