Rename [Var]ZeroVecULE to [Var]ZeroSlice, use Deref

[Manishearth]

Part of #1082

Brought up #1357 (comment)

Currently we have a lot of zerovec types and they all have their own methods:

• ZeroVec: ZeroVec, ZeroVecULE
• VarZeroVec: VarZeroVec, VarZeroVecULE, VarZeroVecOwned

ZeroVecULE and VarZeroVecULE, are, in the metaphor to Vec<T>, really just [T]. "ULE" is a complicated concept and the less users have to care about this the better; calling them [Var]ZeroSlice should be a good first step.

The natural next step from there is to move most method impls to ZeroSlice and use Deref. A slight hitch is that while this will work swimmingly for ZeroVec, it won't work as well for VarZeroVec since currently VarZeroVec's Borrowed variant preparses the index data to some extent. Given that every VZV operation goes through this it might lead to a perf loss, though we expect it to be small.

We should:

• Rename ZVULE and VZVULE to ZeroSlice and VarZeroSlice. Use in a couple more places (Add ZeroSlice and VarZeroSlice, move ZeroVec functionality to ZeroSlice and add Deref #1371)
• Add deref impls, move ZV methods over to ZeroSlice, continue having duplicated methods on VarZeroVec
• Benchmark whether the VarZeroVec methods

[Manishearth]

Just to give an idea of the work involved in constructing VZVB on-the-fly right now:

LLVM IR of `VarZeroVecBorrowed::::from_bytes_unchecked()`

; foo::create_vzv
; Function Attrs: mustprogress nofree noinline nosync nounwind nonlazybind uwtable willreturn
define internal fastcc void @_ZN3foo10create_vzv17h4c4082be55e1ad92E(%"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>"* noalias nocapture dereferenceable(48) %0, [0 x i8]* noalias nonnull readonly align 1 %bytes.0) unnamed_addr #2 {
"_ZN7zerovec10varzerovec8borrowed27VarZeroVecBorrowed$LT$T$GT$20from_bytes_unchecked17h417a8757e2b0e327E.exit":
  tail call void @llvm.experimental.noalias.scope.decl(metadata !29)
  tail call void @llvm.experimental.noalias.scope.decl(metadata !32)
  %_18.sroa.0.0..sroa_cast.i = bitcast [0 x i8]* %bytes.0 to i32*
  %_18.sroa.0.0.copyload.i = load i32, i32* %_18.sroa.0.0..sroa_cast.i, align 1, !alias.scope !32, !noalias !29
  %len.i = zext i32 %_18.sroa.0.0.copyload.i to i64
  %_25.i = shl nuw nsw i64 %len.i, 2
  %_24.i = add nuw nsw i64 %_25.i, 4
  %1 = getelementptr inbounds [0 x i8], [0 x i8]* %bytes.0, i64 0, i64 4
  %2 = getelementptr inbounds [0 x i8], [0 x i8]* %bytes.0, i64 0, i64 %_24.i
  %3 = bitcast %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>"* %0 to i8**
  store i8* %1, i8** %3, align 8, !alias.scope !29, !noalias !32
  %4 = getelementptr inbounds %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>", %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>"* %0, i64 0, i32 2, i32 0
  %5 = bitcast [0 x i8]** %4 to i8**
  store i8* %2, i8** %5, align 8, !alias.scope !29, !noalias !32
  %_7.i.i.i.i = sub nsw i64 2, %_25.i
  %6 = getelementptr inbounds %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>", %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>"* %0, i64 0, i32 1, i32 1
  store i64 %len.i, i64* %6, align 8, !alias.scope !29, !noalias !32
  %7 = getelementptr inbounds %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>", %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>"* %0, i64 0, i32 2, i32 1
  store i64 %_7.i.i.i.i, i64* %7, align 8, !alias.scope !29, !noalias !32
  %8 = getelementptr inbounds %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>", %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>"* %0, i64 0, i32 3, i32 0
  store [0 x i8]* %bytes.0, [0 x i8]** %8, align 8, !alias.scope !29, !noalias !32
  %9 = getelementptr inbounds %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>", %"zerovec::varzerovec::borrowed::VarZeroVecBorrowed<str>"* %0, i64 0, i32 3, i32 1
  store i64 6, i64* %9, align 8, !alias.scope !29, !noalias !32
  ret void
}

[sffc]

I think most of that IR is computing the pointers and saving them with the correct offsets into the struct. With an "on-the-fly" VarZeroSlice::get(), I think some of that IR goes away; i.e., I expect that VarZeroSlice::get() is substantially smaller than VarZeroVecBorrowed::new() + VarZeroVecBorrowed::get()

[Manishearth]

Yeah that's probably fair!

[Manishearth]

Opened #1371

A thing I'm realizing is that even with Deref on VZV we won't be able to get rid of all of the duplication because VZVB is still necessary, though we can make it private again which would be nice.

[Manishearth]

No appreciable difference in benches

vzv_precompute/get/precomputed                        
                        time:   [3.5150 ns 3.5298 ns 3.5461 ns]
Found 3 outliers among 100 measurements (3.00%)
  1 (1.00%) high mild
  2 (2.00%) high severe

vzv_precompute/get/slice                                                                             
                        time:   [3.4623 ns 3.4761 ns 3.4991 ns]
Found 5 outliers among 100 measurements (5.00%)
  2 (2.00%) high mild
  3 (3.00%) high severe

Benchmarking vzv_precompute/search/precomputed: Collecting 100 samples in estimated 5.0002 s (100M iter                                                                                                       vzv_precompute/search/precomputed                        
                        time:   [48.821 ns 49.587 ns 50.664 ns]
Found 10 outliers among 100 measurements (10.00%)
  5 (5.00%) high mild
  5 (5.00%) high severe

vzv_precompute/search/slice                                                                            
                        time:   [58.851 ns 59.301 ns 59.956 ns]
Found 12 outliers among 100 measurements (12.00%)
  8 (8.00%) high mild
  4 (4.00%) high severe

Benchmarking vzv_precompute/search_multi/precomputed: Collecting 100 samples in estimated 5.0019 s (8.3                                                                                                       vzv_precompute/search_multi/precomputed                        
                        time:   [593.80 ns 595.90 ns 598.22 ns]
Found 2 outliers among 100 measurements (2.00%)
  1 (1.00%) high mild
  1 (1.00%) high severe

Benchmarking vzv_precompute/search_multi/slice: Collecting 100 samples in estimated 5.0029 s (8.5M iter                                                                                                       vzv_precompute/search_multi/slice                        
                        time:   [571.34 ns 574.31 ns 577.99 ns]
Found 4 outliers among 100 measurements (4.00%)
  1 (1.00%) high mild
  3 (3.00%) high severe