О каких вещах я должен позаботиться, если я использую unboxed type (например, Int #) в Haskell / GHC?

Question

Я пытаюсь написать небольшой скрипт, который анализирует и выполняет код 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 []                                   = []

Идея заключается в том, что код будет считан из некоторого входного сигнала (строки), подготовлен и упрощен приведенным выше кодом, а затем выполнен некоторыми другими функциями.(Предполагается, что входные данные являются действительными).

Чтобы оптимизировать этот пример, я попытался распаковать Int-параметры MovePointer и AdjustValue конструкторы, делая что-то вроде этого:

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

Это превратит упакованный Int введите в распакованный, необработанный файл Int# тип, который является деталью реализации GHc.Как я читал, этот вариант хорош только в нескольких случаях, поэтому я хочу спросить, на какие вещи я должен обратить внимание, если я хочу выполнить такого рода оптимизацию.Моя цель - разрешить выполнение BF-кода, используя преимущества Haskell - лень (я хочу заархивировать, чтобы код мог храниться в памяти только по мере необходимости) и легкость.

Answer 1

На мой взгляд, это действительно выглядит как преждевременная оптимизация.РАСПАКОВКА в основном полезна, когда у вас очень большое количество BFInstructionсидит без дела.Я сомневаюсь, что у вас когда-нибудь будет достаточно умного кода, чтобы сделать это стоящим.Я согласен с Джаном, это должно быть достаточно просто для тестирования, так что сделайте это в первую очередь.

В любом случае, при использовании РАСПАКОВАННЫХ значений следует помнить о том, что вы не хотите, чтобы компилятору приходилось перепаковывать их.Вы должны быть в порядке с числовыми операциями, но в остальном вам придется внимательно изучить функции, которые вы используете, чтобы увидеть, используете ли вы когда-либо распакованные значения в качестве нестрогого аргумента.Единственный способ убедиться в этом - взглянуть на ядро или файлы интерфейса, чтобы увидеть, какие параметры являются строгими, а какие нет.Как всегда, обязательно компилируйте как минимум с "-O".

Answer 2

Это действительно необходимо? Вы сталкиваетесь с проблемами эффективности с этим кодом, который вы считаете результатом вспомогательных значений? Если нет, не беспокойтесь.

Если вы верите, что это так, то Эта страница в руководстве GHC Похоже, предоставляет необходимые ограничения в удобном формате списка.

Основные моменты, кажется, что любой вид взаимодействия между полиморфными функциями или именами и печатанными типами, которые не отклоняются компилятором, все еще могут привести к неприятным утечкам пространства. Кроме того, не пытаясь, я подозреваю, что вы не получите бросок исключений в случае переполнения, например, напротив, поэтому предположительно вы должны обнаружить такого рода вещи самостоятельно. Простой тест может проверить, если это на самом деле или нет.