Optimise ChoiceField / MultipleChoiceField handling of duplicate submissions

[Jake Howard]

When a ChoiceField / MultipleChoiceField has 5 possible choices, but the form submits 25 values, the choices values are compared once per submitted value. If the submitted values are duplicates, the validation doesn't terminate early, but can still spend a lot of time unnecessarily validating values. This can be very slow when large (~30k) numbers of values are submitted.

A suggested fix is to only validate the unique submitted values (for example for val in set(value)).

This issue was reported to the Security Team, but deemed not a security issue due to the minimal impact when given reasonable input (in the bounds of the security policy).

[Jake Howard]

Note that validation that submissions (and choices) are unique is being handled in a separate feature request: ​https://github.com/django/new-features/issues/121

[Abhimanyu Singh Negi]

I’d like to work on this issue.

From what I understand the slowdown happens because duplicate submitted values are validated again and again. I’m thinking of validating only the unique values internally while keeping the original list unchanged so behaviour stays the same. I’ll add some tests too to make sure duplicates and invalid values are still handled correctly.

If this sounds reasonable and no one is working on this, i would like to assign the issue to myself.

[Natalia Bidart]

Replying to Abhimanyu Singh Negi:

I’d like to work on this issue.

From what I understand the slowdown happens because duplicate submitted values are validated again and again. I’m thinking of validating only the unique values internally while keeping the original list unchanged so behaviour stays the same. I’ll add some tests too to make sure duplicates and invalid values are still handled correctly.

If this sounds reasonable and no one is working on this, i would like to assign the issue to myself.

This ticket has been assigned already and has been reserved to evaluate under the Djangonaut Space umbrella. Sorry!

[Afenomamy]

Hello, I am Aina (Team Saturn) from Djangonaut Space. I will be looking at this ticket

[Jake Howard]

​PR

[Jacob Walls <jacobtylerwalls@…>]

In 26f8929:

Fixed #36913 -- Optimized MultipleChoiceField.validate().

[Jacob Walls <jacobtylerwalls@…>]

In 8b7ea2bc:

Refs #36913 -- Maintained error message determinism in MultipleChoiceField.validate().

Used Django's OrderedSet datastructure instead of set() in MultipleChoiceField.validate()
to prevent submission ordering from being discarded during validation.

Thanks to Jacob Walls, JaeHyuck Sa, Jake Howard and Simon Charette for
the reviews.