Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

bytes, strings: optimize Contains with fast-path for sub-slices #24979

Open
dsnet opened this issue Apr 20, 2018 · 4 comments

Comments

Projects
None yet
4 participants
@dsnet
Copy link
Member

commented Apr 20, 2018

Consider the following:

func Benchmark(b *testing.B) {
	buf := make([]byte, 1<<20)
	rand.Read(buf)
	for n := 64; n <= len(buf); n <<= 1 {
		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				bytes.Contains(buf, buf[n-64:n])
			}
		})
	}
}

On my machine, this prints:

Benchmark/64-8         	100000000	        11.8 ns/op
Benchmark/128-8        	100000000	        22.3 ns/op
Benchmark/256-8        	50000000	        29.1 ns/op
Benchmark/512-8        	30000000	        56.9 ns/op
Benchmark/1024-8       	20000000	       101 ns/op
Benchmark/2048-8       	10000000	       195 ns/op
Benchmark/4096-8       	 5000000	       393 ns/op
Benchmark/8192-8       	 2000000	       976 ns/op
Benchmark/16384-8      	 1000000	      1749 ns/op
Benchmark/32768-8      	  300000	      3968 ns/op
Benchmark/65536-8      	  200000	      8312 ns/op
Benchmark/131072-8     	  100000	     18300 ns/op
Benchmark/262144-8     	   50000	     35918 ns/op
Benchmark/524288-8     	   20000	     75942 ns/op
Benchmark/1048576-8    	   10000	    156854 ns/op

In this situation, the substring is sliced out of the parent slice. It should be know that the parent contains the substring in O(1) with something similar to:

func Contains(b, subslice []byte) bool {
	if (*reflect.SliceHeader).(unsafe.Pointer(&b)).Data <= (*reflect.SliceHeader).(unsafe.Pointer(&subslice)).Data && (*reflect.SliceHeader).(unsafe.Pointer(&b)).Data + uintptr(len(b)) >= (*reflect.SliceHeader).(unsafe.Pointer(&subslice)).Data + uintptr(len(subslice)) {
		return true
	}
	return Index(b, subslice) != -1
}

(the above code is not correct as there is special consideration to manipulating unsafe.Pointer, but the general approach is the same)

@dsnet dsnet added the Performance label Apr 20, 2018

@agnivade

This comment has been minimized.

Copy link
Member

commented Apr 21, 2018

Are we okay with using unsafe.Pointer for operations like these ? I thought those were reserved only for very special cases. Or were you just giving an example and the actual implementation might look different ?

Also, I wonder how many instances like these are out in the wild ? I would guess that the programmer would already know that the slice is a child of the parent slice ?

@dsnet

This comment has been minimized.

Copy link
Member Author

commented Apr 21, 2018

Are we okay with using unsafe.Pointer for operations like these ?

The bytes package delegates the heavy lifting to internal/bytealg which already uses a lot of assembly and unsafe, so there is precedence.

Also, I wonder how many instances like these are out in the wild ? I would guess that the programmer would already know that the slice is a child of the parent slice ?

I was looking at a piece of code where the a certain string sometimes was sub-sliced from the parent, and sometimes it wasn't. At the time that the check happened, it didn't know. It's possible to add more book-keeping to hold this information, but that seems silly.

@dsnet dsnet added this to the Unplanned milestone Apr 21, 2018

@martisch

This comment has been minimized.

Copy link
Member

commented Apr 21, 2018

If i recall correctly bytealg uses unsafe for linknames and to get the offset into structs that is then used in assembler code. There does not seem to be any unsafe imports in bytes.

I do not think we should start using unsafe for performance improvements in normal standard lib functions and i think code reviews have been rejecting the use of unsafe for performance in normal (not reflect, runtime or similar) go std lib code in the past.

I do not think this improvement should introduce the precedence to use unsafe to cast slice header internals outside of asm code and reflect/runtime packages.

I would also expect the additional computation and condition check to slow down the case where it is not a subslice slightly so it might not always be a performance improvement depending on the call site. However i have no idea/data how common either case is.

@robpike

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2018

I agree this case can be made more efficient, but at some overhead to all other cases. How often does the situation arise in practice? Asking if a is inside b when a was made from b seems unnecessary in the first place.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.