check for slice overlap

[Nico]

I'm trying to determine whether two slices overlap.
This is what I have come up with using "unsafe":

package main

import (
"fmt"
"unsafe"
)

func doesOverlap(a, b []float64) bool {
aStart := uintptr(unsafe.Pointer(&a[0]))
aEnd := uintptr(unsafe.Pointer(&a[len(a)-1]))
bStart := uintptr(unsafe.Pointer(&b[0]))
bEnd := uintptr(unsafe.Pointer(&b[len(b)-1]))
return !(aEnd <= bStart || bEnd <= aStart)
}

func main() {
x := []float64{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
ys := x[0:5]
ym := x[2:7]
ye := x[5:10]
fmt.Println(doesOverlap(ys, ye))
fmt.Println(doesOverlap(ye, ys))
fmt.Println(doesOverlap(ys, ym))
fmt.Println(doesOverlap(ym, ye))
fmt.Println(doesOverlap(ys, x))
fmt.Println(doesOverlap(ym, x))
fmt.Println(doesOverlap(ye, x))
// Output:
// false
// false
// true
// true
// true
// true
// true
}

Two questions:
1) Is there a more efficient way?
2) Is it possible to avoid the use of "unsafe" without having to check
the address of each element in both slices?


Nico

PS: Note that I don't want to determine whether two slices share the
same base array as in math/big:

// alias returns true if x and y share the same base array.
func alias(x, y nat) bool {
return cap(x) > 0 && cap(y) > 0 && &x[0:cap(x)][cap(x)-1] ==
&y[0:cap(y)][cap(y)-1]
}

[roger peppe]

there's no need to use unsafe.
something like this should do the trick:

func overlaps(x, y []float64) bool {
if cap(x) == 0 || cap(y) == 0 {
return false
}
if &x[0:cap(x)][cap(x)-1] != &y[0:cap(y)][cap(y)-1] {
return false
}
x0 := -cap(x)
x1 := x0 + len(x)
y0 := -cap(y)
y1 := y0 + len(y)
return x1 > y0 && y1 > x0

> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[minux]

The question is what does the OP actually try to do?

because in the most general case where slices are created using SliceHeader and

package unsafe, i believe we must resort to use unsafe to detect overlaps efficiently.

(simply consider the case that I reduced capacity of a slice that otherwise will

overlap with another slice)

[Nico]

Is it safe to assume that all overlapping slices share the same base array?

[minux]

On Tue, May 21, 2013 at 8:02 PM, Nico <nicolas...@gmail.com> wrote:

Is it safe to assume that all overlapping slices share the same base array?

as i responded, yes if you only consider pure Go programs, no if you also

consider slices produced by cgo and unsafe.

[Nico]

On 21/05/13 12:53, roger peppe wrote:
> return x1 > y0 && y1 > x0

I should've written the condition like that to save one operation:

//return !(aEnd <= bStart || bEnd <= aStart)
return aEnd > bStart && bEnd > aStart

Thanks Roger, minux.
Both answers are very useful.

[roger peppe]

On 21 May 2013 13:01, minux <minu...@gmail.com> wrote:
> The question is what does the OP actually try to do?
> because in the most general case where slices are created using SliceHeader
> and
> package unsafe, i believe we must resort to use unsafe to detect overlaps
> efficiently.
> (simply consider the case that I reduced capacity of a slice that otherwise
> will
> overlap with another slice)

Agreed. In that case, the check in math/big might be wrong too of course.

Perhaps we should provide a single extra language primitive that
provided a way to ask about aliasing - we will need to do
something like this if we are to solve issues 395 and 1642.

Some possibilities, in order of increasing generality:

// alias returns whether x and y share any of the same
// underlying array.
func alias(x, y []T) bool

// overlap returns whether x and y overlap each other.
// The capacities of the slices do not affect the result.
func overlap(x, y []T) bool

// alias returns the slices of x and y that share the
// same memory, or (nil, nil) if they share no memory.
// The capacities of the slices do not affect the result.
func alias(x, y []T) ([]T, []T)

The second form of alias is useful only when we allow
setting the capacity of a slice, but if/when we do, it provides
a way to know *which* part of the slice is aliased, rather
than just whether it is.

[John Nagle]

On 5/21/2013 5:02 AM, Nico wrote:
> Is it safe to assume that all overlapping slices share the same base array?

In general, no. A use case for this is an aliasing check, to check
whether two slice parameters to a function are overlapping parts of the
same array. If there's aliasing, the function may have to make a
temporary copy, do things in a different order, or report an error.

John Nagle

[roger peppe]

Actually, in the absence of unsafe hackery, it *is* currently
true that all overlapping slices will share the same base array.

[minux]

On Tue, May 21, 2013 at 9:56 PM, roger peppe <rogp...@gmail.com> wrote:

On 21 May 2013 13:01, minux <minu...@gmail.com> wrote:
> The question is what does the OP actually try to do?
> because in the most general case where slices are created using SliceHeader
> and
> package unsafe, i believe we must resort to use unsafe to detect overlaps
> efficiently.
> (simply consider the case that I reduced capacity of a slice that otherwise
> will
> overlap with another slice)

Agreed. In that case, the check in math/big might be wrong too of course.

right. I'm wondering if we should file an issue.

i'm not sure we should add that to the language though.

it's very simple to do using unsafe and in environments where unsafe is unavailable

(e.g. App Engine or Go Playground) the simple method of comparing

&s[:cap(s)-1][cap(s)-1] will always work reliably.

[John Nagle]

Miscommunication. If someone submits two slice parameters to
a function which have different base arrays, that needs to be
reported as non-overlapping. The point being that "len" and "cap"
alone don't provide sufficient to decide this issue.

Disjointness is a good candidate for a built-in function.
It's cheap at the machine level and expensive at the reflection
level.

John Nagle

[roger peppe]

On 22 May 2013 14:24, minux <minu...@gmail.com> wrote:
>
> On Tue, May 21, 2013 at 9:56 PM, roger peppe <rogp...@gmail.com> wrote:
>>
>> On 21 May 2013 13:01, minux <minu...@gmail.com> wrote:
>> > The question is what does the OP actually try to do?
>> > because in the most general case where slices are created using
>> > SliceHeader
>> > and
>> > package unsafe, i believe we must resort to use unsafe to detect
>> > overlaps
>> > efficiently.
>> > (simply consider the case that I reduced capacity of a slice that
>> > otherwise
>> > will
>> > overlap with another slice)
>>
>> Agreed. In that case, the check in math/big might be wrong too of course.
>
> right. I'm wondering if we should file an issue.
>
> i'm not sure we should add that to the language though.
> it's very simple to do using unsafe and in environments where unsafe is
> unavailable
> (e.g. App Engine or Go Playground) the simple method of comparing
> &s[:cap(s)-1][cap(s)-1] will always work reliably.

It won't work reliably if we decide to fix either issue 395 or 1642.

If we *did* add it to the language, how would you like it to look?
What do you think about my suggestions above?

[minux]

right. imo solving this is a prerequisite for fixing those issues.

If we *did* add it to the language, how would you like it to look?
What do you think about my suggestions above?

i like the 2nd proposal.

how about we first try a library solution at this problem?

something like this in the runtime package (or reflect), just your 2nd

proposal changed to a package function.

// Overlapping returns true iff object a and b is aliasing each other.

// a and b should be slice or pointer to array, or it panics.

func Overlapping(a, b interface{}) bool

The main reason i don't use your 3rd proposal is that i haven't come up

with a use case where that level details is required.

i think future compiler optimization could make this as efficient as new

compiler intrinsic (to perserve correct stack traces on panics, the compiler

might not be able to inline it if it can panic, we can change so that it

returns false if a or b is of the wrong type).

because this doesn't rely on other things in the reflect package, i think it

should be placed in the runtime package.

[roger peppe]

Do you see a particular use case for allowing a pointer to an array
here? I'd prefer to allow slices only (trivially derivable from array pointers).

> The main reason i don't use your 3rd proposal is that i haven't come up
> with a use case where that level details is required.

Yes, I'm not sure whether how useful it is to know where the
overlap occurs as well as whether there is an overlap.

Anyone have a use case for it?

> i think future compiler optimization could make this as efficient as new
> compiler intrinsic (to perserve correct stack traces on panics, the compiler
> might not be able to inline it if it can panic, we can change so that it
> returns false if a or b is of the wrong type).

I would really prefer a compiler built in so that we get static type
checking (and I'm guessing that converting to interface{}
will incur some overhead too, even if the values don't escape).

> because this doesn't rely on other things in the reflect package, i think it
> should be placed in the runtime package.

That seems right if we go with the non-built-in approach.

cheers,
rog.

[Nico]

>> The main reason i don't use your 3rd proposal is that i haven't come up
>> with a use case where that level details is required.
>
> Yes, I'm not sure whether how useful it is to know where the
> overlap occurs as well as whether there is an overlap.
>
> Anyone have a use case for it?

not mine.
my case was similar to big/math but with multiple views of a submatrix

[minux]

On Thu, May 23, 2013 at 12:55 AM, roger peppe <rogp...@gmail.com> wrote:

On 22 May 2013 17:34, minux <minu...@gmail.com> wrote:
> how about we first try a library solution at this problem?
> something like this in the runtime package (or reflect), just your 2nd
> proposal changed to a package function.
>
> // Overlapping returns true iff object a and b is aliasing each other.
> // a and b should be slice or pointer to array, or it panics.
> func Overlapping(a, b interface{}) bool

Do you see a particular use case for allowing a pointer to an array
here? I'd prefer to allow slices only (trivially derivable from array pointers).

no. i included just for completeness. but now i see no real benefit as it's

very difficult to produce two different but aliasing pointer to array in pure Go.

however, i came up with another contrived use case:

type S struct {

   a [10]byte

   b [10]byte

   buffer []byte

}

where S.buffer could be backed by S.a, or S.b or another unrelated array.

people might expect Aliasing(&someS, someS.buffer) to work if the parameters

are of interface{} type (kinda a drawback for implementing as a library function

rather than a compiler builtin)

note: it's common to have one byte array and a byte slice in the same struct to

reduce garbage.

> i think future compiler optimization could make this as efficient as new

> compiler intrinsic (to perserve correct stack traces on panics, the compiler
> might not be able to inline it if it can panic, we can change so that it
> returns false if a or b is of the wrong type).

I would really prefer a compiler built in so that we get static type
checking (and I'm guessing that converting to interface{}

let's file an issue and see what others say.

will incur some overhead too, even if the values don't escape).

i was expecting the compiler could inline the Aliasing function body so that

the parameters won't need to be "boxed" into interface{}.

[Nigel Tao]

On Thu, May 23, 2013 at 2:34 AM, minux <minu...@gmail.com> wrote:
> // Overlapping returns true iff object a and b is aliasing each other.
> // a and b should be slice or pointer to array, or it panics.
> func Overlapping(a, b interface{}) bool

I don't know if we'd want to do this, but if we did, I don't think a
bool return is enough. For example, if we wanted to be able to
implement the built-in copy function, we'd also need to know whether
the overlapping slices required a forward copy or a backwards copy.

I have a vague memory of wanting something like this for the
2-dimensional equivalent of copy in image/draw, but I've long since
paged out the details.

[minux]

On Thu, May 23, 2013 at 9:10 AM, Nigel Tao <nige...@golang.org> wrote:

On Thu, May 23, 2013 at 2:34 AM, minux <minu...@gmail.com> wrote:
> // Overlapping returns true iff object a and b is aliasing each other.
> // a and b should be slice or pointer to array, or it panics.
> func Overlapping(a, b interface{}) bool

I don't know if we'd want to do this, but if we did, I don't think a
bool return is enough. For example, if we wanted to be able to
implement the built-in copy function, we'd also need to know whether
the overlapping slices required a forward copy or a backwards copy.

Yeah, that's a new use case. However, I can't think of a way to design the

aliasing/overlapping interface to accommodate both use cases.

I have a vague memory of wanting something like this for the
2-dimensional equivalent of copy in image/draw, but I've long since
paged out the details.

i thought about introducing a runtime.Copy for general copy tasks, but

as image/draw has to consider stride, designing a type-safe interface

seems difficult.

[minux]

On Thu, May 23, 2013 at 4:28 PM, minux <minu...@gmail.com> wrote:

On Thu, May 23, 2013 at 9:10 AM, Nigel Tao <nige...@golang.org> wrote:

On Thu, May 23, 2013 at 2:34 AM, minux <minu...@gmail.com> wrote:
> // Overlapping returns true iff object a and b is aliasing each other.
> // a and b should be slice or pointer to array, or it panics.
> func Overlapping(a, b interface{}) bool

I don't know if we'd want to do this, but if we did, I don't think a
bool return is enough. For example, if we wanted to be able to
implement the built-in copy function, we'd also need to know whether
the overlapping slices required a forward copy or a backwards copy.

Yeah, that's a new use case. However, I can't think of a way to design the

aliasing/overlapping interface to accommodate both use cases.

hit send button too soon.

the only interface i got so far:

type AliasingType int

// TODO: they should get better names and comments.

const (

    NonAliasing AliasingType = iota

    ForwardCopy

    BackwardCopy

)

// Overlapping returns 0 iff object a and don't alias each other,

// if a and b alias with each other, it will return the direction you

// need to copy b to a.

// a and b should be slice of the same element type, or it panics.
func Overlapping(a, b interface{}) AliasingType

[roger peppe]

On 23 May 2013 09:28, minux <minu...@gmail.com> wrote:
>
> On Thu, May 23, 2013 at 9:10 AM, Nigel Tao <nige...@golang.org> wrote:
>>
>> On Thu, May 23, 2013 at 2:34 AM, minux <minu...@gmail.com> wrote:
>> > // Overlapping returns true iff object a and b is aliasing each other.
>> > // a and b should be slice or pointer to array, or it panics.
>> > func Overlapping(a, b interface{}) bool
>>
>> I don't know if we'd want to do this, but if we did, I don't think a
>> bool return is enough. For example, if we wanted to be able to
>> implement the built-in copy function, we'd also need to know whether
>> the overlapping slices required a forward copy or a backwards copy.
>
> Yeah, that's a new use case. However, I can't think of a way to design the
> aliasing/overlapping interface to accommodate both use cases.

i think my second "alias" variant allows for that.

func copyDirection(dst, src []T) direction {
dsta, srca := alias(dst, src)
switch {
case dsta == nil:
return dirNone
case &dsta[0] == &dst[0]:
return dirForward
default:
return dirBackward
}
}

in this particular case, just a single slice return value
would be sufficient. i suggested two return values
because that's a way to find out *which* part of each slice
is aliased. i haven't seen a use case for it yet, but it
seems like it may be a reasonable primitive.

i could imagine image manipulation primitives using
a simple copy where things are not aliased, and a more
sophisticated merge operation where things are.
perhaps that's too fantastical though :-)

[odysse...@gmail.com]

I agree that having the ability to detect aliasing at the compiler level is a good idea. It would allow for the sort of optimizations that require the 'restrict' keyword in C. 

Sean