Велосипед на haskell

Сишный понос нечитаемый, сори, прокомментировать не могу, но скобок лишних ты насовал от души, молодец.

Советую избавиться от *p, *s, g, h и придумать нормальные имена.

1. Нет. Почему в shiftFunc ты сдвигаешь и складываешь уже модифицированный h? Тестировать нужно =), попробуй строку «klasdjflkavnslvjsd'agio'usdgaskjldjscnzxvnzxcm,vkjlgasjdk»

2. Перевел дословно сишный код, можно подумать над именами

import Data.Bits
import Data.Word
import Data.List

simpleHash :: [Word8] -> Word32
simpleHash arr = foldl' iter 0 arr
    where iter h s =
              if g /= 0
              then h' `xor` g `xor` (g `shiftR` 24)
              else h'
              where h' = (h `shiftL` 4) + fromIntegral s
                    g = h' .&. 0xf0000000

3. А зачем?

1). используй Vector.Unboxed/Storable или ByteString (в зависимости от внешних условий)

2). посмотри core, всё ли нам анбокснулось.

Сишный код не мой.

1. Потому что глянь: h в исходном коде инициализируется один раз, потом мы его сдвигаем влево на 4 бита, складываем со значением *s. Затем, мы меняем h в том случае, если он соответствует условию и не трогаем в остальных.

middleTransf как раз делает то, что написано в предыдущем предложении. А сам h в каждой итерации изменяется сдвигом на 4 бита перед сложением с *s.

2. Соответственно, в твоём коде это не учтено

3. Интересно, будет ли ленивая реализация выдавать тот же результат. По идее, нет, т.к. следующее значение зависит от предыдущего: если вдруг сумма *s и h вернула слишком большое число, то его надо преобразовать.

1. Ну… я кусок показал. Исходные данные из ByteString приходят, но процесс распаковки не интересен. Интересно то, что потом с массивом делаем.

2. Что имеется в виду?

3. С моим анализом из предыдущего поста согласен? Насчёт ленивого/строгого fold.

нефиг делать list из bytestring, над ним и работай.

2. Что имеется в виду?

получить core, и посмотреть везде ли там # у типов.

3.

тот же результат точно будет, но ленивость тут не нужна, лишний оверхед без единого бонуса.

1. Тест лень написать?

Ты был прав, а я нет. Исправил.

module TestTools (
    strHash
    ) where

import Data.Bits as DB (xor, (.&.), shiftR, shiftL)
import Data.ByteString as DBS (foldl')
import Data.ByteString.UTF8 as DBSU (fromString)

strHash :: String -> Int
strHash str = DBS.foldl' shiftFunc 0 (DBSU.fromString str)
    where
        shiftFunc acc s = checkOverload $ (acc `shiftL` 4) + (fromIntegral s :: Int)


checkOverload :: Int -> Int
checkOverload arg = case (bitAnd arg) of
    0 -> arg
    _ -> (xorShift arg) `xor` (bitAnd arg)
    where
        bitAnd a = a .&. 0xf0000000
        xorShift b = b `xor` ((bitAnd b) `shiftR` 24)

Не очень нравится множественный вызов функции bitAnd, неоптимально, кажется.

Вообще скорее всего никто не будет вызывать одну и ту же функцию с одними и тем же аргументом из одного скоупа три раза (особенно если даже в компилтайме видно что аргумент один). Но можно переписать функцию так.

checkOverload :: Int -> Int
checkOverload arg = case bitAnd of
    0 -> arg
    _ -> xorShift `xor` bitAnd
    where
        bitAnd = arg .&. 0xf0000000
        xorShift = arg `xor` (bitAnd `shiftR` 24)

Спасибо большое всем за ответы. Пошёл дальше копаться, в частности с boxing/unboxing.

К сожалению, пример на http://www.haskell.org/haskellwiki/Performance/GHC#Core_by_example не работает на GHC 7.6.3 как надо, но общий принцип я понял, как и полезность данного дела.

Сравнил производительность с сишным кодом на гиговом дампе. Если вместо [Word8] использовать ByteString, то приближается по скорости к си, а если ByteString.Lazy то почти идентично + память эффективно расходует из-за ленивости