Closed brycelelbach closed 1 year ago
Patch coverage: 88.63%
and project coverage change: -0.09%
:warning:
Comparison is base (
1864f09
) 97.67% compared to head (0d3116f
) 97.58%. Report is 3 commits behind head on main.:exclamation: Current head 0d3116f differs from pull request most recent head abba492. Consider uploading reports for the commit abba492 to get more accurate results
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
Thanks very much for the drive-by fixes, they look great!
In for_each_while_impl
, we need to eventually call the predicate with a tuple of elements, not a tuple of cursors. It looks like you are building up a tuple of elements (despite the param name), but constructing the tuple on line 271 doesn't look right to me -- I think it should be element_t
rather than cursor_t
?
(This happens to work for the particular case of a cartesian product of iotas, because for an iota sequence the element type and the cursor type happen to be the same.)
Other than that I think this looks like a reasonable approach -- I wish the keep_going
variable wasn't necessary at every level, but I can't think of a way to get rid of it, and if it doesn't affect vectorisation then I guess we're okay.
In for_each_while_impl, we need to eventually call the predicate with a tuple of elements, not a tuple of cursors. It looks like you are building up a tuple of elements (despite the param name), but constructing the tuple on line 271 doesn't look right to me -- I think it should be element_t rather than cursor_t?
(This happens to work for the particular case of a cartesian product of iotas, because for an iota sequence the element type and the cursor type happen to be the same.)
Ah-ha, I think I suffered from a misunderstanding here. I believe you are correct.
I'm surprised the tests didn't uncover this, but I just realized we don't have any tests that actually call for_each
on cartesian_product
. I was just testing with my benchmark.
Other than that I think this looks like a reasonable approach -- I wish the keep_going variable wasn't necessary at every level, but I can't think of a way to get rid of it, and if it doesn't affect vectorisation then I guess we're okay.
I was a little bit concerned that the control flow of this would cause issues, but it seems to be fine.
The one idea I had for working around this was to not use flux::for_each_while
to iterate each of the underlying sequences, however that seems like a gross violation of the basic principles here. If we did that, it would break more deeply nested internal iteration (for example, cartesian_product(filter(...), ...)
).
I'm surprised the tests didn't uncover this, but I just realized we don't have any tests that actually call
for_each
oncartesian_product
. I was just testing with my benchmark.
Ironically, the unpack
test that you added does a for_each
on cartesian_product
, but it's on ints
so it doesn't catch this, and I didn't run it before committing anyways.
Ah-ha, I think I suffered from a misunderstanding here. I believe you are correct.
I'm surprised the tests didn't uncover this, but I just realized we don't have any tests that actually call
for_each
oncartesian_product
. I was just testing with my benchmark.
I'm having trouble writing a test that covers this issue. Any ideas?
EDIT: All the cartesian_product
tests currently use things that are convertible to the index types, which is probably why I'm not seeing the failures. I can probably engineer something with a mock type.
In
for_each_while_impl
, we need to eventually call the predicate with a tuple of elements, not a tuple of cursors. It looks like you are building up a tuple of elements (despite the param name), but constructing the tuple on line 271 doesn't look right to me -- I think it should beelement_t
rather thancursor_t
?(This happens to work for the particular case of a cartesian product of iotas, because for an iota sequence the element type and the cursor type happen to be the same.)
Tests added in a240dcc8d6aa4a1023e28ee94d83d3d68d640d82, fixed in 02e73b3c0d97a414f600dfe5391832cf12a67809.
Ah-ha, I think I suffered from a misunderstanding here. I believe you are correct. I'm surprised the tests didn't uncover this, but I just realized we don't have any tests that actually call
for_each
oncartesian_product
. I was just testing with my benchmark.I'm having trouble writing a test that covers this issue. Any ideas?
I think what you want is some sequences where the element type and cursor type are distinct and can't be converted to one another? What about something like:
auto seq1 = flux::ints(1).take(3);
auto seq2 = std::array<std::string_view, 2>{"aaa", "bbb"};
auto cart = flux::cartesian_product(seq1, seq2);
auto cur = flux::find_if(cart, flux::unpack([](auto i, auto s) { return i == 2 && s == "bbb"; }));
STATIC_CHECK(std::get<0>(cart[cur]) == 2);
STATIC_CHECK(std::get<1>(cart[cur]) == "bbb");
This PR implements internal iteration for
cartesian_product[_with]
, which enables compiler vectorization of multidimensional iteration patterns constructed withcartesian_product[_with]
(such as this one).Core tasks:
cartesian_product
.cartesian_product
internal iteration to invoke the predicate with a tuple of elements, not a tuple of indices (review feedback).cartesian_product_with
.cartesian_product[_with]
random access indexing.cartesian_product[_with]
in general.cartesian_product
with 3 underlying sequences.cartesian_product
with less than 2 and more than 3 underlying sequences.cartesian_product
random access indexing.cartesian_product
for_each_while
short circuiting (review feedback).cartesian_product[_with]
withfor_each[_while]
.cartesian_product
ofints
to fix MSVC build (review feedback).cartesian_product
andiota
.cartesian_product
ofiota
multi-dimensional iteration pattern.STATIC_CHECK
to throw instead of returning to improve compile-time diagnostics.word_count
example CTest as it will always hang waiting for stdin.