Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Why does Java's Collection.size() return an int? This limits the size of collections to just over 2 billion entries. With the rapidly increasing amounts of memory available to us, this seems a little short-sighted - no?

share|improve this question
1  
A lot of libraries (not just in Java) have this problem... –  Mysticial Sep 16 '11 at 1:06
15  
"I'm going to design this Thing. Let's see... I'll make it support a bazabegig items. Yeah. Oh, wait! Someday somebody might want to add a degahedricbazigadon items - I'll design it for that instead! But what if they want to add a beezelbubdoodlezigahedron items someday?" Where do you stop to actually have something you can use? And why wouldn't you consider 2 billion items in a Collection to be enough? If you have more items than that, is a Collection really the best way to store and use it? Is the item count really the limit, or the data itself? –  Ken White Sep 16 '11 at 1:14
5  
Is the number of items really the limit? Every collection I've ever needed (not Java) contained more than a single byte of data, so 2 billion * (multiple bytes per item) is the actual issue, not the fact that it returns an int. Two billion items in a Collection doesn't seem to be a limit, even if the individual item only consumed a small amount of memory. (And in the early '90s, 2 billion bytes of memory was huge - PCs then had RAM sizes in MB. I know - in '94 I got my first monster PC with 16MB RAM and a 1GB SCSI drive. The drive was $1000 used, and the RAM was too.) –  Ken White Sep 16 '11 at 1:26
1  
@Ken, when they designed Java did they assume that Moore's law would suddenly stop applying with regard to memory? Perhaps they assumed that nobody would be using Java 15 years later. In either case it would have been a short-sighted assumption. Furthermore, as I've mentioned elsewhere, nothing about the Collection interface assumes that the data the collection contains must be stored in RAM. –  sanity Sep 16 '11 at 1:30
2  
I don't actually know Java very well, but couldn't you just create a Collection of Collections? That would give you about two billion Collections of two billion items each. –  Kusalananda Sep 16 '11 at 8:43
show 7 more comments

migrated from stackoverflow.com Sep 16 '11 at 4:18

This question came from our site for professional and enthusiast programmers.

9 Answers

The vast majority of applications uses collection sizes much less than that. A generic class should be designed to cover the most common cases, not the most extreme ones. A specialized collection class for very large collections will probably be added at some point.

share|improve this answer
20  
I disagree. Collections with more than 2 billion elements will likely always be an extreme case. The vast majority of programming problems just don't involve more than 2 billion objects. –  David Schwartz Sep 16 '11 at 1:14
4  
@sanity You're aware about the large overhead of using longs instead of ints around 1994? When Java was developed 64bit were their least worry and this shows in several other decisions as well. Collection.size() returning long being basically the most uninteresting (look at how 8byte references in bytecode, now THAT'S awkward). If you worry about rare and elusive corner cases (and the fact that even 20years after development it's still an non-existant problem) your language may never get used enough for it to become a problem in the first case. Pragmatism is important. –  Voo Sep 16 '11 at 1:20
3  
It would not have been a zero-cost decision, but it would definitely have been a zero-benefit decision. In any event, the first implementation that can support more than 2 billion elements can also include 'lsize' or some such function that returns a long. –  David Schwartz Sep 16 '11 at 1:24
5  
for somebody long can become not enough too –  Dmitry Sep 16 '11 at 1:26
1  
@sanity I'm currently SSHed into a server with 4tb RAM (well it's a cluster but still), but I've yet to see a program that uses an algorithm where this has become a problem. So what algorithm are you using that uses only a single data structure that is so gigantic that this is a real problem? Seems bad for several reasons, not the least being contention. –  Voo Sep 16 '11 at 1:53
show 12 more comments

The javadoc for the Collection interface says this about size():

Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Therefore there isn't any inherent limit on the size of a Collection.

share|improve this answer
    
indeed there isn't, but the items with indices > Integer.MAX_VALUE can't be addressed by index number. They might be addressable through iterators, which of course gets extremely slow for such massive amounts of data. –  jwenting Sep 16 '11 at 7:15
    
@jwenting a related question then would be "why do the classes in the Collections Framework only accept an int as an index?" Note that the Collection interface doesn't have any methods that directly index an item. –  cgull Sep 16 '11 at 7:55
    
now THAT would be a good question :) And one that might have historical reasons if for example the original implementation of the classes involved did indeed have a limit of 2^32 on the size of the collection. –  jwenting Sep 16 '11 at 11:57
    
@jwenting: Is iterating over a Java collection always slower if you use iterators? –  FredOverflow Dec 25 '11 at 12:42
add comment

IMO people can reasonably disagree about whether int was the right compromise. However, there is nothing stopping you from implementing an interface that redefines size() to mean a minimum size. See how ConcurrentHashMap defines size.

The point is when you have collections of billions of elements, the precise size is most likely unimportant. A sense of the size will most likely get you there.

As a sidenote, precise counts often get expensive, and is why ! a.empty() is a much better expression than a.size() > 0 when dealing with collections.

share|improve this answer
add comment

Why does Java's Collection.size() return an int?

The real answer is to maintain backwards compatibility with older versions of Java.

The size() method was first implemented in the days when all JVMs were 32 bit. In that environment, a size() method that returned a long would have been weird.

Now 64bit JVMs are commonplace, and huge collections are at least feasible. But if they changed size() now to return a long, it would break binary compatibility for millions of existing Java programs.


Now you could argue with some justifications that collections that big have implementation and performance issues. Those issues could be worked by implementing special collection classes. If you do this, then you can also give the class (say) a longSize() method and alternate versions of get, insert, remove and so on that use 64 bit indexes.

share|improve this answer
add comment

Worrying about index numbers is old fashioned. The future looks more like the below:

interface Function < T >
{
     void call ( T t ) ;
}

class Functions
{
     static void apply ( Iterable < T > iterable , Function < T > func )
     {
          for ( T t : iterable )
          {
                func . call ( t ) ;
          }
     }
}

Now that I think about it. They have already implemented a suitable collection - Map.

  1. If you want a list of type V indexed by Integer use the existing List<V> class or use Map<Integer,V>
  2. If you want a list of type V indexed by Long use Map<Long,V>.
  3. If you want a list of type V indexed by BigInteger use Map<BigInteger,V>.
share|improve this answer
    
@BalusC both are equivalent. java ignores whitespace. I fixed it to be consistent. –  emory Sep 16 '11 at 2:13
    
@BalusC yes, it appears my sarcasm meter is malfunctioning. That is just my whitespace preference. –  emory Sep 16 '11 at 2:22
    
@emory Makes my code look like economy class. –  Paul Bellora Sep 16 '11 at 2:35
    
Bad example. Internally this may get translated to code using the index to retrieve items :) –  jwenting Sep 16 '11 at 7:13
    
@jwenting - The Iterator class has only three methods hasNext, next, and remove. It is true that some Iterators may be implemented incorrectly and may experience problems because they internally rely on an index. But that is not really the fault of the example. –  emory Sep 16 '11 at 14:48
add comment

And who knows? Maybe when 2 billion is too small, they would have updated Java so an int holds more, or make a new primitive type.

share|improve this answer
4  
The type has existed since the beginning, its called a "long". They can't change what an int contains without breaking the Java spec and a lot of existing Java code. We are just about at the point where 2 billion is too small, I'm close to being limited by it in a project I'm working on right now. –  sanity Sep 16 '11 at 1:15
    
Of course, once 2^63 elements no longer seems like a reasonable limit on collection sizes, there's no need to retrofit the language to add a 16-byte integral type - there's already BigInteger. ;) –  Karl Knechtel Sep 16 '11 at 1:51
    
The solution was already known, because C did it a decade earlier: size_t. –  MSalters Sep 16 '11 at 11:39
add comment

there is a problem to store all array values into RAM so such big lists will cause usage of swap file and make system too slow, i think it is a bad idea. You'd better use more suitable structures to store such amount of data

share|improve this answer
2  
Nothing about the Collection interface requires that all of its contents be stored in RAM. –  sanity Sep 16 '11 at 1:25
    
meaning Collection implementations usually utilize arrays to store data (Object[]) –  Dmitry Sep 16 '11 at 1:29
1  
ArrayList does, not sure about anything else, but regardless - so what? –  sanity Sep 16 '11 at 1:31
    
computer perfomance grows so maybe it is not an issue, but i still think for such big amount of data Collection is not the best practice and java Collection interface forces to use more effective storage –  Dmitry Sep 16 '11 at 1:44
1  
that just seems like an after-the-fact justification for a short-sighted decision. Nothing about the Collection interface mandates any particular storage mechanism. You could have a Collection that keeps its data on disk. –  sanity Sep 16 '11 at 1:57
add comment

Obviously, Java Collection is mostly made for collections that contain 2 billion entries at most. If you have more entries to manage, chances are that you need something else than, say, an ArrayList. Nothing keeps you from implementing and using such a collection. The only issue is that the standard collection interface is not the best possible match for that beast.

share|improve this answer
add comment

I think they did the right thing. Like everything else to do with computers Algorithms don't necessarily scale.

An hash/storage algorithm which handles a 10,000 items nicely is probably going to die long before it hits 500,000,000 items.

And its not just about Moores law. Core counts are doubling about every five years and while a single threaded "copy" is OK on a set of a few thousand for a set of millions you would want to activate all the available cores.

I think the original "collections" are still fit for purpose as most collections in the real world will hold less than a 1000 entries, and there are relatively few > 10,000.

Someday just like BigDecimal and BigNumber we will have BigHash and HugeArray.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.