benchmarks_test.go

Documentation: cloud.google.com/go/internal/btree

     1  // Copyright 2014 Google LLC
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package btree
    16  
    17  import (
    18  	"fmt"
    19  	"sort"
    20  	"testing"
    21  )
    22  
    23  const benchmarkTreeSize = 10000
    24  
    25  var degrees = []int{2, 8, 32, 64}
    26  
    27  func BenchmarkInsert(b *testing.B) {
    28  	insertP := perm(benchmarkTreeSize)
    29  	for _, d := range degrees {
    30  		b.Run(fmt.Sprintf("degree=%d", d), func(b *testing.B) {
    31  			i := 0
    32  			for i < b.N {
    33  				tr := New(d, less)
    34  				for _, m := range insertP {
    35  					tr.Set(m.Key, m.Value)
    36  					i++
    37  					if i >= b.N {
    38  						return
    39  					}
    40  				}
    41  			}
    42  		})
    43  	}
    44  }
    45  
    46  func BenchmarkDeleteInsert(b *testing.B) {
    47  	insertP := perm(benchmarkTreeSize)
    48  	for _, d := range degrees {
    49  		b.Run(fmt.Sprintf("degree=%d", d), func(b *testing.B) {
    50  			tr := New(d, less)
    51  			for _, m := range insertP {
    52  				tr.Set(m.Key, m.Value)
    53  			}
    54  			b.ResetTimer()
    55  			for i := 0; i < b.N; i++ {
    56  				m := insertP[i%benchmarkTreeSize]
    57  				tr.Delete(m.Key)
    58  				tr.Set(m.Key, m.Value)
    59  			}
    60  		})
    61  	}
    62  }
    63  
    64  func BenchmarkDeleteInsertCloneOnce(b *testing.B) {
    65  	insertP := perm(benchmarkTreeSize)
    66  	for _, d := range degrees {
    67  		b.Run(fmt.Sprintf("degree=%d", d), func(b *testing.B) {
    68  			tr := New(d, less)
    69  			for _, m := range insertP {
    70  				tr.Set(m.Key, m.Value)
    71  			}
    72  			tr = tr.Clone()
    73  			b.ResetTimer()
    74  			for i := 0; i < b.N; i++ {
    75  				m := insertP[i%benchmarkTreeSize]
    76  				tr.Delete(m.Key)
    77  				tr.Set(m.Key, m.Value)
    78  			}
    79  		})
    80  	}
    81  }
    82  
    83  func BenchmarkDeleteInsertCloneEachTime(b *testing.B) {
    84  	insertP := perm(benchmarkTreeSize)
    85  	for _, d := range degrees {
    86  		b.Run(fmt.Sprintf("degree=%d", d), func(b *testing.B) {
    87  			tr := New(d, less)
    88  			for _, m := range insertP {
    89  				tr.Set(m.Key, m.Value)
    90  			}
    91  			b.ResetTimer()
    92  			for i := 0; i < b.N; i++ {
    93  				tr = tr.Clone()
    94  				m := insertP[i%benchmarkTreeSize]
    95  				tr.Delete(m.Key)
    96  				tr.Set(m.Key, m.Value)
    97  			}
    98  		})
    99  	}
   100  }
   101  
   102  func BenchmarkDelete(b *testing.B) {
   103  	insertP := perm(benchmarkTreeSize)
   104  	removeP := perm(benchmarkTreeSize)
   105  	for _, d := range degrees {
   106  		b.Run(fmt.Sprintf("degree=%d", d), func(b *testing.B) {
   107  			i := 0
   108  			for i < b.N {
   109  				b.StopTimer()
   110  				tr := New(d, less)
   111  				for _, v := range insertP {
   112  					tr.Set(v.Key, v.Value)
   113  				}
   114  				b.StartTimer()
   115  				for _, m := range removeP {
   116  					tr.Delete(m.Key)
   117  					i++
   118  					if i >= b.N {
   119  						return
   120  					}
   121  				}
   122  				if tr.Len() > 0 {
   123  					panic(tr.Len())
   124  				}
   125  			}
   126  		})
   127  	}
   128  }
   129  
   130  func BenchmarkGet(b *testing.B) {
   131  	insertP := perm(benchmarkTreeSize)
   132  	getP := perm(benchmarkTreeSize)
   133  	for _, d := range degrees {
   134  		b.Run(fmt.Sprintf("degree=%d", d), func(b *testing.B) {
   135  			i := 0
   136  			for i < b.N {
   137  				b.StopTimer()
   138  				tr := New(d, less)
   139  				for _, v := range insertP {
   140  					tr.Set(v.Key, v.Value)
   141  				}
   142  				b.StartTimer()
   143  				for _, m := range getP {
   144  					tr.Get(m.Key)
   145  					i++
   146  					if i >= b.N {
   147  						return
   148  					}
   149  				}
   150  			}
   151  		})
   152  	}
   153  }
   154  
   155  func BenchmarkGetWithIndex(b *testing.B) {
   156  	insertP := perm(benchmarkTreeSize)
   157  	getP := perm(benchmarkTreeSize)
   158  	for _, d := range degrees {
   159  		b.Run(fmt.Sprintf("degree=%d", d), func(b *testing.B) {
   160  			i := 0
   161  			for i < b.N {
   162  				b.StopTimer()
   163  				tr := New(d, less)
   164  				for _, v := range insertP {
   165  					tr.Set(v.Key, v.Value)
   166  				}
   167  				b.StartTimer()
   168  				for _, m := range getP {
   169  					tr.GetWithIndex(m.Key)
   170  					i++
   171  					if i >= b.N {
   172  						return
   173  					}
   174  				}
   175  			}
   176  		})
   177  	}
   178  }
   179  
   180  func BenchmarkGetCloneEachTime(b *testing.B) {
   181  	insertP := perm(benchmarkTreeSize)
   182  	getP := perm(benchmarkTreeSize)
   183  	for _, d := range degrees {
   184  		b.Run(fmt.Sprintf("degree=%d", d), func(b *testing.B) {
   185  			i := 0
   186  			for i < b.N {
   187  				b.StopTimer()
   188  				tr := New(d, less)
   189  				for _, m := range insertP {
   190  					tr.Set(m.Key, m.Value)
   191  				}
   192  				b.StartTimer()
   193  				for _, m := range getP {
   194  					tr = tr.Clone()
   195  					tr.Get(m.Key)
   196  					i++
   197  					if i >= b.N {
   198  						return
   199  					}
   200  				}
   201  			}
   202  		})
   203  	}
   204  }
   205  
   206  func BenchmarkFind(b *testing.B) {
   207  	for _, d := range degrees {
   208  		var items []item
   209  		for i := 0; i < 2*d; i++ {
   210  			items = append(items, item{i, i})
   211  		}
   212  		b.Run(fmt.Sprintf("size=%d", len(items)), func(b *testing.B) {
   213  			for _, alg := range []struct {
   214  				name string
   215  				fun  func(Key, []item) (int, bool)
   216  			}{
   217  				{"binary", findBinary},
   218  				{"linear", findLinear},
   219  			} {
   220  				b.Run(alg.name, func(b *testing.B) {
   221  					for i := 0; i < b.N; i++ {
   222  						for j := 0; j < len(items); j++ {
   223  							alg.fun(items[j].key, items)
   224  						}
   225  					}
   226  				})
   227  			}
   228  		})
   229  	}
   230  }
   231  
   232  func findBinary(k Key, s []item) (int, bool) {
   233  	i := sort.Search(len(s), func(i int) bool { return less(k, s[i].key) })
   234  	// i is the smallest index of s for which key.Less(s[i].Key), or len(s).
   235  	if i > 0 && !less(s[i-1].key, k) {
   236  		return i - 1, true
   237  	}
   238  	return i, false
   239  }
   240  
   241  func findLinear(k Key, s []item) (int, bool) {
   242  	var i int
   243  	for i = 0; i < len(s); i++ {
   244  		if less(k, s[i].key) {
   245  			break
   246  		}
   247  	}
   248  	if i > 0 && !less(s[i-1].key, k) {
   249  		return i - 1, true
   250  	}
   251  	return i, false
   252  }
   253
View as plain text