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

コミット

コミットハッシュ: 858f0b4d9568bb3a2ef9b9ee6ad078eb3b7c5aaa 作者: Ivan Krasin krasin@golang.org コミット日時: Mon Jan 23 10:31:51 2012 -0500

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

https://github.com/golang/go/commit/858f0b4d9568bb3a2ef9b9ee6ad078eb3b7c5aaa

元コミット内容

compress/flate: delete unused util functions.

R=rsc
CC=golang-dev
https://golang.org/cl/5555071

変更の背景

このコミットは、Go言語の標準ライブラリである compress/flate パッケージから、使用されていないユーティリティ関数を削除することを目的としています。具体的には、util.go ファイル全体が削除され、それに伴い、huffman_bit_writer.go と huffman_code.go 内でこれらのユーティリティ関数が直接使用されていた箇所が、Goの組み込み関数やより直接的なループ処理に置き換えられています。これにより、コードベースの簡素化、不要な依存関係の排除、そして潜在的なパフォーマンスの向上が期待されます。

前提知識の解説

compress/flate パッケージ

compress/flate はGo言語の標準ライブラリの一部で、DEFLATEアルゴリズムの実装を提供します。DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせたデータ圧縮アルゴリズムであり、ZIP、gzip、PNGなどの多くの一般的な圧縮形式で使用されています。このパッケージは、データの圧縮と解凍のための低レベルな機能を提供します。

ハフマン符号化 (Huffman Coding)

ハフマン符号化は、データ圧縮に用いられる可変長符号化の一種です。データの出現頻度に基づいて、頻繁に出現する文字には短い符号を、稀にしか出現しない文字には長い符号を割り当てることで、全体のデータサイズを削減します。compress/flate パッケージでは、このハフマン符号化が圧縮プロセスの中核をなしています。

Go言語におけるスライス操作

Go言語では、スライスは配列のセグメントを参照するデータ構造です。スライスは動的なサイズ変更が可能で、Goプログラミングにおいて非常に頻繁に使用されます。

• copy() 関数: Goの組み込み関数で、ソーススライスからデスティネーションスライスへ要素をコピーします。これは、要素を一つずつループでコピーするよりも効率的です。
• for range ループ: スライスやマップなどのコレクションをイテレートするためのGoの構文です。インデックスと値の両方、または値のみを取得できます。スライスの要素を初期化する際によく使用されます。
• min() 関数: 2つの数値のうち小さい方を返す関数。多くのプログラミング言語で一般的なユーティリティ関数ですが、Goの標準ライブラリには組み込みの min 関数は存在しません（Go 1.21で min と max が組み込み関数として追加されましたが、このコミットが行われた2012年時点では存在しませんでした）。そのため、以前はカスタムのユーティリティ関数として定義されることがありました。

技術的詳細

このコミットの主要な変更点は、src/pkg/compress/flate/util.go ファイルの削除です。このファイルには、min, minInt32, max, fillInts, fillInt32s, fillBytes, fillInt8s, fillUint8s, copyInt8s, copyUint8s といった汎用的なユーティリティ関数が含まれていました。

これらの関数が削除された背景には、以下の理由が考えられます。

1. 不要な抽象化の排除: これらのユーティリティ関数は、Go言語の組み込み機能（例: copy() 関数や for range ループ）で直接、かつより効率的に実現できる操作をカプセル化していました。不要な抽象化を排除することで、コードの可読性と保守性が向上します。
2. Go言語の進化: Go言語は継続的に進化しており、新しいバージョンではより効率的な組み込み関数や言語機能が追加されることがあります。このコミットが行われた時期（2012年）はGo言語の初期段階であり、その後、スライス操作に関する最適化や組み込み関数の追加が行われた可能性があります。
3. パフォーマンスの最適化: ユーティリティ関数を呼び出すオーバーヘッドをなくし、直接的なスライス操作に置き換えることで、コンパイラによる最適化の機会が増え、実行時のパフォーマンスが向上する可能性があります。特に、fill 系関数を for range ループに、copy 系関数を組み込みの copy() 関数に置き換えることは、この目的のためによく行われます。

具体的な変更箇所は以下の通りです。

src/pkg/compress/flate/huffman_bit_writer.go

• fillInt32s(w.codegenFreq, 0) が for i := range w.codegenFreq { w.codegenFreq[i] = 0 } に変更されました。これは、スライスをゼロ値で埋めるためのカスタム関数呼び出しを、Goのイディオムである for range ループによる直接的な初期化に置き換えたものです。
• copyUint8s(codegen[0:numLiterals], w.literalEncoding.codeBits) と copyUint8s(codegen[numLiterals:numLiterals+numOffsets], w.offsetEncoding.codeBits) が、それぞれ copy(codegen[0:numLiterals], w.literalEncoding.codeBits) と copy(codegen[numLiterals:numLiterals+numOffsets], w.offsetEncoding.codeBits) に変更されました。これは、カスタムの copyUint8s 関数をGoの組み込み copy() 関数に置き換えたものです。組み込みの copy() 関数は通常、より最適化されており、パフォーマンスが向上します。
• n := min(count, 6) と n := min(count, 138) が、それぞれ以下のように変更されました。

  n := 6
  if n > count {
      n = count
  }
  

  と

  n := 138
  if n > count {
      n = count
  }
  

  これは、カスタムの min 関数を、条件分岐による直接的な最小値の計算に置き換えたものです。
• fillInt32s(w.literalFreq, 0) と fillInt32s(w.offsetFreq, 0) が、それぞれ for i := range w.literalFreq { w.literalFreq[i] = 0 } と for i := range w.offsetFreq { w.offsetFreq[i] = 0 } に変更されました。これも fillInt32s の削除に伴う変更です。

src/pkg/compress/flate/huffman_code.go

• maxBits = minInt32(maxBits, n-1) が以下のように変更されました。

  if maxBits > n-1 {
      maxBits = n - 1
  }
  

  これは、カスタムの minInt32 関数を、条件分岐による直接的な最小値の計算に置き換えたものです。

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

このコミットのコアとなる変更は、src/pkg/compress/flate/util.go ファイルの削除と、それに伴う他のファイルでのユーティリティ関数の呼び出し箇所の置き換えです。

• src/pkg/compress/flate/Makefile:

  --- a/src/pkg/compress/flate/Makefile
  +++ b/src/pkg/compress/flate/Makefile
  @@ -12,6 +12,5 @@ GOFILES=\
   	inflate.go\
   	reverse_bits.go\
   	token.go\
  -	util.go\
   
   include ../../../Make.pkg
  

  util.go がビルド対象から削除されています。

• src/pkg/compress/flate/huffman_bit_writer.go:

  • fillInt32s の置き換え:

    --- a/src/pkg/compress/flate/huffman_bit_writer.go
    +++ b/src/pkg/compress/flate/huffman_bit_writer.go
    @@ -193,15 +193,17 @@ func (w *huffmanBitWriter) writeBytes(bytes []byte) {
     //  numLiterals      The number of literals in literalEncoding
     //  numOffsets       The number of offsets in offsetEncoding
     func (w *huffmanBitWriter) generateCodegen(numLiterals int, numOffsets int) {
    -	fillInt32s(w.codegenFreq, 0)
    +	for i := range w.codegenFreq {
    +		w.codegenFreq[i] = 0
    +	}
     	// Note that we are using codegen both as a temporary variable for holding
     	// a copy of the frequencies, and as the place where we put the result.
     	// This is fine because the output is always shorter than the input used
     	// so far.
     	codegen := w.codegen // cache
     	// Copy the concatenated code sizes to codegen.  Put a marker at the end.
    -	copyUint8s(codegen[0:numLiterals], w.literalEncoding.codeBits)
    -	copyUint8s(codegen[numLiterals:numLiterals+numOffsets], w.offsetEncoding.codeBits)
    +	copy(codegen[0:numLiterals], w.literalEncoding.codeBits)
    +	copy(codegen[numLiterals:numLiterals+numOffsets], w.offsetEncoding.codeBits)
     	codegen[numLiterals+numOffsets] = badCode
     
      	size := codegen[0]
    @@ -222,7 +224,10 @@ func (w *huffmanBitWriter) generateCodegen(numLiterals int, numOffsets int) {
     		w.codegenFreq[size]++
     		count--
     		for count >= 3 {
    -			n := min(count, 6)
    +			n := 6
    +			if n > count {
    +				n = count
    +			}
     			codegen[outIndex] = 16
     			outIndex++
     			codegen[outIndex] = uint8(n - 3)
    @@ -232,7 +237,10 @@ func (w *huffmanBitWriter) generateCodegen(numLiterals int, numOffsets int) {
     		} else {
     			for count >= 11 {
    -				n := min(count, 138)
    +				n := 138
    +				if n > count {
    +					n = count
    +				}
     				codegen[outIndex] = 18
     				outIndex++
     				codegen[outIndex] = uint8(n - 11)
    @@ -351,8 +359,12 @@ func (w *huffmanBitWriter) writeBlock(tokens []token, eof bool, input []byte) {\
     	if w.err != nil {
     		return
     	}
    -	fillInt32s(w.literalFreq, 0)
    -	fillInt32s(w.offsetFreq, 0)
    +	for i := range w.literalFreq {
    +		w.literalFreq[i] = 0
    +	}
    +	for i := range w.offsetFreq {
    +		w.offsetFreq[i] = 0
    +	}
     
      	n := len(tokens)
      	tokens = tokens[0 : n+1]
    

  • min の置き換え: 上記の差分に含まれています。

• src/pkg/compress/flate/huffman_code.go:

  • minInt32 の置き換え:

    --- a/src/pkg/compress/flate/huffman_code.go
    +++ b/src/pkg/compress/flate/huffman_code.go
    @@ -195,7 +195,9 @@ func (h *huffmanEncoder) bitCounts(list []literalNode, maxBits int32) []int32 {
     
      	// The tree can't have greater depth than n - 1, no matter what.  This
      	// saves a little bit of work in some small cases
    -	maxBits = minInt32(maxBits, n-1)
    +	if maxBits > n-1 {
    +		maxBits = n - 1
    +	}
     
      	// Create information about each of the levels.
      	// A bogus "Level 0" whose sole purpose is so that
    

• src/pkg/compress/flate/util.go:

  --- a/src/pkg/compress/flate/util.go
  +++ /dev/null
  @@ -1,72 +0,0 @@
  -// Copyright 2009 The Go Authors. All rights reserved.
  -// Use of this source code is governed by a BSD-style
  -// license that can be found in the LICENSE file.
  -
  -package flate
  -
  -func min(left int, right int) int {
  -// ... (rest of the file content)
  

  ファイル全体が削除されています。

コアとなるコードの解説

このコミットは、Go言語の設計哲学である「シンプルさ」と「効率性」を反映しています。

1. util.go の削除:

   • このファイルには、min, max, fill*, copy* といった基本的な操作を行う関数が含まれていました。これらは多くのプログラミング言語で一般的なユーティリティ関数ですが、Go言語ではこれらの操作をより直接的かつ効率的に行うための組み込み機能やイディオムが存在します。
   • 例えば、スライスを特定の値で埋める fillInt32s のような関数は、for i := range slice { slice[i] = value } という for range ループで簡単に実現できます。この直接的なループは、関数呼び出しのオーバーヘッドがなく、コンパイラによる最適化の恩恵を受けやすいです。
   • 同様に、スライス間で要素をコピーする copyUint8s のような関数は、Goの組み込み関数である copy() を使用することで、より効率的かつ簡潔に記述できます。組み込みの copy() は、内部的に高度に最適化されたアセンブリコードを使用していることが多く、カスタム実装よりも高速です。
   • min や minInt32 のような最小値を求める関数も、if 文による条件分岐で直接記述することで、関数呼び出しのオーバーヘッドを排除できます。

2. huffman_bit_writer.go と huffman_code.go の変更:

   • これらのファイルで行われた変更は、util.go の削除に伴うものです。カスタムユーティリティ関数への依存をなくし、Goの組み込み機能やイディオムに置き換えることで、コードの依存関係が減り、よりGoらしい（idiomatic Go）コードになっています。
   • 特に、copy 関数の使用は、Go言語におけるスライス操作のベストプラクティスの一つです。
   • for range ループによるスライスの初期化も、Goのコードベースで頻繁に見られるパターンであり、可読性と効率性を両立させます。

このコミットは、Go言語の標準ライブラリが、外部のユーティリティ関数に依存するのではなく、言語自身の強力な組み込み機能とイディオムを最大限に活用して、シンプルで効率的なコードベースを維持しようとする姿勢を示しています。これにより、コードの保守性が向上し、将来的なGo言語の進化にも対応しやすくなります。

関連リンク

• Go言語の compress/flate パッケージのドキュメント: https://pkg.go.dev/compress/flate (現在のドキュメント)
• このコミットのChange-ID: 5555071 (GoのコードレビューシステムGerritのChange-ID)

参考にした情報源リンク

• https://github.com/golang/go/commit/858f0b4d9568bb3a2ef9b9ee6ad078eb3b7c5aaa (GitHub上のコミットページ)
• https://golang.org/cl/5555071 (GoのGerritコードレビューシステムにおける変更リスト)
• Go言語の公式ドキュメント (スライス、組み込み関数 copy などに関する情報): https://go.dev/doc/
• DEFLATEアルゴリズムに関する一般的な情報 (例: Wikipediaなど)
• ハフマン符号化に関する一般的な情報 (例: Wikipediaなど)