diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/main/scala/spray/json/JsValue.scala | 7 | ||||
-rw-r--r-- | src/main/scala/spray/json/JsonParser.scala | 7 | ||||
-rw-r--r-- | src/test/scala/spray/json/HashCodeCollider.scala | 26 | ||||
-rw-r--r-- | src/test/scala/spray/json/JsonParserSpec.scala | 30 | ||||
-rw-r--r-- | src/test/scala/spray/json/PrettyPrinterSpec.scala | 19 |
5 files changed, 76 insertions, 13 deletions
diff --git a/src/main/scala/spray/json/JsValue.scala b/src/main/scala/spray/json/JsValue.scala index 7cd8cd8..9ed94da 100644 --- a/src/main/scala/spray/json/JsValue.scala +++ b/src/main/scala/spray/json/JsValue.scala @@ -19,6 +19,7 @@ package spray.json import collection.immutable +import scala.collection.immutable.TreeMap /** * The general type of a JSON AST node. @@ -53,10 +54,10 @@ case class JsObject(fields: Map[String, JsValue]) extends JsValue { def getFields(fieldNames: String*): immutable.Seq[JsValue] = fieldNames.toIterator.flatMap(fields.get).toList } object JsObject { - val empty = JsObject(Map.empty[String, JsValue]) - def apply(members: JsField*) = new JsObject(Map(members: _*)) + val empty = JsObject(TreeMap.empty[String, JsValue]) + def apply(members: JsField*): JsObject = new JsObject(TreeMap(members: _*)) @deprecated("Use JsObject(JsValue*) instead", "1.3.0") - def apply(members: List[JsField]) = new JsObject(Map(members: _*)) + def apply(members: List[JsField]): JsObject = apply(members: _*) } /** diff --git a/src/main/scala/spray/json/JsonParser.scala b/src/main/scala/spray/json/JsonParser.scala index f29c062..ded8d6a 100644 --- a/src/main/scala/spray/json/JsonParser.scala +++ b/src/main/scala/spray/json/JsonParser.scala @@ -18,9 +18,11 @@ package spray.json import scala.annotation.{switch, tailrec} import java.lang.{StringBuilder => JStringBuilder} -import java.nio.{CharBuffer, ByteBuffer} +import java.nio.{ByteBuffer, CharBuffer} import java.nio.charset.Charset +import scala.collection.immutable.TreeMap + /** * Fast, no-dependency parser for JSON as defined by http://tools.ietf.org/html/rfc4627. */ @@ -89,8 +91,7 @@ class JsonParser(input: ParserInput, settings: JsonParserSettings = JsonParserSe val nextMap = map.updated(key, jsValue) if (ws(',')) members(nextMap) else nextMap } - var map = Map.empty[String, JsValue] - map = members(map) + val map = members(TreeMap.empty[String, JsValue]) require('}') JsObject(map) } else { diff --git a/src/test/scala/spray/json/HashCodeCollider.scala b/src/test/scala/spray/json/HashCodeCollider.scala new file mode 100644 index 0000000..57388b9 --- /dev/null +++ b/src/test/scala/spray/json/HashCodeCollider.scala @@ -0,0 +1,26 @@ +package spray.json + +/** + * Helper that creates strings that all share the same hashCode == 0. + * + * Adapted from MIT-licensed code by Andriy Plokhotnyuk + * at https://github.com/plokhotnyuk/jsoniter-scala/blob/26b5ecdd4f8c2ab7e97bd8106cefdda4c1e701ce/jsoniter-scala-benchmark/src/main/scala/com/github/plokhotnyuk/jsoniter_scala/macros/HashCodeCollider.scala#L6. + */ +object HashCodeCollider { + val visibleChars = (33 until 127).filterNot(c => c == '\\' || c == '"') + def asciiChars: Iterator[Int] = visibleChars.toIterator + def asciiCharsAndHash(previousHash: Int): Iterator[(Int, Int)] = visibleChars.toIterator.map(c => c -> (previousHash + c) * 31) + + /** Creates an iterator of Strings that all have hashCode == 0 */ + def zeroHashCodeIterator(): Iterator[String] = + for { + (i0, h0) <- asciiCharsAndHash(0) + (i1, h1) <- asciiCharsAndHash(h0) + (i2, h2) <- asciiCharsAndHash(h1) if (((h2 + 32) * 923521) ^ ((h2 + 127) * 923521)) < 0 + (i3, h3) <- asciiCharsAndHash(h2) if (((h3 + 32) * 29791) ^ ((h3 + 127) * 29791)) < 0 + (i4, h4) <- asciiCharsAndHash(h3) if (((h4 + 32) * 961) ^ ((h4 + 127) * 961)) < 0 + (i5, h5) <- asciiCharsAndHash(h4) if (((h5 + 32) * 31) ^ ((h5 + 127) * 31)) < 0 + (i6, h6) <- asciiCharsAndHash(h5) if ((h6 + 32) ^ (h6 + 127)) < 0 + (i7, h7) <- asciiCharsAndHash(h6) if h6 + i7 == 0 + } yield new String(Array(i0, i1, i2, i3, i4, i5, i6, i7).map(_.toChar)) +} diff --git a/src/test/scala/spray/json/JsonParserSpec.scala b/src/test/scala/spray/json/JsonParserSpec.scala index e5645a4..36c9726 100644 --- a/src/test/scala/spray/json/JsonParserSpec.scala +++ b/src/test/scala/spray/json/JsonParserSpec.scala @@ -84,6 +84,36 @@ class JsonParserSpec extends Specification { ) list.map(_.asInstanceOf[JsObject].fields("questions").asInstanceOf[JsArray].elements.size) === List.fill(20)(100) } + "not show bad performance characteristics when object keys' hashCodes collide" in { + val numKeys = 10000 + val value = "null" + + val regularKeys = Iterator.from(1).map(i => s"key_$i").take(numKeys) + val collidingKeys = HashCodeCollider.zeroHashCodeIterator().take(numKeys) + + def createJson(keys: Iterator[String]): String = keys.mkString("""{"""", s"""":$value,"""", s"""":$value}""") + + def nanoBench(block: => Unit): Long = { + // great microbenchmark (the comment must be kept, otherwise it's not true) + val f = block _ + + // warmup + (1 to 10).foreach(_ => f()) + + val start = System.nanoTime() + f() + val end = System.nanoTime() + end - start + } + + val regularJson = createJson(regularKeys) + val collidingJson = createJson(collidingKeys) + + val regularTime = nanoBench { JsonParser(regularJson) } + val collidingTime = nanoBench { JsonParser(collidingJson) } + + collidingTime / regularTime must be < 2L // speed must be in same order of magnitude + } "produce proper error messages" in { def errorMessage(input: String) = diff --git a/src/test/scala/spray/json/PrettyPrinterSpec.scala b/src/test/scala/spray/json/PrettyPrinterSpec.scala index 6354ef0..b547f59 100644 --- a/src/test/scala/spray/json/PrettyPrinterSpec.scala +++ b/src/test/scala/spray/json/PrettyPrinterSpec.scala @@ -23,7 +23,7 @@ class PrettyPrinterSpec extends Specification { "The PrettyPrinter" should { "print a more complicated JsObject nicely aligned" in { - val JsObject(fields) = JsonParser { + val js = JsonParser { """{ | "Boolean no": false, | "Boolean yes":true, @@ -40,7 +40,12 @@ class PrettyPrinterSpec extends Specification { | "zero": 0 |}""".stripMargin } - PrettyPrinter(JsObject(ListMap(fields.toSeq.sortBy(_._1):_*))) mustEqual { + def fixedFieldOrder(js: JsValue): JsValue = js match { + case JsObject(fields) => JsObject(ListMap(fields.toSeq.sortBy(_._1).map { case (k, v) => (k, fixedFieldOrder(v)) }:_*)) + case x => x + } + + PrettyPrinter(fixedFieldOrder(js)) mustEqual { """{ | "Boolean no": false, | "Boolean yes": true, @@ -50,17 +55,17 @@ class PrettyPrinterSpec extends Specification { | "number": -0.000012323424, | "simpleKey": "some value", | "sub object": { - | "sub key": 26.5, | "a": "b", | "array": [1, 2, { - | "yes": 1, - | "no": 0 - | }, ["a", "b", null], false] + | "no": 0, + | "yes": 1 + | }, ["a", "b", null], false], + | "sub key": 26.5 | }, | "zero": 0 |}""".stripMargin } } } - + }
\ No newline at end of file |