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

Jump to bottom

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

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

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

dsnet opened this issue Apr 20, 2018 · 4 comments
Labels
NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. Performance
Milestone
Unplanned

Comments

@dsnet
Copy link
Member

dsnet 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)
@agnivade
Copy link
Contributor

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
Copy link
Member Author

dsnet commented Apr 21, 2018 •
edited

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
Copy link
Contributor

martisch commented Apr 21, 2018 •
edited

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
Copy link
Contributor

robpike 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.

@ALTree ALTree added the NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. label Jul 22, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
5 participants
@martisch @agnivade @ALTree @robpike @dsnet