7

我正在尝试编写一个解析和执行 Brainfuck 代码的小脚本，以了解 GHC 优化选项，我正在尝试优化代码以便更快一点并了解那里发生了什么。

其中一部分是 BF 代码的内部表示，我为此使用了一种特殊的数据类型。这是源代码，包括进行转换的两个函数：

data BFinstruction
  = AdjustValue Int
  | MovePointer Int
  | GetChar
  | PutChar
  | Loop BFcode
  deriving (Eq)

type BFcode = [BFinstruction]

unsafeCompileBrainfuck :: String -> BFcode
unsafeCompileBrainfuck = fst . parse [] where
  -- arguments: input string, built code; output: output code, rest of input
  parse :: BFcode -> String -> (BFcode,String)
  parse c ('+':s) = parse (AdjustValue   1 :c) s
  parse c ('-':s) = parse (AdjustValue (-1):c) s
  parse c ('>':s) = parse (MovePointer   1 :c) s
  parse c ('<':s) = parse (MovePointer (-1):c) s
  parse c ('.':s) = parse (PutChar         :c) s
  parse c (',':s) = parse (GetChar         :c) s
  parse c (']':s) = (reverse c, s)
  parse c ('[':s) = parse (Loop l          :c) s' where (l,s') = parse [] s
  parse c []      = (reverse c ,"")
  parse c ( _ :s) = parse                   c  s

simplifyBrainfuck :: BFcode -> BFcode
simplifyBrainfuck ((AdjustValue x):(AdjustValue y):zs) = if x + y /= 0
  then simplifyBrainfuck (AdjustValue (x + y):zs)
  else simplifyBrainfuck zs
simplifyBrainfuck ((MovePointer x):(MovePointer y):zs) = if x + y /= 0
  then simplifyBrainfuck (MovePointer (x + y):zs)
  else simplifyBrainfuck zs
simplifyBrainfuck (x                              :zs) = x: simplifyBrainfuck zs
simplifyBrainfuck []                                   = []

这个想法是，代码将从一些输入（字符串）中读取，由上述代码进行预解析和简化，然后由其他一些函数执行。（假设输入是有效的）。

为了优化此示例，我尝试通过执行以下操作来拆箱MovePointerandAdjustValue构造函数的 Int 参数：

data BFinstruction -- BangPatterns
  = AdjustValue {-# UNPACK #-} !Int
  | MovePointer {-# UNPACK #-} !Int
  | GetChar
  | PutChar
  | Loop BFcode
  deriving (Eq)

这会将装箱的Int类型变成未装箱的原始Int#类型，这是 GHc 的实现细节。在我阅读的过程中，这个选项只在少数情况下有用，所以我想问一下，如果我想进行这种优化，我需要注意哪些事项。我的目标是允许使用 Haskell 的好处执行 BF 代码 - 懒惰（我想归档，代码可能只根据需要保存在内存中）和简单性。

4

2 回答 2

3

这真的有必要吗？您是否遇到此代码的性能问题，您认为这是装箱值的结果？如果没有，请不要打扰。

如果您确实认为是这种情况，那么GHC 手册中的此页面似乎以方便的列表格式提供了必要的限制。

要点似乎是，多态函数或名称与未被编译器拒绝的未装箱类型之间的任何交互仍可能导致严重的空间泄漏。另外，如果不尝试，我怀疑您不会在溢出的情况下抛出异常，例如，所以大概您应该自己检测这种事情。一个简单的测试可以验证是否确实如此。

于 2010-09-04T15:34:43.767 回答
2

对我来说，这确实看起来像是一个过早的优化。当您周围有大量BFInstructions 时，UNPACK 最有用。我怀疑你是否会有足够的brainf**k 代码让它变得有价值。我同意 Gian 的观点，测试应该足够简单，所以先这样做。

无论如何，使用 UNPACK 的值要注意的是，您不希望编译器必须重新装箱它们。您应该对数值操作没问题，但除此之外，您必须仔细查看您正在使用的函数，看看您是否曾经将解压缩的值用作非严格参数。唯一可以确定的方法是查看核心或接口文件，看看哪些参数是严格的，哪些不是。与往常一样，请确保至少使用“-O”进行编译。

于 2010-09-04T16:44:43.913 回答