Create a generic interface for the vector-backed arena

[LegNeato]

In #202 we added a custom vector-backed arena to increase perf. We should make a generic interface for the arena implementation so we can swap out different crates from crates.io and benchmark.

/cc @weiznich

[weiznich]

1. The PR does already introduce such an interface by wrapping the actual implementation into the Object type. All other parts of juniper and all external code could only use the public methods on those type. Therefore it is possible to swap out the actual implementation. So this interface already exists. (Or I miss something important…)

2. I would not call the current implementation a arena. It continues to be a map (from the outside it behaves like one). I just used a Vec<(Key, Value)> there because for a small number of elements this is faster. The argumentation for this is like following:

• For large collections there are the following worst case complexities are assumed:
  • HashMap/IndexMap:
    • Insert a field O(1)
    • Get a field O(1)
  • Vec:
    • Insert a field O(1)
    • Get a field O(n)

First assumption: Our collections are not large, but contain only a few elements (maybe up to 50?)
In that case the asymptotic complexity is quite meaningless because other effects are dominating. In this case this are:

• Cache locality:
  A vector is a homogenous chunk of memory. Therefore the cpu can easily predict where the next element could be found (It will just load the whole (or a big part) of the vector into a local cache). For hash maps this is not given. So a each lookup may result into a fetch from ram.
• Constant factors in asymptotic complexity.
  Normally those factors are ignored because they do not matter for large numbers of n. (O(n^2) is bigger than O(n) and O(1000n) for large numbers of n). For small numbers they matter 😉
  In our case a hash map will do additional work on insert (hashing the key).

Overall this leads to a performance improvement by just using a Vec<(Key, Value)> as "map".

The second part of that performance improvement was preallocating a fixed number of entries in that data structure. This saves the time needed to reallocate a bigger container if there was not enough space. This change was quite easy because for every place where we construct a new object we should already know how many fields will be added.

[LegNeato]

Nope, it was early in the morning here and I wasn't really paying attention. Thank you for digging into this and the insightful comment! I wonder if there is any benefit to using https://github.com/servo/rust-smallvec...

Also, this reminds me I need to get cargo bench back up.

[weiznich]

I wonder if there is any benefit to using https://github.com/servo/rust-smallvec...

That could be useful for some workloads, but I'm not sure if that will generally into wins. Someone needs do some meaningful benchmarks for this.

Edit:

Just tried to use a SmallVec: It won't work because we will create a recursive type without indirection…