Description

The documentation on dictionaries states that iteration (for loops, keys, pairs, ...) happens in insertion order. This is true except for the remove method, which does not maintain insertion order.

Having looked at the sources a bit, this is a matter of using IndexMap::swap_remove (aka IndexMap::remove) vs IndexMap::shift_remove). As the names suggest, swap_remove doesn't maintain order but is a single swap in $O(1)$ whereas shift_remove has to shift down the element to maintain order, resulting in $O(N)$.

I'm honestly not sure if the perf difference is measurable considering the average side of dictionaries in typst, but I'm also not sure we care that much about insertion order. In any case this is either a language bug or a documentation bug, and might be worth discussing.

Reproduction URL

https://typst.app/project/rvDH4aDLb81YXrUPakmTr-

Typst version

• I am using the latest version of Typst