Runtime: Add Overlaps/Within extension methods for ReadOnlySpan<T>

Created on 17 Sep 2017 · 16Comments · Source: dotnet/runtime

This proposal adds utility methods for checking spans for overlaps or if a span is within in another span. For previous discussions see https://github.com/dotnet/corefx/issues/17793, https://github.com/dotnet/corefxlab/issues/827 and https://github.com/dotnet/corefx/issues/18750. And a closed PR https://github.com/dotnet/corefx/pull/18731.

Proposed API

Add two sets of extension methods Overlaps and Within for ReadOnlySpan<T> in SpanExtensions:

public static class SpanExtensions
{
    public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second);
    public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second, 
        out int elementOffset);
    public static bool Within<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second);
    public static bool Within<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second, 
        out int elementOffset);}
}

If second span does not match the alignment of first span an ArgumentException is thrown.
out int elementOffset is the relative offset or index of the start of the second span to the start of the first span.
elementOffset is only valid if the check in question returns true.

Rationale and Usage

For Overlaps the scenario can involve algorithms that transform elements from first to second span,
if the spans overlap the result might be wrong depending on the algorithm. To be able to detect this
the Overlaps method can be called.

For Within the scenario can involve buffer pool management, where spans are leased from a buffer and later needs to be returned to a given buffer. Calling Within allows checking for which
buffer the given span is within and thus where it must be returned to.

Expected Results

A: first entirely before second, no overlap

first:   [--------)
         xRef     xRef + xLength
second:           [------------)     
                  yRef         yRef + yLength

B: first starts before second and ends inside second

first:   [------------)
         xRef         xRef + xLength
second:              [------------)     
                     yRef         yRef + yLength

C: first is entirely within second

first:       [-----------------------)
             xRef                    xRef + xLength
second:    [--------------------------)     
           yRef                       yRef + yLength

D: first starts inside target second and ends after second end

first:            [------)
                  xRef   xRef + xLength
second:    [-------)
           yRef   .            yRef + yLength

E: first entirely after second, no overlap

first:            [------------)     
                  xRef         xRef + xLength
second:  [--------)
         yRef     yRef + yLength

F: first starts before second and
ends after second, i.e. second is contained in first

first:   [-------------------------------)
         xRef                            xRef + xLength
second:    [--------------------------)     
           yRef                       yRef + yLength

G: first is same as second

first:   [--------------------------)
         xRef                       xRef + xLength
second:  [--------------------------)     
         yRef                       yRef + yLength

H: first is empty within second

first:    [)
          xRef
second:  [--------------------------)     
         yRef                       yRef + yLength

I: first is empty before second

first:  [)
        xRef
second:  [--------------------------)     
         yRef                       yRef + yLength

J: first is empty after second

first:                              [)
                                    xRef
second:  [--------------------------)     
         yRef                       yRef + yLength

In table below Overlaps => first.Overlaps(second) or Within => first.Within(second). x => first and y => second.

| |Overlaps |Within |Extra checks/comment |
|--------|-----------|-----------|---------------|
|A/E |false |false |No way to know which case from these methods alone.|
|B |true |false |elementOffset > 0|
|C |true |true | |
|D |true |false |elementOffset < 0|
|F |true |false |elementOffset >= 0 && xLength >= (elementOffset + yLength)|
|G |true |true |elementOffset == 0 && xLength == yLength|
|H |true |true |xLength == 0|
|I/J |false |false |No way to know which case from these methods alone.|

Examples

public static void RepeatEvenIndices(ReadOnlySpan<byte> src, Span<byte> dst)
{
    if (src.Overlaps(dst, out var elementOffset) && elementOffset >= -1)
    {
        throw new ArgumentException();
    }

    for (int i = 0; i < src.Length / 2; i++)
    {
        dst[i + 0] = src[i * 2];
        dst[i + 1] = src[i * 2];
    }
}

Open Questions

Could this API be expressed differently, perhaps with an all encompassing Overlap method returning an enum? Performance downsides?

Naming of the methods should be reviewed.

Updates

UPDATE 1: Rename Contains to Within with reversed first/second relationship, due to naming confusion. Rename elementIndex to elementOffset latter considered better. elementOffset only valid if check returns true. Revise table and add empty cases.

cc: @ektrah @mgravell @ahsonkhan @shiftylogic @jkotas

api-approved area-System.Memory

Source

nietras

Most helpful comment

Should there also be overloads with Span\

public static class SpanExtensions
{
    public static bool Overlaps<T>(this Span<T> first, ReadOnlySpan<T> second);
    public static bool Overlaps<T>(this Span<T> first, ReadOnlySpan<T> second, out int elementOffset);
}

Otherwise users have to cast every Span\

Span<byte> first = ...;
Span<byte> second = ...;
bool result = ((ReadOnlySpan<byte>)first).Overlaps(second);

ektrah on 31 Oct 2017

👍3

All 16 comments

A few thoughts:

elementIndex cannot be an int because the difference between xRef and yRef may be greater than int.MaxValue.
If the spans do not overlap (A and E) then elementIndex is not meaningful, because the GC may change the relative order of the two objects at any time. (This might actually fix the previous issue.)
The name Contains is very confusing.
The name elementIndex should probably be something like startDifference or startOffset.
An empty span does not overlap any other span.

Another idea that might be worth considering:

public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second);
public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second, 
    out int startDifference);
public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second, 
    out int startDifference, out int endDifference);

where startDifference = yRef - xRef and endDifference = (yRef + yLength) - (xRef + xLength) = startDifference + (yLength - xLength).

| | Overlaps | Extra checks
| ----- | ---------- | ------------
| A | false |
| B | true | startDifference > 0 && endDifference > 0
| C | true | startDifference < 0 && endDifference > 0
| D | true | startDifference < 0 && endDifference < 0
| E | false |
| F | true | startDifference > 0 && endDifference < 0
| G | true | startDifference == 0 && endDifference == 0

ektrah on 17 Sep 2017

@ektrah, what is the value of having the following:
```C#
public static bool Overlaps(this ReadOnlySpan first, ReadOnlySpan second,
out int startDifference);

Also, there is no way to distinguish between scenario A & E based on the output of Overlaps (from your design) but I don't think we need to. 
@nietras, if Overlaps returns false, does it ever matter if it is because of scenario A instead of E and vice versa?

Regarding:
> In case of the `second` not matching the alignment of `first` span an `ArgumentException` is thrown.

Can you please provide an example where we would throw an exception?

Similar to @ektrah, I don't think Contains would work as a name. I think of contains the same way as Array.contains or List.Contains:
https://msdn.microsoft.com/en-us/library/bb384015.aspx
https://msdn.microsoft.com/en-us/library/bhkz42b3(v=vs.110).aspx

I am not sure about ContainsSlice either. I think of ContainsSlice as follows:
```C#
Span<byte> src = new byte [1, 2, 3, 4, 5];
Span<byte> items = new byte [2, 3, 4];
src.ContainsSlice(items); // returns true;

Maybe IsContainedWithin?
C# src.IsContainedWithin(dest)

@ektrah's proposal avoids the naming issue altogether.

ahsonkhan on 19 Sep 2017

what is the value of having the following:

You don't have to type , out _ if you don't need the second out parameter.

I don't have a strong opinion if this overload should be there or not. Since endDifference can be easily computed from startDifference and the span lengths, the overload with out endDifference may actually not be strictly necessary.

Also, there is no way to distinguish between scenario A & E based on the output of Overlaps (from your design) but I don't think we need to.

If the spans overlap, then it's reasonable to assume that the spans refer to the same object in managed memory. (Unsafe code can defeat that assumption.)

If the spans do not overlap (A & E), then it's quite likely that they do not refer to the same object in managed memory. Since there is no defined distance or relative order between two arbitrary objects in managed memory, there is no meaningful elementIndex that Overlaps could return from which the caller could infer if it's A or E.

Can you please provide an example where we would throw an exception?

var bytes = new byte[16];

var first = new Span<byte>(bytes, 0, 8).NonPortableCast<byte, int>();
var second = new Span<byte>(bytes, 7, 8).NonPortableCast<byte, int>();

var overlaps = first.Overlaps(second, out int elementIndex);

What should the value of elementIndex be?

Ignoring this corner case may actually not be that bad. An exception would be fine as well though (IMO).

ektrah on 19 Sep 2017

@nietras, any thoughts or updates for this API proposal (fix the TODOs)?

I would consider @ektrah's idea which removes the need of a Contains method:
C# public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second); public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second, out int startDifference, out int endDifference);

You mentioned previously (from https://github.com/dotnet/corefx/issues/18750#issuecomment-296601237):

but we probably need dedicated methods for each since there are different optimizations paths for each

Can you explain why they would have different optimization paths?

ahsonkhan on 28 Oct 2017

@ektrah thanks for the feedback and answering questions :)

elementIndex cannot be an int because the difference between xRef and yRef may be greater than int.MaxValue.

They cannot be greater than int.MaxValue since Span<T> is limited to int Length. Note also that this is element offset.

If the spans do not overlap (A and E) then elementIndex is not meaningful, because the GC may change the relative order of the two objects at any time. (This might actually fix the previous issue.)

If a user knows the spans come from the same memory segment this could have utility, but it is an edge case, and I agree. It makes the API/implementation more straightforward too by removing this case.

The name elementIndex should probably be something like startDifference or startOffset.

I think element is crucial in the name here, since the offset is in number of elements, not in bytes. startElementOffset I can live with, or if we favor brevity then just elementOffset, offset at least seems better than index. Good suggestions.

An empty span does not overlap any other span.

There are edge cases here, an empty span has Length == 0, but it still might have a position i.e. a ref so it still could be interpreted to be inside another span. Perhaps the analogy to Rectangle in System.Drawing could be used as a guiding path here, see below.

The name Contains is very confusing.

It is not ideal I agree, but there is prior work especially from System.Drawing (see e https://msdn.microsoft.com/en-us/library/system.drawing.rectangle(v=vs.110).aspx), where Contains is used for example to find rectangles inside other rectangles. Here IntersectsWith is used instead of Overlaps. Although different rectangle types also use simply Intersects. Arguably, Overlaps is better in my mind than Intersects for spans.

Below examples of Rectangle methods:

Contains(Point) Determines if the specified point is contained within this Rectangle structure.
Contains(Rectangle) Determines if the rectangular region represented by rect is entirely contained within this Rectangle structure.
IntersectsWith(Rectangle)   Determines if this rectangle intersects with rect.
Intersect(Rectangle)    
Replaces this Rectangle with the intersection of itself and the specified Rectangle.

This also suggests that an Intersect extension method may have interest if one was interested in only the intersection of spans.

There are other examples and one I would then pitch instead, namely Within, this reverses the relationship but I think it reads well:

if (child.Within(parent, out var childElementOffset))
{
    // Return to pool
}
if (child.Within(parent))
{
    // Return to pool
}

consider @ektrah's idea which removes the need of a Contains method/why they would have different optimization paths?

@ahsonkhan the Contains/IsSliceOf/Within method started off as a proposal from @mgravell and I believe the scenario is in a hot spot in memory management for kestrel. Thus, Within needs to be fast, and the checks are a bit different for the two methods, which maybe have different performance characteristics. Maybe, but I don't think that should be the main reason for having Within, it should be usability. In my mind it is better to have dedicated methods for each since code will read much better.

So to sum I would change the proposal to:

public static class SpanExtensions
{
    public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second);
    public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second, 
        out int elementOffset);
    public static bool Within<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second);
    public static bool Within<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second, 
        out int elementOffset);}
}

Let me know what you think. And I will try to update the proposal as soon as feedback comes in, sorry for the long reply here. If we still cannot agree on Within perhaps we should consider splitting this proposal again, despite my earlier reservations about this.

Possible other extensions inspired by Rectangle and set theory, just so we consider the family of these set like methods...

public static class SpanExtensions
{
    public static Span<T> Intersect<T>(this Span<T> first, Span<T> second);
    public static ReadOnlySpan<T> Intersect<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second);
}

There is also the Difference between sets. I.e. removing any elements overlapping between spans from say the first span. All of which is probably a bit theoretical, since I have no concrete use case for these yet.

nietras on 28 Oct 2017

So to sum I would change the proposal to

@nietras, I have updated the original post with the method rename (Contains -> Within) and parameter rename (elementOffset -> elementIndex).

If you get a chance, please update (or remove) the TODOs and remove the WIP. Marking API ready for review.

I will solicit additional feedback (if any) during API review.

ahsonkhan on 31 Oct 2017

@ahsonkhan I have revised the proposal and added new cases and checks to remove the last edge cases. Didn't have time to add more examples, hope this is good enough for review.

nietras on 31 Oct 2017

👍1

Video

We seem to believe Overlaps seems like a good addition (having both overloads), but it looks like Within is redundant/not any faster.

C# public static class SpanExtensions { public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second); public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second, out int elementOffset); }

terrajobst on 31 Oct 2017

out int byteOffset? then copes with misaligned

CompareTo uses

benaadams on 31 Oct 2017

Should there also be overloads with Span\

public static class SpanExtensions
{
    public static bool Overlaps<T>(this Span<T> first, ReadOnlySpan<T> second);
    public static bool Overlaps<T>(this Span<T> first, ReadOnlySpan<T> second, out int elementOffset);
}

Otherwise users have to cast every Span\

Span<byte> first = ...;
Span<byte> second = ...;
bool result = ((ReadOnlySpan<byte>)first).Overlaps(second);

ektrah on 31 Oct 2017

👍3

@ektrah Span implicitly converts to ReadOnlySpan

 public static implicit operator ReadOnlySpan<T>(Span<T> span)

UPDATE: Sorry, you are right that for as an extension method this has issues...

it looks like Within is redundant/not any faster.

@terrajobst fair enough. Guess we´ll have to prove that wrong if not 😉 Shall I update the proposal to show only Overlaps has been approved? I also want to add that alignment exception is only thrown if there is overlap and misalignment.

out int byteOffset? then copes with misaligned

@benaadams cast to Span<byte> then check. I believe the current API shape fits most users expectations.

nietras on 31 Oct 2017

@nietras Yes, except if you use extension method syntax.

ektrah on 31 Oct 2017

@ektrah yeah I updated my comment two seconds after realizing that. My
mistake. I think it would be good to add these overloads too, otherwise
they become too cumbersome.

On Oct 31, 2017 8:08 PM, "ektrah" notifications@github.com wrote:

@nietras https://github.com/nietras Yes, except if you use extension
method syntax.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/dotnet/corefx/issues/24103#issuecomment-340875103,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKTG73GwXCkJhZ6__5Kz7Z1__HRnrTB5ks5sx3BEgaJpZM4PaGZ9
.