Skip to content
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

Return ranges instead of vectors #6

Closed
seanmiddleditch opened this issue Jan 23, 2016 · 6 comments
Closed

Return ranges instead of vectors #6

seanmiddleditch opened this issue Jan 23, 2016 · 6 comments

Comments

@seanmiddleditch
Copy link

@seanmiddleditch seanmiddleditch commented Jan 23, 2016

RTTR functions like get_properties currently return a std::vector object. Creation of this object requires allocating backing memory every single time that get_properties is invoked.

A superior approach would be to return a "range" type like an array_view instead of the vector in such interfaces. This type would still allow using C++ iteration and range-based-for over the returned elements, but would remove the use of allocation.

An array_view may be too simple to use for some of the data structures used in RTTR's internals, of course, but an iterator_range can also be written that operates on a custom iterator type that is able to properly introspect RTTR's data.

Using such range types judiciously removes all need to ever allocate temporary containers while querying or enumerating the type database with very little (if any) loss of features currently present in RTTR.

// range for array-like containers
template <class T>
struct array_view {
  T* _begin = nullptr;
  T* _end = nullptr;

  array_view() = default;
  array_view(T* being, T* end) : _begin(begin), _end(end) {}

  T* begin() const { return _begin; }
  T* end() cont { return _end; }
  size_t size() const { return _end - _begin; }
  T& operator[](size_t i) const { return _begin[i]; }
};

// implementation of a range getter
array_view<property> type::get_properties() const
{
  // rough simulacrum of RTTR internals
  return {m_class_properties.data(), m_class_properties.data() + m_class_properties.size()};
}

// usage of the library doesn't change at all
for (property& p : my_type.get_properties())
  { /*...*/ }
@acki-m
Copy link
Contributor

@acki-m acki-m commented Jan 24, 2016

What happens, when somebody doesn't use the RTTR_REGISTRATION macro and register his reflection information somehow later inside main().
For example, a user retrieve an array_view of properties and after that operation additional data is inserted in the source vector of the properties. This would invalidate the iterators. Crash. Right?

When you can show me a way to avoid such situation I will rethink this issue.

But anyway, is this additional memory allocation really such a bottleneck?

Loading

@seanmiddleditch
Copy link
Author

@seanmiddleditch seanmiddleditch commented Jan 25, 2016

The user should not save the array_view. That's pretty much standard for anything of its sort: it's a temporary object used for local work and not to be "saved" long term. If you're paranoid about users doing stupid things, you can instead return an object that wraps the underlying data structure and produces iterators on demand from the current state of the data. Of course, if the user saves an iterator and modifies something, it'll still crash, but that's C++ in general.

Loading

@seanmiddleditch
Copy link
Author

@seanmiddleditch seanmiddleditch commented Jan 25, 2016

Also, since you mentioned usability by game engines in #5, I should note that the needless allocations required by returning a vector here are a very big problem for games. Also, allocations of any kind that can't be overridden and controlled by the application. Game developers are often extremely demanding about controlling, tracking, and optimizing memory usage. :)

Loading

@acki-m
Copy link
Contributor

@acki-m acki-m commented Jan 31, 2016

the next feature I would like to add to RTTR is the possibility to filter the returned properties.
e.g.

// this should return a list of all properties which are statically declared
auto prop_list = type::get_by_name("foo").get_properties(bind_flags::statically); 

These properties will not lie consecutively in memory. I would need some kind of on demand iterator.
This array_view concept should handle this too. I really have to think about this before implementing it.

Loading

@seanmiddleditch
Copy link
Author

@seanmiddleditch seanmiddleditch commented Feb 6, 2016

Lazy forward ranges are a common feature of any range library. :)

I might suggest you read through Eric Niebler's rather extensive writings on what is likely going to become a major C++ library feature in the future (possibly even a TS by C++17). Even if it's not in C++ proper, the general concepts and ideas are pretty useful. Various game engines have been using them for years, ever since Alexandrescu and co popularized them in the D programming language.

The simple version that's more like current C++ would indeed just be a new iterator type that knows how to find the next element with a special form to represent the end iterator (because C++ won't support sentinels until C++17).

class iterator {
  elem* _cur;
  int _flags;

  void next() {
    ++_cur;
    while (*_cur != special_sentinel_value && (_cur->flags & _flags) == _flags)
      ++_cur;
  }

  operator++
  operator+
  operator==
  etc.
};

And of course, if someone actually did want that in a vector, it becomes as simple as:

auto range = type::get_by_name("foo").get_properties(bind_flags::statically); 

  // modern C++ iteration
for (auto const& prop : range)
  stuff(prop);

// copy into a vector
std::vector<rttr::property> props(range.begin(), range.end());

Ranges are neat. Views, like I originally suggested, are just a particular type of range.

Loading

acki-m added a commit that referenced this issue Mar 20, 2016
The class "array_range" is used to get a view into the stored properties,
instead copying all properties together into a std::vector, which allocates heap memory.

Remark: The memory usage will be slightly higher, because all properties including base properties
of a type are now stored inside an own vector.

The class "flat_map" is used for internal usage; it is a map with contiguous memory for key and values.

This branch is to implement the request of issue #6

To Do: Implement the same for methods, constructors, enumerations and types.
@acki-m
Copy link
Contributor

@acki-m acki-m commented Apr 28, 2016

@seanmiddleditch
I merged your feature request to master now. Have a look and tell me what you think.
The new class is called array_range.

Loading

@acki-m acki-m closed this Apr 28, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants