intern_test.go

Documentation: k8s.io/kube-openapi/pkg/internal/third_party/go-json-experiment/json

     1  // Copyright 2022 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package json
     6  
     7  import (
     8  	"bytes"
     9  	"fmt"
    10  	"io"
    11  	"testing"
    12  )
    13  
    14  func TestIntern(t *testing.T) {
    15  	var sc stringCache
    16  	const alphabet = "abcdefghijklmnopqrstuvwxyz"
    17  	for i := 0; i <= len(alphabet); i++ {
    18  		want := alphabet[i:]
    19  		if got := sc.make([]byte(want)); got != want {
    20  			t.Fatalf("make = %v, want %v", got, want)
    21  		}
    22  	}
    23  	for i := 0; i < 1000; i++ {
    24  		want := fmt.Sprintf("test%b", i)
    25  		if got := sc.make([]byte(want)); got != want {
    26  			t.Fatalf("make = %v, want %v", got, want)
    27  		}
    28  	}
    29  }
    30  
    31  var sink string
    32  
    33  func BenchmarkIntern(b *testing.B) {
    34  	datasetStrings := func(name string) (out [][]byte) {
    35  		var data []byte
    36  		for _, ts := range jsonTestdata() {
    37  			if ts.name == name {
    38  				data = ts.data
    39  			}
    40  		}
    41  		dec := NewDecoder(bytes.NewReader(data))
    42  		for {
    43  			k, n := dec.StackIndex(dec.StackDepth())
    44  			isObjectName := k == '{' && n%2 == 0
    45  			tok, err := dec.ReadToken()
    46  			if err != nil {
    47  				if err == io.EOF {
    48  					break
    49  				}
    50  				b.Fatalf("ReadToken error: %v", err)
    51  			}
    52  			if tok.Kind() == '"' && !isObjectName {
    53  				out = append(out, []byte(tok.String()))
    54  			}
    55  		}
    56  		return out
    57  	}
    58  
    59  	tests := []struct {
    60  		label string
    61  		data  [][]byte
    62  	}{
    63  		// Best is the best case scenario where every string is the same.
    64  		{"Best", func() (out [][]byte) {
    65  			for i := 0; i < 1000; i++ {
    66  				out = append(out, []byte("hello, world!"))
    67  			}
    68  			return out
    69  		}()},
    70  
    71  		// Repeat is a sequence of the same set of names repeated.
    72  		// This commonly occurs when unmarshaling a JSON array of JSON objects,
    73  		// where the set of all names is usually small.
    74  		{"Repeat", func() (out [][]byte) {
    75  			for i := 0; i < 100; i++ {
    76  				for _, s := range []string{"first_name", "last_name", "age", "address", "street_address", "city", "state", "postal_code", "phone_numbers", "gender"} {
    77  					out = append(out, []byte(s))
    78  				}
    79  			}
    80  			return out
    81  		}()},
    82  
    83  		// Synthea is all string values encountered in the Synthea FHIR dataset.
    84  		{"Synthea", datasetStrings("SyntheaFhir")},
    85  
    86  		// Twitter is all string values encountered in the Twitter dataset.
    87  		{"Twitter", datasetStrings("TwitterStatus")},
    88  
    89  		// Worst is the worst case scenario where every string is different
    90  		// resulting in wasted time looking up a string that will never match.
    91  		{"Worst", func() (out [][]byte) {
    92  			for i := 0; i < 1000; i++ {
    93  				out = append(out, []byte(fmt.Sprintf("%016x", i)))
    94  			}
    95  			return out
    96  		}()},
    97  	}
    98  
    99  	for _, tt := range tests {
   100  		b.Run(tt.label, func(b *testing.B) {
   101  			// Alloc simply heap allocates each string.
   102  			// This provides an upper bound on the number of allocations.
   103  			b.Run("Alloc", func(b *testing.B) {
   104  				b.ReportAllocs()
   105  				for i := 0; i < b.N; i++ {
   106  					for _, b := range tt.data {
   107  						sink = string(b)
   108  					}
   109  				}
   110  			})
   111  			// Cache interns strings using stringCache.
   112  			// We want to optimize for having a faster runtime than Alloc,
   113  			// and also keeping the number of allocations closer to GoMap.
   114  			b.Run("Cache", func(b *testing.B) {
   115  				b.ReportAllocs()
   116  				for i := 0; i < b.N; i++ {
   117  					var sc stringCache
   118  					for _, b := range tt.data {
   119  						sink = sc.make(b)
   120  					}
   121  				}
   122  			})
   123  			// GoMap interns all strings in a simple Go map.
   124  			// This provides a lower bound on the number of allocations.
   125  			b.Run("GoMap", func(b *testing.B) {
   126  				b.ReportAllocs()
   127  				for i := 0; i < b.N; i++ {
   128  					m := make(map[string]string)
   129  					for _, b := range tt.data {
   130  						s, ok := m[string(b)]
   131  						if !ok {
   132  							s = string(b)
   133  							m[s] = s
   134  						}
   135  						sink = s
   136  					}
   137  				}
   138  			})
   139  		})
   140  	}
   141  }
   142
View as plain text