Exponential behavior in Relax NG validation of optional attributes
The RelaxNG validators exhibits what looks a lot like exponential behaviour when validating optional attributes, as a function of the number of attributes present (not those defined in the schema).
There are some oddities / variations, but relaxng validation performances reliably slow down superlinearly as more optional attributes get added to the document (not the schema), a serious inflexion point occurs around 15 where the validation of a trivial element gets above a second.
The attached test case is a Python script using libxml2 through lxml which:
- creates a schema with 26 attributes, with 0-10 of these being required (and the rest optional), the one script argument is the number of required attributes (default 0)
- create a document with 10+ attributes (starting with the required ones if any)
- check how many attributes it takes to exceed 1s validation time
On my machine the issue occurs at 14~15 optional attributes: if all attributes are optional it's 15, if 5 attributes are required it's 20, if 10 attributes are required it's 24-25.
And of course this is the usual trap of a superlinear slowdown, once past the "hum" slowdown quickly becomes extreme even though the schema doesn't change in any way (only some documents which may be dynamically generated).
demo runs:
$ python test.py 0
0 required of 26 attributes
Validating 10 attributes... 0.00217s
Validating 11 attributes... 0.008s
Validating 12 attributes... 0.0338s
Validating 13 attributes... 0.147s
Validating 14 attributes... 0.562s
Validating 15 attributes... 2.93s
bailing
$ python test.py 5
5 required of 26 attributes
Validating 10 attributes... 2.03e-05s
Validating 11 attributes... 3e-05s
Validating 12 attributes... 8.23e-05s
Validating 13 attributes... 0.000229s
Validating 14 attributes... 0.000788s
Validating 15 attributes... 0.00281s
Validating 16 attributes... 0.0106s
Validating 17 attributes... 0.0443s
Validating 18 attributes... 0.165s
Validating 19 attributes... 0.648s
Validating 20 attributes... 4.08s
bailing
$ python test.py 10
10 required of 26 attributes
Validating 10 attributes... 8.82e-06s
Validating 11 attributes... 4.29e-06s
Validating 12 attributes... 4.29e-06s
Validating 13 attributes... 4.53e-06s
Validating 14 attributes... 6.68e-06s
Validating 15 attributes... 1.31e-05s
Validating 16 attributes... 3.34e-05s
Validating 17 attributes... 8.92e-05s
Validating 18 attributes... 0.000276s
Validating 19 attributes... 0.000985s
Validating 20 attributes... 0.00344s
Validating 21 attributes... 0.013s
Validating 22 attributes... 0.0591s
Validating 23 attributes... 0.294s
Validating 24 attributes... 1.05s
bailing