背景

java 的装箱、拆箱

自动装箱/拆箱大家应该都知道,这个一般而言不是什么大问题。

不过作为一个底层框架,有时候就需要稍微考虑一下这个问题。

优化1-全半角

原始写法

CharUtil.toHalfWidth(c);

具体

    public static char toHalfWidth(final char c) {
        char resultChar = c;
        // 全角空格
        if (resultChar == 12288) {
            resultChar = (char) 32;
        // 其他全角字符
        } else if (resultChar > 65280 && resultChar < 65375) {
            resultChar = (char) (resultChar - 65248);
        }

        return resultChar;
    }

优化思路

更少的局部变量赋值、更精确的范围判断、更扁平的分支结构。

public static char toHalfWidth(char original) {
        // 全角空格
        if (original == '\u3000') return ' ';
        // 其他可转换全角字符
        if (original >= '\uFF01' && original <= '\uFF5E') {
            return (char) (original - 0xFEE0);
        }
        // 其他字符保持不变
        return original;
    }

效果

10W 次,大概6ms->4ms

聊胜于无

优化2-char 的装箱、拆箱

java 基本类型的装箱+拆箱其实也是消耗性能的。

但是很多集合本身又不支持基本类型,比如 Map,而我们的 TrieTree 又是基于此实现的。

WordDataTree#getNowMap 方法

// 这里的 char 已经是统一格式化之后的,所以可以不用再次格式化。
char mappingChar = stringBuilder.charAt(index);

// 这里做一次重复词的处理
WordDataTreeNode currentMap = nowNode.getSubNode(mappingChar);

其中获取 node

public WordDataTreeNode getSubNode(final Character c) {
    if(subNodeMap == null) {
        return null;
    }

    return subNodeMap.get(c);
}

会导致不可避免的一次 char 和 Character 的转换。

修改范围:

1)所有的字符处理映射

2)trie map

实现

基于开源的 Char2CharOpenHashMapChar2ObjectOpenHashMap 替代掉 HashMap 即可。

其他都是接口级别兼容的。

效果

全是测试 3 次,5W 次

1) v0.29.1 基线

5843
5525
5894

2) 改造后

实际测试发现效果不好。

先回滚下 trie map 试一下。

发现效果还是一般

6225
6080
5373

开始效果并不好,猜测是 JIT 前期发力不够,char2char 的优势发挥不出来。

感觉这个方向意义不大。很奇怪,按理说应该性能很高才对。

改造方案2-自己实现

现状

目前先不动 trie,针对数字+英文的转换本身实现比较简单。

我们暂时不引用这个包,自己实现一个精简版本的。

char2charMap 实现

想达到 jdk 的性能还是很难的,这个主要在于简化+取巧。

package com.github.houbb.sensitive.word.collection;

/**
 * 原生无装箱、拆箱的实现
 *
 * @since 0.29.2
 * @author 老马啸西风
 */
public final class Char2CharMap {

    private static final char EMPTY_KEY = '\0'; // 特殊标记,表示空槽
    private static final float LOAD_FACTOR = 0.5f;

    private char[] keys;
    private char[] values;
    private int size;
    private int mask;   // capacity-1,用于快速取模
    private int maxSize;

    public Char2CharMap(int expectedSize) {
        int capacity = tableSizeFor((int) (expectedSize / LOAD_FACTOR) + 1);
        this.keys = new char[capacity];
        this.values = new char[capacity];
        this.mask = capacity - 1;
        this.maxSize = (int) (capacity * LOAD_FACTOR);
        this.size = 0;
    }

    /** 2 的幂次方容量 */
    private static int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 2) ? 2 : (n >= (1 << 30) ? (1 << 30) : n + 1);
    }

    private int hash(char k) {
        return (k * 0x9E3779B9) & mask; // 乘法哈希 + mask
    }

    /** 插入或覆盖 */
    public void put(char key, char value) {
        if (key == EMPTY_KEY) {
            throw new IllegalArgumentException("Key '\0' is reserved as EMPTY_KEY.");
        }
        int idx = hash(key);
        while (true) {
            if (keys[idx] == EMPTY_KEY) {
                keys[idx] = key;
                values[idx] = value;
                if (++size >= maxSize) {
                    resize();
                }
                return;
            } else if (keys[idx] == key) {
                values[idx] = value;
                return;
            }
            idx = (idx + 1) & mask;
        }
    }

    /** 查询,不存在时返回 defaultValue */
    public char get(char key, char defaultValue) {
        if (key == EMPTY_KEY) return defaultValue;
        int idx = hash(key);
        while (true) {
            char k = keys[idx];
            if (k == EMPTY_KEY) return defaultValue;
            if (k == key) return values[idx];
            idx = (idx + 1) & mask;
        }
    }

    public char get(char key) {
        char defaultVal = 0;
        return get(key, defaultVal);
    }

    private void resize() {
        int newCap = keys.length << 1;
        char[] oldKeys = keys;
        char[] oldVals = values;

        keys = new char[newCap];
        values = new char[newCap];
        mask = newCap - 1;
        maxSize = (int) (newCap * LOAD_FACTOR);
        size = 0;

        for (int i = 0; i < oldKeys.length; i++) {
            char k = oldKeys[i];
            if (k != EMPTY_KEY) {
                put(k, oldVals[i]);
            }
        }
    }

    public int size() {
        return size;
    }
}

性能对比

10w 次,原生 HashMap 7ms,c2c 4ms

聊胜于无。

小结

本次主要是一次尝试,对于底层的理解反而有一些助益。

实际上这种装箱、拆箱也会被 JVM 优化。