Re: [Haskell] performance tuning Data.FiniteMap
I believe FiniteMap works by representing the data in binary trees. It is therefore O(log2(n)) to read and update.
However, if my application reads many more times than it writes, then perhaps I can get a substantial performance boost by increasing the branch factor on the tree. For example, if each node was an array of 256 elements, reads would be O(log256(n)), a 128x improvement!
Not quite. In fact, O(log256(n)) is equivalent to O(log2(n)), because there is only a constant factor between the two. That's why basis of logarithms are usually omitted in O() expressions. Besides, the ratio between log256(n) and log2(n) is more like 8 than 128. (And you'd loose this factor in searching the right subtree, as Ketil pointed out) Tuning Data.FiniteMap probably is not what you want. I don't know, but you can have a look at Data.Hashtable. Just my 2 cents, JP. __________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools
Ok. I just looked more carefully at FiniteMap and the Data.HashTable documentation and coded what I had incorrectly imagined would be there. Isn't the following more efficient than FiniteMap without requiring the IO Monad? ------------------------------------------------------------- class MaxRange a where maxRange::(a,a) data HashTable key elt = HashTable (Maybe (Array key (HashTable key elt))) (Maybe elt) emptyHT=HashTable Nothing Nothing hLookup (HashTable x y) [] = y hLookup (HashTable Nothing _) _ = Nothing hLookup (HashTable (Just ar) _) (k:ey) = hLookup (ar!k) ey insert (HashTable x _) [] val = HashTable x val insert (HashTable Nothing y) (k:ey) val = HashTable (Just initArray) y where initArray = array maxRange [(x,if x/=k then emptyHT else insert emptyHT ey val) | x<-[(fst maxRange)..(snd maxRange)]] insert (HashTable (Just ar) y) (k:ey) val = HashTable (Just $ ar//[(k,insert (ar!k) ey val)]) y --support String keys instance MaxRange Char where maxRange=(chr 0,chr 255) -------------------------------------------------------------- It seems like the depth of the tree and therefore the speed of lookups is dependent on the size of maxRange and faster than the repetitive lookups in FiniteMap. I don't know how lookups compare to Data.HashTable. It seems like updates could be very fast because I assume // is implemented with a fast memcpy.... (though not as fast as the destructive updates in Data.HashTable) Note: I don't know how to avoid the namespace conflict with GHC.List.lookup so its hLookup. -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com On Tue, 24 Feb 2004, JP Bernardy wrote:
I believe FiniteMap works by representing the data in binary trees. It is therefore O(log2(n)) to read and update.
However, if my application reads many more times than it writes, then perhaps I can get a substantial performance boost by increasing the branch factor on the tree. For example, if each node was an array of 256 elements, reads would be O(log256(n)), a 128x improvement!
Not quite.
In fact, O(log256(n)) is equivalent to O(log2(n)), because there is only a constant factor between the two. That's why basis of logarithms are usually omitted in O() expressions.
Besides, the ratio between log256(n) and log2(n) is more like 8 than 128. (And you'd loose this factor in searching the right subtree, as Ketil pointed out)
Tuning Data.FiniteMap probably is not what you want.
I don't know, but you can have a look at Data.Hashtable.
Just my 2 cents, JP.
__________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
It seems like updates could be very fast because I assume // is implemented with a fast memcpy....
(//) is very slow
_________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com
On Tue, 24 Feb 2004, JP Bernardy wrote:
I believe FiniteMap works by representing the data in binary trees. It is therefore O(log2(n)) to read and update.
However, if my application reads many more times than it writes, then perhaps I can get a substantial performance boost by increasing the branch factor on the tree. For example, if each node was an array of 256 elements, reads would be O(log256(n)), a 128x improvement!
Not quite.
In fact, O(log256(n)) is equivalent to O(log2(n)), because there is only a constant factor between the two. That's why basis of logarithms are usually omitted in O() expressions.
Besides, the ratio between log256(n) and log2(n) is more like 8 than 128. (And you'd loose this factor in searching the right subtree, as Ketil pointed out)
Tuning Data.FiniteMap probably is not what you want.
I don't know, but you can have a look at Data.Hashtable.
Just my 2 cents, JP.
__________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- Hal Daume III | hdaume@isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume
On Tue, 24 Feb 2004, Hal Daume III wrote:
It seems like updates could be very fast because I assume // is implemented with a fast memcpy....
(//) is very slow
Is that inherent in Haskell (or laziness) or is it just an artifact of the current GHC implementation? Would the problem be solved by making my arrays strict or by using Unboxed arrays? Is there a faster array implementation around? -Alex- PS I'm sorry if these are obvious beginner questions. I would really realy like to use Haskell for a production web application and am trying to work through the various issues. It is hard to find information on these sorts of things and the absense of field testing means you just have to ask these questions in advance. _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com
[Rewrote prior code to be cleaner] Isn't the following more efficient than Data.FiniteMap? class Ix a=>Radix a where maxRange::(a,a) class Radix a => HashKey b a where hashKey::b->[a] instance Radix Char where maxRange=(chr 0,chr 255) instance Radix a=> HashKey [a] a where hashKey x=x data HT radix elt = HT (Maybe (Array radix (HT radix elt))) (Maybe elt) emptyHT=HT Nothing Nothing emptyArray = Just (array maxRange [(x,emptyHT) | x<- [(fst maxRange)..(snd maxRange)]]) hLookup table key = hLookup' table (hashKey key) hLookup' (HT x y) [] = y hLookup' (HT Nothing _) _ = Nothing hLookup' (HT (Just ar) _) (k:ey) = hLookup' (ar!k) ey --insert table key val = insert' table (hashKey key) val insert' (HT x _) [] val = HT x val insert' (HT Nothing y) key val = insert' (HT emptyArray y) key val insert' (HT (Just ar) y) (k:ey) val = HT (Just $ ar//[(k,insert' (ar!k) ey val)]) y Isn't hLookup substantially faster than the binarySearch in FiniteMap for e.g. Strings? Doesn't insert compete with FiniteMap because small array copies should be blisteringly fast? Also, basic Haskell questions: * How do I get insert to typecheck? insert' works fine. * How do I hide the "lookup" automatically imported from GHC.List? -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com
On Tue, 24 Feb 2004, JP Bernardy wrote:
I believe FiniteMap works by representing the data in binary trees. It is therefore O(log2(n)) to read and update.
However, if my application reads many more times than it writes, then perhaps I can get a substantial performance boost by increasing the branch factor on the tree. For example, if each node was an array of 256 elements, reads would be O(log256(n)), a 128x improvement!
Not quite.
In fact, O(log256(n)) is equivalent to O(log2(n)), because there is only a constant factor between the two. That's why basis of logarithms are usually omitted in O() expressions.
Besides, the ratio between log256(n) and log2(n) is more like 8 than 128. (And you'd loose this factor in searching the right subtree, as Ketil pointed out)
Tuning Data.FiniteMap probably is not what you want.
I don't know, but you can have a look at Data.Hashtable.
Just my 2 cents, JP.
__________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
G'day all. Quoting "S. Alexander Jacobson" <alex@i2x.com>:
Isn't the following more efficient than Data.FiniteMap? [deletia]
TernaryTrie is basically this, minus the Radix type class, and using balanced binary trees for each radix levels instead of arrays. Cheers, Andrew Bromage
Hello! If indeed the read performance is at premium and updates are infrequent, by bother with ternary etc. trees -- why not to use just a single, one-level array. Given a reasonable hash function, the retrieval performance is O(1). And still, no IO/ST are necessary. {-# OPTIONS -fglasgow-exts #-} module Foo where import Data.Array import Data.List import Data.HashTable (hashString) import Data.Int (Int32) class Hashy a where hash:: a -> Int data MyFM key val = MyFM { base:: Int , purgatory:: [(key,val)] , store:: Array Int [(key,val)] } deriving Show empty = MyFM {base = 41, purgatory = [], store = listArray (0,base(empty)-1) $ repeat []} lkup fm key = case lookup key (purgatory fm) of t@(Just _) -> t _ -> lookup key item where item = (store fm)! hashv hashv = (hash key) `mod` (base fm) count = length . concat . elems . store purgatory_limit = 10 ins fm key val = rebuild_perhaps $ fm {purgatory = add_uniq (purgatory fm) key val} where rebuild_perhaps fm | length (purgatory fm) > purgatory_limit = rebuild fm rebuild_perhaps fm = fm rebuild fm | 2*(count fm) > base fm = major_rebuild fm rebuild fm = fm{purgatory = [], store = (store fm) // updates} where updates = map (retr . merge) $ groupBy gfirs $ sortBy sfirs $ map (\p@(k,v) -> (hashk k,p)) $ purgatory fm hashk k = (hash k) `mod` (base fm) gfirs (k1,_) (k2,_) = k1 == k2 sfirs (k1,_) (k2,_) = compare k1 k2 merge x = (fst$ head x, map snd x) retr (h,v) = (h, unionBy gfirs v ((store fm)!h)) -- reallocate the hash table to the bigger size major_rebuild fm = undefined -- exercise for the reader -- add association (key,val) to the list, replacing an old association -- with the same key, if any. At most one such association could have -- existed add_uniq [] key val = [(key,val)] add_uniq ((hkey,_):t) key val | hkey == key = (key,val):t add_uniq (h:t) key val = h: add_uniq t key val instance Hashy String where hash = fromInteger . toInteger . hashString test1 = foldl (\fm v -> ins fm v v) empty $ map (:[]) ['a'..'h'] test2 = foldl (\fm v -> ins fm v v) test1 $ map (:[]) ['a'..'o'] test3 = foldl (\fm v -> ins fm v v) test2 $ map (:[]) ['a'..'o']
G'day all. Quoting oleg@pobox.com:
If indeed the read performance is at premium and updates are infrequent, by bother with ternary etc. trees -- why not to use just a single, one-level array. Given a reasonable hash function, the retrieval performance is O(1).
Ah, but key comparison and computing the hash function is _not_ an O(1) operation for keys of non-fixed-size. At the very least, it's O(k) where k is the length of the key. If you have a perfect hash function, and you know that you are not searching for elements which are not in the set, hash searching will take precisely one scan through the whole key. Radix searching, on the other hand, only needs to scan through as much of the key as is necessary to discriminate between them. Plus, even if you need to search for keys which are not in the set, it takes at most one pass through the key, as opposed to at least two for hashing. If constant factors matter, and your keys are appropriately decomposable, I would recommend radix searching over hashing any day. Cheers, Andrew Bromage
On Fri, 27 Feb 2004 oleg@pobox.com wrote:
If indeed the read performance is at premium and updates are infrequent, by bother with ternary etc. trees -- why not to use just a single, one-level array. Given a reasonable hash function
Because updates are not so infrequent that I want to pay the cost of replicating the entire array every update (or every ten!). I'm willing to exchange *some* read time for faster update. Also, because small array copies may be sufficiently faster than tree traversals that I may pay very little extra for faster reads. FYI, my current code looks like this: type HTArray base elt = Array base (HT base elt) data HT base elt = HT (Maybe (HTArray base elt)) (Maybe elt) data MyMap base key elt = ArrMap (HTArray base elt) (key->[base]) (HT base elt) newMap minBase maxBase toBase = ArrMap proto toBase emptyHT where proto= array (minBase,maxBase) [(x,emptyHT) | x<- [minBase..maxBase]] emptyHT=HT Nothing Nothing lookup (ArrMap _ toBase ht) key = lookup' ht $ toBase key lookup' (HT x y) [] = y lookup' (HT Nothing _) _ = Nothing lookup' (HT (Just ar) _) (k:ey) = lookup' (ar!k) ey insert (ArrMap proto toBase ht) key elt = ArrMap proto toBase newHT where newHT= insert' proto ht (toBase key) elt insert' _ (HT x _) [] = HT x insert' proto (HT Nothing y) key = insert' proto (HT (Just proto) y) key insert' p (HT (Just ar) y) (k:ey) = \val -> HT (Just $ newArray val) y where newArray val = ar//[(k,insert' p (ar!k) ey val)] ----- testMap=newMap (chr 0) (chr 255) id main = do print $ lookup (insert testMap "abc" (Just "def")) "abc" Make the difference between in minBase and maxBase larger in the call to newMap to prefer reads more. Note: This format seems awkward. I feel like I want to have the user to define an enumeration type e.g. data UpToFive = One | Two | Three | Four | Five instance Ix UpToFive where.... and have newMap::(Bounded base,Ix base)=>(key->[base]) -> MyMap base key elt But I can't figure out a nice way to auto-generate arbitrary size enumerations and manually doing so is too wearisome to contemplate. If you can generate these enumeration classes, then it would seem you could auto-derive functions that translate from an arbitrary key into [base]. -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com
[BTW, should we move to Haskell-Cafe?]
Because updates are not so infrequent that I want to pay the cost of replicating the entire array every update (or every ten!). I'm willing to exchange *some* read time for faster update. Also, because small array copies may be sufficiently faster than tree traversals that I may pay very little extra for faster reads.
FYI, my current code looks like this:
I'm afraid I'm somewhat confused. The hash-table related code makes the copy of the whole array every purgatory-size times. Thus, given the sequence of 'n' unique inserts (which don't trigger the major_rebuild), at most 2*n/|purgatory| elements will be moved. As I understand your code, in particular,
insert (ArrMap proto toBase ht) key elt = ArrMap proto toBase newHT where newHT= insert' proto ht (toBase key) elt insert' _ (HT x _) [] = HT x insert' proto (HT Nothing y) key = insert' proto (HT (Just proto) y) key insert' p (HT (Just ar) y) (k:ey) = \val -> HT (Just $ newArray val) y where newArray val = ar//[(k,insert' p (ar!k) ey val)]
you make a copy of an array of the size |base| |key| times. _If_ the tree is kept balanced and filled, then the sequence of n inserts will copy (log n)/(log |base|)*|base| elements. For small n and large |base|, that can be a lot. For example,
testMap=newMap (chr 0) (chr 255) id main = do print $ lookup (insert testMap "abc" (Just "def")) "abc"
involves copying a 256-element array three times. Right? I guess we have come to the point where we really need to know the distribution of reads and writes, the length of the key (and if it is bounded), and the distribution of key values. We must also be sure of the cost basis. So far, we have concentrated only on the traversal through and moving of elements as the function of the size of the map. This is clearly not sufficient, as Andrew Bromage pointed out.
participants (6)
-
ajb＠spamcop.net -
Hal Daume III -
JP Bernardy -
oleg＠pobox.com -
S. Alexander Jacobson -
S. Alexander Jacobson