Действительно ли порядок конструкторов/случаев/охранников/если-то-другой имеет значение?

Я видел этот комментарий в Containers/Data/Set/Base.hs

-- [Note: Order of constructors]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- The order of constructors of Set matters when considering performance.
-- Currently in GHC 7.0, when type has 2 constructors, a forward conditional
-- jump is made when successfully matching second constructor. Successful match
-- of first constructor results in the forward jump not taken.
-- On GHC 7.0, reordering constructors from Tip | Bin to Bin | Tip
-- improves the benchmark by up to 10% on x86.

Где еще порядок имеет незначительное измеримое воздействие на производительность? В частности, я задаюсь вопросом о случаях с множеством опций.

Ответ 1

Это зависит. К сожалению, порядок конструкторов имеет значение. Это означает, что порядок шаблонов для этого типа не выполняется. Если вы пишете

foo (Bin x y) = ...
foo Tip = ...

или

foo Tip = ...
foo (Bin x y) = ...

не имеет значения, потому что они будут упорядочены по порядку конструктора немедленно в процессе "desugaring". Порядок сопоставления для нескольких шаблонов всегда семантически слева направо, поэтому порядок аргументов может иметь значение, если вы используете несколько шаблонов вместе (вы всегда можете обойти это с помощью case). Но GHC чувствует себя очень свободно, чтобы реорганизовать код, иногда навсегда, а иногда и на зло. Например, если вы пишете

foo :: Int -> Bool
foo x = x == 5 || x == 0 || x == 7 || x == 4

GHC разломит его (по существу)

foo = \x -> case x of
              0 -> True
              4 -> True
              5 -> True
              7 -> True
              _ -> False

а затем выполните своего рода двоичный поиск этих возможностей. Вероятно, это во многих случаях не оптимально, и особенно раздражает, если вам известно, что x==5 особенно вероятен. Но то, как это происходит сейчас, и его изменение заставит все плохо работать в определенных ситуациях, если кто-то не сделает много работы.