Please add a method to update a value in place #6

Closed
peti opened this Issue May 26, 2013 · 10 comments

Comments

Projects
None yet
7 participants
@peti

peti commented May 26, 2013

I would like to update a value stored in a hashtable. The unordered-containers package provides methods like insertWith to do this, but the hashtable package unfortunately doesn't. The only way to update a value in place seems to be to do a lookup followed by an insert, but this strikes me as unnecessarily inefficient. Or am I missing something terribly obvious?

@fatlazycat

This comment has been minimized.

Show comment
Hide comment
@fatlazycat

fatlazycat Jun 4, 2013

Had the same thought, looking for an insertWith. Thanks.

As a driver for this, my code with insertWith using HashMap is barely any different in performance than using the mutable version here.

Had the same thought, looking for an insertWith. Thanks.

As a driver for this, my code with insertWith using HashMap is barely any different in performance than using the mutable version here.

@hvr

This comment has been minimized.

Show comment
Hide comment
@hvr

hvr Mar 13, 2014

I'd even suggest to add a generalized update operation that allows to handle the following use-cases:

  • a way to communicate to the caller whether an entry existed for the key
  • to allow conditional updates (i.e. update only if the the key existed)
  • a way to communicate the previously stored value to the caller
  • conditionally delete an entry

This would lead to a type-signature of the following style:

updateEntry :: (Eq k, Hashable k) => h s k v -> k -> (Maybe v -> (Maybe v,a)) -> ST s a

where the Maybe v would encode the existence of the entry before and after the update.

PS: This is inspired by the Data.Map.alter operation

hvr commented Mar 13, 2014

I'd even suggest to add a generalized update operation that allows to handle the following use-cases:

  • a way to communicate to the caller whether an entry existed for the key
  • to allow conditional updates (i.e. update only if the the key existed)
  • a way to communicate the previously stored value to the caller
  • conditionally delete an entry

This would lead to a type-signature of the following style:

updateEntry :: (Eq k, Hashable k) => h s k v -> k -> (Maybe v -> (Maybe v,a)) -> ST s a

where the Maybe v would encode the existence of the entry before and after the update.

PS: This is inspired by the Data.Map.alter operation

@gregorycollins

This comment has been minimized.

Show comment
Hide comment
@gregorycollins

gregorycollins Mar 13, 2014

Owner

Looks reasonable to me. Anyone want to have a go at implementing it? :)

Owner

gregorycollins commented Mar 13, 2014

Looks reasonable to me. Anyone want to have a go at implementing it? :)

@hvr

This comment has been minimized.

Show comment
Hide comment
@hvr

hvr Mar 13, 2014

Here's a more concrete pseudo-implementation to demonstrate the semantics I had in mind:

updateEntry ht k op = do
    mv <- HT.lookup ht k

    case op mv of
        (Nothing, r) -> do
            unless (isNothing mv) $
                HT.delete ht k
            return r

        (Just v, r) -> do
            HT.insert ht k v
            return r

hvr commented Mar 13, 2014

Here's a more concrete pseudo-implementation to demonstrate the semantics I had in mind:

updateEntry ht k op = do
    mv <- HT.lookup ht k

    case op mv of
        (Nothing, r) -> do
            unless (isNothing mv) $
                HT.delete ht k
            return r

        (Just v, r) -> do
            HT.insert ht k v
            return r
@gregorycollins

This comment has been minimized.

Show comment
Hide comment
@gregorycollins

gregorycollins Mar 13, 2014

Owner

@hvr: yes, semantically this would be ok but it shouldn't be implemented this way. We should lookup the slot and do the modify/delete in place (delete or insert would do the lookup twice).

Owner

gregorycollins commented Mar 13, 2014

@hvr: yes, semantically this would be ok but it shouldn't be implemented this way. We should lookup the slot and do the modify/delete in place (delete or insert would do the lookup twice).

@ppetr

This comment has been minimized.

Show comment
Hide comment
@ppetr

ppetr Jun 15, 2015

+1, I'm missing a way how to get the old value overwritten by insert without an additional lookup. The suggested updateEntry sounds like an ideal solution.

Or perhaps a lens-like generalization:

updateEntry :: (Eq k, Hashable k, Traversable f)
            => h s k v -> k -> (Maybe v -> f (Maybe v)) -> ST s (f ())

ppetr commented Jun 15, 2015

+1, I'm missing a way how to get the old value overwritten by insert without an additional lookup. The suggested updateEntry sounds like an ideal solution.

Or perhaps a lens-like generalization:

updateEntry :: (Eq k, Hashable k, Traversable f)
            => h s k v -> k -> (Maybe v -> f (Maybe v)) -> ST s (f ())
@FranklinChen

This comment has been minimized.

Show comment
Hide comment
@FranklinChen

FranklinChen Jun 23, 2015

Contributor

It would be really great to have an update-in-place. I have verified that when I changed my code using immutable hashtables (from unordered-containers) to use this mutable API, having to look up and then reinsert basically doubled the time, and so I went back to the immutable for performance!

Contributor

FranklinChen commented Jun 23, 2015

It would be really great to have an update-in-place. I have verified that when I changed my code using immutable hashtables (from unordered-containers) to use this mutable API, having to look up and then reinsert basically doubled the time, and so I went back to the immutable for performance!

@gregorycollins

This comment has been minimized.

Show comment
Hide comment
@gregorycollins

gregorycollins Jun 24, 2015

Owner

@ppetr re: traversable, in a library like this we're going to stick with the monomorphic :)

I also propose "mutate" as the function name. "alter" would work also.
Enough people want this, but hashtables is number 3 in my project queue (at best) right now. I don't have time to work on this issue but here is broadly what is needed, in this order:

  • add mutate to the typeclass
  • write failing unit tests for mutate
  • implement mutate for the three hashtable implementations, tests go green (and coverage 100%). Separate CLs would be preferred for each (and easier to review).

I've done the first two items (adding mutate to typeclass and writing a failing unit test), but I don't have time to work on it further right now. If you want to send pull requests please send them to the "mutate" branch I just uploaded to github.

Owner

gregorycollins commented Jun 24, 2015

@ppetr re: traversable, in a library like this we're going to stick with the monomorphic :)

I also propose "mutate" as the function name. "alter" would work also.
Enough people want this, but hashtables is number 3 in my project queue (at best) right now. I don't have time to work on this issue but here is broadly what is needed, in this order:

  • add mutate to the typeclass
  • write failing unit tests for mutate
  • implement mutate for the three hashtable implementations, tests go green (and coverage 100%). Separate CLs would be preferred for each (and easier to review).

I've done the first two items (adding mutate to typeclass and writing a failing unit test), but I don't have time to work on it further right now. If you want to send pull requests please send them to the "mutate" branch I just uploaded to github.

@jamesdbrock

This comment has been minimized.

Show comment
Hide comment
@jamesdbrock

jamesdbrock Jun 7, 2016

I'm trying out the mutate branch #26, and for my case the values stored in the hashtable are (Ptr Int)s. I would like to be able to dereference and mutate the pointees during the hashtable mutation.

Perhaps the mutate handler function should be an ST monadic function? Since the mutation is in the ST context, it should be simple to pass that context to the handler, and then the handler would be general enough for my case.

mutate :: (Eq k, Hashable k) => h s k v -> k -> (Maybe v -> ST s (Maybe v, a)) -> ST s a

jamesdbrock commented Jun 7, 2016

I'm trying out the mutate branch #26, and for my case the values stored in the hashtable are (Ptr Int)s. I would like to be able to dereference and mutate the pointees during the hashtable mutation.

Perhaps the mutate handler function should be an ST monadic function? Since the mutation is in the ST context, it should be simple to pass that context to the handler, and then the handler would be general enough for my case.

mutate :: (Eq k, Hashable k) => h s k v -> k -> (Maybe v -> ST s (Maybe v, a)) -> ST s a
@jamesdbrock

This comment has been minimized.

Show comment
Hide comment
@jamesdbrock

jamesdbrock Jun 16, 2016

I implemented mutate in the ST context and pushed it to the mutate-st branch of my clone, if anyone's curious.

https://github.com/jamesdbrock/hashtables/tree/mutate-st

(It didn't give me the performance improvement over lookup + insert which I was hoping for, though.)

I implemented mutate in the ST context and pushed it to the mutate-st branch of my clone, if anyone's curious.

https://github.com/jamesdbrock/hashtables/tree/mutate-st

(It didn't give me the performance improvement over lookup + insert which I was hoping for, though.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment