L'ordine dei costruttori/casi/guardie/if-then-else è importante per le prestazioni?

Question

Ho visto questo commento in contenitori/dati/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. 

Dove altro si fa ordine hanno piccoli impatti misurabili sulle prestazioni? In particolare, mi chiedo delle dichiarazioni del caso con molte opzioni.

Answer 1

Dipende. L'ordine dei costruttori fa, purtroppo, fare la differenza. Ciò significa che l'ordine dei modelli per quel tipo non è non. Sia che si scrive

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

o

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

non fa differenza, perché saranno riordinati in ordine costruttore immediatamente nel processo "Dezuccheraggio". L'ordine di corrispondenza per più pattern è sempre semanticamente da sinistra a destra, quindi l'ordine degli argomenti può essere importante se si utilizzano più schemi contemporaneamente (è sempre possibile aggirare questo problema con case). Ma GHC si sente molto libero di riorganizzare il codice, a volte per il bene e talvolta per il male. Per esempio, se si scrive

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

GHC romperà in (essenzialmente)

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

e poi fare una sorta di ricerca binaria di queste possibilità. Questo probabilmente non è ottimale in molti casi, ed è particolarmente fastidioso se ti capita di sapere che x==5 è particolarmente probabile. Ma è così che è per ora, e cambiarlo farà sì che le cose si comportino male in certe situazioni senza che qualcuno lavori molto.