How to make an iteration in a for-loop faster?

Question

I have a list with contentlets and want all languages from every contentlet (I get these with the method languageAPI.getAllValuesByKey(key , contentList). I get a HashMap and iterate over it. There are 1000 keys available. In the beginning it only takes 2 ms per key. But after a while it increases. And the last one takes 35ms. How can I decrease these times? How can I make it faster/more efficient?

JSONArray arrAll = new JSONArray();
JSONObject jsonObject = new JSONObject();
JSONArray arr = new JSONArray();
JSONObject values = new JSONObject();
List<Contentlet> contentlets = languageFactory.getAllContentlets(null);
List<Contentlet> keys = languageAPI.getLanguageKeys(null, contentlets);
for(Contentlet key : keys) {
 Long startTime = System.currentTimeMillis();
 jsonObject = new JSONObject();
 HashMap<Long, String> allValues = languageAPI.getAllValuesByKey(key.getStringProperty("key"), contentlets);
 Iterator<java.util.Map.Entry<Long, String>> it = allValues.entrySet().iterator();
 arr = new JSONArray();
 while (it.hasNext()) {
 values = new JSONObject();
 java.util.Map.Entry<Long, String> pairs = it.next();
 values.put("l", pairs.getKey());
 values.put("v", pairs.getValue());
 arr.add(values);
 it.remove(); // avoids a ConcurrentModificationException
 }
 try {
 jsonObject.put("k", key.getStringProperty("key"));
 jsonObject.put("t", (Object)arr);
 jsonObject.put("p", key.isLive());
 jsonObject.put("l", key.isLocked());
 jsonObject.put("a", key.isArchived());
 } catch (DotStateException e) {
 throw new RuntimeException(e.toString(),e);
 } catch (DotDataException e) {
 throw new RuntimeException(e.toString(),e);
 } catch (DotSecurityException e) {
 throw new RuntimeException(e.toString(),e);
 }
 arrAll.add(jsonObject);
 Long end = System.currentTimeMillis() - startTime;
 Logger.info(this, "For key: " + key.getStringProperty("key") + " " + end + "ms");
}

Edit:

One of the problems is that the for loop in the getStringKey method take some time. Of course in the beginning the value is at the beginning, but after a while, it is at the end of the list. So I think one of the problems might be here (this takes 8ms, in the last records)

public HashMap<Long, String> getAllValuesByKey(String key, List<Contentlet> contentlets) {
 HashMap<Long, String> keys = new HashMap<Long, String>();
 for(Language language : APILocator.getLanguageAPI().getLanguages()) {
 keys.put(language.getId(), getStringKey(language.getId(), key, contentlets));
 }
 return keys;
}
public String getStringKey(Long languageId, String key, List<Contentlet> contentlets){
 String value=null;
 for(Contentlet keyEntry : contentlets) {
 if(keyEntry.getStringProperty("key").equals(key) && languageId == keyEntry.getLanguageId()) {
 return keyEntry.getStringProperty("value");
 }
 }
 if(value==null)
 {
 value = "";
 }
 return value;
} 

Edit 2: found the problem, but how to solve it?

The code after this phrase takes 20ms in the last records. The only thing what happens here is adding some things to a JSONObject. Why is this taking so long? I even don't know, how to make this faster, because this is the only way to handle it?

 end = System.currentTimeMillis() - startTime;
 Logger.info(this, "Before add: " + key.getStringProperty("key") + " " + end + "ms");
 try {
 jsonObject.put("k", key.getStringProperty("key"));
 jsonObject.put("t", (Object)arr);
 jsonObject.put("p", key.isLive());
 jsonObject.put("l", key.isLocked());
 jsonObject.put("a", key.isArchived());
 } catch (DotStateException e) {
 throw new RuntimeException(e.toString(),e);
 } catch (DotDataException e) {
 throw new RuntimeException(e.toString(),e);
 } catch (DotSecurityException e) {
 throw new RuntimeException(e.toString(),e);
 }
 end = System.currentTimeMillis() - startTime;
 Logger.info(this, "After add: " + key.getStringProperty("key") + " " + end + "ms");

• NPE: Use a profiler to find out where the time is spent. Then you'll know what to optimize.
• kutschkem: Is it necessary that you remove the entries?
• kutschkem: also, what type does arrAll have?
• imxylz: The 'Map.Entry.remove()' method need some time to find the current Object in the entry. Also you need more time-watch to check the slowest method calling.
• Taky: Try to profile this method with JVIsual VM. Thus you can gather more information.

Answer 1

1. getStringKey iterates over the contentlets list for every key. It looks O(n^2) which does not scale well. You could create a HashMap<ContentletCacheKey, Contentlet> cache with a proper hashCode and equals for ContentletCacheKey and use this instead of iterating over the list every time.

2. Try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method, declare them where they are first used. (Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

   This object creation is unnecessary since you create a new object at the beginning of the for loop:

   JSONObject jsonObject = new JSONObject();
   

   The same is true for values and arr.

3. Your statistics log could show invalid data because if you change the system date System.currentTimeMillis() will reflect that. I suggest using System.nanoTime() or a stopwatch class (Guava, Apache Commons).

4. public String getStringKey(Long languageId, String key, 
    List<Contentlet> contentlets) {
    String value = null;
    for (final Contentlet keyEntry: contentlets) {
    if (keyEntry.getStringProperty("key").equals(key) 
    && languageId == keyEntry.getLanguageId()) {
    return keyEntry.getStringProperty("value");
    }
    }
    if (value == null) {
    value = "";
    }
    return value;
   }
   

   This could be more simple:

   public String getStringKey(Long languageId, String key, 
    List<Contentlet> contentlets) {
    for (final Contentlet keyEntry: contentlets) {
    if (keyEntry.getStringProperty("key").equals(key) 
    && languageId == keyEntry.getLanguageId()) {
    return keyEntry.getStringProperty("value");
    }
    }
    return "";
   }
   

5.  Iterator<java.util.Map.Entry<Long, String>> it 
    = allValues.entrySet().iterator();
    JSONArray arr = new JSONArray();
    while (it.hasNext()) {
    JSONObject values = new JSONObject();
    java.util.Map.Entry<Long, String> pairs = it.next();
    values.put("l", pairs.getKey());
    values.put("v", pairs.getValue());
    arr.add(values);
    it.remove(); // avoids a ConcurrentModificationException
    }
   

   If I'm right you can clear the the whole map after loop (instead of remove in every iteration) and could use a foreach loop:

   for (final Map.Entry<Long, String> pairs: allValues.entrySet()) {
    final JSONObject values = new JSONObject();
    values.put("l", pairs.getKey());
    values.put("v", pairs.getValue());
    arr.add(values);
   }
   allValues.clear();
   

   Actually, the clear() need unnecessary (as well as the it.remove()) since you don't use the allValues map after the while (for) loop. Furthermore, importing java.util.Map.Entry makes the code easier to read.

6. HashMap<...> reference types should be simply Map<...>. See: Effective Java, 2nd edition, Item 52: Refer to objects by their interfaces