Author: etnu
Date: Fri Dec 5 03:49:32 2008
New Revision: 723717
URL: http://svn.apache.org/viewvc?rev=723717&view=rev
Log:
Improved JSON serialization library that is several times faster than the
closest alternative in CPU usage and that produces a few orders of magnitude
less garbage by avoiding making many allocations when escaping strings.
Included is a benchmark that demonstrates the CPU gap, but running it under a
profiler will show the far more dramatic difference in memory usage.
Added:
incubator/shindig/trunk/java/common/src/main/java/org/apache/shindig/common/JsonSerializer.java
incubator/shindig/trunk/java/common/src/test/java/org/apache/shindig/common/JsonSerializerTest.java
Added:
incubator/shindig/trunk/java/common/src/main/java/org/apache/shindig/common/JsonSerializer.java
URL:
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/common/src/main/java/org/apache/shindig/common/JsonSerializer.java?rev=723717&view=auto
==============================================================================
---
incubator/shindig/trunk/java/common/src/main/java/org/apache/shindig/common/JsonSerializer.java
(added)
+++
incubator/shindig/trunk/java/common/src/main/java/org/apache/shindig/common/JsonSerializer.java
Fri Dec 5 03:49:32 2008
@@ -0,0 +1,336 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.shindig.common;
+
+import org.json.JSONArray;
+import org.json.JSONObject;
+
+import java.io.IOException;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Map;
+
+/**
+ * Serializes a JSONObject.
+ *
+ * The methods here are designed to be substantially more CPU and memory
efficient than those found
+ * in org.json or net.sf.json. In profiling, the performance of both of these
libraries has been
+ * found to be woefully inadequate for large scale deployments.
+ *
+ * The append*() methods can be used to serialize directly into an Appendable,
such as an output
+ * stream. This avoids unnecessary copies to intermediate objects.
+ */
+public final class JsonSerializer {
+ // Multiplier to use for allocating the buffer.
+ private static final int BASE_MULTIPLIER = 256;
+
+ private static final String[] UNICODE_TABLE = createUnicodeTable();
+
+ private JsonSerializer() {}
+
+ private static String[] createUnicodeTable() {
+ int size = 0;
+ String[] table = new String['\u2100'];
+ for (char c = 0; c < table.length; ++c) {
+ String hex = Integer.toHexString(c);
+ table[c] = "u" + (("000" + hex).substring(hex.length() - 1));
+ size += 2 + (2 * table[c].length());
+ }
+ // Other characters can be sent with plain UTF-8 encoding.
+ return table;
+ }
+
+ /**
+ * Serialize a JSONObject. Does not guard against cyclical references.
+ */
+ public static String serialize(JSONObject object) {
+ StringBuilder buf = new StringBuilder(object.length() * BASE_MULTIPLIER);
+ try {
+ appendJsonObject(buf, object);
+ } catch (IOException e) {
+ // Can't happen.
+ }
+ return buf.toString();
+ }
+
+ /**
+ * Serializes a Map as a JSON object. Does not guard against cyclical
references.
+ */
+ public static String serialize(Map<String, ? extends Object> map) {
+ StringBuilder buf = new StringBuilder(map.size() * BASE_MULTIPLIER);
+ try {
+ appendMap(buf, map);
+ } catch (IOException e) {
+ // Can't happen.
+ }
+ return buf.toString();
+ }
+
+ /**
+ * Serializes a Collection as a JSON array. Does not guard against cyclical
references.
+ */
+ public static String serialize(Collection<? extends Object> collection) {
+ StringBuilder buf = new StringBuilder(collection.size() * BASE_MULTIPLIER);
+ try {
+ appendCollection(buf, collection);
+ } catch (IOException e) {
+ // Can't happen.
+ }
+ return buf.toString();
+ }
+
+ /**
+ * Serializes an array as a JSON array. Does not guard against cyclical
references
+ */
+ public static String serialize(Object[] array) {
+ StringBuilder buf = new StringBuilder(array.length * BASE_MULTIPLIER);
+ try {
+ appendArray(buf, array);
+ } catch (IOException e) {
+ // Can't happen.
+ }
+ return buf.toString();
+ }
+
+ /**
+ * Serializes a JSON array. Does not guard against cyclical references
+ */
+ public static String serialize(JSONArray array) {
+ StringBuilder buf = new StringBuilder(array.length() * BASE_MULTIPLIER);
+ try {
+ appendJsonArray(buf, array);
+ } catch (IOException e) {
+ // Can't happen.
+ }
+ return buf.toString();
+ }
+
+ /**
+ * Appends a value to the buffer.
+ *
+ * @throws IOException If [EMAIL PROTECTED] Appendable#append(char)} throws
an exception.
+ */
+ @SuppressWarnings("unchecked")
+ public static void append(Appendable buf, Object value) throws IOException {
+ if (value == null) {
+ buf.append("null");
+ } else if (value instanceof JSONObject) {
+ appendJsonObject(buf, (JSONObject)value);
+ } else if (value instanceof String) {
+ appendString(buf, (String)value);
+ } else if (value instanceof Number || value instanceof Boolean) {
+ buf.append(value.toString());
+ } else if (value instanceof JSONArray) {
+ buf.append(value.toString());
+ } else if (value instanceof Map) {
+ appendMap(buf, (Map<String, Object>)value);
+ } else if (value instanceof Collection) {
+ appendCollection(buf, (Collection<Object>)value);
+ } else if (value.getClass().isArray()) {
+ appendArray(buf, (Object[])value);
+ } else {
+ appendString(buf, value.toString());
+ }
+ }
+
+ /**
+ * Appends an array to the buffer.
+ *
+ * @throws IOException If [EMAIL PROTECTED] Appendable#append(char)} throws
an exception.
+ */
+ public static void appendArray(Appendable buf, Object[] array) throws
IOException {
+ buf.append('[');
+ boolean firstDone = false;
+ for (Object o : array) {
+ if (firstDone) {
+ buf.append(',');
+ } else {
+ firstDone = true;
+ }
+ append(buf, o);
+ }
+ buf.append(']');
+ }
+
+ /**
+ * Append a JSONArray to the buffer.
+ * @throws IOException If [EMAIL PROTECTED] Appendable#append(char)} throws
an exception.
+ */
+ public static void appendJsonArray(Appendable buf, JSONArray array) throws
IOException {
+ buf.append('[');
+ boolean firstDone = false;
+ for (int i = 0, j = array.length(); i < j; ++i) {
+ if (firstDone) {
+ buf.append(',');
+ } else {
+ firstDone = true;
+ }
+ append(buf, array.opt(i));
+ }
+ buf.append(']');
+ }
+
+ /**
+ * Appends a Collection to the buffer.
+ *
+ * @throws IOException If [EMAIL PROTECTED] Appendable#append(char)} throws
an exception.
+ */
+ public static void appendCollection(Appendable buf, Collection<? extends
Object> collection)
+ throws IOException {
+ buf.append('[');
+ boolean firstDone = false;
+ for (Object o : collection) {
+ if (firstDone) {
+ buf.append(',');
+ } else {
+ firstDone = true;
+ }
+ append(buf, o);
+ }
+ buf.append(']');
+ }
+
+ /**
+ * Appends a Map to the buffer.
+ *
+ * @throws IOException If [EMAIL PROTECTED] Appendable#append(char)} throws
an exception.
+ */
+ public static void appendMap(Appendable buf, Map<String, ? extends Object>
map)
+ throws IOException {
+ buf.append('{');
+ boolean firstDone = false;
+ for (Map.Entry<String, ? extends Object> entry : map.entrySet()) {
+ if (firstDone) {
+ buf.append(',');
+ } else {
+ firstDone = true;
+ }
+ appendString(buf, entry.getKey());
+ buf.append(':');
+ append(buf, entry.getValue());
+ }
+ buf.append('}');
+ }
+
+ /**
+ * Appends a JSONObject to the buffer.
+ *
+ * @throws IOException If [EMAIL PROTECTED] Appendable#append(char)} throws
an exception.
+ */
+ @SuppressWarnings("unchecked")
+ public static void appendJsonObject(Appendable buf, JSONObject object)
throws IOException {
+ buf.append('{');
+ Iterator<String> keys = object.keys();
+ boolean firstDone = false;
+ while (keys.hasNext()) {
+ if (firstDone) {
+ buf.append(',');
+ } else {
+ firstDone = true;
+ }
+ String key = keys.next();
+ appendString(buf, key);
+ buf.append(':');
+ append(buf, object.opt(key));
+ }
+ buf.append('}');
+ }
+
+ /**
+ * Appends a string to the buffer. The string will be JSON encoded and
enclosed in quotes.
+ *
+ * @throws IOException If [EMAIL PROTECTED] Appendable#append(char)} throws
an exception.
+ */
+ public static void appendString(Appendable buf, CharSequence string) throws
IOException {
+ if (string == null || string.length() == 0) {
+ buf.append("\"\"");
+ return;
+ }
+
+ char previous, current = 0;
+ buf.append('"');
+ for (int i = 0, j = string.length(); i < j; ++i) {
+ previous = current;
+ current = string.charAt(i);
+ switch (current) {
+ case '\\':
+ case '"':
+ buf.append('\\');
+ buf.append(current);
+ break;
+ case '/':
+ if (previous == '<') {
+ buf.append('\\');
+ }
+ buf.append(current);
+ break;
+ default:
+ if (current < ' ' || (current >= '\u0080' && current < '\u00a0') ||
+ (current >= '\u2000' && current < '\u2100')) {
+ buf.append('\\');
+ switch (current) {
+ case '\b':
+ buf.append('b');
+ break;
+ case '\t':
+ buf.append('t');
+ break;
+ case '\n':
+ buf.append('n');
+ break;
+ case '\f':
+ buf.append('f');
+ break;
+ case '\r':
+ buf.append('r');
+ break;
+ default:
+ // The three possible alternative approaches for dealing with
unicode characters are
+ // as follows:
+ // Method 1 (from json.org.JSONObject)
+ // 1. Append "000" + Integer.toHexString(current)
+ // 2. Truncate this value to 4 digits by using
value.substring(value.length() - 4)
+ //
+ // Method 2 (from net.sf.json.JSONObject)
+ // This method is fairly unique because the entire thing uses
an intermediate fixed
+ // size buffer of 1KB. It's an interesting approach, but
overall performs worse than
+ // org.json
+ // 1. Append "000" + Integer.toHexString(current)
+ // 2. Append value.charAt(value.length() - 4)
+ // 2. Append value.charAt(value.length() - 3)
+ // 2. Append value.charAt(value.length() - 2)
+ // 2. Append value.charAt(value.length() - 1)
+ //
+ // Method 3 (previous experiment)
+ // 1. Calculate Integer.hexString(current)
+ // 2. for (int i = 0; i < 4 - value.length(); ++i) {
buf.append('0'); }
+ // 3. buf.append(value)
+ //
+ // Of these, the second proved fastest. The current
implementation performs slightly
+ // faster than the second in the benchmark found in
JsonSerializerTest.
+ buf.append(UNICODE_TABLE[current]);
+ }
+ } else {
+ buf.append(current);
+ }
+ }
+ }
+ buf.append('"');
+ }
+}
Added:
incubator/shindig/trunk/java/common/src/test/java/org/apache/shindig/common/JsonSerializerTest.java
URL:
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/common/src/test/java/org/apache/shindig/common/JsonSerializerTest.java?rev=723717&view=auto
==============================================================================
---
incubator/shindig/trunk/java/common/src/test/java/org/apache/shindig/common/JsonSerializerTest.java
(added)
+++
incubator/shindig/trunk/java/common/src/test/java/org/apache/shindig/common/JsonSerializerTest.java
Fri Dec 5 03:49:32 2008
@@ -0,0 +1,256 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.shindig.common;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import com.google.common.collect.Maps;
+
+import org.apache.commons.lang.StringUtils;
+import org.json.JSONArray;
+import org.json.JSONObject;
+import org.junit.Test;
+
+import java.lang.reflect.Method;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Map;
+
+/**
+ * Tests for JsonSerializer.
+ *
+ * This class may be executed to perform micro benchmarks comparing the
performance of the
+ * serializer with that of json.org and net.sf.json.
+ */
+public class JsonSerializerTest {
+
+ @Test
+ public void serializeSimpleJsonObject() throws Exception {
+ JSONObject json = new JSONObject("{\"foo\":\"bar\"}");
+ assertTrue("Did not produce results matching reference implementation.",
+ jsonEquals(json.toString(), JsonSerializer.serialize(json)));
+ }
+
+ @Test
+ public void serializeSimpleMap() throws Exception {
+ Map<String, String> map = Maps.immutableMap("hello", "world", "foo",
"bar");
+ assertTrue("Did not produce results matching reference implementation.",
+ jsonEquals(new JSONObject(map).toString(),
JsonSerializer.serialize(map)));
+ }
+
+ @Test
+ public void serializeSimpleCollection() throws Exception {
+ Collection<String> collection = Arrays.asList("foo", "bar", "baz");
+ assertEquals("[\"foo\",\"bar\",\"baz\"]",
JsonSerializer.serialize(collection));
+ }
+
+ @Test
+ public void serializeArray() throws Exception {
+ String[] array = new String[] {"foo", "bar", "baz"};
+ assertEquals("[\"foo\",\"bar\",\"baz\"]", JsonSerializer.serialize(array));
+ }
+
+ @Test
+ public void serializeJsonArray() throws Exception {
+ JSONArray array = new JSONArray(new String[] {"foo", "bar", "baz"});
+ assertEquals("[\"foo\",\"bar\",\"baz\"]", JsonSerializer.serialize(array));
+ }
+
+ @Test
+ public void serializeMixedObjects() throws Exception {
+ Map<String, ? extends Object> map = Maps.immutableMap(
+ "integer", Integer.valueOf(100),
+ "double", Double.valueOf(233333333333.7d),
+ "boolean", Boolean.TRUE,
+ "map", Maps.immutableMap("hello", "world", "foo", "bar"),
+ "string", "hello!");
+ assertTrue("Did not produce results matching reference implementation.",
+ jsonEquals(new JSONObject(map).toString(),
JsonSerializer.serialize(map)));
+ }
+
+ @Test
+ public void serializeMixedArray() throws Exception {
+ Collection<Object> data = Arrays.asList(
+ "integer", Integer.valueOf(100),
+ "double", Double.valueOf(233333333333.7d),
+ "boolean", Boolean.TRUE,
+ Arrays.asList("one", "two", "three"),
+ new JSONArray(new String[] {"foo", "bar"}),
+ "string", "hello!");
+ assertEquals(new JSONArray(data).toString(),
JsonSerializer.serialize(data));
+ }
+
+ @Test
+ public void emptyString() throws Exception {
+ StringBuilder builder = new StringBuilder();
+ JsonSerializer.appendString(builder, "");
+
+ assertEquals("\"\"", builder.toString());
+ }
+
+ @Test
+ public void escapeSequences() throws Exception {
+ StringBuilder builder = new StringBuilder();
+ JsonSerializer.appendString(builder, "\t\r value
\\\foo\b\uFFFF\uBCAD\n\u0083");
+
+ assertEquals("\"\\t\\r value \\\\\\foo\\b\uFFFF\uBCAD\\n\\u0083\"",
builder.toString());
+ }
+
+ private static String avg(long start, long end, long runs) {
+ double delta = end - start;
+ return String.format("%f5", delta / runs);
+ }
+
+ private static String runJsonOrgTest(Map<String, Object> data, int
iterations) {
+ org.json.JSONObject object = new org.json.JSONObject(data);
+ long start = System.currentTimeMillis();
+ String result = null;
+ for (int i = 0; i < iterations; ++i) {
+ result = object.toString();
+ }
+ System.out.println("json.org: " + avg(start, System.currentTimeMillis(),
iterations) + "ms");
+ return result;
+ }
+
+ private static String runSerializerTest(Map<String, Object> data, int
iterations) {
+ long start = System.currentTimeMillis();
+ String result = null;
+ for (int i = 0; i < iterations; ++i) {
+ result = JsonSerializer.serialize(data);
+ }
+ System.out.println("serializer: " + avg(start, System.currentTimeMillis(),
iterations) + "ms");
+ return result;
+ }
+
+ private static String runNetSfJsonTest(Map<String, Object> data, int
iterations) {
+ net.sf.json.JSONObject object = net.sf.json.JSONObject.fromObject(data);
+ long start = System.currentTimeMillis();
+ String result = null;
+ for (int i = 0; i < iterations; ++i) {
+ result = object.toString();
+ }
+ System.out.println("net.sf.json: " + avg(start,
System.currentTimeMillis(), iterations) + "ms");
+ return result;
+ }
+
+ public static Map<String, Object> perfComparison100SmallValues() {
+ Map<String, Object> data = Maps.newHashMap();
+ for (int i = 0; i < 100; ++i) {
+ data.put("key-" + i, "small value");
+ }
+
+ return data;
+ }
+
+ public static Map<String, Object> perfComparison1000SmallValues() {
+ Map<String, Object> data = Maps.newHashMap();
+ for (int i = 0; i < 1000; ++i) {
+ data.put("key-" + i, "small value");
+ }
+
+ return data;
+ }
+
+ public static Map<String, Object> perfComparison100LargeValues() {
+ Map<String, Object> data = Maps.newHashMap();
+ for (int i = 0; i < 100; ++i) {
+ data.put("key-" + i, StringUtils.repeat("small value", 100));
+ }
+ return data;
+ }
+
+ public static Map<String, Object> perfComparison10LargeValuesAndEscapes() {
+ Map<String, Object> data = Maps.newHashMap();
+ for (int i = 0; i < 10; ++i) {
+ data.put("key-" + i, StringUtils.repeat("\tsmall\r value
\\foo\b\uFFFF\uBCAD\n\u0083", 100));
+ }
+ return data;
+ }
+
+ public static Map<String, Object> perfComparison100Arrays() {
+ Map<String, Object> data = Maps.newHashMap();
+ String[] array = new String[] {
+ "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
"ten"
+ };
+
+ for (int i = 0; i < 100; ++i) {
+ data.put("key-" + i, array);
+ }
+
+ return data;
+ }
+
+ private static boolean jsonEquals(JSONObject left, JSONObject right) {
+ if (left.length() != right.length()) {
+ return false;
+ }
+ for (String name : JSONObject.getNames(left)) {
+ Object leftValue = left.opt(name);
+ Object rightValue = right.opt(name);
+ if (leftValue instanceof JSONObject) {
+ if (!jsonEquals((JSONObject)leftValue, (JSONObject)rightValue)) {
+ return false;
+ }
+ } else if (leftValue instanceof JSONArray) {
+ JSONArray leftArray = (JSONArray)leftValue;
+ JSONArray rightArray = (JSONArray)rightValue;
+ for (int i = 0; i < leftArray.length(); ++i) {
+ if (!(leftArray.opt(i).equals(rightArray.opt(i)))) {
+ return false;
+ }
+ }
+ } else if (!leftValue.equals(rightValue)) {
+ System.out.println("Not a match: " + leftValue + " != " + rightValue);
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static boolean jsonEquals(String reference, String comparison)
throws Exception {
+ return jsonEquals(new JSONObject(reference), new JSONObject(comparison));
+ }
+
+ public static void main(String[] args) throws Exception {
+ int iterations = args.length > 0 ? Integer.parseInt(args[0]) : 1000;
+ System.out.println("Running tests with " + iterations + " iterations.");
+
+ for (Method method : JsonSerializerTest.class.getMethods()) {
+ if (method.getName().startsWith("perfComparison")) {
+ Map<String, Object> data = (Map<String, Object>)method.invoke(null);
+ System.out.println("Running: " + method.getName());
+
+ String jsonOrg = runJsonOrgTest(data, iterations);
+ String serializer = runSerializerTest(data, iterations);
+ String netSfJson = runNetSfJsonTest(data, iterations);
+
+ if (!jsonEquals(jsonOrg, serializer)) {
+ System.out.println("Serializer did not produce results matching the
reference impl.");
+ }
+
+ if (!jsonEquals(jsonOrg, netSfJson)) {
+ System.out.println("net.sf.json did not produce results matching the
reference impl.");
+ }
+ System.out.println("-----------------------");
+ }
+ }
+ System.out.println("Done");
+ }
+}
