Come modificare impuritamente uno stato associato a un oggetto?

Question

In Haskell, ho un contenitore simile:

data Container a = Container { length :: Int, buffer :: Unboxed.Vector (Int,a) } 

Questo contenitore è un albero appiattito. L'accessore (!) esegue una ricerca binaria (log(N)) attraverso il vettore per trovare il bucket corretto in cui è memorizzato lo index.

(!) :: Container a -> Int -> a 
container ! index = ... binary search ... 

Da accessi consecutivi sono suscettibili di essere nello stesso bucket, questo potrebbe essere ottimizzato nel modo seguente:

if `index` is on the the last accessed bucket, skip the search 

Il punto difficile è la parte last accessed bucket. In JavaScript, modificherei impuramente una variabile nascosta sull'oggetto contenitore.

function read(index,object){ 

    var lastBucket = object.__lastBucket; 

    // if the last bucket contains index, no need to search 
    if (contains(object, lastBucket, index)) 
     var bucket = lastBucket; 

    // if it doesn't 
    else { 
     // then we search the bucket 
     var bucket = searchBucket(index,object); 

     // And impurely annotate it on the container, so the 
     // next time we access it we could skip the search. 
     container.__lastBucket = bucket; 
    } 

    return object.buffer[bucket].value; 
} 

Dal momento che questo è solo l'ottimizzazione ed il risultato è lo stesso indipendentemente dal ramo preso, credo che non si rompe la trasparenza referenziale. Come è possibile, in Haskell, modificare impuriosamente uno stato associato a un valore di runtime?

~

ho pensato in 2 possibili soluzioni.

1. A, hashmap mutabile globale che collega i puntatori al valore lastBucket, e utilizzare unsafePerformIO di scrivere su di esso. Ma avrei bisogno di un modo per ottenere il puntatore di runtime di un oggetto, o almeno un id univoco di qualche tipo (come?).

2. Aggiungi un campo in più per Container, lastBucket :: Int, e in qualche modo impurely modificare entro (!), e ritengono che campo interno (perché ovviamente rompere trasparenza referenziale).

Answer 1

Utilizzando la soluzione (1), sono riuscito a ottenere il seguente progetto. In primo luogo, ho aggiunto un campo __lastAccessedBucket :: IORef Int al mio tipo di dati, come suggerito da @ Xico:

data Container a = Container { 
    length :: Int, 
    buffer :: V.Vector (Int,a), 
    __lastAccessedBucket :: IORef Int } 

Poi, ho dovuto aggiornare le funzioni che creano un nuovo Container al fine di creare un nuovo IOREF utilizzando unsafePerformIO:

fromList :: [a] -> Container a 
fromList list = unsafePerformIO $ do 
    ref <- newIORef 0 
    return $ Container (L.length list) buffer ref 
    where buffer = V.fromList (prepare list) 

Infine, ho creato due nuove funzioni, findBucketWithHint, una funzione di pura che cerca la benna di un indice con supposizione (cioè, il secchio in cui si pensa che potrebbe essere), e la funzione unsafeFindBucket, che sostituisce la pura findBucket quando è necessaria la prestazione, da sempre usando l'ultimo segmento letta come suggerimento:

unsafeFindBucket :: Int -> Container a -> Int 
unsafeFindBucket findIdx container = unsafePerformIO $ do 
    let lastBucketRef = __lastAccessedBucket contianer 
    lastBucket  <- readIORef lastBucketRef 
    let newBucket  = findBucketWithHint lastBucket findIdx container 
    writeIORef lastBucketRef newBucket 
    return $ newBucket 

Con questo, unsafeFindBucket è tecnicamente una funzione pura con la stessa API della funzione originale findBucket, ma è un ordine di grandezza più velocemente in alcuni parametri di riferimento. Non ho idea di quanto sia sicuro e dove potrebbe causare bug. I thread sono certamente una preoccupazione.

Answer 2

^{(Questo è più un commento esteso che una risposta.)}

Innanzitutto suggerirei di verificare se questo non è un caso di premature optimization. Dopotutto, O (log n) non è così male.

Se questa parte è davvero critica dal punto di vista delle prestazioni, la tua intenzione è sicuramente valida. Il solito avviso per unsafePerformIO è "usalo solo se sai cosa stai facendo", cosa che ovviamente fai e può aiutare a rendere le cose pure e veloci allo stesso tempo. Assicuratevi di seguire tutto lo the precautions in the docs, in particolare impostando i corretti flag del compilatore (potreste voler usare the OPTIONS_GHC pragma).

Assicurarsi inoltre che l'operazione IO sia thread-safe. Il modo più semplice per garantire che sia quello di utilizzare IORef insieme a atomicModifyIORef.

Lo svantaggio di uno stato interno mutabile è che le prestazioni della cache si deteriorano se si accede da più thread, se cercano elementi diversi.

Un rimedio sarebbe quello di inserire esplicitamente lo stato aggiornato invece di utilizzare lo stato interno mutabile. Questo è ovviamente quello che vuoi evitare, ma se il tuo programma usa le Monade, puoi semplicemente aggiungere un altro layer monadico che mantiene internamente lo stato per te ed esporre l'operazione di ricerca come azione monadica.

Infine, è possibile considerare l'utilizzo di splay trees anziché l'array. Avresti ancora (ammortizzato) la complessità O (log n), ma il loro grande vantaggio è che, per impostazione, spostano gli elementi a cui si accede frequentemente nella parte superiore. Quindi, se accederai a un sottoinsieme di elementi della dimensione k, verranno presto spostati in cima, quindi le operazioni di ricerca saranno solo O (log k) (costante per un elemento singolo, ripetutamente accessibile). Di nuovo, aggiornano la struttura sulle ricerche, ma è possibile utilizzare lo stesso approccio con unsafePerformIO e gli aggiornamenti atomici di IORef per mantenere l'interfaccia esterna pura.