Repository: ogen-go/ogen
Pull request #600 (2022-10-03 18:40:21)

perf(naming): use hashmap to search naming rules
Performance of `strings.ToLower` + hashmap is much better than linear search, binary search
and B-Tree because of slow string comparison.
```
name                 time/op
Rule/Rule-4          56.3ns ± 2%
Rule/LinearSearch-4   394ns ± 2%
```


Patch:
diff --git a/gen/ir/description.go b/gen/ir/description.go
index 936bbfaa..dc2226cf 100644
--- a/gen/ir/description.go
+++ b/gen/ir/description.go
@@ -5,7 +5,7 @@ import (
 	"unicode"
 	"unicode/utf8"
 
-	"github.com/ogen-go/ogen/internal/capitalize"
+	"github.com/ogen-go/ogen/internal/naming"
 )
 
 func splitLine(s string, limit int) (r []string) {
@@ -49,7 +49,7 @@ func prettyDoc(s, deprecation string) (r []string) {
 		r = append(r, splitLine(line, lineLimit)...)
 	}
 	if len(r) > 0 {
-		r[0] = capitalize.Capitalize(r[0])
+		r[0] = naming.Capitalize(r[0])
 
 		if last := r[len(r)-1]; len(last) > 0 && last[len(last)-1] != '.' {
 			r[len(r)-1] = last + "."
diff --git a/gen/ir/json.go b/gen/ir/json.go
index d8769432..cd5f83e7 100644
--- a/gen/ir/json.go
+++ b/gen/ir/json.go
@@ -4,7 +4,7 @@ import (
 	"sort"
 	"strings"
 
-	"github.com/ogen-go/ogen/internal/capitalize"
+	"github.com/ogen-go/ogen/internal/naming"
 	"github.com/ogen-go/ogen/jsonschema"
 )
 
@@ -124,7 +124,7 @@ func (j JSON) Format() string {
 	typePrefix := func(f string) string {
 		switch s.Type {
 		case jsonschema.String:
-			return "String" + capitalize.Capitalize(f)
+			return "String" + naming.Capitalize(f)
 		default:
 			return f
 		}
@@ -156,7 +156,7 @@ func (j JSON) Format() string {
 		if s.Type != jsonschema.String {
 			return ""
 		}
-		return "String" + capitalize.Capitalize(f)
+		return "String" + naming.Capitalize(f)
 	case "unix", "unix-seconds":
 		return typePrefix("UnixSeconds")
 	case "unix-nano":
@@ -290,7 +290,7 @@ func (j JSON) Fn() string {
 		s := j.t.Primitive.String()
 		return strings.ToUpper(s[:2]) + s[2:]
 	default:
-		return capitalize.Capitalize(j.t.Primitive.String())
+		return naming.Capitalize(j.t.Primitive.String())
 	}
 }
 
diff --git a/gen/ir/template_helpers.go b/gen/ir/template_helpers.go
index 8b229bda..58d16076 100644
--- a/gen/ir/template_helpers.go
+++ b/gen/ir/template_helpers.go
@@ -4,7 +4,7 @@ import (
 	"fmt"
 	"strings"
 
-	"github.com/ogen-go/ogen/internal/capitalize"
+	"github.com/ogen-go/ogen/internal/naming"
 	"github.com/ogen-go/ogen/jsonschema"
 )
 
@@ -27,7 +27,7 @@ func (t *Type) EncodeFn() string {
 		Uint, Uint8, Uint16, Uint32, Uint64,
 		Float32, Float64,
 		String, Bool:
-		return capitalize.Capitalize(t.Primitive.String())
+		return naming.Capitalize(t.Primitive.String())
 	case UUID, Time, IP, Duration, URL:
 		return afterDot(t.Primitive.String())
 	default:
@@ -39,7 +39,7 @@ func (t Type) uriFormat() string {
 	if s := t.Schema; s != nil {
 		switch f := s.Format; f {
 		case "time", "date":
-			return capitalize.Capitalize(f)
+			return naming.Capitalize(f)
 		case "date-time":
 			return "DateTime"
 		case "int8",
@@ -54,7 +54,7 @@ func (t Type) uriFormat() string {
 			if s.Type != jsonschema.String {
 				break
 			}
-			return "String" + capitalize.Capitalize(f)
+			return "String" + naming.Capitalize(f)
 		case "unix", "unix-seconds":
 			return "UnixSeconds"
 		case "unix-nano":
diff --git a/gen/ir/type.go b/gen/ir/type.go
index 3e5e478a..a4764351 100644
--- a/gen/ir/type.go
+++ b/gen/ir/type.go
@@ -5,7 +5,7 @@ import (
 	"regexp"
 	"strings"
 
-	"github.com/ogen-go/ogen/internal/capitalize"
+	"github.com/ogen-go/ogen/internal/naming"
 	"github.com/ogen-go/ogen/jsonschema"
 )
 
@@ -177,7 +177,7 @@ func (t *Type) NamePostfix() string {
 		typePrefix := func(f string) string {
 			switch s.Type {
 			case jsonschema.String:
-				return "String" + capitalize.Capitalize(f)
+				return "String" + naming.Capitalize(f)
 			default:
 				return f
 			}
@@ -205,7 +205,7 @@ func (t *Type) NamePostfix() string {
 			if s.Type != jsonschema.String {
 				return t.Primitive.String()
 			}
-			return "String" + capitalize.Capitalize(f)
+			return "String" + naming.Capitalize(f)
 		case "unix", "unix-seconds":
 			return typePrefix("UnixSeconds")
 		case "unix-nano":
diff --git a/gen/names.go b/gen/names.go
index bcc1ebe5..634a2730 100644
--- a/gen/names.go
+++ b/gen/names.go
@@ -8,6 +8,8 @@ import (
 	"unicode"
 
 	"github.com/go-faster/errors"
+
+	"github.com/ogen-go/ogen/internal/naming"
 )
 
 func cleanRef(ref string) string {
@@ -147,23 +149,9 @@ func (g *nameGen) isAllowed(r rune) bool {
 }
 
 func (g *nameGen) checkPart(part string) string {
-	rules := []string{
-		"ACL", "API", "ASCII", "AWS", "CPU", "CSS", "DNS", "EOF", "GB", "GUID",
-		"HTML", "HTTP", "HTTPS", "ID", "IP", "JSON", "KB", "LHS", "MAC", "MB",
-		"QPS", "RAM", "RHS", "RPC", "SLA", "SMTP", "SQL", "SSH", "SSO", "TCP",
-		"TLS", "TTL", "UDP", "UI", "UID", "URI", "URL", "UTF8", "UUID", "VM",
-		"XML", "XMPP", "XSRF", "XSS", "SMS", "CDN", "TCP", "UDP", "DC", "PFS",
-		"P2P", "SHA256", "SHA1", "MD5", "SRP", "2FA", "OAuth", "OAuth2",
-
-		"PNG", "JPG", "GIF", "MP4", "WEBP",
+	if rule, ok := naming.Rule(part); ok {
+		return rule
 	}
-
-	for _, rule := range rules {
-		if strings.EqualFold(part, rule) {
-			return rule
-		}
-	}
-
 	return part
 }
 
diff --git a/gen/schema_gen.go b/gen/schema_gen.go
index 39e369b1..22c18367 100644
--- a/gen/schema_gen.go
+++ b/gen/schema_gen.go
@@ -8,7 +8,7 @@ import (
 	"go.uber.org/zap"
 
 	"github.com/ogen-go/ogen/gen/ir"
-	"github.com/ogen-go/ogen/internal/capitalize"
+	"github.com/ogen-go/ogen/internal/naming"
 	"github.com/ogen-go/ogen/jsonschema"
 )
 
@@ -44,7 +44,7 @@ func newSchemaGen(filename string, lookupRef func(ref string) (*ir.Type, bool))
 }
 
 func variantFieldName(t *ir.Type) string {
-	return capitalize.Capitalize(t.NamePostfix())
+	return naming.Capitalize(t.NamePostfix())
 }
 
 func (g *schemaGen) generate(name string, schema *jsonschema.Schema, optional bool) (*ir.Type, error) {
diff --git a/gen/templates.go b/gen/templates.go
index b51fc8d1..7c9d70e9 100644
--- a/gen/templates.go
+++ b/gen/templates.go
@@ -11,7 +11,7 @@ import (
 	"github.com/go-faster/errors"
 
 	"github.com/ogen-go/ogen/gen/ir"
-	"github.com/ogen-go/ogen/internal/capitalize"
+	"github.com/ogen-go/ogen/internal/naming"
 )
 
 // RouterElem is variable helper for router generation.
@@ -69,7 +69,7 @@ func templateFunctions() template.FuncMap {
 		},
 		"pascalSpecial": pascalSpecial,
 		"camelSpecial":  camelSpecial,
-		"capitalize":    capitalize.Capitalize,
+		"capitalize":    naming.Capitalize,
 		"upper":         strings.ToUpper,
 
 		// Helpers for recursive encoding and decoding.
diff --git a/internal/capitalize/capitalize.go b/internal/naming/capitalize.go
similarity index 74%
rename from internal/capitalize/capitalize.go
rename to internal/naming/capitalize.go
index 70a3d52c..c4a3c8e4 100644
--- a/internal/capitalize/capitalize.go
+++ b/internal/naming/capitalize.go
@@ -1,5 +1,4 @@
-// Package capitalize contains capitalize function.
-package capitalize
+package naming
 
 import (
 	"unicode"
diff --git a/internal/naming/naming.go b/internal/naming/naming.go
new file mode 100644
index 00000000..cbe62aa6
--- /dev/null
+++ b/internal/naming/naming.go
@@ -0,0 +1,2 @@
+// Package naming contains some utilities for generating names.
+package naming
diff --git a/internal/naming/rules.go b/internal/naming/rules.go
new file mode 100644
index 00000000..32e7e9ae
--- /dev/null
+++ b/internal/naming/rules.go
@@ -0,0 +1,37 @@
+package naming
+
+import (
+	"strings"
+)
+
+var (
+	rules = [...]string{
+		"ACL", "API", "ASCII", "AWS", "CPU", "CSS", "DNS", "EOF", "GB", "GUID",
+		"HTML", "HTTP", "HTTPS", "ID", "IP", "JSON", "KB", "LHS", "MAC", "MB",
+		"QPS", "RAM", "RHS", "RPC", "SLA", "SMTP", "SQL", "SSH", "SSO", "TLS",
+		"TTL", "UI", "UID", "URI", "URL", "UTF8", "UUID", "VM", "XML", "XMPP",
+		"XSRF", "XSS", "SMS", "CDN", "TCP", "UDP", "DC", "PFS", "P2P",
+		"SHA256", "SHA1", "MD5", "SRP", "2FA", "OAuth", "OAuth2",
+
+		"PNG", "JPG", "GIF", "MP4", "WEBP",
+	}
+	// rulesMap is a map of lowered rules to their canonical form.
+	//
+	// NOTE: we're using a map instead of a linear/binary search because
+	// lowered string allocation is much cheaper than string comparison.
+	// Also, ToLower doesn't allocate if the string is already in lower case.
+	rulesMap = func() (r map[string]string) {
+		r = make(map[string]string)
+		for _, v := range rules {
+			r[strings.ToLower(v)] = v
+		}
+		return r
+	}()
+)
+
+// Rule returns the rule for the given part, if any.
+// Otherwise, it returns ("", false).
+func Rule(part string) (string, bool) {
+	v, ok := rulesMap[strings.ToLower(part)]
+	return v, ok
+}


Test patch:
diff --git a/gen/ir/description_test.go b/gen/ir/description_test.go
index 4edddd34..9cb52534 100644
--- a/gen/ir/description_test.go
+++ b/gen/ir/description_test.go
@@ -7,7 +7,7 @@ import (
 
 	"github.com/stretchr/testify/require"
 
-	"github.com/ogen-go/ogen/internal/capitalize"
+	"github.com/ogen-go/ogen/internal/naming"
 )
 
 func Test_prettyDoc(t *testing.T) {
@@ -65,7 +65,7 @@ func Test_prettyDoc(t *testing.T) {
 		{
 			input: strings.Repeat("a", lineLimit-4) + string(rune(12288)) + strings.Repeat("a", 10),
 			wantR: []string{
-				capitalize.Capitalize(strings.Repeat("a", lineLimit-4)),
+				naming.Capitalize(strings.Repeat("a", lineLimit-4)),
 				strings.Repeat("a", 10) + ".",
 			},
 		},
diff --git a/internal/naming/rules_test.go b/internal/naming/rules_test.go
new file mode 100644
index 00000000..c9e83fc2
--- /dev/null
+++ b/internal/naming/rules_test.go
@@ -0,0 +1,77 @@
+package naming
+
+import (
+	"strings"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+)
+
+func TestRule(t *testing.T) {
+	a := require.New(t)
+	for _, rule := range rules {
+		testFind := func(key string) {
+			v, ok := Rule(key)
+			a.True(ok)
+			a.Equal(rule, v)
+		}
+		testFind(rule)
+		testFind(strings.ToLower(rule))
+		testFind(strings.ToUpper(rule))
+		testFind(strings.ToLower(rule[:1]) + rule[1:])
+	}
+}
+
+func BenchmarkRule(b *testing.B) {
+	suite := [...]string{
+		"wifi",
+		"WiFi",
+		"ASCII",
+		"mp3",
+		"Oauth",
+		"WebP",
+		"JPEG",
+	}
+
+	b.Run("Rule", func(b *testing.B) {
+		b.ReportAllocs()
+		b.ResetTimer()
+
+		var (
+			v  string
+			ok bool
+		)
+		for i := 0; i < b.N; i++ {
+			rule := suite[i%len(suite)]
+			v, ok = Rule(rule)
+		}
+		if ok && v == "" {
+			b.Fatal("sink is empty")
+		}
+	})
+
+	linear := func(s string) (string, bool) {
+		for _, rule := range &rules {
+			if strings.EqualFold(s, rule) {
+				return rule, true
+			}
+		}
+		return "", false
+	}
+	b.Run("LinearSearch", func(b *testing.B) {
+		b.ReportAllocs()
+		b.ResetTimer()
+
+		var (
+			v  string
+			ok bool
+		)
+		for i := 0; i < b.N; i++ {
+			rule := suite[i%len(suite)]
+			v, ok = linear(rule)
+		}
+		if ok && v == "" {
+			b.Fatal("sink is empty")
+		}
+	})
+}