6
\$\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\$
7
  • 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
    Commented Apr 18, 2018 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\$
    – user128454
    Commented Apr 18, 2018 at 18:02
  • \$\begingroup\$ @Franke see icl.cs.utk.edu/hpcc/software/index.html \$\endgroup\$
    – R zu
    Commented Apr 18, 2018 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\$
    – user128454
    Commented Apr 18, 2018 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
    Commented Apr 19, 2018 at 4:49

2 Answers 2

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\$
5
  • \$\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
    Commented Apr 18, 2018 at 18:24
  • \$\begingroup\$ @RZu You can sort this out easily by allowing Const_span<> to be implicitely constructed from a span<>. \$\endgroup\$
    – user128454
    Commented Apr 18, 2018 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
    Commented Apr 18, 2018 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
    Commented Apr 18, 2018 at 21:08
  • \$\begingroup\$ "The whole point of span is for it to be a value type:" <- span is a reference type. \$\endgroup\$
    – einpoklum
    Commented Mar 9, 2021 at 8:16
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\$
4
  • \$\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
    Commented Apr 26, 2018 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
    Commented Apr 26, 2018 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
    Commented Apr 26, 2018 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
    Commented Apr 26, 2018 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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