GHC的自动派生`Eq`实例是否真的* O（N）*？ [英] Is GHC's auto-derived `Eq` instance really *O(N)*?

问题描述

我在学习阅读GHC Core时注意到，
为枚举类型的数据类型（如

）自动派生 Eq

 数据EType = ETypeA | ETypeB | ETypeC | ETypeD 
 | ETypeE | ETypeF | ETypeG | ETypeH 
派生（Eq）
  

似乎转换成了一个 O（N ）在查看GHC的核心代表时： -like lookup：

  $ fEqEType_ $ c == = 
 \（a_ahZ :: EType）（b_ai0 :: EType） - > 
案例a_ahZ of _ {
 ETypeA  - > 
案例b_ai0 of _ {
 ETypeA  - >真正; 
 ETypeB  - >假; 
 ETypeC  - >假; 
 ETypeD  - >假; 
 ETypeE  - >假; 
 ETypeF  - >假; 
 ETypeG  - >假; 
 ETypeH  - >假
}; 
 ETypeB  - > _ {__DEFAULT  - >的情况b_ai0假; ETypeB  - >真正}; 
 ETypeC  - > _ {__DEFAULT  - >的情况b_ai0假; ETypeC  - >真正}; 
 ETypeD  - > _ {__DEFAULT  - >的情况b_ai0假; ETypeD  - >真正}; 
 ETypeE  - > _ {__DEFAULT  - >的情况b_ai0假; ETypeE  - >真正}; 
 ETypeF  - > _ {__DEFAULT  - >的情况b_ai0假; ETypeF  - >真正}; 
 ETypeG  - > _ {__DEFAULT  - >的情况b_ai0假; ETypeG  - >真正}; 
 ETypeH  - > _ {__DEFAULT  - >的情况b_ai0假; ETypeH  - > True} 
} 
  

我误解了GHC核心输出？代数数据类型不应该为每个构造函数提供一个整数id，然后可以直接在 O（1）中进行比较。另外，为什么 ETypeA 的第一个case子句不能像其他子句一样使用 __ DEFAULT ？

update：

根据Simon Marlow的建议，我添加了第9个构造函数 ETypeI ，然后GHC切换到使用 dataToOtag＃：

  $ fEqEType_ $ c / = = 
 \（a_ahS :: EType）（b_ahT :: EType） - > 
 case dataToTag＃@ EType a_ahS一个＃_ahQ {
 __DEFAULT  - > 
 case dataToTag＃@ EType b_ahT of b＃_ahR {
 __DEFAULT  - > 
 case ==＃a＃_ahQ b＃_ahR of _ {
 False  - >真正;真 - >假
} 
} 
} 
  

对我来说，这增加了关于GHC核心情况和 dataToTag＃使用之间的取舍问题，以及为什么这个特定问题在GHC中实现了使用 dataToTag＃的9个构造函数的截断。

解决方案

因为情况结构是O（1），所以 EType 的平等比较是O（1） p>

构造函数可能有也可能不是整型标记。有几种低级代表选择，所以核心产生了所有这些作品。也就是说，你总是可以为构造函数创建一个整型标记，这就是我编写Haskell编译器时通常实现的派生比较。

我不知道为什么 ETypeA 会得到不同的待遇。看起来像bug。

I just noticed while trying to learn to read GHC Core, that the automatically derived Eq instance for enum-style data types such as

data EType = ETypeA | ETypeB | ETypeC | ETypeD
           | ETypeE | ETypeF | ETypeG | ETypeH
           deriving (Eq)

seems to be transformed into a O(N)-like lookup when looking at GHC's core representation:

$fEqEType_$c== =
  \ (a_ahZ :: EType) (b_ai0 :: EType) ->
    case a_ahZ of _ {
      ETypeA ->
        case b_ai0 of _ {
          ETypeA -> True;
          ETypeB -> False;
          ETypeC -> False;
          ETypeD -> False;
          ETypeE -> False;
          ETypeF -> False;
          ETypeG -> False;
          ETypeH -> False
        };
      ETypeB -> case b_ai0 of _ {__DEFAULT -> False; ETypeB -> True};
      ETypeC -> case b_ai0 of _ {__DEFAULT -> False; ETypeC -> True};
      ETypeD -> case b_ai0 of _ {__DEFAULT -> False; ETypeD -> True};
      ETypeE -> case b_ai0 of _ {__DEFAULT -> False; ETypeE -> True};
      ETypeF -> case b_ai0 of _ {__DEFAULT -> False; ETypeF -> True};
      ETypeG -> case b_ai0 of _ {__DEFAULT -> False; ETypeG -> True};
      ETypeH -> case b_ai0 of _ {__DEFAULT -> False; ETypeH -> True}
    }

Am I misinterpreting the GHC core output? Shouldn't algebraic data types provide an integer id for each constructor, which could then be compared directly in O(1)? Also, why does the first case clause for ETypeA not make use of __DEFAULT as the other clauses do?

update:

As per suggestion by Simon Marlow, I addad a 9th constructor ETypeI, and then GHC switched to using dataToOtag#:

$fEqEType_$c/= =
  \ (a_ahS :: EType) (b_ahT :: EType) ->
    case dataToTag# @ EType a_ahS of a#_ahQ {
      __DEFAULT ->
        case dataToTag# @ EType b_ahT of b#_ahR {
          __DEFAULT ->
            case ==# a#_ahQ b#_ahR of _ {
              False -> True; True -> False
            }
        }
    }

For me, this adds the question as to what the trade-offs between GHC core's case and use of dataToTag# are, and why this particular cut-off of 9 constructors for using dataToTag# is implemented in GHC.

解决方案

Equality comparison of EType is O(1) because the case construct is O(1).

There might or might not be an integer tag for constructors. There are several low level representation choices, so the Core generated works for all of them. That said, you can always make an integer tag for constructors, and that's how I usually implement the derived comparison when I write Haskell compilers.

I have no idea why ETypeA gets a different treatment. Looks like bug.

这篇关于GHC的自动派生`Eq`实例是否真的* O（N）*？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！