[インデックス 15990] ファイルの概要

このコミットは、Go言語の標準ライブラリである net/url パッケージ内の url.go ファイルに対する変更です。具体的には、文字列の分割処理を行う split 関数において、手動で実装されていたループベースの検索処理を strings.Index 関数に置き換えることで、コードの簡潔化とパフォーマンスの向上を図っています。

コミット

commit 731dcb7680303792315625a86ec0390ca41c03b9
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Thu Mar 28 13:43:34 2013 -0700

    net/url: use strings.Index instead of a loop
    
    We already depend on strings in this file, so use it.
    
    Plus strings.Index will be faster than a manual loop
    once issue 3751 is finished.
    
    R=golang-dev, khr
    CC=golang-dev
    https://golang.org/cl/8116043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/731dcb7680303792315625a86ec0390ca41c03b9

元コミット内容

net/url: use strings.Index instead of a loop

変更の背景

この変更の背景には、主に以下の2点があります。

既存の依存関係の活用: url.go ファイルは既に strings パッケージに依存しており、その機能を利用できる状態でした。手動で文字列検索ループを実装する代わりに、既存の標準ライブラリ関数を活用することで、コードの重複を避け、保守性を向上させることができます。
パフォーマンスの最適化: コミットメッセージに「Plus strings.Index will be faster than a manual loop once issue 3751 is finished.」とあるように、strings.Index 関数の内部実装が改善される予定（または既に改善された）であり、それによって手動ループよりも高速になることが期待されていました。Issue 3751は、Go言語の標準ライブラリにおける文字列操作関数のパフォーマンス改善に関するもので、特にstrings.Indexのような基本的な操作の効率化が図られていました。これにより、URLのパース処理全体の速度向上に寄与します。

前提知識の解説

Go言語の `strings` パッケージ

Go言語の strings パッケージは、UTF-8でエンコードされた文字列を操作するための関数を提供します。このパッケージには、文字列の検索、置換、分割、結合など、様々なユーティリティ関数が含まれています。

strings.Index(s, substr string) int: この関数は、文字列 s 内で substr が最初に現れるインデックスを返します。substr が見つからない場合は -1 を返します。この関数は、内部的に高度に最適化されたアルゴリズム（例えば、Rabin-KarpアルゴリズムやBoyer-Mooreアルゴリズムの変種など）を使用しており、多くの場合、手動で実装された単純なループよりも高速です。

URLの構造とパース

URL (Uniform Resource Locator) は、インターネット上のリソースを一意に識別するための文字列です。一般的なURLの構造は以下のようになります。

scheme://[userinfo@]host[:port]/path[?query][#fragment]

Scheme (スキーム): リソースにアクセスするためのプロトコル（例: http, https, ftp）。
Userinfo (ユーザー情報): ユーザー名とパスワード（オプション）。
Host (ホスト): サーバーのドメイン名またはIPアドレス。
Port (ポート): サーバーのポート番号（オプション）。
Path (パス): サーバー上のリソースのパス。
Query (クエリ): サーバーに渡す追加のパラメータ（キーと値のペア）。
Fragment (フラグメント): ドキュメント内の特定の部分へのアンカー。

net/url パッケージは、このようなURL文字列を解析（パース）し、各コンポーネントに分解して url.URL 構造体に格納する機能を提供します。このパース処理の中で、特定の区切り文字（例: #, ?, /, :）を見つけて文字列を分割する操作が頻繁に行われます。

コミットメッセージで言及されている「issue 3751」は、Go言語の標準ライブラリにおける文字列操作のパフォーマンス改善に関するものです。このIssueは、特にstrings.Indexのような基本的な文字列検索操作の効率を向上させることを目的としていました。当時のGo言語のstrings.Indexの実装は、特定の条件下で最適化の余地があり、より高速なアルゴリズム（例えば、Boyer-Mooreアルゴリズムなど）を導入することで、大幅なパフォーマンス向上が期待されていました。このコミットは、その改善が完了した、または完了間近であることを前提として、strings.Indexへの移行を決定したと考えられます。

技術的詳細

このコミットの主要な技術的変更点は、net/url パッケージ内の split 関数の実装です。

`split` 関数の役割

split 関数は、与えられた文字列 s を、指定された区切り文字 c で分割し、2つの部分文字列を返すユーティリティ関数です。cutc パラメータが true の場合、区切り文字 c は結果の文字列に含まれません。

変更前は、この関数は byte 型の区切り文字 c を受け取り、文字列 s をループで1文字ずつ走査して c を探していました。

`strings.Index` への移行

変更後、split 関数は string 型の区切り文字 c を受け取るように変更され、内部の検索ロジックが strings.Index(s, c) に置き換えられました。

引数の型変更: func split(s string, c byte, cutc bool) から func split(s string, c string, cutc bool) へと変更されました。これにより、split 関数は単一のバイトだけでなく、任意の文字列を区切り文字として扱えるようになりました。ただし、このコミットで変更された split 関数の呼び出し箇所では、依然として単一の文字（"#", "?", "/", ":"）が区切り文字として渡されています。これは、将来的な拡張性を見越した変更であるか、または strings.Index の引数型に合わせた必然的な変更であると考えられます。
検索ロジックの変更:
- 変更前:
```
for i := 0; i < len(s); i++ {
    if s[i] == c {
        // ...
    }
}
```
  このループは、文字列 s を先頭から順に走査し、各文字が区切り文字 c と一致するかどうかを比較していました。
- 変更後:
```
i := strings.Index(s, c)
```
  strings.Index 関数は、Go言語のランタイムによって高度に最適化されたC/アセンブリコードで実装されていることが多く、特に長い文字列や頻繁に呼び出されるケースで、手動ループよりもはるかに高速に動作します。
部分文字列の抽出ロジックの調整:
- cutc が true の場合、区切り文字を除外して部分文字列を返す必要があります。
- 変更前: return s[0:i], s[i+1:] c が byte であったため、i+1 で区切り文字の次の位置から文字列を抽出していました。
- 変更後: return s[0:i], s[i+len(c):] c が string になったため、len(c) を使用して区切り文字の長さ分だけオフセットを調整し、正確に区切り文字の次の位置から文字列を抽出するように変更されました。これにより、c が複数文字の文字列であっても正しく動作するようになります。

影響範囲

この変更は、net/url パッケージ内部の split 関数の実装に限定されており、外部から net/url パッケージを利用するコードのAPIには影響を与えません。しかし、net/url パッケージがURLのパース処理において頻繁に split 関数を使用するため、この変更はURLパースの全体的なパフォーマンス向上に寄与します。

コアとなるコードの変更箇所

src/pkg/net/url/url.go ファイルの split 関数と、その呼び出し箇所が変更されています。

--- a/src/pkg/net/url/url.go
+++ b/src/pkg/net/url/url.go
@@ -317,23 +317,22 @@ func getscheme(rawurl string) (scheme, path string, err error) {
 // Maybe s is of the form t c u.
 // If so, return t, c u (or t, u if cutc == true).
 // If not, return s, "".
-func split(s string, c byte, cutc bool) (string, string) {
-	for i := 0; i < len(s); i++ {
-		if s[i] == c {
-			if cutc {
-				return s[0:i], s[i+1:]
-			}
-			return s[0:i], s[i:]
-		}
-	}
-	return s, ""
+func split(s string, c string, cutc bool) (string, string) {
+	i := strings.Index(s, c)
+	if i < 0 {
+		return s, ""
+	}
+	if cutc {
+		return s[0:i], s[i+len(c):]
+	}
+	return s[0:i], s[i:]
 }
 
 // Parse parses rawurl into a URL structure.
 // The rawurl may be relative or absolute.
 func Parse(rawurl string) (url *URL, err error) {
 	// Cut off #frag
-	u, frag := split(rawurl, '#', true)
+	u, frag := split(rawurl, "#", true)
 	if url, err = parse(u, false); err != nil {
 		return nil, err
 	}
@@ -380,7 +379,7 @@ func parse(rawurl string, viaRequest bool) (url *URL, err error) {
 	}
 	url.Scheme = strings.ToLower(url.Scheme)
 
-	rest, url.RawQuery = split(rest, '?', true)
+	rest, url.RawQuery = split(rest, "?", true)
 
 	if !strings.HasPrefix(rest, "/") {
 		if url.Scheme != "" {
@@ -396,7 +395,7 @@ func parse(rawurl string, viaRequest bool) (url *URL, err error) {
 
 	if (url.Scheme != "" || !viaRequest && !strings.HasPrefix(rest, "///")) && strings.HasPrefix(rest, "//") {
 		var authority string
-		authority, rest = split(rest[2:], '/', false)
+		authority, rest = split(rest[2:], "/", false)
 		url.User, url.Host, err = parseAuthority(authority)
 		if err != nil {
 			goto Error
@@ -428,7 +427,7 @@ func parseAuthority(authority string) (user *Userinfo, host string, err error) {
 		}
 		user = User(userinfo)
 	} else {
-		username, password := split(userinfo, ':', true)
+		username, password := split(userinfo, ":", true)
 		if username, err = unescape(username, encodeUserPassword); err != nil {
 			return
 		}

コアとなるコードの解説

`split` 関数の変更

シグネチャの変更:
- 変更前: func split(s string, c byte, cutc bool) (string, string)
- 変更後: func split(s string, c string, cutc bool) (string, string) c の型が byte から string に変更されました。これにより、strings.Index 関数が期待する引数型に合致するようになりました。
内部ロジックの変更:
- 変更前は、for ループを使って文字列 s を1文字ずつ走査し、s[i] == c で区切り文字を探していました。
- 変更後は、i := strings.Index(s, c) を使用して、s 内で c が最初に現れるインデックスを効率的に取得しています。strings.Index は、Go言語の標準ライブラリによって最適化された実装であり、多くの場合、手動ループよりも高速です。
部分文字列抽出の調整:
- if cutc ブロック内で、区切り文字 c を除外して残りの文字列を返す際のオフセットが変更されました。
- 変更前: return s[0:i], s[i+1:] (c が1バイト文字であることを前提)
- 変更後: return s[0:i], s[i+len(c):] (c が複数バイトの文字列である可能性を考慮し、len(c) を使用して正確なオフセットを計算)

`split` 関数の呼び出し箇所の変更

net/url/url.go 内の split 関数のすべての呼び出し箇所で、第2引数のリテラルが byte リテラル（例: '#'）から string リテラル（例: "#"）に変更されています。

split(rawurl, '#', true) -> split(rawurl, "#", true)
split(rest, '?', true) -> split(rest, "?", true)
split(rest[2:], '/', false) -> split(rest[2:], "/", false)
split(userinfo, ':', true) -> split(userinfo, ":", true)

これらの変更は、split 関数のシグネチャ変更に合わせて行われたもので、機能的な意味合いは変わりません。

参考にした情報源リンク

コミットメッセージ内のGo言語コードレビューリンク: https://golang.org/cl/8116043
Go言語のIssue 3751に関する情報 (Web検索結果に基づく):
- https://github.com/golang/go/issues/3751 (これは直接的なIssueではない可能性もありますが、当時のGoの文字列最適化に関する議論の文脈で参照されることがあります。)
- 一般的なGo言語の文字列操作のパフォーマンスに関する記事やドキュメント。
- strings.Index の内部実装に関するGo言語のソースコード。
- URLの構造に関する一般的なWeb技術ドキュメント。
- Go言語の公式ドキュメント。
- Go言語の標準ライブラリのソースコード (src/strings/strings.go および src/pkg/net/url/url.go)。
- Go言語のコミット履歴と関連する議論。
- Boyer-Mooreアルゴリズムなどの文字列検索アルゴリズムに関する情報。# [インデックス 15990] ファイルの概要

コミット

commit 731dcb7680303792315625a86ec0390ca41c03b9
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Thu Mar 28 13:43:34 2013 -0700

    net/url: use strings.Index instead of a loop
    
    We already depend on strings in this file, so use it.
    
    Plus strings.Index will be faster than a manual loop
    once issue 3751 is finished.
    
    R=golang-dev, khr
    CC=golang-dev
    https://golang.org/cl/8116043

既存の依存関係の活用: url.go ファイルは既に strings パッケージに依存しており、その機能を利用できる状態でした。手動で文字列検索ループを実装する代わりに、既存の標準ライブラリ関数を活用することで、コードの重複を避け、保守性を向上させることができます。
パフォーマンスの最適化: コミットメッセージに「Plus strings.Index will be faster than a manual loop once issue 3751 is finished.」とあるように、strings.Index 関数の内部実装が改善される予定（または既に改善された）であり、それによって手動ループよりも高速になることが期待されていました。Issue 3751は、Go言語の標準ライブラリにおける文字列操作関数のパフォーマンス改善に関するもので、特にstrings.Indexのような基本的な操作の効率化が図られていました。これにより、URLのパース処理全体の速度向上に寄与します。

前提知識の解説

Go言語の `strings` パッケージ

strings.Index(s, substr string) int: この関数は、文字列 s 内で substr が最初に現れるインデックスを返します。substr が見つからない場合は -1 を返します。この関数は、内部的に高度に最適化されたアルゴリズム（例えば、Rabin-KarpアルゴリズムやBoyer-Mooreアルゴリズムの変種など）を使用しており、多くの場合、手動で実装された単純なループよりも高速です。

URLの構造とパース

URL (Uniform Resource Locator) は、インターネット上のリソースを一意に識別するための文字列です。一般的なURLの構造は以下のようになります。

scheme://[userinfo@]host[:port]/path[?query][#fragment]

Scheme (スキーム): リソースにアクセスするためのプロトコル（例: http, https, ftp）。
Userinfo (ユーザー情報): ユーザー名とパスワード（オプション）。
Host (ホスト): サーバーのドメイン名またはIPアドレス。
Port (ポート): サーバーのポート番号（オプション）。
Path (パス): サーバー上のリソースのパス。
Query (クエリ): サーバーに渡す追加のパラメータ（キーと値のペア）。
Fragment (フラグメント): ドキュメント内の特定の部分へのアンカー。

引数の型変更: func split(s string, c byte, cutc bool) から func split(s string, c string, cutc bool) へと変更されました。これにより、split 関数は単一のバイトだけでなく、任意の文字列を区切り文字として扱えるようになりました。ただし、このコミットで変更された split 関数の呼び出し箇所では、依然として単一の文字（"#", "?", "/", ":"）が区切り文字として渡されています。これは、将来的な拡張性を見越した変更であるか、または strings.Index の引数型に合わせた必然的な変更であると考えられます。
検索ロジックの変更:
- 変更前:
```
for i := 0; i < len(s); i++ {
    if s[i] == c {
        // ...
    }
}
```
  このループは、文字列 s を先頭から順に走査し、各文字が区切り文字 c と一致するかどうかを比較していました。
- 変更後:
```
i := strings.Index(s, c)
```
  strings.Index 関数は、Go言語のランタイムによって高度に最適化されたC/アセンブリコードで実装されていることが多く、特に長い文字列や頻繁に呼び出されるケースで、手動ループよりもはるかに高速に動作します。
部分文字列の抽出ロジックの調整:
- cutc が true の場合、区切り文字を除外して部分文字列を返す必要があります。
- 変更前: return s[0:i], s[i+1:] (c が1バイト文字であることを前提)
- 変更後: return s[0:i], s[i+len(c):] (c が複数バイトの文字列である可能性を考慮し、len(c) を使用して正確なオフセットを計算)

影響範囲

コアとなるコードの変更箇所

src/pkg/net/url/url.go ファイルの split 関数と、その呼び出し箇所が変更されています。

--- a/src/pkg/net/url/url.go
+++ b/src/pkg/net/url/url.go
@@ -317,23 +317,22 @@ func getscheme(rawurl string) (scheme, path string, err error) {
 // Maybe s is of the form t c u.
 // If so, return t, c u (or t, u if cutc == true).
 // If not, return s, "".
-func split(s string, c byte, cutc bool) (string, string) {
-	for i := 0; i < len(s); i++ {
-		if s[i] == c {
-			if cutc {
-				return s[0:i], s[i+1:]
-			}
-			return s[0:i], s[i:]
-		}
-	}
-	return s, ""
+func split(s string, c string, cutc bool) (string, string) {
+	i := strings.Index(s, c)
+	if i < 0 {
+		return s, ""
+	}
+	if cutc {
+		return s[0:i], s[i+len(c):]
+	}
+	return s[0:i], s[i:]
 }
 
 // Parse parses rawurl into a URL structure.
 // The rawurl may be relative or absolute.
 func Parse(rawurl string) (url *URL, err error) {
 	// Cut off #frag
-	u, frag := split(rawurl, '#', true)
+	u, frag := split(rawurl, "#", true)
 	if url, err = parse(u, false); err != nil {
 		return nil, err
 	}
@@ -380,7 +379,7 @@ func parse(rawurl string, viaRequest bool) (url *URL, err error) {
 	}
 	url.Scheme = strings.ToLower(url.Scheme)
 
-	rest, url.RawQuery = split(rest, '?', true)
+	rest, url.RawQuery = split(rest, "?", true)
 
 	if !strings.HasPrefix(rest, "/") {
 		if url.Scheme != "" {
@@ -396,7 +395,7 @@ func parse(rawurl string, viaRequest bool) (url *URL, err error) {
 
 	if (url.Scheme != "" || !viaRequest && !strings.HasPrefix(rest, "///")) && strings.HasPrefix(rest, "//") {
 		var authority string
-		authority, rest = split(rest[2:], '/', false)
+		authority, rest = split(rest[2:], "/", false)
 		url.User, url.Host, err = parseAuthority(authority)
 		if err != nil {
 			goto Error
@@ -428,7 +427,7 @@ func parseAuthority(authority string) (user *Userinfo, host string, err error) {
 		}
 		user = User(userinfo)
 	} else {
-		username, password := split(userinfo, ':', true)
+		username, password := split(userinfo, ":", true)
 		if username, err = unescape(username, encodeUserPassword); err != nil {
 			return
 		}

コアとなるコードの解説

`split` 関数の変更

シグネチャの変更:
- 変更前: func split(s string, c byte, cutc bool) (string, string)
- 変更後: func split(s string, c string, cutc bool) (string, string) c の型が byte から string に変更されました。これにより、strings.Index 関数が期待する引数型に合致するようになりました。
内部ロジックの変更:
- 変更前は、for ループを使って文字列 s を1文字ずつ走査し、s[i] == c で区切り文字を探していました。
- 変更後は、i := strings.Index(s, c) を使用して、s 内で c が最初に現れるインデックスを効率的に取得しています。strings.Index は、Go言語の標準ライブラリによって最適化された実装であり、多くの場合、手動ループよりも高速です。
部分文字列抽出の調整:
- if cutc ブロック内で、区切り文字 c を除外して残りの文字列を返す際のオフセットが変更されました。
- 変更前: return s[0:i], s[i+1:] (c が1バイト文字であることを前提)
- 変更後: return s[0:i], s[i+len(c):] (c が複数バイトの文字列である可能性を考慮し、len(c) を使用して正確なオフセットを計算)

`split` 関数の呼び出し箇所の変更

split(rawurl, '#', true) -> split(rawurl, "#", true)
split(rest, '?', true) -> split(rest, "?", true)
split(rest[2:], '/', false) -> split(rest[2:], "/", false)
split(userinfo, ':', true) -> split(userinfo, ":", true)

これらの変更は、split 関数のシグネチャ変更に合わせて行われたもので、機能的な意味合いは変わりません。

参考にした情報源リンク

コミットメッセージ内のGo言語コードレビューリンク: https://golang.org/cl/8116043
Go言語のIssue 3751に関する情報 (Web検索結果に基づく):
- https://github.com/golang/go/issues/3751 (これは直接的なIssueではない可能性もありますが、当時のGoの文字列最適化に関する議論の文脈で参照されることがあります。)
- 一般的なGo言語の文字列操作のパフォーマンスに関する記事やドキュメント。
- strings.Index の内部実装に関するGo言語のソースコード。
- URLの構造に関する一般的なWeb技術ドキュメント。
- Go言語の公式ドキュメント。
- Go言語の標準ライブラリのソースコード (src/strings/strings.go および src/pkg/net/url/url.go)。
- Go言語のコミット履歴と関連する議論。
- Boyer-Mooreアルゴリズムなどの文字列検索アルゴリズムに関する情報。

comemo

[インデックス 15990] ファイルの概要

コミット

GitHub上でのコミットページへのリンク

元コミット内容

変更の背景

前提知識の解説

Go言語の `strings` パッケージ

URLの構造とパース

Issue 3751 (Go言語のパフォーマンス改善)

技術的詳細

`split` 関数の役割

`strings.Index` への移行

影響範囲

コアとなるコードの変更箇所

コアとなるコードの解説

`split` 関数の変更

`split` 関数の呼び出し箇所の変更

関連リンク

参考にした情報源リンク

コミット

GitHub上でのコミットページへのリンク

元コミット内容

変更の背景

前提知識の解説

Go言語の `strings` パッケージ

URLの構造とパース

Issue 3751 (Go言語のパフォーマンス改善)

技術的詳細

`split` 関数の役割

`strings.Index` への移行

影響範囲

コアとなるコードの変更箇所

コアとなるコードの解説

`split` 関数の変更

`split` 関数の呼び出し箇所の変更

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo