Add a "cost" concept to validations

[adriangb]

The idea here would be to first validate the less costly options. E.g. in unions we'd start with the less costly option, in typed-dict we'd go through the fields in order of cost.

We could do this by adding a cost to BuildValidator:

trait BuildValidator {
  fn cost(&self) -> usize {
      // return the max usize by default
  }

Then at build time we can "sort" choices by least cost.

Costs can be calculated recursively, e.g. a typed-dict schema can be the sum of the cost of it's fields while a list can be the cost of it's item validator * some fixed heuristic number like 1000 to represent a "medium sized list" (this could even be adjusted dynamically at runtime, but that's a matter for muuuuch in the future).

In combination with the idea of #430 this could go a long way towards making a non-tagged union much more performant. You can imagine that if we have a union like:

class Branch1:
    x: int
   y: List[Expensive]

class Branch2:
   x: date
   y: List[Expensive]

We would always validate the x field first and short circuit as soon as that fails. So passing in {"x": "2023-03-10", "y": [...]} would be very performant.

[dmontagu]

One thing to keep in mind is that the most performant choice also depends on the frequency with which different union members are parsed. E.g., imagine you have two union items that might be validated, call them Case1 and Case2, and Case1 is somewhat more costly to validate than Case2, but in your application Case1 occurs much more frequently than Case2. In that case, it would probably be more performant overall to validate Case1 before Case2, even if it would be better to do Case2 first if the balance was 50/50.

I think the current approach of validating in the order that items are listed in the union gives the user control over this, and while that might leave performance on the table for people not in the know, I would be concerned that if we aren't careful, we'll take away an important optimization lever for "power users", or add some more annoyingly-complex-to-use-and-maintain configuration options.

---

Another alternative that I think might actually be a better choice would be to add some lightweight form of branch prediction to the UnionValidator on the Rust side.

I actually think that might be more likely to result in performance wins across applications regardless of usage pattern, and I don't think it should need to be very complex. Admittedly I am not very experienced with the topic.

[adriangb]

I think the current approach of validating in the order that items are listed in the union gives the user control over this

Great point. That may be more important than any other consideration!

My concern with a branch prediction type approach or anything else that relies on runtime data would be that it has a runtime cost. I am also not experienced with those sorts of things.

[dmontagu]

I would expect that the runtime cost of managing some kind of simplistic data structure for tracking which union case/cases are most likely to be hit would be orders of magnitude lower overhead than attempting validation of a single variant of a BaseModel, considering all the python objects that need to be created/functions that might need to be called. It's just the kind of thing where even if the logic is a bit complicated, it will compile down very tight. (Of course, for the overhead to be negligible, this is making the absolutely critical assumption that it is implemented in Rust, which it would be.)

The complexity of the relevant logic might rule this out as a thing to try implementing in the short term, but in principle I don't think this should be much harder than implementing the appropriate data structure. (Again, not to say that that would be easy.. 😄)

The biggest argument against even trying something like this would be that it could make it less deterministic what happens if you try to parse objects that could pass validation as multiple choices. (Right now, you know it will always be whichever is listed first.) I guess this is also an issue for any approach to using "cost" estimates to choose the union validation order.

[adriangb]

Great stuff. Agreed on everything. I think all of this is like you say not something to attempt in the short term.