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.

Sign up for GitHub

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

s2: index speedup #554

Closed
SaveTheRbtz opened this issue Apr 7, 2022 · 2 comments · Fixed by #555
Closed

s2: index speedup #554

SaveTheRbtz opened this issue Apr 7, 2022 · 2 comments · Fixed by #555

Comments

@SaveTheRbtz
Copy link

Currently index Find operations are using linear search, which are simple but quite slow:

compress/s2/index.go

Lines 103 to 109 in 458f435

for _, info := range i.info {
if info.uncompressedOffset > offset {
break
}
compressedOff = info.compressedOffset
uncompressedOff = info.uncompressedOffset
}
.

What do you think about replacing them with either:
@klauspost
Copy link
Owner

@SaveTheRbtz Indexes are limited to 65535 entries, so a linear search will never really be that expensive.

Sorted search is faster at ~200 entries, so I will add that.

klauspost added a commit that referenced this issue Apr 7, 2022
@klauspost
s2: Use sorted search for index
862b5cf 
```
cpu: AMD Ryzen 9 3950X 16-Core Processor
BenchmarkIndexFind
BenchmarkIndexFind/blocks-1-32         	194769370	         6.180 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-2-32         	199258790	         6.057 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-4-32         	204297220	         5.879 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-8-32         	190476280	         6.321 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-16-32        	158611744	         7.537 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-32-32        	100000000	        10.04 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-64-32        	79986668	        14.90 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-128-32       	74996250	        14.95 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-256-32       	19506928	        60.93 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-512-32       	 8450894	       142.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-1024-32      	 3858536	       307.3 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-2048-32      	 2556153	       470.4 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-4096-32      	  840476	      1457 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-8192-32      	  571398	      2091 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-16384-32     	  195525	      6022 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-32768-32     	  138596	      8665 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-65535-32     	   86328	     13993 ns/op	       0 B/op	       0 allocs/op
```

after:

```
cpu: AMD Ryzen 9 3950X 16-Core Processor
BenchmarkIndexFind
BenchmarkIndexFind/blocks-1-32         	195354979	         6.054 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-2-32         	193981434	         6.140 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-4-32         	201894782	         6.023 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-8-32         	180996812	         6.978 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-16-32        	148147708	         8.016 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-32-32        	100000000	        10.43 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-64-32        	75000000	        15.95 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-128-32       	75000000	        15.59 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-256-32       	49979174	        22.83 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-512-32       	46302012	        25.00 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-1024-32      	44444937	        27.43 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-2048-32      	38709552	        29.62 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-4096-32      	37005741	        31.86 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-8192-32      	34297766	        34.43 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-16384-32     	30763077	        36.89 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-32768-32     	29656209	        39.45 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-65535-32     	27980180	        42.53 ns/op	       0 B/op	       0 allocs/op
```

Fixes #554
@klauspost klauspost mentioned this issue Apr 7, 2022
Merged
klauspost added a commit that referenced this issue Apr 7, 2022
@klauspost
s2: Use sorted search for index (#555)
c06ba5f 
```
cpu: AMD Ryzen 9 3950X 16-Core Processor
BenchmarkIndexFind
BenchmarkIndexFind/blocks-1-32         	194769370	         6.180 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-2-32         	199258790	         6.057 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-4-32         	204297220	         5.879 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-8-32         	190476280	         6.321 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-16-32        	158611744	         7.537 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-32-32        	100000000	        10.04 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-64-32        	79986668	        14.90 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-128-32       	74996250	        14.95 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-256-32       	19506928	        60.93 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-512-32       	 8450894	       142.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-1024-32      	 3858536	       307.3 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-2048-32      	 2556153	       470.4 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-4096-32      	  840476	      1457 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-8192-32      	  571398	      2091 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-16384-32     	  195525	      6022 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-32768-32     	  138596	      8665 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-65535-32     	   86328	     13993 ns/op	       0 B/op	       0 allocs/op
```

after:

```
cpu: AMD Ryzen 9 3950X 16-Core Processor
BenchmarkIndexFind
BenchmarkIndexFind/blocks-1-32         	195354979	         6.054 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-2-32         	193981434	         6.140 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-4-32         	201894782	         6.023 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-8-32         	180996812	         6.978 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-16-32        	148147708	         8.016 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-32-32        	100000000	        10.43 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-64-32        	75000000	        15.95 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-128-32       	75000000	        15.59 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-256-32       	49979174	        22.83 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-512-32       	46302012	        25.00 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-1024-32      	44444937	        27.43 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-2048-32      	38709552	        29.62 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-4096-32      	37005741	        31.86 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-8192-32      	34297766	        34.43 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-16384-32     	30763077	        36.89 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-32768-32     	29656209	        39.45 ns/op	       0 B/op	       0 allocs/op
BenchmarkIndexFind/blocks-65535-32     	27980180	        42.53 ns/op	       0 B/op	       0 allocs/op
```

Fixes #554
@SaveTheRbtz
Copy link
Author

SaveTheRbtz commented Apr 7, 2022 •
edited
Loading

Wow, that was fast!! And here I thought about starting to implement it, lol =))) Thank you!!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

s2: Use sorted search for index klauspost/compress
2 participants
@SaveTheRbtz @klauspost