Optimizing string memory footprint in Java - Part 1

This is first in a series of blog posts where I will try to describe my miserable attempts at storing large amount of strings to build efficient spell correction and auto-suggest facility in Java. I learned some important lessons doing this and it will be a waste if I didn't share it. So here it goes..

In order to efficiently store large amount of strings, we first need to understand how JVM stores string objects in memory. In this post I will try to summarize memory layout of String object.

Each object in JVM has fixed, unavoidable structural overhead called object header that JVM uses for various tasks such as Garbage Collection, Identification, addressing and others that I don't understand. A 32-bit HotSpot VM uses 8 bytes header per object, 64-bit HotSpot VM with heap larger than 32g as well as IBM's J9 VM takes 16 bytes per object. As always, arrays are treated differently. Array is an object so it has a fixed header of its own as described above. However, since Java spec guarantees array bounds check on every array operation it has to store length of each array which is another 4 byte, making effective array header size 12 bytes instead of regular 8 for objects. And finally there's object padding in multiples of 8 or 16 bytes, depending on CPU word size and JVM to make memory to CPU communication efficient.

Assuming 32-bit JVM, the java.lang.String class has three bookkeeping integer fields called offset, count, hash occupying 12 bytes plus a 4 byte char array pointer and 8 byte header totaling 24 bytes fixed overhead per string. This is inefficient but slightly clever because padding is not required for string object itself making hash a free cache.

Here's the formula to calculate String's shallow and deep sizes:

• Shallow size = HEADER + ( offset + count + hash + char array pointer) = 24 bytes
• Retained size = Shallow size + 12 byte array header + (nchars * 2 + padding)

Where padding = ( (nchars * 2) mod word_size) is rounded off to 8/16 bytes depending on 32/64-bit JVM (Except J9) word_size.

So, on a 32-bit HotSpot VM, 6 byte word "Memory" takes :
24 + 12 + (6 * 2 + 4 padding) = 24 + 12 + 16 = 52 bytes

That is 77% JVM imposed overhead v/s 23% actual data considering it a unicode string.

One way to make string representations efficient is to amortize structural overhead by storing larger strings. To illustrate, 100 char string will be 80% data v/s 20% overhead, 200 char string will be 94.33% data v/s overhead, 500 char string will be 97.6% data v/s overhead and so on. This will be one of the key technique in reducing string's memory footprint I will write about in later blog posts. Following is a rough graph that depicts this theory.

It is easy to see that storing a lot of small strings actually waste huge amount of memory which in no less part the reason why Java is considered a memory hog.

That's all with the basics of understanding overhead involved with storing strings. In next blog post, I will write about various implementations I tried and general rant on Java Collections' memory efficiency.

On using "PermGen" as application level cache

I was reading an interesting article 'Assualt by GC' by stack exchange guy and it felt like a Déjà vu with my past couple of years of development on the JVM. It struck to me that we can definitely do better, so here it goes..

Automatic GC is really a great step forward in software development, except when it is not. If you have deployed application on a JVM with large heap (4g+) you probably know what a long GC pause really feels like [insert familiar knock-knock joke about java]. Jokes aside, JVM's GC advancement is unprecedented. The amount of tuning you can do with different garbage collectors can define a niche profession.

For most applications where GC latency isn't an issue; default garbage collector works just fine. For applications which need to scale GC can (and does) become a 'bottleneck'. If you disagree, try running a JVM under memory pressure and see app response times. It should be surprising because in most data driven applications bottleneck is usually IO or other IO bound resources (e.g. a DB). This situation generally happens when GC is completely thrashing the process because there are too many "tenured" objects which don't fit in the allocated heap or heap is fragmented and GC wastes a lot of time compacting the heap. Unlike .NET, Java folks are not very lucky with platform specific optimizations such as locking pages to prevent swapping. So it is not uncommon that a full GC causes excessive paging, making GC IO bound.

Turns out that GCing large "tenured" object space is expensive compared to short lived young objects (sweep). A large population of "tenured" objects is generally a genuine requirement for long running server processes relying on large amounts of data and this requirement shouldn't really punish application with long GC pauses. While not impossible, it is not really practical to set size of tenured generation very large because it may adversely affect young generation collections. JVM GC optimization is a skill not in abundance but the problem is all too common. So what can we do about it?

One way to eliminate GC on predictable "tenured" application data is to just not store it on JVM heap (i.e. use direct byte buffer etc. ). I've been watching solutions like Terracotta's BigMemory which uses similar approach to address GC issues. However all such solutions seem a mix of  manual memory management with hacks to circumvent GC which end up being half-baked reinvention of JVM's copy-on-write "permgen".

Most of the java developers I know consider "permgen" to be some kind of evil which causes all kinds of problems including "eclipse crashing", crying JSP/[insert other template library] compiler, unpredictable class unloading and really large interned strings which stick around. "permgen" is going to go away from the hotspot vm, which is kind of sad because I think it could be a great way to achieve GC free heap storage for application level data (more specifically cache). This is not really possible unless "permgen" is used for one specific purpose, and if that specific purpose allows application to store its data, we can have standard supported GC free application data without the need of third party solutions which achieve the goal poorly. Even better would be java.cache using "permgen" for cache storage.

One of the commenter at HN talked about Smalltalk VM's way of using permgen (just send a message to  object to move itself to "permgen"). I like this approach because applications can control which objects are long lived which is sensible because they have the best knowledge about long lived objects. The only similarity in JVM we have is String.intern, which unfortunately caches strings forever and it is not really as useful as having some kind of eviction control.

So, what do you think about this approach?

Fork/Join Concurrency with Scala Actors

Have you ever wondered why there are no special frameworks to address concurrency in a Java based application? Considering Java's rich (NIH) ecosystem, I do wonder why I have to write same old state management code while introducing even a small amount of concurrency in Java application.

The reason why I think it is almost impossible to consider concurrency as an aspect in arbitrary application is because of JVM's native support for shared memory concurrency. As a result every developer is forced to think in terms of threaded shared state with guarded blocks. If you have read or written non-trivial piece of code using shared memory concurrency primitives (Mutex, Semaphore etc.) you probably know that the resultant code is hard to visualize and test.

I have been reading about Scala's Actor library and its share-nothing message passing abstraction built over existing concurrency model of JVM. While it doesn't try to solve the fundamental problem, it provides an alternative to address concurrency in your application from a different perspective which is testable and easier to understand.

In actor model, an Actor is a forkable task which runs independently, something like a serializable+immutable object with its private data and behavior. Each actor can send and receive (or react to) messages asynchronously, very similar to object oriented programming with objects responding to messages, but in a concurrent way. This abstraction can seamlessly be applied to a given application of divide and conquer nature and can be made concurrent with minimal efforts as compared to adapting to Java's concurrency primitives.

To explain my point further take a look at classically trivial Producer/Consumer example in Java.

public class Consumer extends Thread {
private final Buffer buffer;
public Consumer(Buffer buffer) {
 super("Consumer");
 this.buffer = buffer;
}
@Override
public void run() {
 while (true){
  System.out.println(buffer.next());
 }
}
}
public class Producer extends Thread {
private final Buffer buffer;
public Producer(Buffer buffer) {
 this.buffer = buffer;
}
@Override
public void run() {
 Random random = new Random(System.nanoTime());
 while (true) {
  String num = Integer.toString(random.nextInt());
  System.out.println(getName() + "=putting: " + num);
  buffer.add(num + ": " + getName());
  try {
   sleep(400);
  } catch (InterruptedException e) {
  }
 }
}
}
public class Buffer {
private String string;
private boolean ready = false;
public synchronized String next() {
 if (ready != true)
  try {
   wait();
  } catch (InterruptedException e) {
  }
 ready = false;
 return string;
}

public synchronized void add(String string) {
 while(ready == true)
  try {
   wait();
  } catch (InterruptedException e) {
  }
 this.string = string;
 notifyAll();
 ready = true;
}

}
public class Test {
public static void main(String[] args) throws Throwable {
 Buffer buffer = new Buffer();
 new Consumer(buffer).start();
 Producer producer = new Producer(buffer);
 producer.start();
 producer.join();
}
}

Take a look at Buffer class, we have used some concurrency primitives there since that's the place where state is being manipulated. We didn't declare variable ready as volatile since primitive assignments are guaranteed to be atomic (except long and double), Even a simple problem like this involves fair bit of understanding of the underlying threading model. There's no doubt this complexity will extrapolate in non-trivial applications e.g. multi-phase concurrent incremental compiler, SEDA based server etc.

Now take a look at the equivalent Producer/Consumer example in Scala.

import actors._
import actors.Actor._
import util.Random

case class SimpleMessage(num: Long)

class Producer(c: Consumer) extends Actor{
val random = new Random(System nanoTime)
def act = {
 loop{
  val num = produce
  println("Sending: " + num )
  c ! SimpleMessage(num)  // asynchronous message passing
 }
}
def produce(): Long = {
 Thread sleep 400
 return random.nextLong
}
}
class Consumer() extends Actor{
def act = {
  loop{
   receive{ //blocks here
     case SimpleMessage(num) => println("Received: " + num);
   }
  }
}
}
object PCTest {
def main(args : Array[String]) : Unit = {
var c = new Consumer()
var p = new Producer(c)
c.start;p.start
}
}

Even if we don't compare the amount of code, the Scala code above is much more clear in terms of its functionality. In Scala, Actors can be mapped to a single native thread with 'receive' (similar to Thread#wait()) or we can replace 'receive' with 'react' which is event based invocation but doesn't cost a blocked thread. The code within 'react' is executed by any non-blocked thread from a pre-created thread-pool. Just a single change and your application is scalable!

The Java example code above can be equally trivialized with the util.concurrent BlockingQueue, but the important point to take away is, writing shared memory concurrency code is inherently difficult and error-prone. With JDK1.7 we will get similar fork/join abstraction in Java itself (JSR166y), which will add new alternative to how we design and write concurrent applications.

Scala borrowed Actors from Erlang and similar libraries exist for Java as well. If you are curious about interesting details on Actor based OO concurrency implementation in Java, take a look at some of the thoughts Sebastian is sharing with his ConcurrentObjects library.

Your Language is not SLOW!

Do you really give a thought when you say "Ruby is slow or Python is slow"? Just because Twitter moved their back end messaging to JVM doesn't necessarily make Ruby any slower than it already was. If a language runtime can't handle concurrent load or long running processes it is not a limitation of the language!

This is dejavu for me as Java was considered "a slow language" back in 1.1 days when HotSpot JVM was in its poorer life and ISO/IEC C++ was hot girl in town. Now that you realized your pony implementations can't catch up with real life performance expectation you start blaming languages, are you serious?

Whether it's global interpreter lock or lack of native threads it's the runtime (re-read the runtime) and not the language that is slow. For the love of technology, Stop blaming languages for poor performance of your suboptimal reinventions!

Every language implementor should at least consider the host platform support before coming up with their "Not Invented Here" approach, sadly that's what is happening with most modern languages.

Executable Models

Imagine...

A work place where your regular tasks involve analyzing and modeling the parts of system based on stories (or requirements, whatever) and writing few snippets of instructions. You've a world class IDE with some wonderful perspectives, editors, views and a state of art execution infrastructure. The IDE allows quick execution of your models to test them, allows visual model debugging while encouraging ergonomics to prevent heavy "keying and mousing", IDE supporting finest model refactoring to allow painless design change, while providing real time collaboration for distributed brainstorming and discussions...

You pair model it, you test drive it, you version it at finer granular unit of control, you've a catalogue of blueprints (design + domain) which can be used statically as well as in context of existing system, you have continuous integration of models which compiles, validates (tests) and builds the system. At end of the day, you've a system which can simulate in development environment as well as deployable as production software....

Imagine a execution infrastructure able interpret UML (relax, take unambiguous parts of UML or Mellor subsets) directly, or may be it emits a script which can be plugged in existing JVM, or may be UML VM itself with attach on demand and hot model replacements :) ....

I dream to be in such an environment as well as developing such environment.

Realize....

These imaginations, although will sound like philosophies, are not without basis, existing tools and technologies can be leveraged and bridged to provide this envisioned platform; it's hard, takes lot of resources but not impossible. Ok, it will not give quick returns, will have adoption problems which can be handled.

At first, Executable UML will seem like a buzzword, to me it sounded daunting and it seemed like everyone wants to change the world. That change is for good, how long you want to work with something as ugly as XML or JSP and other complexities which in no way adds to customer requirements? They deserve to be generated or they don't even deserve to be in our codebase (I should say modelbase :) ).

Executability of models is not something entirely new (apart from Virtual Machines, OOP etc.), guys like Steven Mellor and Marc Balcer are working on it for quite sometime now.

If you feel, that, support for such tooling is not enough; Let me tell you, Eclipse has made such feeling "Past"; With Eclipse, We can leverage most of the Eclipse related technologies for achieving it, ECF for collaboration, UML/EMF/GEF/GMF for modeling, Debug Framework and GEF for simulation and model debugging (in this case, we may need to change the abstraction semantics of stack frames etc.) . Of course building VM or runtime is non-trivial, but it's worth trying alternative approaches like integrating with existing runtime.

This is the time for improving the software crafting (or engineering?), no one needs costly software, and current fashions make them expensive; Well its different topic to debate about productivity levels of existing methods but it can surely be improved.

Escape Analysis in Mustang - II

EDIT: As commented by Brian, these Escape Analysis optimizations were dropped before final release and deferred to Java 7. The debug version of VM can no longer be found at http://download.java.net/download/jdk6/6u1/promoted/b03/binaries/jdk-6u1-ea-bin-b03-windows-i586-debug-19_jan_2007.jar

In my previous post, I mentioned that escape analysis is available in mustang releases and debug flags available for it in HotSpot(tm) VM.

I ran some micro benchmarks yesterday, they are fairly trivial but good enough to identify the performance gains, and here is what I found:

import java.io.ByteArrayOutputStream;
import java.io.OutputStream;
import java.io.PrintStream;

public class TestEA {
   public static class MyPrintStream extends PrintStream {
       public MyPrintStream(OutputStream out) {
           super(out);
       }
      
       @Override
       public void println(int cnt) {/* deep inline candidate */
       }
      
   }
  
   private static final int COUNT = 10000000;
  
   public static void main(String[] args) throws Exception {
       System.setOut(new MyPrintStream(new ByteArrayOutputStream()));
       for (int i = 0; i <= 10; i++)
           test();
      
   }
  
   private static void test() {
       int cnt = 0;
       Object objLock = new Object();
       long start = System.currentTimeMillis();
       for (int i = 0; i < COUNT; i++) {
           synchronized (objLock) {
               cnt++;
           }
           consume(cnt);
       }
       long end = System.currentTimeMillis();
       System.err.println(cnt + ", time=" + (end - start) / 1000.0);
   }
  
   private static void consume(int cnt) {
       System.out.println(cnt);
   }
  
} 

The results
VMArgs: -server

10000000, time=0.907
10000000, time=0.938
10000000, time=0.969
10000000, time=0.906
10000000, time=0.906

With
VMArgs: -server -XX+DoEscapeAnalysis
10000000, time=0.89
10000000, time=0.922
10000000, time=0.016
10000000, time=0.016
10000000, time=0.015
10000000, time=0.016

JVMOut:
28 JavaObject NoEscape [[ 54F]] 28 Allocate ....
40 LocalVar NoEscape [[ 28P]] 40 Proj ....
90 LocalVar NoEscape [[ 28P]] 90 Phi ....
213 JavaObject NoEscape [[]] 213 Allocate ....
225 LocalVar NoEscape [[ 213P]] 225 Proj ....
======== Connection graph for TestEscapeAnalysis::test ....
172 JavaObject NoEscape [[]] 172 Allocate ....
184 LocalVar NoEscape [[ 172P]] 184 Proj ....

I ran the loop in main for few times because server VM does a deep inline and it might optimize the execution considering cnt is not significantly used anywhere.

Well, It can be seen that escape analysis successfully eliminated synchronization on objLock (lock elision) . As I posted earlier, synchronization has significant impact on execution speed, elimination of this heavy operation improved the speed substantially. Consider the effect of it on a highly concurrent web server (JAWS) handling hundreds of simultaneous requests. Of course, it happened because objLock is allocated locally and VM identified that it can't be shared between multiple threads and its safe to remove the sync overhead.

I also tried making objLock a static field of the class and found that escape analysis has no positive impact on execution speed as can be seen here:

VMArgs: -server -XX:+DoEscapeAnalysis (objLock as static field in above program)
10000000, time=0.922
10000000, time=0.922
10000000, time=0.906
10000000, time=0.891
10000000, time=0.921

As expected, objLock being a shared field, VM has no way of identifying whether lock on it can be eliminated or not.

Unfortunately, stack allocation seems to be absent in current builds of mustang (or there were no hints in debug output as when it was done. Also, its hard to decipher the VM output and I found no explanation for it). Here is an excellent presentation on new optimization in HotSpot(tm) VM. And for lock elimination enhancements refer to this.

So, there you go, one more optimization for the managed runtime; for those who are still in the illusion that native static compiler optimized programs are the fastest, think again, your programs are static at runtime can't organize itself, managed runtime is metamorphic, it can adapt and substantially optimize itself at runtime. Man, that's what I call programming.

Escape Analysis in Mustang - I

EDIT: As commented by Brian, these Escape Analysis optimizations were dropped before final release and deferred to Java 7. The debug version of VM can no longer be found at http://download.java.net/download/jdk6/6u1/promoted/b03/binaries/jdk-6u1-ea-bin-b03-windows-i586-debug-19_jan_2007.jar. Production VM here means production release type, as compared to debug, not the final release.

Java 6 brings a lot of improvements in (much ignored) synchronization; like lock elision, adaptive locking etc., under, the awaited, escape analysis hood. I've been reading quite a bit on stack allocation and lock detection techniques to reduce GC overhead. (as stack comes for free; and sometimes, on full speed core).

Escape analysis is one of the interesting techniques in compiler optimization, read more here.

Few days back, I posted an off-topic curiosity on lang.java google group, It's not officially mentioned anywhere that escape analysis is implemented in mustang releases. Brian Goetz wrote an article stating EA is available in mustang builds, that article is pretty old and someone questioned whether it's really available or not...

A web search revealed that escape analysis *is* available in mustang (not well marketed?), and production VM binary (I've b-03) supports it out of the box in server mode; debug binaries supports few more switches to see the analysis. I'm trying to benchmark it with few programs playing around large number of object creation, not a big deal.

Well, if you are interested, try these switches with mustang (in server mode)
-XX:+PrintEscapeAnalysis,
-XX:+PrintOptoAssembly,
-XX:+DoEscapeAnalysis (works on production VM only).

May be this weekend, I'll post the results of the benchmarks and other findings on it.
Java's performance is getting better and better..

Some Lost+Found gyan from JMM :)

Findings from an article by Goetz:

“While the JMM specified in chapter 17 of the Java Language Specification was an ambitious attempt to define a consistent, cross-platform memory model, it had some subtle but significant failings. The semantics of synchronized and volatile were quite confusing….

...JSR 133, chartered to fix the JMM...

Most programmers know that the synchronized keyword enforces a mutex (mutual exclusion) …. But synchronization also has another aspect: It enforces certain memory visibility rules as specified by the JMM. It ensures that caches are flushed when exiting a synchronized block and invalidated when entering one, (significant performance degradation on multiprocessors) so that a …. It also ensures that the compiler does not move instructions from inside a synchronized block to outside…. The JMM does not make this guarantee in the absence of synchronization -- which is why synchronization (or its younger sibling, volatile) must be used whenever multiple threads are accessing the same variables.”

I’m not sure if this cache flush is entire cache flush (128k to 2m) or cache-line flushes, but i consider it really bad. All operations are stalled until memory request is complete.

I never knew this behavior of “synchronized”. I always wondered about the bad performance of concurrency primitives, some facts like these makes my understanding clearer, why it's not scalable,

This will give one certain idea of how painful it is to achieve "Platform Independence", apart from being the buzzword.

(and who likes snoopy cache being flushed like dumb one:( )

JVM Optimization

Kudos !!! We've been assigned new project on Performance & Profiling of our product Wallet Service Center. I'm wondering from where to start optimizing, optimize JVM through configuration, optimize Code, optimize AppServer?? Its hardly easier to improve code overnight, so I think i will look into JVM configuration and optimize it. Sun's website is full of performance tips, most of them relate to GC and JIT. It was fun to knew some cool aspects and behavior of JIT (Just In Time) Compiler e.g. Default threshold for method compilation is 1500 executions, What it means is, If a method is called more than 1499 times in HotSpot Client VM, the method will be compiled to native code.

Kewl!! So C++ guys we are ready to outperform. Still Generational GC isn't clear to me, I think I should read more about it. Now that I have the book of Jack Shirazi on performance tuning, I'll be doing something better. I'm happy as I've got the work that I like!!