[JavaSpecialits] - Memory Usage of Maps

http://www.javaspecialists.eu/archive/Issue193.html

Memory Usage of Maps

by Dr. Heinz M. Kabutz
Abstract:
In this newsletter we measure the memory requirements of various types of hash maps available in Java. Maps usually need to be threadsafe, but non-blocking is not always the most important requirement.

Welcome to the 193rd issue of The Java(tm) Specialists' Newsletter, sent from the amazing Island of Crete. A few weeks ago my Greek teacher introduced me to "aoristos", the simple past. This is great, because now I can bore my Greek friends with wild tales of life in Africa when I was a child. "Ipia me tous elefantes" - I drank with the elephants. The beauty of being from Africa is that Europeans will believe anything you say. "Ahh, so you had a lion as a pet? I knew it!" If you know a bit of Greek, try this aoristos flash card test. My name is on top at the moment, but I'm sure I will easily be dethroned :-)

In my previous newsletter, I challenged you to explain why the anonymous class sets the this$0 field before calling super(). Kai Windmoeller was the first to send me a partial reason and Wouter Coekaerts was the first with a perfect explanation. Both Kai and Wouter subsequently sent me other clever ideas that I would like to incorporate in future newsletters. [And the explanation is ....... you'll have to figure that out yourself :-) A hint though, if you compile the class with -source 1.3 and -target 1.3, it does not do that. See what issues that can cause and you will see why we need this.]

In-house courses if these dates or locations do not suit you. Note that the course in Crete may also be attended remotely via webinar.

Memory Usage of Maps

My newsletter is strongly connected to my courses. When I research Java for my newsletter, ideas emerge on how to improve my advanced Java courses. Questions asked during the courses often stimulate ideas for new research topics. It is a delicate ecosystem. They cannot exist without each other.
A few months ago, during one of my masters courses, one of the programmers mentioned that they had noticed a memory bottleneck with the ConcurrentHashMap. They were creating about 100000 maps and wanted them to be threadsafe. The natural choice seemed to be the ConcurrentHashMap, since it, well, is supposed to work with concurrent access.

The ConcurrentHashMap splits the bucket table into a number of segments, thus reducing the probability that you would have contention when modifying the map. It is quite a clever design and scales nicely to about 50 cores. Above 50 cores, you would be better off using Cliff Click's Highly Scalable Libraries. Since my friends did not need high scalability, the ConcurrentHashMap seemed fine.

Whilst doing a memory profile, JVisualVM showed that the top culprit was the ConcurrentHashMap.Segment class. The default number of segments per ConcurrentHashMap is 16. The HashEntry tables within the segments would probably be tiny, but each Segment is a ReentrantLock. Each ReentrantLock contains a Sync, in this case a NonFairSync, which is a subclass of Sync and then AbstractQueuedSynchronizer. Each of these contains a queue of nodes that maintain state of what is happening with your threads. It is used when fairness is determined. This queue and the nodes use a lot of memory.

Many years ago, I wrote a newsletter that demonstrated a simple memory test bench. It would construct an object, then release it again with System.gc() and measure the difference. Here is a slightly updated version of the MemoryTestBench. It still does virtually the same, with the only enhancement that I sleep a bit after each System.gc() call:

public class MemoryTestBench {
  public long calculateMemoryUsage(ObjectFactory factory) {
    Object handle = factory.makeObject();
    long memory = usedMemory();
    handle = null;
    lotsOfGC();
    memory = usedMemory();
    handle = factory.makeObject();
    lotsOfGC();
    return usedMemory() - memory;
  }

  private long usedMemory() {
    return Runtime.getRuntime().totalMemory() -
        Runtime.getRuntime().freeMemory();
  }

  private void lotsOfGC() {
    for (int i = 0; i < 20; i++) {
      System.gc();
      try {
        Thread.sleep(100);
      } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
      }
    }
  }

  public void showMemoryUsage(ObjectFactory factory) {
    long mem = calculateMemoryUsage(factory);
    System.out.println(
        factory.getClass().getSimpleName() + " produced " +
            factory.makeObject().getClass().getSimpleName() +
            " which took " + mem + " bytes");
  }
}
  
I created an ObjectFactory interface and some basic classes to test that it still worked correctly:


public interface ObjectFactory {
  Object makeObject();
}

public class BasicObjectFactory implements ObjectFactory {
  public Object makeObject() {
    return new Object();
  }
}

public class IntegerObjectFactory implements ObjectFactory {
  public Object makeObject() {
    return new Integer(333);
  }
}

public class LongObjectFactory implements ObjectFactory {
  public Object makeObject() {
    return new Long(333L);
  }
}
  
I tried this out with Java 1.6.0_24 on my Mac OS X 10.6.8 and with a self-built Java 1.7.0 based on the OpenJDK. I also tried 32 vs. 64 bit, server vs. client on the 32 bit and the flag -XX:+UseCompressedOops on the Server Hotspot Compiler. The -server and -client made the least difference, so I only include the -server results. Also, the results for Java 1.7.0 were similar enough to 1.6.0_24 that I will only show the 1.6 data:

Java Version 1.6.0_24 with -server
32/64bit         64   64   32
CompressedOops   No  Yes  N/A
Object           24   24    8
Long             24   24   16
Integer          24   24   16
  
It looks as if the -XX:+UseCompressedOops flag has no effect on these objects. You will only see the difference with more complex objects that have pointers to others. This flag can also speed up your application substantially if you are using a 64 bit machine.

Here are some factories for creating various hash maps. The first is not threadsafe, the other two are:

public class HashMapFactory implements ObjectFactory {
  public Object makeObject() {
    return new HashMap();
  }
}

public class SynchronizedHashMapFactory implements ObjectFactory {
  public Object makeObject() {
    return Collections.synchronizedMap(new HashMap());
  }
}

public class HashtableFactory implements ObjectFactory {
  public Object makeObject() {
    return new Hashtable();
  }
}
  
We see that even basic hash tables differ greatly in size between various implementations. If memory space is a major issue, like it was for my friends, then the Java 1.0 Hashtable class might work best. Hashtable is fully synchronized, which means that it will cause contention when accessed from more than one core at a time. It also uses integer division to locate the correct bucket, which is slower than the bit masking approach used since Java 1.4. However, if memory is your bottleneck, then Hashtable might be a good solution. Here are the memory sizes:

32/64bit          64   64   32
CompressedOops    No   Yes  N/A
HashMap           216  128  120
SynchronizedMap   272  160  152
Hashtable         176  112   96
  
The ConcurrentHashMap allows us to construct it with a concurrency level, which is used to calculate the number of segments that the map will contain. The actual number of segments is a power of 2 greater or equal to the concurrency level. Thus if we construct a map with concurrency level of 200, it will create 256 segments. As mentioned above, every segment is subclassed from ReentrantLock. Thus we will show the sizes for ReentrantLock, and ConcurrentHashMaps with sizes 16 (the default), 2 and 256:

public class ReentrantLockFactory implements ObjectFactory {
  public Object makeObject() {
    return new ReentrantLock();
  }
}

public class ConcurrentHashMapFactory implements ObjectFactory {
  public Object makeObject() {
    return new ConcurrentHashMap();
  }
}

public class SmallConcurrentHashMapFactory implements ObjectFactory {
  public Object makeObject() {
    return new ConcurrentHashMap(16, .75f, 2);
  }
}

public class BigConcurrentHashMapFactory implements ObjectFactory {
  public Object makeObject() {
    return new ConcurrentHashMap(16, .75f, 256);
  }
}
  
Based on these results, we can see why the ConcurrentHashMap uses so much memory, even when it is empty.

32/64bit                    64      64      32
CompressedOops              No     Yes     N/A
ReentrantLock               72      56      40
ConcurrentHashMap         2272    1664    1272
SmallConcurrentHashMap     480     312     272
BigConcurrentHashMap     34912   25664   19512
  
Another option is Cliff Click's Highly Scalable Libraries.

import org.cliffc.high_scale_lib.*;

public class HighlyScalableTable implements ObjectFactory {
  public Object makeObject() {
    return new NonBlockingHashMap();
  }
}
  
Click's empty NonBlockingHashMap uses a lot less memory than the ConcurrentHashMap.

32/64bit                  64     64      32
CompressedOops            No    Yes     N/A
ConcurrentHashMap       2272   1664    1272
NonBlockingHashMap 1312 936 872
  
Let's see what happens when we put some elements into the map, by writing an ObjectFactory that fills the map with objects. By adding autoboxed Integers from the integer cache and constant Strings, we can measure the hash map overhead, instead of the objects contained inside the map.

public class FullMapObjectFactory implements ObjectFactory {
  private final ObjectFactory factory;

  protected FullMapObjectFactory(ObjectFactory factory) {
    this.factory = factory;
  }

  public Object makeObject() {
    return fill((Map) factory.makeObject());
  }

  protected Map fill(Map map) {
    for (int i = -128; i < 128; i++) {
      map.put(i, "dummy");
    }
    return map;
  }
}
  
With this particular data set, the NonBlockingHashMap uses the least amount of memory, but I have seen other data sets where the Hashtable uses the least. You would have to try it out in your particular situation to find the best possible map for your needs. Also remember that the NonBlockingHashMap scales to hundreds of cores, whereas the Hashtable would have contention with two.

32/64bit                    64      64      32
CompressedOops              No     Yes     N/A
ConcurrentHashMap        30024   21088   16872
SmallConcurrentHashMap   16736   10488    8400
BigConcurrentHashMap     48144   34040   26416
Hashtable                15440    9792    7728
NonBlockingHashMap       10912    6696    6632
  
As in all performance issues, you need to measure and not guess. Please only change your code if you have measured and verified that this is indeed your bottleneck.

Kind regards from sunny Crete
Heinz

P.S. You might have seen disturbing images of Greek rioting. Fortunately this is far away from where we live on the Island of Crete. The despair is quite real though.

Large collection of Free Microsoft eBooks

Large collection of Free Microsoft eBooks for you, including: SharePoint, Visual Studio, Windows Phone, Windows 8, Office 365, Office 2010, SQL Server 2012, Azure, and more.


            



Throughout the year I try to share resources and information with you that I think will be helpful for you. Often times these resources will include links to free eBooks that we make available on a variety of topics. Today, I thought I would post a large collection of eBooks for you here so that you can find them in one place and consume them as you see fit. Also, if you find this list helpful, please share it with your peers and colleagues so that they too can benefit from these resources.


Access the whole list of these free books HERE.

A Comparison of Canvas and SVG

By Patrick_Dengler | 26 Oct 2011
This article is an extract of the original one from The Code Project. These articles are intended to provide you with information on products and services that we consider useful and of value to developers.

Canvas and SVG are two exciting graphics features introduced in Internet Explorer 9 and are hardware accelerated. These technologies can be used to address a range of graphic scenarios on the modern Web.

The following is a high-level summary of Canvas and SVG meant to frame a discussion of when to use one particular vector graphic technology over the other.



A Comparison of Canvas and SVG
CanvasSVG
Pixel-based (canvas is essentially an image element with a drawing API)Object Model-based (SVG elements are similar to HTML elements)
Single HTML element similar <IMG>  to in behavior
Multiple graphical elements which become part of the Document Object Model (DOM)
Visual presentation created and modified programmatically through scriptVisual presentation created with markup and modified by CSS or programmatically through script
Event model/user interaction is coarse—at the canvas element only; interactions must be manually programmed from mouse coordinatesEvent model/user interaction is object-based at the level of primitive graphic elements—lines, rectangles, paths
API does not support accessibility; markup-based techniques must be used in addition to canvasSVG markup and object model directly supports accessibility




SVG is known as a retained mode graphics model persisting in an in-memory model. Analogous to HTML, SVG builds an object model of elements, attributes, and styles. When the Canvas is a bitmap with an immediate mode graphics application programming interface (API) for drawing on it. Canvas is a “fire and forget” model that renders its graphics directly to its bitmap and then subsequently has no sense of the shapes that were drawn; only the resulting bitmap stays around.

One way to think of these is that Canvas resembles the Windows GDI API, where you programmatically draw graphics to a window, and SVG resembles HTML markup with elements, styles, events, and DOM-based programmability. Canvas is procedural whereas SVG is declarative.


Example of code using CANVAS:


function GreenScreenAtoB(a, b) {
   var aImageData = a.getImageData(0, 0, a.canvas.width, a.canvas.height);
   var bImageData = b.getImageData(0, 0, b.canvas.width, b.canvas.height);
   var aPixels = aImageData.data;
   var bPixels = bImageData.data;

if (aPixels.length != bPixels.length) {
window.alert("Canvases do not have the same number of pixels");
return bImageData;
}

var pixelCount = bPixels.length;
for (var pixelIndex = 0; pixelIndex < pixelcount; pixelIndex += 4) {
// grab the RGBA components of each pixel in b
var r = bPixels[pixelIndex + 0];
var g = bPixels[pixelIndex + 1];
var b = bPixels[pixelIndex + 2];
var a = bPixels[pixelIndex + 3];

// if the b pixel is green, replace it with a pixel from a
if (r == 0 && g == 255 && b == 0 && a == 255) {
bPixels[pixelIndex + 0] = aPixels[pixelIndex + 0];
bPixels[pixelIndex + 1] = aPixels[pixelIndex + 1];
bPixels[pixelIndex + 2] = aPixels[pixelIndex + 2];
bPixels[pixelIndex + 3] = aPixels[pixelIndex + 3];
}
}

return bImageData;
}

READ MORE HERE >>>








License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)