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

Какой хороший способ генерировать специальные клавиши, где каждый ключ уникален для программы? В идеале действие вида:

newKey :: IO Key

такое, что:

do a <- newKey
   b <- newKey
   return (a == b)

всегда возвращает false. Кроме того, должно быть возможно использовать Key в эффективном ассоциативном контейнере (например, a Map).

Это может быть использовано, например, для поддержки коллекции обработчиков событий, поддерживающих случайную вставку и удаление:

Map Key EventHandler

Параметры, о которых я знаю:

  • newIORef (): Удовлетворяет инварианту выше, но IORef не имеет экземпляра Ord.

  • malloc: Быстро, а Ptr () имеет экземпляр Ord, но результат не является сборкой мусора.

  • newStablePtr (): не собран мусор, а StablePtr не имеет экземпляра Ord.

  • newIORef () >>= makeStableName: должны удовлетворять инварианту выше и сбор мусора, но сложнее в использовании (требуется, чтобы я использовал хеш-таблицу).

  • mallocForeignPtrBytes 1: Удовлетворяет оба критерия, но эффективен ли он?

mallocForeignPtrBytes 1 кажется моим лучшим вариантом. Я полагаю, что я мог бы сделать его немного более эффективным, используя непосредственный приём GHC newPinnedByteArray#.

Есть ли лучшие варианты? Является ли подход mallocForeignPtrBytes ошибочным по какой-то неочевидной причине?

Ответы

Ответ 1

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

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

Ответ 3

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

Unique2.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

Unique3.hs

На основе 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 и скажите мне, как это происходит.

Ответ 4

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

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)