• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

ArrayList vs LinkedList?

 
Ranch Hand
Posts: 290
Debian Fedora Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:If you have any idea how many references you wish to keep in your List, you can use the ensureCapacity(int) method to speed things up. You will find that method in ArrayList and Vector, but not in LinkedList because it is unnecessary there.


But it's hard to know that , if you don't utilize the capacity it would result in waste of resouce , even though the capacity get's increased by 50 percent for Vector twice.
 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Arun Giridharan wrote:

Campbell Ritchie wrote:If you have any idea how many references you wish to keep in your List, you can use the ensureCapacity(int) method to speed things up. You will find that method in ArrayList and Vector, but not in LinkedList because it is unnecessary there.


But it's hard to know that , if you don't utilize the capacity it would result in waste of resouce



Not necessarily a problem. If you have even a rough upper bound, that may be enough. For instance, suppose you know it will be no more than 20M elements, so you use ArrayList's constructor or ensureSize() to give it 20M elements all at once. Say you only end up with 1M elements. That's 19M elements * 4 bytes = 78M bytes wasted. That's not really that much even on a modest PC, and that's for an extreme overestimation. Estimating 10M and using 6M leaves only 16M bytes wasted.

Additionally, ArrayList has trimToSize(), which can be used after we're done filling it to get rid of wasted memory.
 
Arun Giridharan
Ranch Hand
Posts: 290
Debian Fedora Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:
Additionally, ArrayList has trimToSize(), which can be used after we're done filling it to get rid of wasted memory.


yep !! good point (now why did i forget that ! )
 
Sheriff
Posts: 3837
66
Netbeans IDE Oracle Firefox Browser
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:Not necessarily a problem. If you have even a rough upper bound, that may be enough. For instance, suppose you know it will be no more than 20M elements, so you use ArrayList's constructor or ensureSize() to give it 20M elements all at once. Say you only end up with 1M elements. That's 19M elements * 4 bytes = 78M bytes wasted. That's not really that much even on a modest PC, and that's for an extreme overestimation. Estimating 10M and using 6M leaves only 16M bytes wasted.

Additionally, ArrayList has trimToSize(), which can be used after we're done filling it to get rid of wasted memory.


More important is the relative size of the overestimate. 20 times more from your example seems much, but setting the initial capacity at an innocent thousand (just 4 KB!) and filling up on average just ten items will give you an overhead of 100 times! Allocate a few hundred lists like this and a problem is here. Additionally, ArrayList increases the capacity by 50% when reallocating, in the long run the sum of all allocations will be approaching 3 times the target capacity. Depending on circumstances, that might be more friendly to the GC than overallocating 20 times and trimming to size. And while overallocationg an ArrayList does not have negative impacts except the memory overhead, overallocating a HashSet in a similar manner will make iterating it much slower. Though this is clearly stated in the javadoc, it is easy to forget about it once you get into the initial capacity refurbishing spree...

I had started putting initial capacities everywhere because NetBeans were warning me on every occasion where it was not done. I've stopped completely after I've made a few measurements and found no significant difference (on lists sized from hundreds to thousand elements at most), especially in the context of the whole application. The most frustrating task when providing the initial capacities was to keep the guesses accurate even as related code (and especially database data) changes. Not worth the effort in my opinion. Sure, a few cases where the initial capacity has to be specified certainly do exist, but to provide it in all circumstances is a case of a premature optimization, in my opinion.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Martin Vajsar wrote:

Jeff Verdegan wrote:Not necessarily a problem. If you have even a rough upper bound, that may be enough. For instance, suppose you know it will be no more than 20M elements, so you use ArrayList's constructor or ensureSize() to give it 20M elements all at once. Say you only end up with 1M elements. That's 19M elements * 4 bytes = 78M bytes wasted. That's not really that much even on a modest PC, and that's for an extreme overestimation. Estimating 10M and using 6M leaves only 16M bytes wasted.

Additionally, ArrayList has trimToSize(), which can be used after we're done filling it to get rid of wasted memory.


More important is the relative size of the overestimate.



I wouldn't say that's more important by itself. Certainly it's a combination of that and how big your cumulative initial size is, as your following comments illustrate...

20 times more from your example seems much, but setting the initial capacity at an innocent thousand (just 4 KB!) and filling up on average just ten items will give you an overhead of 100 times! Allocate a few hundred lists like this and a problem is here. Additionally, ArrayList increases the capacity by 50% when reallocating, in the long run the sum of all allocations will be approaching 3 times the target capacity. Depending on circumstances, that might be more friendly to the GC than overallocating 20 times and trimming to size. And while overallocationg an ArrayList does not have negative impacts except the memory overhead, overallocating a HashSet in a similar manner will make iterating it much slower. Though this is clearly stated in the javadoc, it is easy to forget about it once you get into the initial capacity refurbishing spree...

I had started putting initial capacities everywhere because NetBeans were warning me on every occasion where it was not done. I've stopped completely after I've made a few measurements and found no significant difference (on lists sized from hundreds to thousand elements at most), especially in the context of the whole application. The most frustrating task when providing the initial capacities was to keep the guesses accurate even as related code (and especially database data) changes. Not worth the effort in my opinion. Sure, a few cases where the initial capacity has to be specified certainly do exist, but to provide it in all circumstances is a case of a premature optimization, in my opinion.



Right. I'm definitely not advocating blindly pre-allocating huge amounts as a matter of course. Just pointing out that it's not necessarily a problem, and illustrating with a fairly extreme example. As with any optimization, you have to take a holistic view, and use good judgment about when to apply it and what parameters to use.

About the only time I use the c'tor that takes an initial size is when I know exactly how many I'll need, such as when copying from another collection. Since the resizing uses an exponential function, it usually doesn't take too many resizings to get to the necessary capacity, so there's not a lot of CPU wasted on it.
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic