Java Performance Puzzlers by Douglas Hawkins

[@nO_d3N1AL]

Performance talks like this rarely disappoint. Some might call it trivia, but it's nice to understand what's going on behind the scenes, especially when optimising performance.

[@StefanReich]

Yeah it was a great talk. Even Java oldtimers like me learned a few things here

[@chinmayachowdary]

Wow! Excellent.

[@heinzkabutz]

By default Vector doubles the number of elements when you run out of space. We can override that behaviour by constructing it with a capacityIncrement, but hardly anyone ever does that.

[@AndrewKay]

At 37:10, the claim about O(n log n) is wrong - exponential resizing really does take only O(n) operations to build a collection of n items. If the scale factor is 2, for example, then the total number of copies is up to n + n/2 + n/4 + ... + 2 + 1. This is a geometric sequence with a sum of 2n - 1, which is O(n). The same is true for any other scale factor.

[@NovaCyn]

He's talking about vector. vector as he said a few seconds before does NOT scale exponentially (with a factor) What you say is true of all the OTHER collections

[@jonaskoelker]

> exponential resizing really does take only O(n) [...] [n + n/2 + ... + 1 = an + b which is in O(n)] I'd like to restate this in plain terms. The speaker did say something right: there is a copy every log n iterations*. However: most of those copies are a lot smaller than the size of the final array. That's why it's O(n) and not O(n log n). (* approximately. If the starting size is 10 rather than 1, the first few copy operations can be skipped. So it's (log n) - (log 10) or something. Still O(log n) though.)

[@StefanReich]

@@NovaCyn My God it's true - it grows by 1 every time another element is added! So adding n elements takes O(n^2). That makes Vector pretty much unusable... but thankfully no one is using it anymore anyway

[@NovaCyn]

@@StefanReich You can actually set the growth size, so that's something. But yes that's still O(n^2) to add n elements

[@dhawaljoshi]

really interesting insights

[@SprockPls]

I love this guy, He's pretty funny XD

[@almazglaz]

toArray example with more details is explained here: shipilev.net/blog/2016/arrays-wisdom-ancients/