Подтвердить что ты не робот

Как надежно сравнить время исполнения Haskell и C?

Я использовал библиотеку Criterion для записи тестов для моих функций Haskell. Теперь я реализую тот же алгоритм в C, чтобы сравнить производительность с Haskell. Вопрос в том, как я могу сделать это надежно? Критерий имеет множество причудливых вещей, таких как учет затрат на часовые вызовы и статистический анализ результатов. Я предполагаю, что если бы я просто измерил время, необходимое для моей функции C, это не будет сравнимо с результатами, возвращаемыми Criterion. В своем оригинальном посте о Criterion Брайан О'Салливан пишет: "Он должен быть даже простым в использовании критерием для тестирования C-кода и программ командной строки". Вопрос в том, как? Takayuki Muranushi сравнивает C реализацию DFT с Haskell, создавая потоки и вызывая исполняемый файл, но я боюсь, что это добавит много дополнительных накладных расходов (создайте новый поток, запустите приложение, вывод на stdio, а затем чтение из него), что делает результаты несравнимыми. Я также подумал об использовании FFI, но снова опасаюсь, что дополнительные накладные расходы сделают такое сравнение несправедливым.

Если нет возможности использовать критерий для надежного тестирования C, то какие подходы к сравнительному анализу C вы бы порекомендовали? Я прочитал здесь несколько вопросов по SO, и кажется, что существует множество различных функций, которые позволяют измерять системное время, но они либо обеспечивают время в миллисекундах, либо имеют большие накладные расходы.

4b9b3361

ОТВЕТЫ

Ответ 1

FFI может использоваться таким образом, чтобы он не увеличивал накладные расходы. Рассмотрим следующую программу (полный код здесь):

foreign import ccall unsafe "mean" c_mean :: Ptr CInt -> CUInt -> IO CFloat

main :: IO ()
main = do
  buf <- mallocBytes (bufSize * sizeOfCInt)
  fillBuffer buf 0
  m <- c_mean buf (fromIntegral bufSize)
  print $ realToFrac m

Вызов C скомпилирован на следующий Cmm:

s2ni_ret() { ... }
    c2qy:
        Hp = Hp + 12;
        if (Hp > I32[BaseReg + 92]) goto c2qC;
        _c2qD::I32 = I32[Sp + 4];
        (_s2m3::F32,) = foreign "ccall"
          mean((_c2qD::I32, PtrHint), (100,));

Здесь сборка:

s2ni_info:
.Lc2qy:
        addl $12,%edi
        cmpl 92(%ebx),%edi
        ja .Lc2qC
        movl 4(%ebp),%eax
        subl $4,%esp
        pushl $100
        pushl %eax
        ffree %st(0) ;ffree %st(1) ;ffree %st(2) ;ffree %st(3)
        ffree %st(4) ;ffree %st(5)
        call mean

Итак, если вы помечаете свой импорт C как unsafe и выполняете все сортировки перед измерением, ваш вызов C будет в основном просто встроенной инструкцией call - так же, как если бы вы делали все бенчмаркинга в C. Вот что Критерий сообщает, когда я тестирую функцию C, которая ничего не делает:

benchmarking c_nothing
mean: 13.99036 ns, lb 13.65144 ns, ub 14.62640 ns, ci 0.950
std dev: 2.306218 ns, lb 1.406215 ns, ub 3.541156 ns, ci 0.950
found 10 outliers among 100 samples (10.0%)
  9 (9.0%) high severe
variance introduced by outliers: 91.513%
variance is severely inflated by outliers

Это примерно в 400 раз меньше расчетного разрешения часов на моей машине (~ 5,5 us). Для сравнения здесь приведены контрольные данные для функции, которая вычисляет среднее арифметическое 100 целых чисел:

benchmarking c_mean
mean: 184.1270 ns, lb 183.5749 ns, ub 185.0947 ns, ci 0.950
std dev: 3.651747 ns, lb 2.430552 ns, ub 5.885120 ns, ci 0.950
found 6 outliers among 100 samples (6.0%)
  5 (5.0%) high severe
variance introduced by outliers: 12.329%
variance is moderately inflated by outliers