基本功：ConcurrentArrayList

男娘i 2022-02-05 07:27 217阅读 0赞

很多时候，如何保障你的代码高并发高性能，这的确是个很耐人寻味的话题。高性能意味着你要对采用的每一个容器、集合（数据结构）要非常讲究，而它往往是很多人不太注意的地方，这也行就是你不能专家级的一方面原因！so，基本功很重要，尽可能的接触底层实现。在java圈中，ArrayList 是非线程安全的，难道在多线程场景下我们只有Vector这一种线程安全的数组实现可以选择么？

> 当然也有List synchronizedList = Collections.synchronizedList(new ArrayList());但是当你不可避免使用contains() 进行搜索的时，它不可避免会锁住整个list，太恐怖了。

> Queue 和Deque (基于Linked List)有并发的实现是因为他们的接口相比List的接口有更多的限制，这些限制使得实现并发成为可能。

> CopyOnWriteArrayList它规避了只读操作（如get/contains）并发的瓶颈，但是它为了做到这点，在修改操作中做了很多工作和修改可见性规则。 此外，修改操作还会锁住整个List，因此这也是一个并发瓶颈。所以从理论上来说，CopyOnWriteArrayList并不算是一个通用的并发List。

总之，数组ArrayList 虽然insert和get是最快的，但是非线程安全的，CopyOnWriteArrayList虽安全，但insert速度慢

**如何优化呢？**

其实也不复杂，只需做的这2点

*  要继续发挥数组ArrayList 的优点
 *  要去掉锁采用高性能的CAS

**1. 高性能Unsafe**

[Unsafe 这一part][Unsafe _part]其实之前就讲过的，直接看下面代码

public class UnsafeUtils {
        final static private Unsafe _unsafe;
        static {
            Unsafe tmpUnsafe = null;
    
            try {
                java.lang.reflect.Field field = sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
                field.setAccessible(true);
                tmpUnsafe = (sun.misc.Unsafe) field.get(null);
            } catch (java.lang.Exception e) {
                throw new Error(e);
            }
    
            _unsafe = tmpUnsafe;
        }
        public static final Unsafe unsafe() {
            return _unsafe;
        }
    }
    public class Unsafe_test {
        @Test
        public void test() {
            Unsafe u = UnsafeUtils.unsafe();
            int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            //返回当前数组第一个元素地址(数组起始地址的偏移值)，返回6
            int b = u.arrayBaseOffset(int[].class);
            //返回当前数组一个元素占用的字节数s，返回4
            int s = u.arrayIndexScale(int[].class);
            int pos=9;
            //获取数组对象某个位置偏移值（b + s * pos)，将intval写入内存
            u.putInt(arr, (long) b + s * pos, 1);
            for (int i = 0; i < 10; i++) {
                //获取数组对象某个位置上偏移值，从而获得元素的值
                int v = u.getInt(arr, (long) b + s * i);
                System.out.print(v + " ");//1 2 3 4 5 6 7 8 9 1
            }
        }
    }

**2. 保持数组ArrayList的优点**

/**
     * 仅支持get/set，不支持remove
     */
    public class ConcurrentArrayList<T> implements RandomAccess {
        public static final int MAX_CAPACITY = 1 << 30;
        private static final long SIZE_OFFSET;
        private static final int ABASE;
        private static final int ASHIFT;
        private volatile Object[] values;
        //unsafe operate
        private volatile int size;
        static {
            try {
                Field field = ConcurrentArrayList.class.getDeclaredField("size");
                SIZE_OFFSET = UnsafeUtils.unsafe().objectFieldOffset(field);
                ABASE = UnsafeUtils.unsafe().arrayBaseOffset(Object[].class);
                int scale = UnsafeUtils.unsafe().arrayIndexScale(Object[].class);
                if ((scale & (scale - 1)) != 0) {
                    throw new Error("array index scale not a power of two");
                }          
                ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
            } catch (Throwable e) {
                throw new Error(e);
            }
        }
        public T get(int index) {
            return (T) UnsafeUtils.unsafe().getObjectVolatile(values, offset(ABASE, ASHIFT, index));
        }
    
        public void add(T value) {
            int index = insertIndex();
            set(index, value);
        }
    
        private int insertIndex() {
            int index = UnsafeUtils.unsafe().getAndAddInt(this, SIZE_OFFSET, 1);
            ensureCapacity(index + 1);
            return index;
        }
    
        public void set(int index, T value) {
            final long offset = offset(ABASE, ASHIFT, index);
            for (; ; ) {// like cas
                final Object[] before = values;
                UnsafeUtils.unsafe().putOrderedObject(before, offset, value);
                final Object[] after = values;
    
                if (before == after) {
                    return;
                }
            }
        }
    
        public ConcurrentArrayList() {
            this(16);
        }
    
        public ConcurrentArrayList(int initialCapacity) {
            if (initialCapacity > MAX_CAPACITY) {
                throw new IndexOutOfBoundsException("Illegal initial capacity: " + initialCapacity);
            }
            ensureCapacity(initialCapacity);
        }
    
        private void ensureCapacity(int capacity) {
            Object[] theArray = values;
            if (theArray != null && theArray.length >= capacity) {
                return;
            }
            synchronized (this) {
                Object[] finalArray = values;
                if (finalArray != null && finalArray.length >= capacity) {
                    return;
                }
                int newCapacity = tableSizeFor(capacity);
                if (newCapacity > MAX_CAPACITY) {
                    throw new IndexOutOfBoundsException("" + newCapacity);
                }
    
                Object[] objs = new Object[newCapacity];
    
                if (finalArray != null) {
                    System.arraycopy(finalArray, 0, objs, 0, finalArray.length);
                }
                values = objs;
            }
        }
    
        /**
         * 成倍扩容
         *
         * @param cap
         * @return
         */
        public int tableSizeFor(final int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAX_CAPACITY) ? MAX_CAPACITY : n + 1;
        }
        /**
         * 获取某个元素的offset
         *
         * @param arrayBase
         * @param arrayShift
         * @param index
         * @return
         */
        public long offset(final long arrayBase, final int arrayShift, final int index) {
            return ((long) index << arrayShift) + arrayBase;
        }
    
        public int size() {
            return size;
        }
        public void clear() {
            size = 0;
        }
    }

**基本的测试**

> **synchronizedList:157.6 ms  
> arrayList:60.30 ms  
> vector:164.9 ms  
> concurrentArrayList:86.83 ms  
> copyOnWriteArrayList:慢到无法统计**

public class ConcurrentArrayList_unit {
        private static final ArrayList<Boolean> arrayList = new ArrayList<>();
        private static final Vector<Boolean> vector = new Vector<>();
        private List synchronizedList = Collections.synchronizedList(new ArrayList());
        private static final CopyOnWriteArrayList<Boolean> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
        private static final ConcurrentArrayList<Boolean> concurrentArrayList = new ConcurrentArrayList<>();
        private int maxConcurrent = 200;
        private int maxSet = 8000;
        private int maxGet = 8000;
    
        @Test
        public void arrayList() throws InterruptedException {
            Consumer arrayListConsumer = x -> {
                for (int i = 0; i < maxSet; i++) {
                    arrayList.add(Boolean.TRUE);
                }
                for (int j = 0; j < maxGet; j++) {
                    arrayList.get(j);
                }
            };
            runTimes(maxConcurrent, "arrayList", arrayListConsumer);
        }
    
        @Test
        public void concurrentArrayList() throws InterruptedException {
            Consumer concurrentArrayListConsumer = x -> {
                for (int i = 0; i < maxSet; i++) {
                    concurrentArrayList.add(Boolean.TRUE);
                }
                for (int j = 0; j < maxGet; j++) {
                    concurrentArrayList.get(j);
                }
            };
            runTimes(maxConcurrent, "concurrentArrayList", concurrentArrayListConsumer);
        }
    
        @Test
        public void vector() throws InterruptedException {
            Consumer vectorConsumer = x -> {
                for (int i = 0; i < maxSet; i++) {
                    vector.add(Boolean.TRUE);
                }
                for (int j = 0; j < maxGet; j++) {
                    vector.get(j);
                }
            };
            runTimes(maxConcurrent, "vector", vectorConsumer);
        }
    
        @Test
        public void synchronizedList() throws InterruptedException {
            Consumer synchronizedListConsumer = x -> {
                for (int i = 0; i < maxSet; i++) {
                    synchronizedList.add(Boolean.TRUE);
                }
                for (int j = 0; j < maxGet; j++) {
                    synchronizedList.get(j);
                }
            };
            runTimes(maxConcurrent, "synchronizedList", synchronizedListConsumer);
        }
    
        @Test
        public void copyOnWriteArrayList() throws InterruptedException {
            Consumer copyOnWriteArrayListConsumer = x -> {
                for (int i = 0; i < maxSet; i++) {
                    copyOnWriteArrayList.add(Boolean.TRUE);
                }
                for (int j = 0; j < maxGet; j++) {
                    copyOnWriteArrayList.get(j);
                }
            };
            runTimes(maxConcurrent, "copyOnWriteArrayList", copyOnWriteArrayListConsumer);
        }
    
    
        private void runTimes(int maxConcurrent, String tag, Consumer consumer) throws InterruptedException {
            Stopwatch stopwatch = Stopwatch.createStarted();
            CountDownLatch latch = new CountDownLatch(maxConcurrent);
            for (int i = 0; i < maxConcurrent; i++) {
                new Thread(() -> {
                    consumer.accept(null);
                    latch.countDown();
                }).start();
            }
            latch.await();
            System.out.println(tag + ":" + stopwatch);
        }
    }

充分利用cpu高性能位运算的，Integer.numberOfLeadingZeros()返回0位的个数，基准选定的分别是2的1、2、3、4次幂

如：2818048，对应二进制（补码）：00000000  00101011  00000000  00000000，会返回10。![88960059][]

[Unsafe _part]: https://blog.csdn.net/alex_xfboy/article/details/85101402
[88960059]: /images/20220205/250969b224b446d9b192e9ce906a82df.png