Ben J. Christensen

I recently made several implementations of a RollingNumber (allowing a sum to be calculated over a 10 second period with 1 second increments with continual updates) to determine what would perform best under high-concurrency.

In my case, concurrency means 4-8000 writes/second from hundreds of threads on an 8-core machine and only a handful of reads per second.

In the end, a circular-array (using AtomicReferenceArray internally) won my throughput tests and also achieved my side goal of being non-blocking.

The code is on GitHub and the winning implementation is RollingNumberViaTryLockWithAtomicCircularArray.

Note that this code is NOT what I would deploy in production, since I forced each implementation to comply to the same interface so they could all be run by my test-harness.

However, a modified version of RollingNumberViaTryLockWithAtomicCircularArray is being run in production processing billions of writes per day.

Another aspect of the test is the use of ReentrantLock.tryLock() instead of a synchronized block. The tryLock() works well in this use-case, allowing only 1 thread to get the lock and routing all others around it instead of blocking them.

Test Results

Here are charts (higher is better) showing the differences in performance between implementations on two different machines:

MacBook Pro 2.2GHz Intel Core i7, 8GB Memory, SSD Drive, OSX Lion 10.7.1

$ uname -a
Darwin 11.1.0 Darwin Kernel Version 11.1.0: Tue Jul 26 16:07:11 PDT 2011; root:xnu-1699.22.81~1/RELEASE_X86_64 x86_64

$ java -version
java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03-383-11A511)
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02-383, mixed mode)

The winner is the blue bar which is the highest.

Amazon EC2 m2.4xlarge
High-Memory Quadruple Extra Large Instance 68.4 GB of memory, 26 EC2 Compute Units (8 virtual cores with 3.25 EC2 Compute Units each), 1690 GB of local instance storage, 64-bit platform

$ uname -a
Linux 2.6.21.7-2.ec2.v1.3.fc8xen #1 SMP Sat Sep 25 01:16:50 EDT 2010 x86_64 x86_64 x86_64 GNU/Linux

$ /usr/java/latest/bin/java -version
java version "1.6.0_25"
Java(TM) SE Runtime Environment (build 1.6.0_25-b06)
Java HotSpot(TM) 64-Bit Server VM (build 20.0-b11, mixed mode)

The winner is the orange bar which is the highest.

Running the Test

You can run the test using an executable JAR with the command:

java -Xmx1g -jar RollingNumberThroughputTest.jar

The test also validates that the code does what it should and is able to find non-thread-safe implementations by looking for incorrect math caused by concurrency bugs.

Conclusion

I found it very interesting how differently the results were on the 2 machines (operating systems and CPUs are very different, the JVM implementations are also different). In both cases though the AtomicCircularArray performed better, far better on the EC2 instance running the Sun JVM.

These tests provided me with the data to choose AtomicCircularArray and as mentioned above it is similar to what I’m now using in production.

Filed under: Code, Performance

I’ve spent the past day playing with Ruby and decided to test some basic performance – iterating and string parsing – to get an idea of what the performance is really like.

Ruby is not doing so well in my tests.

Note to Ruby Experts: If anyone can demonstrate what I’m doing wrong in my code or testing, I would love to be corrected.

My approach was to write the exact same code in Java and Ruby that loads up a file, reads each lines, tokenizes it into words using whitespace as the delimiter and counts up the tokens.

This avoids network or database IO and other external resources – except the filesystem which I don’t consider a significant variable in the test.

Further testing I’m planning on doing will test Rails, multi-threading and other common things I do in my apps.

On my laptop, a MacBook Pro 2.53Ghz Core 2 Duo with 4GB memory, the average times are:

• Ruby 1.8.6 app: 8022ms
• Java 5 app: 2986ms
• Java 6 app: 1443ms

Source Code

• FileReadParse.java
• file_read_parse.rb

After downloading, strip the .doc ending off of the files.

Program Output

macbook-pro:src benjc$ /System/Library/Frameworks/JavaVM.framework/Versions/1.6/Home/bin/java FileReadParse

Starting to read file…

The number of tokens is: 7764115

It took 1502 ms

macbook-pro:performance benjc$ ruby file_read_parse.rb

Starting to read file …

The number of tokens is: 7764115

It took 7999.955 ms

Filed under: Code, Performance

A simple test of performance for ConcurrentHashMap.

The insert is only a little slower, but the retrieval is 3x slower in this quick and dirty single-threaded test.

TimeUtil timer = new TimeUtil();

        timer.start();

        HashMap map = new HashMap();

        for (int i = 0; i < 1000000; i++) {

            map.put(i, i);

        }

        timer.printCurrent();

        timer.start();

        ConcurrentHashMap cmap = new ConcurrentHashMap();

        for (int i = 0; i < 1000000; i++) {

            cmap.put(i, i);

        }

        timer.printCurrent();

        timer = new TimeUtil();

        timer.start();

        map = new HashMap();

        for (int i = 0; i < 1000000; i++) {

            map.get(i);

        }

        timer.printCurrent();

        timer.start();

        cmap = new ConcurrentHashMap();

        for (int i = 0; i < 1000000; i++) {

            cmap.get(i);

        }

        timer.printCurrent();

Action completed in: 458 ms 0.458 seconds

Action completed in: 574 ms 0.574 seconds

Action completed in: 30 ms 0.03 seconds

Action completed in: 113 ms 0.113 seconds

Filed under: Code, Performance

I recently came across the problem of large resultsets being pulled into a java app via MySQL JDBC. I had dealt with this years ago but forgotten about it.

The test case below shows how the entire ResultSet is buffered in memory by default — which can be a “very bad thing” when dealing with hundreds or thousands of megabytes of data when it’s intended to be processed row by row.

Using mysql-connector-java-3.1.12-bin.jar and a JDK 5 with 32MB heap:

ET-COMMONS INFO: JVM MEMORY MONITOR => Total: 33  Used: 1  Free: 32

Retrieving data …

Ran out of memory at row: 0

java.lang.OutOfMemoryError: Java heap space

at com.mysql.jdbc.ByteArrayBuffer.getBytes(ByteArrayBuffer.java:128)

at com.mysql.jdbc.ByteArrayBuffer.readLenByteArray(ByteArrayBuffer.java:248)

at com.mysql.jdbc.MysqlIO.nextRow(MysqlIO.java:1304)

at com.mysql.jdbc.MysqlIO.readSingleRowSet(MysqlIO.java:2272)

at com.mysql.jdbc.MysqlIO.getResultSet(MysqlIO.java:423)

at com.mysql.jdbc.MysqlIO.readResultsForQueryOrUpdate(MysqlIO.java:1962)

at com.mysql.jdbc.MysqlIO.readAllResults(MysqlIO.java:1385)

at com.mysql.jdbc.MysqlIO.sqlQueryDirect(MysqlIO.java:1728)

at com.mysql.jdbc.Connection.execSQL(Connection.java:2988)

at com.mysql.jdbc.Connection.execSQL(Connection.java:2917)

at com.mysql.jdbc.Statement.executeQuery(Statement.java:824)

at JDBCTest.main(JDBCTest.java:26)

Using mysql-connector-java-5.1.6-bin.jar and the same JDK 5 with 32MB heap:

ET-COMMONS INFO: JVM MEMORY MONITOR => Total: 33  Used: 1  Free: 32

Retrieving data …

Ran out of memory at row: 0

java.lang.OutOfMemoryError: Java heap space

at com.mysql.jdbc.ByteArrayBuffer.getBytes(ByteArrayBuffer.java:128)

at com.mysql.jdbc.ByteArrayBuffer.readLenByteArray(ByteArrayBuffer.java:248)

at com.mysql.jdbc.MysqlIO.nextRow(MysqlIO.java:1304)

at com.mysql.jdbc.MysqlIO.readSingleRowSet(MysqlIO.java:2272)

at com.mysql.jdbc.MysqlIO.getResultSet(MysqlIO.java:423)

at com.mysql.jdbc.MysqlIO.readResultsForQueryOrUpdate(MysqlIO.java:1962)

at com.mysql.jdbc.MysqlIO.readAllResults(MysqlIO.java:1385)

at com.mysql.jdbc.MysqlIO.sqlQueryDirect(MysqlIO.java:1728)

at com.mysql.jdbc.Connection.execSQL(Connection.java:2988)

at com.mysql.jdbc.Connection.execSQL(Connection.java:2917)

at com.mysql.jdbc.Statement.executeQuery(Statement.java:824)

at JDBCTest.main(JDBCTest.java:26)

Thus we see that both the old and new versions of the MySQL JDBC driver by default attempt to load the entire resultset into memory.

I now increase the heap to 1GB to allow it to grow and find that the test query uses up > 500MB of heap before it even starts the rs.next() loop.

ET-COMMONS INFO: JVM MEMORY MONITOR => Total: 33  Used: 1  Free: 32

Retrieving data …

ET-COMMONS INFO: JVM MEMORY MONITOR => Total: 298  Used: 183  Free: 115

ET-COMMONS INFO: JVM MEMORY MONITOR => Total: 527  Used: 381  Free: 146

Starting to retrieve data. Memory Used: 517

Done retrieving data => 2318284   Memory Used: 551

Here is the code for this:

            ResultSet rs = conn.createStatement().executeQuery(“<sql query that returns lots of data>”);

            System.out.println(“Starting to retrieve data. Memory Used: “ + getUsedMemory());

            while (rs.next()) {

                rs.getString(1);

                rowsReturned++;

            }

            System.out.println(“Done retrieving data => “ + rowsReturned + ”   Memory Used: “  

+ getUsedMemory());

Thus you can see that the “executeQuery()” method loads up 500MB of data before it passes on the “rs.next()” loop. The full ResultSet is being buffered in memory.

Solution

To make the JDBC driver stream the results instead of buffer them all first we do the following:

            stmt.setFetchSize(Integer.MIN_VALUE);

Now it behaves like we expect it to … only 2MB used instead of > 500MB.

There are some caveats:

• http://javaquirks.blogspot.com/2007/12/mysql-streaming-result-set.html
• http://dev.mysql.com/doc/refman/5.0/en/connector-j-reference-implementation-notes.html

stmt = conn.createStatement(java.sql.ResultSet.TYPE_FORWARD_ONLY,
              java.sql.ResultSet.CONCUR_READ_ONLY);
stmt.setFetchSize(Integer.MIN_VALUE);

Filed under: Code, Performance

As I work on another set of indexes with large numbers of ints I’ve revisited how different storage mechanisms behave.

I’ve set the JVM to just over 64MB (70MB to be precise).

An int being 4 bytes means that 64MB of ints is as follows:

       int sixtyFourMB = 64 * 1024 * 1024 / 4;

That is 16,777,216 ints.

An int array can successfully store 64MB in the JVM meaning it is properly assigning each int to 4 bytes without overhead.

      int[] vals = new int[sixtyFourMB];

However, if you use ArrayList<Integer> you run out of memory after 3,392,918 ints being added.

That is 1/5 of what can be stored in the int[]!

Now, assigning the space to ArrayList is fine:

                ArrayList<Integer> ints = new ArrayList<Integer>(sixtyFourMB);

It’s when you add the Integer objects (int is cast to Integer behind the scenes in JDK 5) that it dies 1/5 in.

So the overhead is obviously in the Integer object.

I next try the Trove library and use the TIntArrayList.

If I leave it to assign its memory space by default, it runs out of memory at 10,485,760 (62%).

If however I tell it how many ints to expect it sizes itself properly and does not try to grow too large and fits the entire 64MB.

     TIntArrayList ints = new TIntArrayList(sixtyFourMB);

Thus, when backed by an int[] the memory can be efficiently stored, but when using an Object[] memory is very inefficient when attempting to store primitive ints.

Out of curiosity for what an Object() really does with memory I did the following:

            ArrayList<Object> ints = new ArrayList<Object>(sixtyFourMB);

            for (i = 0; i < sixtyFourMB; i++) {

                ints.add(null);

            }

That works, it all fits in memory.

If however I change the “null” to “new Object()” such as:

                ints.add(new Object());

It fails at 702065 … which means that the object[] has already taken up the space and there is no room for the objects on the heap.

Thus, for storage of simple data primitive arrays is MUCH more efficient.

If the flexibility of the Collections API is needed for dynamic manipulation of those arrays then use GNU Trove … but carefully or the dynamic sizing of the arrays in the background can cause a lot of waste.

An old but interesting article specifies memory usage by normal objects and classes:

http://www.roseindia.net/javatutorials/determining_memory_usage_in_java.shtml

Here are two points from that article of note:

1. The class takes up at least 8 bytes. So, if you say new Object(); you will allocate 8 bytes on the heap.
2. Each data member takes up 4 bytes, except for long and double which take up 8 bytes. Even if the data member is a byte, it will still take up 4 bytes! In addition, the amount of memory used is increased in 8 byte blocks. So, if you have a class that contains one byte it will take up 8 bytes for the class and 8 bytes for the data, totalling 16 bytes (groan!).

Filed under: Code, Performance

We did some simple testing on various sort algorithms we found and compared them with the Java Arrays.sort QuickSort implementation.

This is rudimentary testing since it’s not attempting to test all the variety of distributions of numbers that could exist and should be tested.

That being said, we are creating a collection of 50k, 500k, or 5million numbers randomly generated, and then cloning that collection to be sorted by each of the algorithms.

This first test had 1/2 the numbers as 4 digits, the other half as 5 digits meaning that in the larger collects, there should be a lot of duplicates.

The second test below had 1/2 the numbers as 4 digits, the other half as 8 digits.

This change in number of digits makes dramatic changes for FlashSort and completely breaks it.

Radix is just bad all the time … I have yet to figure out where it’s strength lies.

This is not thorough enough to make any conclusion, but I found it interesting nonetheless.

***Test 1 with 4 & 5 digit numbers***

—————————–
Run with 50k
—————————–
Arrays.sort(int) => 15ms
FlashSort.sort(int) => 11ms Valid: true
fastqs.sort(int) => 10ms Valid: true
eqsort.sort(int) => 16ms Valid: true
radix.sort(int) => 175ms Valid: true
radix.sort(int, 5) => 130ms Valid: true
—————————–
Run with 500k
—————————–
Arrays.sort(int) => 101ms
FlashSort.sort(int) => 56ms Valid: true
fastqs.sort(int) => 72ms Valid: true
eqsort.sort(int) => 96ms Valid: true
radix.sort(int) => 2164ms Valid: true
radix.sort(int, 5) => 1203ms Valid: true
—————————–
Run with 5million
—————————–
Arrays.sort(int) => 748ms
FlashSort.sort(int) => 717ms Valid: true
fastqs.sort(int) => 780ms Valid: true
eqsort.sort(int) => 1625ms Valid: true
radix.sort(int) => 82218ms Valid: true
radix.sort(int, 5) => 11387ms Valid: true
—————————–

***Test 1 with 4 & 8 digit numbers***

—————————–
Run with 50k
—————————–
Arrays.sort(int) => 14ms
FlashSort.sort(int) => 662ms Valid: true
fastqs.sort(int) => 10ms Valid: true
eqsort.sort(int) => 11ms Valid: true
radix.sort(int) => 294ms Valid: true
radix.sort(int, 8 ) => 225ms Valid: true
—————————–
Run with 500k
—————————–
Arrays.sort(int) => 91ms
FlashSort.sort(int) => 17832ms Valid: true
fastqs.sort(int) => 72ms Valid: true
eqsort.sort(int) => 95ms Valid: true
radix.sort(int) => 2066ms Valid: true
radix.sort(int, 8 ) => 2003ms Valid: true
—————————–
Run with 5million
—————————–
Arrays.sort(int) => 909ms
FlashSort.sort(int) => 197796ms Valid: true
fastqs.sort(int) => 825ms Valid: true
eqsort.sort(int) => 1494ms Valid: true
radix.sort(int) => 22957ms Valid: true
radix.sort(int, 8 ) => 20041ms Valid: true
—————————–

Filed under: Code, Performance