5
\$\begingroup\$

A span provides a view to a contiguous piece of memory. Internally a span wraps a pointer, and a size.

I tried an existing implementation: gsl-lite. A function like template <typename T> void f(gsl::span<const T>& s) {} can't accept a gsl::span<T> as an argument. The problem is that no type conversion can occur during template instantiation (link to so question).

It would not be always as fast as C because it doesn't use the restrict keyword. It also doesn't specify the memory alignment.

Below is the header for span. Is the design ok? How to improve?

Thanks.

The code and google tests are at https://github.com/rzu512/algorithms

span.h

/// \file
/// \brief Span and Const_span. Wrapper for a pointer and a size.
/// \details Span<T> and const Span<T> both provides mutable access.
/// Const_span<T> and const Const_span<T> both provides immutable access.
/// Type T should not be const. For example Span<const int> is not allowed.
/// A Span can be implicitly converted to a Const_span.
/// A Const_span can not be implicitly converted to a Span.

#ifndef ALGORITHMS_SPAN_H
#define ALGORITHMS_SPAN_H

#include <cstddef>
#include <type_traits>

#ifndef SPAN_NDEBUG

    #include <stdexcept>
    #include <exception>

#endif

namespace {
    typedef std::ptrdiff_t span_index;

    void throw_out_of_range(bool cond, std::string s) {
        #ifndef SPAN_NDEBUG
        if (cond) std::throw_with_nested(std::out_of_range(s));
        #endif
    }
}

template<typename T> class Span;

/// \brief Const_span over contiguous memory.
template<typename T>
class Const_span {
    static_assert(!std::is_const<T>::value,
                  "Template parameter should not be const.");
public:
    typedef span_index index_type;
    typedef index_type size_type;

    typedef T value_type;
    typedef T* iterator;
    typedef const T* const_iterator;

    Const_span(const T* const data, const size_type size)
            : data_(data), size_(size) {}

    const_iterator begin() const {
        return data_;
    }

    const_iterator end() const { return data_ + size_; }

    const_iterator cbegin() const { return data_; }

    const_iterator cend() const { return data_ + size_; }

    const T& operator[](const size_type i) const {
        throw_out_of_range(i >= size_, "Index is out of bound.");
        return data_[i];
    }

    const T* data() const { return cdata(); }

    const T* cdata() const { return data_; }

    size_type size() const { return size_; }

protected:
    const T* const data_;  ///< pointer to data
    const index_type size_;  ///< Number of elements in data.
    friend class Span<T>;
};


/// \brief Span over contiguous memory.
template<typename T>
class Span : public Const_span<T> {
    static_assert(!std::is_const<T>::value,
                  "Template parameter should not be const.");
    typedef Const_span<T> Base;
public:
    typedef typename Base::index_type index_type;
    typedef typename Base::size_type size_type;
    typedef typename Base::value_type value_type;
    typedef typename Base::iterator iterator;
    typedef typename Base::const_iterator const_iterator;

    Span(T* const data, const size_type size) : Base(data, size) {}

    iterator begin() const { return mutable_data(); }

    iterator end() const { return mutable_data() + size_; }

    T& operator[](const size_type i) const {
        throw_out_of_range(i >= size_, "Index is out of bound.");
        return mutable_data()[i];
    }

    T* data() const { return mutable_data(); }

private:
    /// \brief Cast away const-ness of pointer to data
    /// \warning Evil. Do not use.
    T* mutable_data() const { return const_cast<T*>(data_); }
    using Const_span<T>::data_;
    using Const_span<T>::size_;
};

namespace {
    template<typename C>
    using V_nc=typename std::remove_const<typename C::value_type>::type;
}
template<typename C> using Container_span=Span<V_nc<C>>;
template<typename C> using Const_container_span=Const_span<V_nc<C>>;

template<typename C>
Span<V_nc<C>> make_span(C& c, const span_index pos,
                            const span_index size) {
    throw_out_of_range(pos + size > c.size(),
                       "Size and pos are out of bound.");
    return Span<V_nc<C>>(c.data() + pos, size);
}

template<typename C>
Container_span<C> make_span(C& c, const span_index size) {
    return make_span(c, 0, size);
}

template<typename C, typename T=V_nc<C>>
Container_span<C> make_span(C& c) {
    return make_span(c, 0, c.size());
}

template<typename C>
Const_container_span<C> make_const_span(C& c, const span_index pos,
                                        const span_index size) {
    throw_out_of_range(pos + size > c.size(),
                       "Size and pos are out of bound.");
    return Const_container_span<C>(c.data() + pos, size);
}

template<typename C>
Const_container_span<C> make_const_span(C& c, const span_index size) {
    return make_const_span<C>(c, 0, size);
}

template<typename C>
Const_container_span<C> make_const_span(C& c) {
    return make_const_span<C>(c, 0, c.size());
}

template<typename T>
Span<T> make_subspan(const Span<T>& s, const span_index offset,
                     const span_index size) {
    throw_out_of_range(offset + size > s.size(),
                       "Size and offset are out of bound.");
    return Span<T>(s.data() + offset, size);
}

template<typename T>
Const_span<T> make_const_subspan(const Const_span<T>& s,
                                 const span_index offset,
                                 const span_index size) {
    throw_out_of_range(offset + size > s.size(),
                       "Size and offset are out of bound.");
    return Const_span<T>(s.data() + offset, size);
}

template<typename T>
Const_span<T> make_subspan(const Const_span<T>& s, const span_index offset,
                     const span_index size) {
    return make_const_subspan(s, offset, size);
}

#endif //ALGORITHMS_SPAN_H
\$\endgroup\$
  • 2
    \$\begingroup\$ Should a const Span<T> prevent any mutable access? Currently it doesn't. It is more like a const iterator. \$\endgroup\$ – R zu Apr 18 '18 at 17:17
  • \$\begingroup\$ You say the lack of restrict is slowing things down. Have you tested this empirically? In templated code, the compiler can oftentimes infer aliasing or lack thereof. \$\endgroup\$ – Frank Apr 18 '18 at 18:02
  • \$\begingroup\$ @Franke see icl.cs.utk.edu/hpcc/software/index.html \$\endgroup\$ – R zu Apr 18 '18 at 18:19
  • \$\begingroup\$ I don't see how that matters, restrict is not a magic wand that you shake at any code to make it faster. It's a hint you can give to the compiler to help it sort things out easier in certain scenarios. I'm talking about parameters and member variables of fully inlinable and inferable functions and types, which generally do not need assistance. \$\endgroup\$ – Frank Apr 18 '18 at 18:24
  • \$\begingroup\$ I guess I can try to make span<T> inherits from span<const T> with sfinae and std::is_const. \$\endgroup\$ – R zu Apr 19 '18 at 4:49
1
\$\begingroup\$

Good work in general!

There are, however, two very large problems:

I really do not like SPAN_NDEBUG

Having different exception behaviors between debug and release is super bad. Exceptions exist to be handled. In your case, handling that exception sanely in debug but crashing in release would be catastrophic.

use assert() instead, that's what it's there for.

Inherit to expand is a massive code smell.

The whole point of span is for it to be a value type:

foo(Const_span<int>) {}

and NOT

foo(const Const_span<int>&) {}

So span<>s will always have to be converted into a Const_span<>s anyways. This makes having Span<> inherit from Const_span<> uncalled for, and brings nothing to the table.

Should a const Span prevent any mutable access? Currently it doesn't. It is more like a const iterator.

It's 100% clear that span<> does not have ownership of the data, so accessing mutable data from a const span is absolutely fine in my opinion

\$\endgroup\$
  • \$\begingroup\$ Use case: Span A has mutable access outside of function f. And it should only have immutable access within function f. Maybe the point about never using Const_span<int>& as an argument is right. \$\endgroup\$ – R zu Apr 18 '18 at 18:24
  • \$\begingroup\$ @RZu You can sort this out easily by allowing Const_span<> to be implicitely constructed from a span<>. \$\endgroup\$ – Frank Apr 18 '18 at 18:25
  • \$\begingroup\$ Thanks a lot for the help. I'm fixing the code and removing the Const_span. Const_span looks like a bad idea now. \$\endgroup\$ – R zu Apr 18 '18 at 18:42
  • \$\begingroup\$ No type conversion during template instantiation. The inheritance seems to make conversion from Span<T> to Const_span<T> possible even when T is a template parameter. I mean the case of template <typename T> void foo(Const_span<const T> x) {} Have to test this a bit more. \$\endgroup\$ – R zu Apr 18 '18 at 21:08
1
\$\begingroup\$

Frank has addressed the larger design issues as to whether you should in fact have a const_span. You might get what you want from propagate_const or some code based on that implementation.

But I want to address the question

A function like template <typename T> void f(gsl::span<const T> s) {} can't accept a gsl::span<int>. ⋯ So I make a Span<T>, which inherits from Const_span<T>.

Many years ago, long before Boost shared_ptr existed, I implemented reference counted pointers (as did a lot of people, I’m sure). Since the compiler did not have partial specializations it was basically impossible to make type<T> and type<const T> automatically produce different classes (the const version lacking the read-write forms of access and having different implementations for some of the functions).

So I did the obvious and made two different named types — handle and const_handle. Nobody was bothered by this, even years later when it would have been possible to write a partial specialization instead of two classes. (It was also natural to have more than one flavor of non-constness by having separate names — shared reference vs copy-on-write).

Also, compilers did not allow for template member functions, so it was not possible to write a templated constructor that implicitly converts. I used two work arounds which you can find on the linked page.

\$\endgroup\$
  • \$\begingroup\$ I like const_range<int> more than range<const int>. But I worry that it can cause some extra complications. For example, can handle<const int> implicitly convert to const_handle<int>? \$\endgroup\$ – R zu Apr 26 '18 at 1:05
  • \$\begingroup\$ @Rzu in my case, I never considered what happens if you put the const as part of the element type. That is, I never used handle<const T>. Writing these templates today, you could automatically ignore it, reject it at compile time, or make them synonyms for the same type. \$\endgroup\$ – JDługosz Apr 26 '18 at 17:03
  • \$\begingroup\$ I am thinking about adding a typedef that says const_range<T> is range<const T>. That sounds a good idea. Thanks. Now the user just have to remember range<const T> provides immutable access... hopefully that won't add too much to the cognitive load. \$\endgroup\$ – R zu Apr 26 '18 at 18:06
  • \$\begingroup\$ @Rzu if you mean a type alias (with the using keyword) rather than typedef, then exactly. Re cognative load: it’s the same as with string literals: "abc" is an array of const char. A span of that would be just like the pointer/length it directly replaces. That is, you should already understand that in general principle and not find it an additional thing to learn. \$\endgroup\$ – JDługosz Apr 26 '18 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.