Java字串編碼解碼效能提升的技巧分享

2022-05-18 19:02:32

1.常見字串編碼

常見的字串編碼有：

LATIN1 只能儲存ASCII字元，又稱ISO-8859-1。

UTF-8 變長位元組編碼，一個字元需要使用1個、2個或者3個byte表示。由於中文通常需要3個位元組表示，中文場景UTF-8編碼通常需要更多的空間，替代的方案是GBK/GB2312/GB18030。

UTF-16 2個位元組，一個字元需要使用2個byte表示，又稱UCS-2 (2-byte Universal Character Set)。根據大小端的區分，UTF-16有兩種形式，UTF-16BE和UTF-16LE，預設UTF-16指UTF-16BE。Java語言中的char是UTF-16LE編碼。

GB18030 變長位元組編碼，一個字元需要使用1個、2個或者3個byte表示。類似UTF8，中文只需要2個字元，表示中文更省位元組大小，缺點是在國際上不通用。

為了計算方便，記憶體中字串通常使用等寬字元，Java語言中char和.NET中的char都是使用UTF-16。早期Windows-NT只支援UTF-16。

2.編碼轉換效能

UTF-16和UTF-8之間轉換比較複雜，通常效能較差。

如下是一個將UTF-16轉換為UTF-8編碼的實現，可以看出演演算法比較複雜，所以效能較差，這個操作也無法使用vector API做優化。

static int encodeUTF8(char[] utf16, int off, int len, byte[] dest, int dp) {
    int sl = off + len, last_offset = sl - 1;

    while (off < sl) {
        char c = utf16[off++];
        if (c < 0x80) {
            // Have at most seven bits
            dest[dp++] = (byte) c;
        } else if (c < 0x800) {
            // 2 dest, 11 bits
            dest[dp++] = (byte) (0xc0 | (c >> 6));
            dest[dp++] = (byte) (0x80 | (c & 0x3f));
        } else if (c >= 'uD800' && c < 'uE000') {
            int uc;
            if (c < 'uDC00') {
                if (off > last_offset) {
                    dest[dp++] = (byte) '?';
                    return dp;
                }

                char d = utf16[off];
                if (d >= 'uDC00' && d < 'uE000') {
                    uc = (c << 10) + d + 0xfca02400;
                } else {
                    throw new RuntimeException("encodeUTF8 error", new MalformedInputException(1));
                }
            } else {
                uc = c;
            }
            dest[dp++] = (byte) (0xf0 | ((uc >> 18)));
            dest[dp++] = (byte) (0x80 | ((uc >> 12) & 0x3f));
            dest[dp++] = (byte) (0x80 | ((uc >> 6) & 0x3f));
            dest[dp++] = (byte) (0x80 | (uc & 0x3f));
            off++; // 2 utf16
        } else {
            // 3 dest, 16 bits
            dest[dp++] = (byte) (0xe0 | ((c >> 12)));
            dest[dp++] = (byte) (0x80 | ((c >> 6) & 0x3f));
            dest[dp++] = (byte) (0x80 | (c & 0x3f));
        }
    }
    return dp;
}

由於Java中char是UTF-16LE編碼，如果需要將char[]轉換為UTF-16LE編碼的byte[]時，可以使用sun.misc.Unsafe#copyMemory方法快速拷貝。比如：

static int writeUtf16LE(char[] chars, int off, int len, byte[] dest, final int dp) {
    UNSAFE.copyMemory(chars
            , CHAR_ARRAY_BASE_OFFSET + off * 2
            , dest
            , BYTE_ARRAY_BASE_OFFSET + dp
            , len * 2
    );
    dp += len * 2;
    return dp;
}

3.Java String的編碼

不同版本的JDK String的實現不一樣，從而導致有不同的效能表現。char是UTF-16編碼，但String在JDK 9之後內部可以有LATIN1編碼。

3.1. JDK 6之前的String實現

static class String {
    final char[] value;
    final int offset;
    final int count;
}

在Java 6之前，String.subString方法產生的String物件和原來String物件共用一個char[] value，這會導致subString方法返回的String的char[]被參照而無法被GC回收。於是使得很多庫都會針對JDK 6及以下版本避免使用subString方法。

3.2. JDK 7/8的String實現

static class String {
    final char[] value;
}

JDK 7之後，字串去掉了offset和count欄位，value.length就是原來的count。這避免了subString參照大char[]的問題，優化也更容易，從而JDK7/8中的String操作效能比Java 6有較大提升。

3.3. JDK 9/10/11的實現

static class String {
    final byte code;
    final byte[] value;

    static final byte LATIN1 = 0;
    static final byte UTF16  = 1;
}

JDK 9之後，value型別從char[]變成byte[]，增加了一個欄位code，如果字元全部是ASCII字元，使用value使用LATIN編碼；如果存在任何一個非ASCII字元，則用UTF16編碼。這種混合編碼的方式，使得英文場景佔更少的記憶體。缺點是導致Java 9的String API效能可能不如JDK 8，特別是傳入char[]構造字串，會被做壓縮為latin編碼的byte[]，有些場景會下降10%。

4.快速構造字串的方法

為了實現字串是不可變特性，構造字串的時候，會有拷貝的過程，如果要提升構造字串的開銷，就要避免這樣的拷貝。

比如如下是JDK8的String的一個建構函式的實現

public final class String {
    public String(char value[]) {
        this.value = Arrays.copyOf(value, value.length);
    }
}

在JDK8中，有一個建構函式是不做拷貝的，但這個方法不是public，需要用一個技巧實現MethodHandles.Lookup & LambdaMetafactory繫結反射來呼叫，文章後面有介紹這個技巧的程式碼。

public final class String {
    String(char[] value, boolean share) {
        // assert share : "unshared not supported";
        this.value = value;
    }
}

快速構造字元的方法有三種：

使用MethodHandles.Lookup & LambdaMetafactory繫結反射
使用JavaLangAccess的相關方法
使用Unsafe直接構造

這三種方法，1和2效能差不多，3比1和2略慢，但都比直接new字串要快得多。JDK8使用JMH測試的資料如下:

Benchmark Mode Cnt Score Error Units
StringCreateBenchmark.invoke thrpt 5 784869.350 ± 1936.754 ops/ms
StringCreateBenchmark.langAccess thrpt 5 784029.186 ± 2734.300 ops/ms
StringCreateBenchmark.unsafe thrpt 5 761176.319 ± 11914.549 ops/ms
StringCreateBenchmark.newString thrpt 5 140883.533 ± 2217.773 ops/ms

在JDK 9之後，對全部是ASCII字元的場景，直接構造能達到更好的效果。

4.1 基於MethodHandles.Lookup & LambdaMetafactory繫結反射的快速構造字串的方法

4.1.1 JDK8快速構造字串

public static BiFunction<char[], Boolean, String> getStringCreatorJDK8() throws Throwable {
   Constructor<MethodHandles.Lookup> constructor = MethodHandles.Lookup.class.getDeclaredConstructor(Class.class, int.class);
   constructor.setAccessible(true);
    MethodHandles lookup = constructor.newInstance(
          String.class
             , -1 // Lookup.TRUSTED
             );
    
    MethodHandles.Lookup caller = lookup.in(String.class);
  
    MethodHandle handle = caller.findConstructor(
                String.class, MethodType.methodType(void.class, char[].class, boolean.class)
                );

    CallSite callSite = LambdaMetafactory.metafactory(
            caller
            , "apply"
            , MethodType.methodType(BiFunction.class)
            , handle.type().generic()
            , handle
            , handle.type()
            );

    return (BiFunction) callSite.getTarget().invokeExact();
}

4.1.2 JDK 11快速構造字串的方法

public static ToIntFunction<String> getStringCode11() throws Throwable {
    Constructor<MethodHandles.Lookup> constructor = MethodHandles.Lookup.class.getDeclaredConstructor(Class.class, int.class);
    constructor.setAccessible(true);
    MethodHandles.Lookup lookup = constructor.newInstance(
            String.class
            , -1 // Lookup.TRUSTED
    );

    MethodHandles.Lookup caller = lookup.in(String.class);
    MethodHandle handle = caller.findVirtual(
            String.class, "coder", MethodType.methodType(byte.class)
   );

    CallSite callSite = LambdaMetafactory.metafactory(
            caller
            , "applyAsInt"
            , MethodType.methodType(ToIntFunction.class)
            , MethodType.methodType(int.class, Object.class)
            , handle
            , handle.type()
    );

    return (ToIntFunction<String>) callSite.getTarget().invokeExact();
}

if (JDKUtils.JVM_VERSION == 11) {
    Function<byte[], String> stringCreator = JDKUtils.getStringCreatorJDK11();

    byte[] bytes = new byte[]{'a', 'b', 'c'};
    String apply = stringCreator.apply(bytes);
    assertEquals("abc", apply);
}

4.1.3 JDK 17快速構造字串的方法

在JDK 17中，MethodHandles.Lookup使用Reflection.registerFieldsToFilter對lookupClass和allowedModes做了保護，網上搜尋到的通過修改allowedModes的辦法是不可用的。

在JDK 17中，要通過設定JVM啟動引數才能使用MethodHandlers。如下：

--add-opens java.base/java.lang.invoke=ALL-UNNAMED

public static BiFunction<byte[], Charset, String> getStringCreatorJDK17() throws Throwable {
    Constructor<MethodHandles.Lookup> constructor = MethodHandles.Lookup.class.getDeclaredConstructor(Class.class, Class.class, int.class);
    constructor.setAccessible(true);
    MethodHandles.Lookup lookup = constructor.newInstance(
           String.class
            , null
            , -1 // Lookup.TRUSTED
    );

    MethodHandles.Lookup caller = lookup.in(String.class);
    MethodHandle handle = caller.findStatic(
            String.class, "newStringNoRepl1", MethodType.methodType(String.class, byte[].class, Charset.class)
    );

    CallSite callSite = LambdaMetafactory.metafactory(
            caller
            , "apply"
            , MethodType.methodType(BiFunction.class)
            , handle.type().generic()
            , handle
            , handle.type()
    );
    return (BiFunction<byte[], Charset, String>) callSite.getTarget().invokeExact();
}

if (JDKUtils.JVM_VERSION == 17) {
    BiFunction<byte[], Charset, String> stringCreator = JDKUtils.getStringCreatorJDK17();

    byte[] bytes = new byte[]{'a', 'b', 'c'};
    String apply = stringCreator.apply(bytes, StandardCharsets.US_ASCII);
    assertEquals("abc", apply);
}

4.2 基於JavaLangAccess快速構造

通過SharedSecrets提供的JavaLangAccess，也可以不拷貝構造字串，但是這個比較麻煩，JDK 8/11/17的API都不一樣，對一套程式碼相容不同的JDK版本不方便，不建議使用。

JavaLangAccess javaLangAccess = SharedSecrets.getJavaLangAccess();
javaLangAccess.newStringNoRepl(b, StandardCharsets.US_ASCII);

4.3 基於Unsafe實現快速構造字串

public static final Unsafe UNSAFE;
static {
    Unsafe unsafe = null;
    try {
        Field theUnsafeField = Unsafe.class.getDeclaredField("theUnsafe");
        theUnsafeField.setAccessible(true);
        unsafe = (Unsafe) theUnsafeField.get(null);
    } catch (Throwable ignored) {}
    UNSAFE = unsafe;
}

////////////////////////////////////////////

Object str = UNSAFE.allocateInstance(String.class);
UNSAFE.putObject(str, valueOffset, chars);

注意：在JDK 9之後，實現是不同，比如:

Object str = UNSAFE.allocateInstance(String.class);
UNSAFE.putByte(str, coderOffset, (byte) 0);
UNSAFE.putObject(str, valueOffset, (byte[]) bytes);

4.4 快速構建字串的技巧應用：

如下的方法格式化日期為字串，效能就會非常好。

public String formatYYYYMMDD(Calendar calendar) throws Throwable {
    int year = calendar.get(Calendar.YEAR);
    int month = calendar.get(Calendar.MONTH) + 1;
    int dayOfMonth = calendar.get(Calendar.DAY_OF_MONTH);

    
    byte y0 = (byte) (year / 1000 + '0');
    byte y1 = (byte) ((year / 100) % 10 + '0');
    byte y2 = (byte) ((year / 10) % 10 + '0');
    byte y3 = (byte) (year % 10 + '0');
    byte m0 = (byte) (month / 10 + '0');
    byte m1 = (byte) (month % 10 + '0');
    byte d0 = (byte) (dayOfMonth / 10 + '0');
    byte d1 = (byte) (dayOfMonth % 10 + '0');

    if (JDKUtils.JVM_VERSION >= 9) {
        byte[] bytes = new byte[] {y0, y1, y2, y3, m0, m1, d0, d1};

        if (JDKUtils.JVM_VERSION == 17) {
            return JDKUtils.getStringCreatorJDK17().apply(bytes, StandardCharsets.US_ASCII);
        }

        if (JDKUtils.JVM_VERSION <= 11) {
            return JDKUtils.getStringCreatorJDK11().apply(bytes);
        }

        return new String(bytes, StandardCharsets.US_ASCII);
    }

    char[] chars = new char[]{
            (char) y0, 
            (char) y1, 
            (char) y2, 
            (char) y3, 
            (char) m0,
            (char) m1, 
            (char) d0, 
            (char) d1
    };

    if (JDKUtils.JVM_VERSION == 8) {
        return JDKUtils.getStringCreatorJDK8().apply(chars, true);
    }

    return new String(chars);
}

5.快速遍歷字串的辦法

無論JDK什麼版本，String.charAt都是一個較大的開銷，JIT的優化效果並不好，無法消除引數index範圍檢測的開銷，不如直接操作String裡面的value陣列。

public final class String {
    private final char value[];
    
    public char charAt(int index) {
        if ((index < 0) || (index >= value.length)) {
            throw new StringIndexOutOfBoundsException(index);
        }
        return value[index];
    }
}

在JDK 9之後的版本，charAt開銷更大

public final class String {
    private final byte[] value;
    private final byte coder;
    
    public char charAt(int index) {
        if (isLatin1()) {
            return StringLatin1.charAt(value, index);
        } else {
            return StringUTF16.charAt(value, index);
        }
    }
}

5.1 獲取String.value的方法

獲取String.value的方法有如下：

使用Field反射
使用Unsafe

Unsafe和Field反射在JDK 8 JMH的比較資料如下：

Benchmark Mode Cnt Score Error Units
StringGetValueBenchmark.reflect thrpt 5 438374.685 ± 1032.028 ops/ms
StringGetValueBenchmark.unsafe thrpt 5 1302654.150 ± 59169.706 ops/ms

5.1.1 使用反射獲取String.value

static Field valueField;
static {
    try {
        valueField = String.class.getDeclaredField("value");
        valueField.setAccessible(true);
    } catch (NoSuchFieldException ignored) {}
}

////////////////////////////////////////////

char[] chars = (char[]) valueField.get(str);

5.1.2 使用Unsafe獲取String.value

static long valueFieldOffset;
static {
    try {
        Field valueField = String.class.getDeclaredField("value");
        valueFieldOffset = UNSAFE.objectFieldOffset(valueField);
    } catch (NoSuchFieldException ignored) {}
}

////////////////////////////////////////////

char[] chars = (char[]) UNSAFE.getObject(str, valueFieldOffset);

static long valueFieldOffset;
static long coderFieldOffset;
static {
    try {
        Field valueField = String.class.getDeclaredField("value");
        valueFieldOffset = UNSAFE.objectFieldOffset(valueField);
        
        Field coderField = String.class.getDeclaredField("coder");
        coderFieldOffset = UNSAFE.objectFieldOffset(coderField);
        
    } catch (NoSuchFieldException ignored) {}
}

////////////////////////////////////////////

byte coder = UNSAFE.getObject(str, coderFieldOffset);
byte[] bytes = (byte[]) UNSAFE.getObject(str, valueFieldOffset);

6.更快的encodeUTF8方法

當能直接獲取到String.value時，就可以直接對其做encodeUTF8操作，會比String.getBytes(StandardCharsets.UTF_8)效能好很多。

6.1 JDK8高效能encodeUTF8的方法

public static int encodeUTF8(char[] src, int offset, int len, byte[] dst, int dp) {
    int sl = offset + len;
    int dlASCII = dp + Math.min(len, dst.length);

    // ASCII only optimized loop
    while (dp < dlASCII && src[offset] < 'u0080') {
        dst[dp++] = (byte) src[offset++];
    }

    while (offset < sl) {
        char c = src[offset++];
        if (c < 0x80) {
            // Have at most seven bits
            dst[dp++] = (byte) c;
        } else if (c < 0x800) {
            // 2 bytes, 11 bits
            dst[dp++] = (byte) (0xc0 | (c >> 6));
            dst[dp++] = (byte) (0x80 | (c & 0x3f));
        } else if (c >= 'uD800' && c < ('uDFFF' + 1)) { //Character.isSurrogate(c) but 1.7
            final int uc;
            int ip = offset - 1;
            if (c >= 'uD800' && c < ('uDBFF' + 1)) { // Character.isHighSurrogate(c)
                if (sl - ip < 2) {
                    uc = -1;
                } else {
                    char d = src[ip + 1];
                    // d >= 'uDC00' && d < ('uDFFF' + 1)
                    if (d >= 'uDC00' && d < ('uDFFF' + 1)) { // Character.isLowSurrogate(d)
                        uc = ((c << 10) + d) + (0x010000 - ('uD800' << 10) - 'uDC00'); // Character.toCodePoint(c, d)
                    } else {
                        dst[dp++] = (byte) '?';
                        continue;
                    }
                }
            } else {
                //
                if (c >= 'uDC00' && c < ('uDFFF' + 1)) { // Character.isLowSurrogate(c)
                    dst[dp++] = (byte) '?';
                    continue;
                } else {
                    uc = c;
                }
            }

            if (uc < 0) {
                dst[dp++] = (byte) '?';
            } else {
                dst[dp++] = (byte) (0xf0 | ((uc >> 18)));
                dst[dp++] = (byte) (0x80 | ((uc >> 12) & 0x3f));
                dst[dp++] = (byte) (0x80 | ((uc >> 6) & 0x3f));
                dst[dp++] = (byte) (0x80 | (uc & 0x3f));
                offset++; // 2 chars
            }
        } else {
            // 3 bytes, 16 bits
            dst[dp++] = (byte) (0xe0 | ((c >> 12)));
            dst[dp++] = (byte) (0x80 | ((c >> 6) & 0x3f));
            dst[dp++] = (byte) (0x80 | (c & 0x3f));
        }
    }
    return dp;
}

使用encodeUTF8方法舉例

char[] chars = UNSAFE.getObject(str, valueFieldOffset);
// ensureCapacity(chars.length * 3)
byte[] bytes = ...; // 
int bytesLength = IOUtils.encodeUTF8(chars, 0, chars.length, bytes, bytesOffset);

這樣encodeUTF8操作，不會有多餘的arrayCopy操作，效能會得到提升。

6.1.1 效能測試比較

測試程式碼

public class EncodeUTF8Benchmark {
    static String STR = "01234567890ABCDEFGHIJKLMNOPQRSTUVWZYZabcdefghijklmnopqrstuvwzyz一二三四五六七八九十";
    static byte[] out;

    static long valueFieldOffset;

    static {
        out = new byte[STR.length() * 3];
        try {
            Field valueField = String.class.getDeclaredField("value");
            valueFieldOffset = UnsafeUtils.UNSAFE.objectFieldOffset(valueField);
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
        }
    }

    @Benchmark
    public void unsafeEncodeUTF8() throws Exception {
        char[] chars = (char[]) UnsafeUtils.UNSAFE.getObject(STR, valueFieldOffset);
        int len = IOUtils.encodeUTF8(chars, 0, chars.length, out, 0);
    }

    @Benchmark
    public void getBytesUTF8() throws Exception {
        byte[] bytes = STR.getBytes(StandardCharsets.UTF_8);
        System.arraycopy(bytes, 0, out, 0, bytes.length);
    }

    public static void main(String[] args) throws RunnerException {
        Options options = new OptionsBuilder()
                .include(EncodeUTF8Benchmark.class.getName())
                .mode(Mode.Throughput)
                .timeUnit(TimeUnit.MILLISECONDS)
                .forks(1)
                .build();
        new Runner(options).run();
    }
}

測試結果

EncodeUTF8Benchmark.getBytesUTF8 thrpt 5 20690.960 ± 5431.442 ops/ms
EncodeUTF8Benchmark.unsafeEncodeUTF8 thrpt 5 34508.606 ± 55.510 ops/ms

從結果來看，通過unsafe + 直接呼叫encodeUTF8方法，編碼的所需要開銷是newStringUTF8的58%。

6.2 JDK9/11/17高效能encodeUTF8的方法

public static int encodeUTF8(byte[] src, int offset, int len, byte[] dst, int dp) {
    int sl = offset + len;
    while (offset < sl) {
        byte b0 = src[offset++];
        byte b1 = src[offset++];

        if (b1 == 0 && b0 >= 0) {
            dst[dp++] = b0;
        } else {
            char c = (char)(((b0 & 0xff) << 0) | ((b1 & 0xff) << 8));
            if (c < 0x800) {
                // 2 bytes, 11 bits
                dst[dp++] = (byte) (0xc0 | (c >> 6));
                dst[dp++] = (byte) (0x80 | (c & 0x3f));
            } else if (c >= 'uD800' && c < ('uDFFF' + 1)) { //Character.isSurrogate(c) but 1.7
                final int uc;
                int ip = offset - 1;
                if (c >= 'uD800' && c < ('uDBFF' + 1)) { // Character.isHighSurrogate(c)
                    if (sl - ip < 2) {
                        uc = -1;
                    } else {
                        b0 = src[ip + 1];
                        b1 = src[ip + 2];
                        char d = (char) (((b0 & 0xff) << 0) | ((b1 & 0xff) << 8));
                        // d >= 'uDC00' && d < ('uDFFF' + 1)
                        if (d >= 'uDC00' && d < ('uDFFF' + 1)) { // Character.isLowSurrogate(d)
                            uc = ((c << 10) + d) + (0x010000 - ('uD800' << 10) - 'uDC00'); // Character.toCodePoint(c, d)
                        } else {
                            return -1;
                        }
                    }
                } else {
                    //
                    if (c >= 'uDC00' && c < ('uDFFF' + 1)) { // Character.isLowSurrogate(c)
                        return -1;
                    } else {
                        uc = c;
                    }
                }

                if (uc < 0) {
                    dst[dp++] = (byte) '?';
                } else {
                    dst[dp++] = (byte) (0xf0 | ((uc >> 18)));
                    dst[dp++] = (byte) (0x80 | ((uc >> 12) & 0x3f));
                    dst[dp++] = (byte) (0x80 | ((uc >> 6) & 0x3f));
                    dst[dp++] = (byte) (0x80 | (uc & 0x3f));
                    offset++; // 2 chars
                }
            } else {
                // 3 bytes, 16 bits
                dst[dp++] = (byte) (0xe0 | ((c >> 12)));
                dst[dp++] = (byte) (0x80 | ((c >> 6) & 0x3f));
                dst[dp++] = (byte) (0x80 | (c & 0x3f));
            }
        }
    }
    return dp;
}

使用encodeUTF8方法舉例

byte coder = UNSAFE.getObject(str, coderFieldOffset);
byte[] value = UNSAFE.getObject(str, coderFieldOffset);

if (coder == 0) {
    // ascii arraycopy
} else {
    // ensureCapacity(chars.length * 3)
    byte[] bytes = ...; // 
    int bytesLength = IOUtils.encodeUTF8(value, 0, value.length, bytes, bytesOffset);
}

這樣encodeUTF8操作，不會有多餘的arrayCopy操作，效能會得到提升。