#navi_header|Java|

[[1317]] に続いたメモ5.

* Stringクラスで文字列を保持している実体は何か？ → char[]

Oracle JDK 7(jdk7u25)のJDKソースを確認してみる。
#pre||>
public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    /** The value is used for character storage. */
    private final char value[];
||<

→Stringクラスのコンストラクタは、いずれも最終的にvalueというchar配列に値を設定してる。

参考：
- String (Java) class – Under the hood | Play with Java
-- http://shyamalmadura.wordpress.com/2013/11/01/string-java-class-under-the-hood/
- String Memory Internals | Javalobby
-- http://java.dzone.com/articles/string-memory-internals
- What is the Java's internal represention for String? Modified UTF-8? UTF-16? - Stack Overflow
-- http://stackoverflow.com/questions/9699071/what-is-the-javas-internal-represention-for-string-modified-utf-8-utf-16

* byte[]からStringを生成するコンストラクタは何をしているのか？

"String(byte[], int, int, Charset)"のコンストラクタから追ってみる。
JDK7u25のソースを参考にしている。
#pre||>
    public String(byte bytes[], int offset, int length, Charset charset) {
        // (...)
        this.value =  StringCoding.decode(charset, bytes, offset, length);
    }
||<
StringCodingはpackage privateスコープのクラスのため、未公開。JDKのソースで確認する。細かいエラー処理とかは思い切って省略すると以下の流れになっている。
#pre||>
    static char[] decode(Charset cs, byte[] ba, int off, int len) {
        // Charset#newDecoder()から、CharsetDecoderインスタンスを取得
        CharsetDecoder cd = cs.newDecoder();
        // 1バイト辺りの最大文字数とlenより、最大の文字数を計算
        int en = scale(len, cd.maxCharsPerByte());
        // 最大の文字数でchar配列を作成
        char[] ca = new char[en];

        // CharsetDecoderの準備
        cd.onMalformedInput(CodingErrorAction.REPLACE)
          .onUnmappableCharacter(CodingErrorAction.REPLACE)
          .reset();

        if (cd instanceof ArrayDecoder) {
            // CharsetDecoderがsun.nio.cs.ArrayDecoderの派生クラスならそのままdecode()メソッドを呼ぶ。

            int clen = ((ArrayDecoder)cd).decode(ba, off, len, ca);
            return safeTrim(ca, clen, cs, isTrusted);

        } else {
            // sun.nio.cs.ArrayDecoderの派生クラスでなければ、
            // ByteBufferとCharBufferにラップしてdecode()メソッドを呼ぶ。

            ByteBuffer bb = ByteBuffer.wrap(ba, off, len);
            CharBuffer cb = CharBuffer.wrap(ca);
            try {
                CoderResult cr = cd.decode(bb, cb, true);
                if (!cr.isUnderflow())
                    cr.throwException();
                cr = cd.flush(cb);
                if (!cr.isUnderflow())
                    cr.throwException();
            } catch (CharacterCodingException x) {
                // Substitution is always enabled,
                // so this shouldn't happen
                throw new Error(x);
            }
            return safeTrim(ca, cb.position(), cs, isTrusted);
        }
    }
||<

CharsetDecoderの実装については後述するが、JDKで提供されているものについては "sun.nio.cs" パッケージ以下で実装されている。
インターフェイスとしては java.nio.charset.CharsetDecoder abstract class として公開されている。

* Java 7u6 で行われたString.substring()に関するチューニングとは？

それまでのJavaでは、String.substring()の結果は、元のStringインスタンスの"char[] value"をそのまま参照し、beginとendだけを変更したインスタンスを返していた。
その場合、巨大なテキストデータから文字列を切り出す処理を考えると、元のテキストデータが不要になっても、切りだされたStringインスタンスが巨大な"char[] value"を参照しつづけ、GCで回収されない。
これによるメモリリークが問題視されたらしく、Java 7u6 では、元の"char[] value"から必要な範囲だけをコピーして新規に作成する形式に変更された。これにより、不要になった元の巨大なテキストデータが適切にGCで回収されるようになる。

参考：
- Changes to String in Java 7u6 - Java Performance Tuning Guide
-- http://java-performance.info/changes-to-string-java-1-7-0_06/
- Oracle Tunes Java's Internal String Representation
-- http://www.infoq.com/news/2013/12/Oracle-Tunes-Java-String

実際にJDKのソースを確認してみる。

JDK6のString.substring()の流れを確認する：
http://grepcode.com/file_/repository.grepcode.com/java/root/jdk/openjdk/6-b27/java/lang/String.java/?v=source
#pre||>
    public String substring(int beginIndex, int endIndex) {
        // (...)
        return ((beginIndex == 0) && (endIndex == count)) ? this :
            new String(offset + beginIndex, endIndex - beginIndex, value);
    }
||<
→ String(int, int, char[]) のコンストラクタで生成したのを返している。このコンストラクタは以下のようにpackage privateとなっており、外部には公開されていない。
#pre||>
    String(int offset, int count, char value[]) {
        this.value = value;
        this.offset = offset;
        this.count = count;
    }
||<
このコンストラクタでは、確かに、元の"char[] value"をそのまま引き継ぎ、offsetとcountだけを更新している。このため、元のStringが巨大なテキストデータだった場合、その"char[] value"で本来は使われない領域が参照され続ける。
これにより、元の巨大なテキストデータが不要になっても、substring()されたインスタンスの方で参照が残っているため、不要なデータがGCに回収されない。(substring()された新しいStringインスタンスが不要になってようやくGC対象になる。)

一方、JDK 7u40 のソースを確認してみる。
http://grepcode.com/file_/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/lang/String.java/?v=source
#pre||>
    public String substring(int beginIndex, int endIndex) {
        // (...)
        return ((beginIndex == 0) && (endIndex == value.length)) ? this
                : new String(value, beginIndex, subLen);
    }
||<
→JDK6とは異なり、String(char[], int, int)のコンストラクタを呼んでいる。
#pre||>
    public String(char value[], int offset, int count) {
        // (...)
        this.value = Arrays.copyOfRange(value, offset, offset+count);
    }
||<
新しく配列をコピーして作ったのを、"this.value"に設定している。

* new String(byte bytes[], int offset, int length)はどうやってCharsetを決定しているのか？

JDK7の場合：
+ Javaのシステムプロパティ："file.encoding" で指定された名前をデフォルトのCharsetとして使ってみる。
+ ↑で無効なCharset名だったら、ISO-8859-1を仮定して使ってみる。

Oracle JDK 7(jdk7u25)のJDKソースを確認してみる。
java.lang.Stringのコンストラクタ：
#pre||>
    public String(byte bytes[], int offset, int length) {
        checkBounds(bytes, offset, length);
        this.value = StringCoding.decode(bytes, offset, length);
    }
||<

→ StringCodingはpackageスコープのクラスのため、未公開。JDKのソースを確認する。

java.lang.StringCoding:
#pre||>
class StringCoding {

    // (...)

    static char[] decode(byte[] ba, int off, int len) {
        String csn = Charset.defaultCharset().name();
        try {
            // use charset name decode() variant which provides caching.
            return decode(csn, ba, off, len);
        } catch (UnsupportedEncodingException x) {
            warnUnsupportedCharset(csn);
        }
        try {
            return decode("ISO-8859-1", ba, off, len);
        } catch (UnsupportedEncodingException x) {
            // If this code is hit during VM initialization, MessageUtils is
            // the only way we will be able to get any kind of error message.
            MessageUtils.err("ISO-8859-1 charset not available: "
                             + x.toString());
            // If we can not find ISO-8859-1 (a required encoding) then things
            // are seriously wrong with the installation.
            System.exit(1);
            return null;
        }
    }
||<

→最初にCharset.defaultCharset()でCharset名を取得し、StringCoding.decode()でデコードを試みてる。それに失敗したら、"ISO-8859-1"でデコードできないか試してみて、ソレでも駄目ならISO-8859-1でエラーになるというのはシステムレベルでおかしいので、JVMを終了(System.exit(1))してる。

Charset.defaultCharset()はどこからCharset名を取り出してるのか？これも、Charset.defaultCharset()の実装をJDKのソースで確認する。
#pre||>
    public static Charset defaultCharset() {
        if (defaultCharset == null) {
            synchronized (Charset.class) {
                String csn = AccessController.doPrivileged(
                    new GetPropertyAction("file.encoding"));
                Charset cs = lookup(csn);
                if (cs != null)
                    defaultCharset = cs;
                else
                    defaultCharset = forName("UTF-8");
            }
        }
        return defaultCharset;
    }
||<
→ "file.encoding" システムプロパティから取得している。"file.encoding"の値がおかしかったら、"UTF-8"を試してる。


* "ISO-8859-1"と、"US-ASCII"は何が違うのか？

US-ASCIIは7bitの範囲の文字までしかマッピングしていないことから、US-ASCIIはISO-8859-1のサブセットと考えることができる。
- Running EncodingSampler.java with ISO-8859-1 and US-ASCII
-- http://www.herongyang.com/JDK/charset-Character-Encoding-Test-ISO-8859-1-US-ASCII.html

* Charsetの実装コードはどこにあるのか？

OpenJDK7だと、sun.nio.cs パッケージ以下にあるぽい。
- ISO-8859-1の実装：
-- http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/sun/nio/cs/ISO_8859_1.java?av=f
-- http://code.metager.de/source/xref/openjdk/jdk7/jdk/src/share/classes/sun/nio/cs/ISO_8859_1.java
- US-ASCIIの実装：
-- http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/sun/nio/cs/US_ASCII.java?av=f
-- http://code.metager.de/source/xref/openjdk/jdk7/jdk/src/share/classes/sun/nio/cs/US_ASCII.java

* java.nio.charset.CoderResult クラスでのスレッド間ロックについての再考

[[1317]] で軽く触れた、"java.nio.charset.CoderResult" について再考する。
- Thread blocking on java.nio.charset.CoderResult | Oracle Community
-- https://community.oracle.com/thread/1145918?start=0&tstart=0

java.nio.charset.CoderReusltクラスは、java.nio.charset.CharsetDecoder#decode() や java.nio.charset.CharsetEncoder#encode() などの処理結果を表現するクラスになっている。
byte配列をdecodeする、あるいはUnicode文字の配列をbyte配列にencodeする処理はどうしても状態遷移が伴う処理であり、入力バッファ・出力バッファの長さや中途半端なデータ、対応していないデータなど様々な異常処理が発生し得る。
そのため、CharsetDecoder/CharsetEncoderの実装は、内部でCoderResultに適切な異常状態の詳細を設定して、呼び出し元に返す仕組みになっている。
http://docs.oracle.com/javase/jp/7/api/java/nio/charset/CoderResult.html

「長さが中途半端」なパターンが頻用されるのか、専用のstatic factoryが用意されている。
- CoderResult#malformedForLength(int length) : 指定された長さの不正入力エラーを表した一意のオブジェクトを返す
- CoderResult#unmappableForLength(int length) : 指定された長さのマップ不可文字エラーを表した一意のオブジェクトを返す

このstatic factoryが、内部で length に対応するCoderResultのインスタンスをstaticにキャッシュしている。これが CoderResultクラスに対するsynchronizedブロックでスレッドセーフティを確保している。
つまりこれが、マルチスレッド（正確にはClassLoaderに対してとなるが、システムクラスなので事実上システム全体）間でのロックにつながるsynchronizedブロックになる。

以下が上記２つのstatic factoryのJDK7u25におけるソース。
#pre||>
    public static CoderResult malformedForLength(int length) {
        return malformedCache.get(length);
    }
    public static CoderResult unmappableForLength(int length) {
        return unmappableCache.get(length);
    }
||<
"malformedCache", "unmappableCache"ともにCoderResultのstaticメンバ。
#pre||>
    private static Cache malformedCache
        = new Cache() {
                public CoderResult create(int len) {
                    return new CoderResult(CR_MALFORMED, len);
                }};

    private static Cache unmappableCache
        = new Cache() {
                public CoderResult create(int len) {
                    return new CoderResult(CR_UNMAPPABLE, len);
                }};
||<
"Cache"はCoderResultクラス内のインナークラスとして宣言されており、"create(int len)"をabstractとしている。
#pre||>

    private static abstract class Cache {

        private Map<Integer,WeakReference<CoderResult>> cache = null;

        protected abstract CoderResult create(int len);

        private synchronized CoderResult get(int len) {
            if (len <= 0)
                throw new IllegalArgumentException("Non-positive length");
            Integer k = new Integer(len);
            WeakReference<CoderResult> w;
            CoderResult e = null;
            if (cache == null) {
                cache = new HashMap<Integer,WeakReference<CoderResult>>();
            } else if ((w = cache.get(k)) != null) {
                e = w.get();
            }
            if (e == null) {
                e = create(len);
                cache.put(k, new WeakReference<CoderResult>(e));
            }
            return e;
        }

    }
||<
これにより、CR_MALFORMED/CR_UNMAPPABLEにそれぞれ対応する、長さ毎のCoderResultインスタンスをstaticかつスレッドセーフにキャッシュしている。

確かにクラスのstaticメンバに対するsynchronizedなのでマルチスレッド間でグローバルにロックされてしまう。しかし、これがチューニングレベルで影響してしまうのはどのような時か？

まず、これらのstatic factoryは長さが不正であったり文字とのマッピングに失敗している状態を表している。つまり、異常処理で呼ばれるのを意図している。
したがって、大抵の時間が正常処理に費やされる一般的なシステムであれば、これらのstatic factoryが呼ばれることはほとんど無いと考えられ、チューニングレベルで影響することも無いと考えられる。

チューニングに影響するレベルとしては、システムが想定している文字コードとは異なるデータを大量に扱う状態が考えられる。
ただその場合、当然decode/encodeが正常に終了していないため、結果として文字化けなどが大量発生してすぐに異常に気づくだろう。
あるいはそもそもどんな文字コードがくるか分からず、アスキー範囲だけを文字として扱いたい場合に、UTF-8などdecode/encodeで状態遷移が必要なCharsetを使ってしまっているケースが考えられる。
バイナリデータを無理やり、アスキー範囲だけでも文字として扱う際に、UTF-8を使ってStringにすると、UTF-8に従わないbyte[]部分でunmappableが発生する可能性がある。
つまり定常的に文字コード処理の異常が発生している状態であり、そのようなユースケースだと体感レベルでパフォーマンスに影響してしまうかもしれない。

解決策としては、システムの特性によっていくつか考えられる。
- バイナリデータを無理やり、アスキー範囲だけでも文字として扱いたい場合
-- UTF-8などではなく、ISO-8859-1を使う。特にISO-8859-1のCharsetDecoder実装(byte[] -> char[]変換)では、CoderResult.malformedForLength()/unmappableForLength()が一切呼ばれない。
--- http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/sun/nio/cs/ISO_8859_1.java?av=f
--- ただし、CharsetEncoderの実装については、u00FF 以上の文字についてはサロゲートペアの処理を経由し、CoderResult.malformedForLength()/unmappableForLength()が呼ばれる可能性がある。
--- 上記については、元々ISO-8859-1でdecode()したStringであれば、そのchar[]の中身についてもu0000 - u00FFまでの範囲に収まってるはずなので、心配要らないかも・・・？
- 諸事情で文字コードを変更できない場合
-- 対応策不明。
-- 原理的にはCoderResultのクラスを改変する他ない。
--- システムクラスに属してしまうため、ClassLoader#loadClass()でゴニョゴニョする難易度が半端ない。
--- agentの仕組みを使って、CoderResultクラスのロードが発生するタイミングで、synchronized cacheでない実装に改変した独自のCoderResultに挿げ替える仕組みは出来るかもしれないが、システム全体への影響が発生してしまうため、影響度が大きい。
-- CoderResult.malformedForLength()/unmappableForLength()を呼ばない、独自のCharsetProviderを実装するのはアリかもしれない・・・。

#navi_footer|Java|