Since a few users will want to know the specifics:

Associative lists use a temporary struct that gets allocated and freed whenever items are added/removed. The new optimization reuses them. Strings, ID arrays, vars, and datums already do something similar.

Strings had an imbalance appearing in the tree on deletion. Our old procedure was to replace the dying node with its left branch, then reattach the right branch wherever it should go. This required an additional call to our traversal routine and also could cause major imbalances. The new version will replace the dying node with its immediate neighbor in the sort order (favoring the left), which involves much less traversal and doesn't make the balance any worse.