4 ms·

Did you count an allocation of LinkedList.Node<E> on every add operation? You may say it's negligible thanks to TLAB, and I will agree that fast allocation is J

Did you count an allocation of LinkedList.Node<E> on every add operation? You may say it's negligible thanks to TLAB, and I will agree that fast allocation is Java's strength, but in practice I've seen that creating new objects gives order-of-magnitude perf degradation.

SillyUsername 1y ago
I have seen it for millions of add/del operations, an analytics framework actually for a big American games company (first guess and you'll probably say it), which is where I originally did the analysis about 10 years ago. I've also written a a video processor around that time too that was bottle necked using ArrayLists - typically a decode, store and read once op. It was at this point I looked at other collections, other list implementations and blocking deques (ArrayList was the wrong collection type to use, but I'd been in a rush for MVP) and ultimately came across https://github.com/conversant/disruptor https://github.com/conversant/disruptor and used that instead. The ArrayList Vs Linkedlist was a real eye opener for me in two different systems this same behaviour was replicated when using ArrayLists like queues or incorrect sizing of the buffer increments as load increases.
- stopthe 1y ago
  Of course, deletion is a whole different story. I was talking about addition in isolation. Anyway, I felt I had to run the benchmarks myself. @Benchmark @Fork(1) @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.SECONDS) public Object arrayListPreallocAddMillionNulls() { ArrayList<Object> arrList = new ArrayList<>(1048576); for (int i = 0; i <= 1_000_000; i++) { arrList.add(null); } return arrList; } @Benchmark @Fork(1) @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.SECONDS) public Object arrayListAddMillionNulls() { ArrayList<Object> arrList = new ArrayList<>(); for (int i = 0; i <= 1_000_000; i++) { arrList.add(null); } return arrList; } @Benchmark @Fork(1) @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.SECONDS) public Object linkedListAddMillionNulls() { LinkedList<Object> linkList = new LinkedList<>(); for (int i = 0; i <= 1_000_000; i++) { linkList.add(null); } return linkList; } And as I expected, on JDK 8 ArrayList with an appropriate initial capacity was faster than LinkedList. Admittedly not an order of magnitude difference, only 1.7x. JDK8 Benchmark Mode Cnt Score Error Units MyBenchmark.arrayListAddMillionNulls thrpt 5 229.950 ± 9.994 ops/s MyBenchmark.arrayListPreallocAddMillionNulls thrpt 5 344.116 ± 7.070 ops/s MyBenchmark.linkedListAddMillionNulls thrpt 5 199.446 ± 15.910 ops/s But! On JDK 17 the situation is completely upside-down: JDK17 Benchmark Mode Cnt Score Error Units MyBenchmark.arrayListAddMillionNulls thrpt 5 90.462 ± 18.576 ops/s MyBenchmark.arrayListPreallocAddMillionNulls thrpt 5 214.079 ± 15.505 ops/s MyBenchmark.linkedListAddMillionNulls thrpt 5 216.796 ± 19.392 ops/s I wonder why ArrayList with default initial capacity got so much worse. Worth investigating further.
  - SillyUsername 1y ago
    Thanks for taking the time to test. This helps prove my point that adds (and deletes) are generally faster by default when not pre sizing, or removing. Typically (in my experience) ArrayLists are used without thought to sizing, often because initial capacity and amount to resize, cannot be determined sensibly or consistently. If in your example you were also to resize the lists, (perhaps adding then dropping those in the Fibonacci sequence?), it would help prove my statement further. Certainly not worth the -2 points I got from making the statement, but hey you can "please some people some of the time..." :D

SillyUsername 1y ago

I have seen it for millions of add/del operations, an analytics framework actually for a big American games company (first guess and you'll probably say it), which is where I originally did the analysis about 10 years ago. I've also written a a video processor around that time too that was bottle necked using ArrayLists - typically a decode, store and read once op. It was at this point I looked at other collections, other list implementations and blocking deques (ArrayList was the wrong collection type to use, but I'd been in a rush for MVP) and ultimately came across https://github.com/conversant/disruptor https://github.com/conversant/disruptor and used that instead. The ArrayList Vs Linkedlist was a real eye opener for me in two different systems this same behaviour was replicated when using ArrayLists like queues or incorrect sizing of the buffer increments as load increases.

stopthe 1y ago
Of course, deletion is a whole different story. I was talking about addition in isolation. Anyway, I felt I had to run the benchmarks myself. @Benchmark @Fork(1) @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.SECONDS) public Object arrayListPreallocAddMillionNulls() { ArrayList<Object> arrList = new ArrayList<>(1048576); for (int i = 0; i <= 1_000_000; i++) { arrList.add(null); } return arrList; } @Benchmark @Fork(1) @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.SECONDS) public Object arrayListAddMillionNulls() { ArrayList<Object> arrList = new ArrayList<>(); for (int i = 0; i <= 1_000_000; i++) { arrList.add(null); } return arrList; } @Benchmark @Fork(1) @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.SECONDS) public Object linkedListAddMillionNulls() { LinkedList<Object> linkList = new LinkedList<>(); for (int i = 0; i <= 1_000_000; i++) { linkList.add(null); } return linkList; } And as I expected, on JDK 8 ArrayList with an appropriate initial capacity was faster than LinkedList. Admittedly not an order of magnitude difference, only 1.7x. JDK8 Benchmark Mode Cnt Score Error Units MyBenchmark.arrayListAddMillionNulls thrpt 5 229.950 ± 9.994 ops/s MyBenchmark.arrayListPreallocAddMillionNulls thrpt 5 344.116 ± 7.070 ops/s MyBenchmark.linkedListAddMillionNulls thrpt 5 199.446 ± 15.910 ops/s But! On JDK 17 the situation is completely upside-down: JDK17 Benchmark Mode Cnt Score Error Units MyBenchmark.arrayListAddMillionNulls thrpt 5 90.462 ± 18.576 ops/s MyBenchmark.arrayListPreallocAddMillionNulls thrpt 5 214.079 ± 15.505 ops/s MyBenchmark.linkedListAddMillionNulls thrpt 5 216.796 ± 19.392 ops/s I wonder why ArrayList with default initial capacity got so much worse. Worth investigating further.
- SillyUsername 1y ago
  Thanks for taking the time to test. This helps prove my point that adds (and deletes) are generally faster by default when not pre sizing, or removing. Typically (in my experience) ArrayLists are used without thought to sizing, often because initial capacity and amount to resize, cannot be determined sensibly or consistently. If in your example you were also to resize the lists, (perhaps adding then dropping those in the Fibonacci sequence?), it would help prove my statement further. Certainly not worth the -2 points I got from making the statement, but hey you can "please some people some of the time..." :D