Quadratic performance on JObject construction with the JSON dsl due to extensive ::: usage…?

[Viktor Hedefalk]

The pattern suggested on the docs [1] with using ~ to construct JObjects seem to get me into this overloaded implicit:

https://github.com/lift/framework/blob/master/core/json/src/main/scala/net/liftweb/json/JsonAST.scala#L1169

which uses ::: making the construction of json objects O(n^2)

I haven't really analysed it with any profiling but both my inner implicit resolver and IntelliJ Idea seems to suggest that any JObject with more than two fields get to this ::: for all ~ chained after the first one.

Have anyone else noticed this or had performance issues with the DSL when constructing larger objects?

Cheers,

Viktor

[1] - https://github.com/lift/lift/tree/master/framework/lift-base/lift-json

[Viktor Hedefalk]

Missed to use the canonical code url. Might be good for the future: https://github.com/lift/framework/blob/de91b3aa1f66ae38b0ac0d3fda129d154ad75072/core/json/src/main/scala/net/liftweb/json/JsonAST.scala#L1169

[Antonio Salazar Cardozo]

I've never really used the DSL to construct larger objects (usually I'm reading them in, so

parsing, or decomposing a case class), but this definitely looks like it would be an issue.

Unfortunately lift-json has a built-in usage of List that's rather endemic in older Scala

libraries but can be quite costly as a decision in certain cases like this one. Since the List

is part of the public interface, it gets complicated to change without introducing additional

performance surprises.

In the meantime, the best approach is probably to avoid the DSL when building an object

with enough fields that your performance starts to suffer. The DSL operates on basic lift-json

data structures, so I think you can do this for just the pieces that need it.

Thanks,

Antonio

[Viktor Hedefalk]

Thanks for feedback!

Yeah, we decided we could probably use the implicit from pairs to JFields, but ditch the usage of ~ for explicit JObject constructors.

I guess the underlying List implementation is rather problematic as a basis for a builder pattern, but changing that would be really hard on backward compatibility I guess…

Thanks,
Viktor

[Antonio Salazar Cardozo]

Yeah… Doesn't mean I've not been thinking of how to do it though :)

The first step would probably be breaking API compatibility by making the interface

work with `Seq`, and keep the underlying implementation as `List`. We need a major

version for that though. Once we've done that, the underlying implementation can

use a `Vector` or whatever else, as needed.

Thanks,

Antonio