Генерация уникальных, сопоставимых значений

Question

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

newKey :: IO Key

такое, что:

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

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

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

Map Key EventHandler

Опции, которые мне известны:

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

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

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

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

• mallocForeignPtrBytes1: удовлетворяет обоим критериям, но эффективно ли это?

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

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

Answer 1

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

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

Answer 2

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

Answer 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

unique-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 и скажите, как оно работает.

Answer 4

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