Создание уникальных, сопоставимых значений

Если вы не хотите добавлять какие-либо дополнительные зависимости в свой проект, вы можете использовать Data.Unique в базовом пакете.

Внутри система использует TVar (который опирается на систему STM GHC) из Integers, так что каждый раз, когда вы вызываете newUnique, TVar увеличивается атомарно, а новый Integer сохраняется в непрозрачном типе данных Unique. Поскольку TVar не могут быть изменены разными потоками одновременно, они гарантируют, что Unique генерируются последовательно и фактически должны быть уникальными.

На hackage есть несколько соответствующих пакетов. пакет concurrent-supply выглядит довольно тщательно разработанным.

Спасибо, dflemstr, за указание Data.Unique. Я сравнил Data.Unique с парой альтернативных реализаций:

Уникальный2.hs

На основе mallocForeignPtrBytes< /а>:

{-# LANGUAGE DeriveDataTypeable #-}
module Unique2 (Unique2, newUnique2) where

import Control.Applicative
import Data.Typeable (Typeable)
import Data.Word (Word8)
import Foreign.ForeignPtr

newtype Unique2 = Unique2 (ForeignPtr Word8)
    deriving (Eq, Ord, Typeable)

newUnique2 :: IO Unique2
newUnique2 = Unique2 <$> mallocForeignPtrBytes 1

На основе newPinnedByteArray, который используется внутри mallocForeignPtrBytes. Это в основном то же самое, что и Unique2, за исключением некоторых накладных расходов.

{-# LANGUAGE DeriveDataTypeable #-}
module Unique3 (Unique3, newUnique3) where

import Control.Applicative
import Data.Primitive.ByteArray
import Data.Primitive.Types
import Data.Typeable

newtype Unique3 = Unique3 Addr
    deriving (Eq, Ord, Typeable)

newUnique3 :: IO Unique3
newUnique3 = Unique3 . mutableByteArrayContents <$> newPinnedByteArray 1

уникальный-benchmark.hs

import Criterion.Main

import Control.Exception (evaluate)
import Control.Monad
import Data.Unique
import Unique2
import Unique3

import qualified Data.Set as S

main :: IO ()
main = defaultMain
    [ bench "Unique" $
        replicateM 10000 newUnique  >>= evaluate . S.size . S.fromList
    , bench "Unique2" $
        replicateM 10000 newUnique2 >>= evaluate . S.size . S.fromList
    , bench "Unique3" $
        replicateM 10000 newUnique3 >>= evaluate . S.size . S.fromList
    ]

Полученные результаты:

Скомпилировано с ghc -Wall -O2 -threaded -fforce-recomp unique-benchmark.hs:

benchmarking Unique
mean: 15.75516 ms, lb 15.62392 ms, ub 15.87852 ms, ci 0.950
std dev: 651.5598 us, lb 568.6396 us, ub 761.7921 us, ci 0.950

benchmarking Unique2
mean: 20.41976 ms, lb 20.11922 ms, ub 20.67800 ms, ci 0.950
std dev: 1.427356 ms, lb 1.254366 ms, ub 1.607923 ms, ci 0.950

benchmarking Unique3
mean: 14.30127 ms, lb 14.17271 ms, ub 14.42338 ms, ci 0.950
std dev: 643.1826 us, lb 568.2373 us, ub 737.8637 us, ci 0.950

Если я увеличу величину с 10000 до 100000:

benchmarking Unique
collecting 100 samples, 1 iterations each, in estimated 21.26808 s
mean: 206.9683 ms, lb 206.5749 ms, ub 207.7638 ms, ci 0.950
std dev: 2.738490 ms, lb 1.602821 ms, ub 4.941017 ms, ci 0.950

benchmarking Unique2
collecting 100 samples, 1 iterations each, in estimated 33.76100 s
mean: 319.7642 ms, lb 316.2466 ms, ub 323.2613 ms, ci 0.950
std dev: 17.94974 ms, lb 16.93904 ms, ub 19.34948 ms, ci 0.950

benchmarking Unique3
collecting 100 samples, 1 iterations each, in estimated 21.22741 s
mean: 200.0456 ms, lb 199.2538 ms, ub 200.9107 ms, ci 0.950
std dev: 4.231600 ms, lb 3.840245 ms, ub 4.679455 ms, ci 0.950

Вывод:

Data.Unique (встроенная реализация) и Unique3 (на основе newPinnedByteArray) идут ноздря в ноздрю в этих тестах. newUnique3 сам по себе более чем в десять раз быстрее, чем newUnique, но накладные расходы на генерацию ключей ничтожны по сравнению с затратами на использование.

Unique2 проигрывает из-за накладных расходов на оболочку, но между Data.Unique и Unique3 мои результаты неубедительны. Я бы рекомендовал Data.Unique просто потому, что он уже доступен в базе. Однако, если вы изо всех сил пытаетесь выжать последнюю часть производительности из какого-либо приложения, попробуйте заменить Data.Unique на Unique3 и расскажите мне, как это работает.

Один из способов, который я видел, если вы хотите, чтобы это было на верхнем уровне, - это такой хак:

import Data.IORef
import System.IO.Unsafe

newtype Key = Key Integer deriving (Ord, Eq, Show)

newKey :: IO Key
{-# NOINLINE newKey #-}
newKey = unsafePerformIO mkNewKey

mkNewKey :: IO (IO Key)
mkNewKey = do
  r <- newIORef 0
  return $ do
    modifyIORef r (+1)
    Key `fmap` (readIORef r)

main = do
  a <- newKey
  b <- newKey
  print (a,b)