You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
We were thinking of adding STL-style iterators. But nobody implemented this yet. Would be great to have. As they are random access, this might indeed not be so difficult.
I was experimenting with isl_*_iterator types. To avoid having a new iterator type for each thing it could iterate (e.g. isl_map_basic_map_iterator, isl_basic_map_list_iterator), the difficulty was to support multiple internal data structures (mainly hashtables and flat arrays, but their size is stored differently everwhere).
What was the problem with having multiple iterator classes?
I see two category of things worthy of iterator behavior:
- implicitly "iterable" objects, like a map is a collection of
basic_maps and a union_map is a collection of maps;
- explicitly-defined collections, isl_*_list.
For the second, I was thinking about a class template isl_list_iterator
which is aware of the internals of the list.
On 25/07/17 15:02, Michael Kruse wrote:
I was experimenting with isl_*_iterator types. To avoid having a new
iterator type for each thing it could iterate (e.g.
isl_map_basic_map_iterator, isl_basic_map_list_iterator), the
difficulty was to support multiple internal data structures (mainly
hashtables and flat arrays, but their size is stored differently
everwhere).
—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
<#5 (comment)>, or
mute the thread
<https://github.com/notifications/unsubscribe-auth/ABcTa8Fzb_h8Du9zhUhkbrq41vkpQhEfks5sRedZgaJpZM4Oiadw>.
What was the problem with having multiple iterator classes?
No genericity for the library's user / missing abstraction.
Lot's and lot's of new public functions necessary.
Library blow-up with boilerplate code.
It is common for C++ to make a template for this, but not really C-like.
In contrast to C++ templates, no performance advantage. Unless we declare them in the headers, they cannot be inlined. Speed will be governed by the function call overhead.
For the second, I was thinking about a class template isl_list_iterator
which is aware of the internals of the list.
IMHO the C++ binding should only use the public C interface.
I agree with @ftynse, it seems discussing isl_*_list and implicitly "iterable" objects separately is a good idea.
I would expect that for list types, we automatically derive a begin(), and end() iterator. I assume we can use the functions isl_element_list_n_element, isl_element_list_get_element, and isl_element_list_get_element to make this happen to implement an iterator here.
For functions such as isl_set_foreach_point, I would just derive an iterator that calls the foreach function, adds all elements to a vector, and then uses the iterator of this vector. I doubt there will be a performance problem here (but we can fix it later). Even if we want to fix this today, having a already working iterator is a good start to see what is missing in the isl interface to make the iterator more efficient.
Same here. If we all work on this together, chances are that less work
needs to be done overall. Until know it seems you guys just pile up a
large set of islpp hacks. ;-)
I am glad to review patches.
Best,
Tobias
Let's proceed with lists first. We already have some public functions like union_map_to_basic_map_list, which we can expose once we have the list iterators.
The problem for me with lists is that list element type name is included in the signature, in some cases twice, like isl_id_list_get_id. If we had a set of overloaded functions %elementtype% isl::list_get(%listtype%, int) or int isl::list_n(%listtype%), we could create a template class for iterators that relies on these functions. However, I cannot immediately see how we can make a standalone begin for that. Something like
won't be able to deduce Elem. We will need a sort of list_traits that would decay a list type into an element type, potentially through generated template specializations.
At this point, it appears reasonable to just have a template class isl::list instead, which would include the non-template iterator class and member begin/end functions. Overloaded functions are still useful unless we want to generate a bunch of specializations.
So I guess my question here is: can we get those overloads generated?
@TobiG the problem with creating a vector for implicit collections is that a new vector will be created on each call to begin(), and the iterators of different vectors won't compare true. I find it reasonable to expect set.foreach_point_begin() == set.foreach_point_begin() to be true.
@ftynse : I agree with the vector issue. Let's postpone it for now.
Regarding the lists, the first patch to be written is to expose some lists to the isl C++ bindings. This probably requires some minor macro hacking, as we likely do not want to expose all lists (isl_band_list e.g. should likely not be exposed).
If you want to go crazy with C++ the following might work, assuming we have list_add() always exported and already C++ types for it:
@TobiG the problem with creating a vector for implicit collections is that a new vector will be created on > each call to begin(), and the iterators of different vectors won't compare true. I find it reasonable to
expect set.foreach_point_begin() == set.foreach_point_begin() to be true.
This probably depends on the comparison function. Does anything prevent us from just comparing the position in the vector and the (pointer to the isl object) from which the vectors have been constructed? In case the iterator keeps a reference to the object we work on it cannot even be modified behind our back. let me give this a quick shot.
template<class T, class E>
class iterator {
std::vector<E> elements;
int position;
public:
iterator(T &obj) : position(0) {
// Some type traits here?
obj.foreach_basic_set(
[&] (E element) -> isl::stat {
elements.push_back(element);
return isl::stat::ok;
}
);
}
iterator() : position(-1) {}
iterator& operator++() {
if (position < elements.size() - 1)
position++;
else
position = -1;
return *this;
}
E operator*() { return elements[position]; }
bool operator==(iterator other) const { return position == other.position; };
bool operator!=(iterator other) const { return position != other.position; };
};
class set;
class basic_set;
iterator<set, basic_set> begin(set &obj) {
return iterator<set, basic_set>(obj);
}
iterator<set, basic_set> end(set &obj) {
return iterator<set, basic_set>();
}
it can be used as follows:
for (isl::basic_set bset : s)
isl_basic_set_dump(bset.get());
I certainly missed something, but as comparing iterators from different objects is undefined behavior (https://stackoverflow.com/a/4664519) the above implementation seems to be sufficient, no?
Indeed we can leverage the undefined behavior. Having an
assertion/exception for such cases seems philosophically safer though.
Keeping a vector inside each iterator seems somehow unsatisfying, but it
should be fine if we carefully avoid excessive copying: iterators are
supposed to be lightweight. At minimum, I would pass them by-reference
in our functions.
A tricky case is comparing values pointed-to by the iterator. I don't
know to which extent this should hold.
```c++
isl::set s(/*...*/);
if (*begin(s) != *begin(s)) cout << "this happens always";
```
|template<class T, class E> class iterator { std::vector<E> elements;
int position; public: iterator(T &obj) : position(0) { // Some type
traits here? obj.foreach_basic_set( [&] (E element) -> isl::stat {
elements.push_back(element); return isl::stat::ok; } ); } iterator() :
position(-1) {} iterator& operator++() { if (position <
elements.size() - 1) position++; else position = -1; return *this; } E
operator*() { return elements[position]; } bool operator==(iterator
other) const { return position == other.position; }; bool
operator!=(iterator other) const { return position != other.position;
}; }; class set; class basic_set; iterator<set, basic_set> begin(set
&obj) { return iterator<set, basic_set>(obj); } iterator<set,
basic_set> end(set &obj) { return iterator<set, basic_set>(); } |
it can be used as follows:
|for (isl::basic_set bset : s) isl_basic_set_dump(bset.get()); |
I certainly missed something, but as comparing iterators from
different objects is undefined behavior
(https://stackoverflow.com/a/4664519) the above implementation seems
to be sufficient, no?
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#5 (comment)>, or
mute the thread
<https://github.com/notifications/unsubscribe-auth/ABcTazG8NG1I7x2oQS2UjwI6Nr3_Tv5_ks5sZfMAgaJpZM4Oiadw>.
We can always make the vector a shared pointer, in case we want to make copying even cheaper. Not sure if this is worth the effort, though. It can also always be added later.
If we want the last to hold, we likely need to keep a cache of all start iterators in the object. I feel this could also be added later.
Combining both of your remarks gives the following idea: how about keeping a (shared/unique pointer to the) vector of basic_sets inside the set object itself? It can be filled on demand during the first call to begin(). This feels like a cleaner abstraction...
Potentially. The only problem I see is that this would require to change the code generator and special case it for objects that are iteratable. Also, there are objects with multiple foreachs.
I feel that if this is just part of the iterator class, the impact of the changes is more local. Complexity wise and performance wise, it should give the same results, right?
auto it = find(begin(container), end(container), something);
auto index = distance(begin(container), it);
idiom, the container will be traversed for each call to begin. On the other hand, we can document that iterator creation (but not copying) traverses the entire container. Although not typical, this behavior could occur in pointer-based data structures like single-linked lists or trees. So we can go with this.
Not sure how this would work with integration in isl though. This implementation looks like it can be placed in a separate header that does not require anything other than exported isl stuff.
Activity
tobiasgrosser commentedon Jul 25, 2017
We were thinking of adding STL-style iterators. But nobody implemented this yet. Would be great to have. As they are random access, this might indeed not be so difficult.
tobiasgrosser commentedon Jul 25, 2017
@Meinersbur had some ideas how to do this best.
Meinersbur commentedon Jul 25, 2017
I was experimenting with isl_*_iterator types. To avoid having a new iterator type for each thing it could iterate (e.g. isl_map_basic_map_iterator, isl_basic_map_list_iterator), the difficulty was to support multiple internal data structures (mainly hashtables and flat arrays, but their size is stored differently everwhere).
ftynse commentedon Jul 25, 2017
Meinersbur commentedon Jul 25, 2017
IMHO the C++ binding should only use the public C interface.
tobiasgrosser commentedon Jul 25, 2017
I agree with @ftynse, it seems discussing isl_*_list and implicitly "iterable" objects separately is a good idea.
I would expect that for list types, we automatically derive a begin(), and end() iterator. I assume we can use the functions isl_element_list_n_element, isl_element_list_get_element, and isl_element_list_get_element to make this happen to implement an iterator here.
For functions such as isl_set_foreach_point, I would just derive an iterator that calls the foreach function, adds all elements to a vector, and then uses the iterator of this vector. I doubt there will be a performance problem here (but we can fix it later). Even if we want to fix this today, having a already working iterator is a good start to see what is missing in the isl interface to make the iterator more efficient.
tobiasgrosser commentedon Aug 1, 2017
@ftynse: Any plans to move this forward? I would be glad to see a patch we can upstream?
ftynse commentedon Aug 1, 2017
tobiasgrosser commentedon Aug 1, 2017
ftynse commentedon Aug 1, 2017
Let's proceed with lists first. We already have some public functions like
union_map_to_basic_map_list, which we can expose once we have the list iterators.The problem for me with lists is that list element type name is included in the signature, in some cases twice, like
isl_id_list_get_id. If we had a set of overloaded functions%elementtype% isl::list_get(%listtype%, int)orint isl::list_n(%listtype%), we could create a template class for iterators that relies on these functions. However, I cannot immediately see how we can make a standalonebeginfor that. Something likewon't be able to deduce
Elem. We will need a sort oflist_traitsthat would decay a list type into an element type, potentially through generated template specializations.At this point, it appears reasonable to just have a template class
isl::listinstead, which would include the non-template iterator class and member begin/end functions. Overloaded functions are still useful unless we want to generate a bunch of specializations.So I guess my question here is: can we get those overloads generated?
ftynse commentedon Aug 1, 2017
@TobiG the problem with creating a vector for implicit collections is that a new vector will be created on each call to begin(), and the iterators of different vectors won't compare true. I find it reasonable to expect
set.foreach_point_begin() == set.foreach_point_begin()to be true.tobiasgrosser commentedon Aug 1, 2017
@ftynse : I agree with the vector issue. Let's postpone it for now.
Regarding the lists, the first patch to be written is to expose some lists to the isl C++ bindings. This probably requires some minor macro hacking, as we likely do not want to expose all lists (isl_band_list e.g. should likely not be exposed).
If you want to go crazy with C++ the following might work, assuming we have list_add() always exported and already C++ types for it:
https://stackoverflow.com/questions/27879815/c11-get-type-of-first-second-etc-argument-similar-to-result-of
Realistically, I would just adapt the generator to print iterators for any type which ends with "_list".
tobiasgrosser commentedon Aug 18, 2017
It seems even without iterators exporting isl_id_list would be useful for #11.
tobiasgrosser commentedon Aug 18, 2017
Interestingly, isl lists also have a function:
isl_##EL##_list_foreach
It seems as if we come up with a solution for the normal foreach loop, this would also cover lists.
tobiasgrosser commentedon Aug 18, 2017
@ftynse:
This probably depends on the comparison function. Does anything prevent us from just comparing the position in the vector and the (pointer to the isl object) from which the vectors have been constructed? In case the iterator keeps a reference to the object we work on it cannot even be modified behind our back. let me give this a quick shot.
tobiasgrosser commentedon Aug 18, 2017
The following works for me:
it can be used as follows:
I certainly missed something, but as comparing iterators from different objects is undefined behavior (https://stackoverflow.com/a/4664519) the above implementation seems to be sufficient, no?
ftynse commentedon Aug 18, 2017
tobiasgrosser commentedon Aug 19, 2017
We can always make the vector a shared pointer, in case we want to make copying even cheaper. Not sure if this is worth the effort, though. It can also always be added later.
If we want the last to hold, we likely need to keep a cache of all start iterators in the object. I feel this could also be added later.
ftynse commentedon Aug 28, 2017
Combining both of your remarks gives the following idea: how about keeping a (shared/unique pointer to the) vector of basic_sets inside the set object itself? It can be filled on demand during the first call to
begin(). This feels like a cleaner abstraction...tobiasgrosser commentedon Aug 28, 2017
Potentially. The only problem I see is that this would require to change the code generator and special case it for objects that are iteratable. Also, there are objects with multiple foreachs.
I feel that if this is just part of the iterator class, the impact of the changes is more local. Complexity wise and performance wise, it should give the same results, right?
ftynse commentedon Sep 1, 2017
Well, if you repeatedly call
beginlike in theidiom, the container will be traversed for each call to begin. On the other hand, we can document that iterator creation (but not copying) traverses the entire container. Although not typical, this behavior could occur in pointer-based data structures like single-linked lists or trees. So we can go with this.
Not sure how this would work with integration in isl though. This implementation looks like it can be placed in a separate header that does not require anything other than exported isl stuff.