Special case for sparse IndexSpace overlap test

[mpokorny]

The implementation of Realm::IndexSpace<N,T>::overlaps_approx()

legion/runtime/realm/indexspace.inl

Lines 1285 to 1305 in 9074bbf

	template <int N, typename T>
	inline bool IndexSpace<N,T>::overlaps_approx(const IndexSpace<N,T>& other) const
	{
	if(dense()) {
	if(other.dense()) {
	// just test bounding boxes
	return bounds.overlaps(other.bounds);
	} else {
	// have the other guy test against our bounding box
	return other.contains_any_approx(bounds);
	}
	} else {
	if(other.dense()) {
	return contains_any_approx(other.bounds);
	} else {
	// nasty case - both sparse
	assert(0);
	return true;
	}
	}
	}

bails out when both index spaces are sparse. However, I was wondering whether there isn't a special case that is actually fairly easy to resolve: that is, when the sparsity maps are identical and the bounds overlap. Something like
if (sparsity == other.sparsity) return bounds.overlaps(other.bounds);
before the assert(0);.
I'm uncertain about the correctness in general, but it seems reasonable based on my limited understanding. Making this change in my local repo allowed me to work around the otherwise missing implementation, and provided the correct result in my application.

[streichler]

Yes, that'd be correct. Apart from a minor code reordering tweak, I'll submit a fix for that shortly. Thanks for the suggestion!

[mpokorny]

Another test when both IndexSpaces are sparse?
if (!bounds.overlaps(other.bounds)) return false;
Perhaps that's always valid and could be done up front, although I'm not sure of the relative performance impacts of applying tests in the various branches.

[mpokorny]

Another question: if I understand the purpose (doubtful!) of Realm::IndexSpace<N,T>::overlaps_approx(), if it's the case that when the return value is false then necessarily the IndexSpaces don't overlap, wouldn't it be correct to return the value of bounds.overlaps(other.bounds) whenever both IndexSpaces are sparse? Maybe not efficient for the runtime, but at least correct. Sorry to keep bugging you, but my code continues to trip over this section of the Legion code, even with the changes proposed so far.

[streichler]

Yes, overlaps_approx must return true if there is overlap, but it's also allowed to return true in non-overlap cases. The goal is that this imprecision will only happen when it's holes in a sparsity mask that avoid the overlap. (Technically it'd be legal to simply return true in all cases, but that wouldn't be very useful.)

Can you describe the use case that is causing you to call this method?

[mpokorny]

I believe (based on the call stack in the core file) that this method is being called as a consequence of my application calling `Legion::Runtime::create_partition_by_image_range()`, although I'm not certain of it. The idea is to project an IndexPartition on IndexSpace "I_A" that is a subspace of IndexSpace "I" to another IndexSpace "I_B" that is also a subspace of "I", where any of the IndexSpaces may be sparse.

…

On Fri, 21 Dec 2018 at 11:35, streichler wrote: Yes, `overlaps_approx` must return true if there is overlap, but it's also allowed to return true in non-overlap cases. The goal is that this imprecision will only happen when it's holes in a sparsity mask that avoid the overlap. (Technically it'd be legal to simply return true in all cases, but that wouldn't be very useful.) Can you describe the use case that is causing you to call this method?

-- Martin

[streichler]

Can you paste the backtrace here?

[mpokorny]

#0 0x0000003d1da32495 in raise () from /lib64/libc.so.6
#1 0x0000003d1da33c75 in abort () from /lib64/libc.so.6
#2 0x0000003d1da2b60e in __assert_fail_base () from /lib64/libc.so.6
#3 0x0000003d1da2b6d0 in __assert_fail () from /lib64/libc.so.6
#4 0x0000000002217555 in Realm::IndexSpace<3, long long>::overlaps_approx (this=0x7fb41d013c80, other=...)
at legion/runtime/realm/indexspace.inl:1195
#5 0x00000000022187f0 in Realm::OverlapTester<3, long long>::test_overlap (this=0x7fb400012aa0, space=...,
overlaps=std::set with 1 element = {...}, approx=true)
at legion/runtime/realm/deppart/partitions.cc:279
#6 0x000000000237120f in Realm::ImageOperation<3, long long, 3, long long>::set_overlap_tester (this=0x7fb41cb029c0,
tester=0x7fb400012aa0) at legion/runtime/realm/deppart/image.cc:574
#7 0x0000000002218a9e in Realm::ComputeOverlapMicroOp<3, long long>::execute (this=0x7fb40000f770)
at legion/runtime/realm/deppart/partitions.cc:499
#8 0x0000000002200dec in Realm::PartitioningMicroOp::finish_dispatch (this=0x7fb40000f770, op=0x7fb41cb029c0, inline_ok=true)
at legion/runtime/realm/deppart/partitions.cc:429
#9 0x0000000002218c13 in Realm::ComputeOverlapMicroOp<3, long long>::dispatch (this=0x7fb40000f770, op=0x7fb41cb029c0,
inline_ok=true) at legion/runtime/realm/deppart/partitions.cc:524
#10 0x0000000002370939 in Realm::ImageOperation<3, long long, 3, long long>::execute (this=0x7fb41cb029c0)
at legion/runtime/realm/deppart/image.cc:523
#11 0x0000000002201d27 in Realm::PartitioningOpQueue::worker_thread_loop (this=0x318d430)
at legion/runtime/realm/deppart/partitions.cc:874
#12 0x000000000221a7d2 in Realm::Thread::thread_entry_wrapper<Realm::PartitioningOpQueue, &Realm::PartitioningOpQueue::worker_thread_loop> (obj=0x318d430) at legion/runtime/realm/threads.inl:131
#13 0x00000000021cc126 in Realm::KernelThread::pthread_entry (data=0x318d560)
at legion/runtime/realm/threads.cc:700
#14 0x0000003d1e207aa1 in start_thread () from /lib64/libpthread.so.0
#15 0x0000003d1dae8bcd in clone () from /lib64/libc.so.6

[streichler]

Ok, I've reproduced the error with a small test case. I'll work on a fix tonight.

[streichler]

@mpokorny can you try this again in the master branch? Commit fcbfb04 hopefully cleans this up.

[mpokorny]

Looks good, all test cases for my application now pass. Thanks, @streichler.