Interesting Links – 2017/Jun/12

Interesting Links – 2017/Jun/5

Interesting Links – 2017/May/25

  • How Fonts are Fueling the Culture Wars is an article talking about, well, font usage and what specific fonts mean, which has only a tangential relation to Java — but think about it in terms of user experience, too. Do you think the user experience of Java communicates a specific mode of thought? If so, what would it be? (And no, “Duhhhh” is not a valid answer!)
  • From DZone: The Soon-to-Be-Hated Object Locator presents a pattern for a type of God Object, except possibly restricted in scope enough to not earn the full derision that a God Object deserves… maybe.
  • Also from DZone: The Genius of the Law of Demeter, an article with far less controversy than a God Object would create. The short form of the Law of Demeter says that you call methods on objects that your class owns directly: this.getFoo().bar() is okay, but this.getFoo().getBar().baz() is not (and, as usual, there’s more to it than this.)
  • Stack Overflow: Helping One Million Developers Exit Vim documents the usage patterns for questions that … help developers exit vim. Vim isn’t especially common for Java developers (although it happens) – but still! What a great editor! How user-friendly does an editor have to be that one in 20000 visits to Stack Overflow is specifically about how to exit the editor? (And now I wonder how many visits are about exiting Emacs, too…)
  • Java 9 expert group minutes: http://openjdk.java.net/projects/jigsaw/spec/minutes/2017-05-18 – it’s good to keep up on the current status, because the implications of every choice made are pretty serious. The second set of minutes are also available.
  • vJUG24 is back! (… I didn’t know what this was until someone sent it to me.)

Interesting Links – 22/May/2017

  • Github gets an App Store.
  • Jenetics is an advanced Genetic Algorithm, respectively an Evolutionary Algorithm, library written in modern day Java.
  • Need to run things before or after your unit test executes? Don’t forget the lifecycle annotations, for TestNG and JUnit.

Interesting Links – 8/May/2017

DropWizard Metrics Advice

I was working on an application with DropWizard, and I was having trouble getting my own metrics to show up in the display. The Metrics Getting Started is useful, and it actually showed me what I needed, but didn’t make it obvious enough for me.
What I needed was, in DropWizard Metrics parlance, a “meter.” This gives me performance data over time; basically, every time an event happens, I’d mark it and thus be able to see how busy the system was in the last minute, the last five minutes, and the last 15 minutes.
I followed the Metrics Getting Started:

  • I got a MetricsRegistry (by using new MetricsRegistry())
  • I created a Meter by calling register.meter(name) if necessary (and stored the Meter in a map so I could retrieve it again at will)
  • I marked an event by calling Meter.mark()

But at no point was I able to see the meter displayed in the DropWizard servlet.
The reason is because I created my own MetricsRegistry. One right way to do it is documented; it’s to use SharedMetricRegistries.getDefault(); instead (which gets you a MetricsRegistry that is displayed automatically).
Note that the DropWizard documentation is not wrong – it just steps past something that most people probably want by default.

Interesting Links – 2017/May/1

If you have a teammate who suffers from mental illness, I’d encourage you to champion (heart and balance) within your team. Be an ally. Help create a safe and inclusive space. Not only because it’s the right thing to do, but because being around people different from you broadens your horizons and builds empathy. And empathy for others makes you better at just about every job.

Interesting Links – 2017/Apr/26

Yes, it’s been a while, I’ve been busy and I’m the only curator of this content:

… and just because I have a weird sense of humor:

randomUser> This code would run really well if it didn't keep waiting for the PRNG to determine the sign of a random number.

LinkedList vs. ArrayList

Recently, The Java Programmer published “Difference between ArrayList and LinkedList in Java“, asserting different cases of when to prefer one List implementation over another. It’s a link full of conventional wisdom, and while it has some good information, it’s also wrong.
Here’s the channel’s factoid on LinkedList, as of 2017/Apr/25 (prior to it having been changed to point to the page you’re reading):

LinkedList is almost always slower than ArrayList/ArrayDeque. It might be best to use ArrayList/ArrayDeque to start. But if you have an actual performance problem, you can compare the two for your specific case. Otherwise, just use ArrayDeque. (It too has O(1) performance for insert-at-beginning, and unlike LinkedList is actually fast).

Implementation

The “Difference” page says that ArrayList uses an internal array to represent stored objects, while a LinkedList uses a doubly-linked list internally. In this, it’s correct.

Searching

The next point of comparison is entitled “Searching.” Here’s what it says about ArrayList:

An elements can be retrieved or accessed in O(1) time. ArrayList is faster because it uses array data structure and hence index based system is used to access elements.

And about LinkedList:

An element can be accessed in O(N) time. LinkedList is slower because it uses doubly linked list and for accessing an element it iterates from start or end (whichever is closer).

First off, in the interest of honesty, the last bit of information – that it iterates from either forward or backward, depending on which is closer – was a surprise to me (although it’s perfectly logical.) It’s also accurate.
However, this isn’t searching – it’s element access. Access and searching are different things; it’s get(42) vs. list.contains(matchingObject). This is important; contains() will have O(N) time for either List implementation, whereas ArrayList will have O(1) for get(), and LinkedList will have O(N) for get().
The thing is: LinkedList is not only O(N) for get() but the nature of the internal implementation makes it slower than one might think, because of cache locality. In an ArrayList, the element references are stored sequentially in memory; a LinkedList potentially splatters the references all over the heap. (This is not entirely likely, but it’s possible.) Thus, a LinkedList not only has O(N) performance for indexed access (where the ArrayList has O(1)), but the O(N) is worse than one might expect.
For accessing elements, there’s no situation apart from accessing the first or last element where a LinkedList competes with an ArrayList‘s speed.

Note that programming hates absolutes. It’s fully possible to create situations in which that last claim is not entirely true… but they’re rare and unlikely.

Insertion

About ArrayList:

Normally the insertion time is O(1). But in case array is full then array is resized by copying elements to new array, which makes insertion time O(N).

And about LinkedList:

Insertion of an element in LinkedList is faster, it takes O(1) time.

Incomplete data is provided here. For one thing, the author conflates mutation with “insertion.” There are two different kinds of additive list mutations (where data is added to a List): insertion (meaning that elements are prepended to other elements) and addition (where an element “follows” the last element in the list prior to mutation.)
Where the elements go as part of the additive mutation is really important, and it’s also important to note that the claim of LinkedList‘s O(1) time is very much a single type of insertion.
For an ArrayList, a list append (i.e., calling add(), which adds the provided element at the end of the list) has O(N) performance, but typically has O(1) performance. The O(N) complexity is because the internal array size might be exceeded by the addition of the element, in which case a new internal array is allocated, and the array references are copied over to the new internal array, and then the new element is appended. Thus, in the worst case, it is O(N), but this is misleading because:

  1. It’s fairly rare (the list resizes with a formula of currentSize*1.5 (the actual line is int newCapacity = oldCapacity + (oldCapacity >> 1);, if you’re interested.)
  2. Java’s blits are very, very, very fast; Java uses the blit mechanism constantly, and let’s be real, modern CPUs are really good at this anyway.

So is it actually O(N), then? … given what conventional Big O notation means, yes, it is; it’s just that O(N) is a lot less expensive than one might think in this case. And typically, the add() will be O(1) in actuality.
But what about LinkedList?
Insertion at the beginning or the end of the list is, in fact, O(1). This is even the common case (add(Object) calls linkLast(Object) by default.) However, if positional notation is used at all (i.e., add(int, Object) you degrade to O(N), because the LinkedList has to find the position at which the new element has to be inserted – and finding that position is O(N).
So what’s the conclusion? ArrayList does in fact have O(N) performance for adds, but it’s close enough to O(1) in real world conditions that we can colloquially speak of it being likely as fast as LinkedList‘s similar case… and if we add any kind of positional insertion, ArrayList‘s degradation under the worst case is far better than LinkedList‘s degradation.
As usual, we can create situations under which this is not the case (for example, if we always insert after the first position in a LinkedList, which will “search” one element and only that element) but these are fairly rare.

Deletion

Let’s see about ArrayList:

Deletion of an element is slower as all the elements have to be shifted to fill the space created by deleted element.

And LinkedList:

Deletion of an element is faster in LinkedList because no elements shifting are required.

Well, um, no.
Here, the author is confusing complexity – big O notation – with speed, for ArrayList. (He or she is wrong about LinkedList in any event.)
For an ArrayList, deleting an element by index is indeed O(N) because the JVM does have to blit the elements after the removed element (it has to shift them all in the internal array.)
However, for a LinkedList, it also has to find the elements around the element to remove – and if you recall, accessing a specific element for a LinkedList is an O(N) complexity itself. Even though the removal is simple (it’s simply relinking the nodes before and after the removed element), actually finding those nodes is O(N), thus deletion is O(N) for LinkedList – and slower than ArrayList, to boot.

Memory and Initial Capacity

The author says that an ArrayList has a default internal capacity of 10. This is incorrect for Java 8. See this code.
For the rest of it, the author is correct; a LinkedList is “empty” (there are no linked nodes internally); an ArrayList has capacity references in the internal list, while a LinkedList has a chain of objects, which will have higher memory consumption, but that’s not likely to matter unless your lists are huge.

The Comparison’s Conclusion

  • As search or get operation is faster in ArrayList so it is used in the scenario where more search or get operations are required.
  • As insertion or deletion of an element is faster in LinkedList so it is used in the scenario where more insertion and deletion operations are required.

The thing that the conclusion is missing is that “insertion and deletion” operations in LinkedList typically involve searches and gets – which are terrible for LinkedList – and therefore for even the operations that LinkedList is potentially better, ArrayList will typically perform better.
The factoid stands. If you need a List, use ArrayList first, then ArrayDeque if your access patterns demand… use LinkedList only after exhausting other possibilities.

Interesting Links, 2017-Feb-23