Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

How Random Access works

 
Anant Jagania
Ranch Hand
Posts: 49
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All,

There is a marker interface called java.util.RandomAccess. It says that when this is implemented over sequential or random access it gives better performance. The API also say that

As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:

for (int i=0, n=list.size(); i < n; i++)
list.get(i);

runs faster than this loop:

for (Iterator i=list.iterator(); i.hasNext(); )
i.next();


How the first for loop becomes faster then another one? What does JVM do to make the access faster?

Thanks & Regards,
Anant
 
Henry Wong
author
Marshal
Pie
Posts: 21122
78
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How the first for loop becomes faster then another one? What does JVM do to make the access faster?


I think you got it backwards. The first "for" loop doesn't become faster if the interface is implemented. The JavaDoc is saying that if the first "for" loop is already faster, then the interface should be implemented to tell users of the container that it supports fast random access.

Henry
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
IMO the documentation here is poorly written. An iterator returned be an ArrayList uses calls to get(index) behind the scenes. But for the additional overhead of the Iterator object the difference in performace of the two loops should be unnoticable. I would say :

As a rule of thumb, a List implementation should implement this interface if, elements can be accessed by get(index) in more or less constant (O(1)) time.


The marker interface has no functionality, but it does serve as an indicator as to which algorithms should give better performance. For instance if you receive a sorted List and you want to find a particular element, if the List is random access then a binary search will be the optimal solution, however that would be a totally inappropriate choice for a sequential list. The JVM does nothing to optimize the performance of lists tagged as RandomAccess.
[ March 21, 2007: Message edited by: Garrett Rowe ]
 
Anant Jagania
Ranch Hand
Posts: 49
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
if JVM doesn't do anything when RandomAccess has been used over the implementation of ArrayList then why JavaDoc says that

The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

there must be something which JVM or Collection framework does to improve the performance of lists. what could be that?
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
there must be something which JVM or Collection framework does to improve the performance of lists. what could be that?
As the documentation suggests, methods that receive a List as a parameter can check to see if the List implements RandomAccess. If it does the method can make assumptions about the best algorithm to use. The simplest example I can think of is:



[ March 22, 2007: Message edited by: Garrett Rowe ]
[ March 22, 2007: Message edited by: Garrett Rowe ]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic