RE: [Haskell] performance tuning Data.FiniteMap
I was thinking about improving array performance, and was wondering if a transactional model would work well. You would keep a base copy of the array, and any writes would be written to a delta style transaction list. A reference to the array would be the list plus the base array. Different references to the same array would just reference different points in the delta list. The garbage colector would eat the delta list from the tail, merging writes into the base array once references to that part of the list are discarded. Writes would be very fast - just the time to add a delta to the transaction list. Reads would slow down as the transaction list grows, but the list would only be as long as the oldest reference, so providing references to very old copies of the array are not required, the transaction list would remain short. It would be even more efficient if the 'liveness' of references could be checked when writing the array - at the cost of a slight slowdown in write performance. I would be interested in any comments... I suspect somebody has done this before, but I havent looked for any papers yet. Regards Keean Schupke. ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: [Haskell] performance tuning Data.FiniteMap
MR K P SCHUPKE [EMAIL PROTECTED] writes: I was thinking about improving array performance, and was wondering if a transactional model would work well. I would be interested in any comments... I suspect somebody has done this before, but I havent looked for any papers yet. O'Neill and Burton, A New Method for Functional Arrays, JFP 7(5), 1997. http://citeseer.ist.psu.edu/328736.html Regards, Malcolm ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: [Haskell] performance tuning Data.FiniteMap
Hi Simon! On Fri, Feb 27, 2004 at 09:20:40AM -, Simon Peyton-Jones wrote: There are several things that aren't research issues: notably, faster copying, fewer intermediate lists, fewer state-monad-induced intermediate closures. These are things that would move sharply up our priority list if you had a real application that was stumbling on them. From the context, it is not clear to me, if you are writing about arrays or FiniteMap. Regarding FiniteMap: I would want it to be as good as possible and advertised more. If you see how pervasive dictionarys are eg in Python, finite maps should be our counterpart, and they should be so good that nobody would ever think about using a plain list for storing items that have to be looked up later. However, they me already be that good, I do not have any complaints, I just wanted to state that I think them important. Just my humble opinion... Greetings, Carsten -- Carsten Schultz (2:38, 33:47), FB Mathematik, FU Berlin http://carsten.codimi.de/ PGP/GPG key on the pgp.net key servers, fingerprint on my home page. pgp0.pgp Description: PGP signature ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: [Haskell] performance tuning Data.FiniteMap
[Moving to GHC users list] There are several things that aren't research issues: notably, faster copying, fewer intermediate lists, fewer state-monad-induced intermediate closures. These are things that would move sharply up our priority list if you had a real application that was stumbling on them. What I obviously can't promise is that improving these things would solve your problem -- if, indeed, you turn out to have one! Simon | -Original Message- | From: S. Alexander Jacobson [mailto:[EMAIL PROTECTED] | Sent: 26 February 2004 23:27 | To: Simon Peyton-Jones | Cc: [EMAIL PROTECTED] | Subject: RE: [Haskell] performance tuning Data.FiniteMap | | Is fixing GHC arrays a big research job or is it | something that someone can straightforwardly | handle if my site actually gets enough traffic to | warrant it? | | -Alex- | | On Thu, 26 Feb 2004, Simon Peyton-Jones wrote: | | | But in managing this tradeoff, what is faster: | | * constructing/destructing e.g. 16 trees (for a 65000 item table) | | * 2 memcpy of 256 item arrays (perhaps after you primop?) | | | | If the later is not dramatically slower than I | | will bias towards more arrayness. | | I doubt the latter is dramatically slower, but you'd have to experiment | to find out. And GHC is not doing as well as it should on arrays just | now. (One of the things on our to-do list.) Might vary between | implementations too. | | Simon | | | _ | S. Alexander Jacobson mailto:[EMAIL PROTECTED] | tel:917-770-6565 http://alexjacobson.com ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: [Haskell] performance tuning Data.FiniteMap
| But in managing this tradeoff, what is faster: | * constructing/destructing e.g. 16 trees (for a 65000 item table) | * 2 memcpy of 256 item arrays (perhaps after you primop?) | | If the later is not dramatically slower than I | will bias towards more arrayness. I doubt the latter is dramatically slower, but you'd have to experiment to find out. And GHC is not doing as well as it should on arrays just now. (One of the things on our to-do list.) Might vary between implementations too. Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: [Haskell] performance tuning Data.FiniteMap
Is fixing GHC arrays a big research job or is it something that someone can straightforwardly handle if my site actually gets enough traffic to warrant it? -Alex- On Thu, 26 Feb 2004, Simon Peyton-Jones wrote: | But in managing this tradeoff, what is faster: | * constructing/destructing e.g. 16 trees (for a 65000 item table) | * 2 memcpy of 256 item arrays (perhaps after you primop?) | | If the later is not dramatically slower than I | will bias towards more arrayness. I doubt the latter is dramatically slower, but you'd have to experiment to find out. And GHC is not doing as well as it should on arrays just now. (One of the things on our to-do list.) Might vary between implementations too. Simon _ S. Alexander Jacobson mailto:[EMAIL PROTECTED] tel:917-770-6565 http://alexjacobson.com ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: [Haskell] performance tuning Data.FiniteMap
| (//) 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? It's slow because it costs O(n) for what someone might expect to be an O(1) operation. Since the compiler does not know whether the 'old' array is going to be re-used for something else, it's forced to make a copy of the array, modifying the specified slot(s). Yes, the implementation could use memcpy, but it's still ridiculously expensive to copy a 10,000 word array to only modify one word. (GHC does not use memcpy -- it generates an explicit loop instead -- but it could if we added a new primop to encapsulate memcpy.) Advanced compiler optimisations might help, by detecting when the old copy isn't needed, but they are much much harder in a lazy language, and fragile to small program changes to boot. GHC makes no such attempt. An alternative is to put single-threaded-ness into the type system, as Clean does. Haskell's current story is to use O(log n) structures such as trees -- or to use a state monad. | 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. You should feel no need to apologise. Our community *needs* people like you, who are using Haskell for real applications. That's how we'll learn where the shoe pinches. Ask away. Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Use Radix for FiniteMap? (was Re: [Haskell] performance tuning Data.FiniteMap)
G'day all. Quoting S. Alexander Jacobson [EMAIL PROTECTED]: 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 ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: [Haskell] performance tuning Data.FiniteMap
I know that array copy is much more expensive than a single update. But when you say: On Wed, 25 Feb 2004, Simon Peyton-Jones wrote: Haskell's current story is to use O(log n) structures such as trees -- Yes, I got that. The question is how I trade off between reads and writes. If I write very infrequently I may be willing to pay for varying levels of more arrayness (lower read time, higher update time). But in managing this tradeoff, what is faster: * constructing/destructing e.g. 16 trees (for a 65000 item table) * 2 memcpy of 256 item arrays (perhaps after you primop?) If the later is not dramatically slower than I will bias towards more arrayness. In this context, I believe that mmx insns in modern CPUs dramatically accelerate in-cache memcpy. If that is the case, then e.g. 256 element arrays could be optimal. You should feel no need to apologise. Our community *needs* people like you, who are using Haskell for real applications. That's how we'll learn where the shoe pinches. Ask away. Thank you. -Alex- _ S. Alexander Jacobson mailto:[EMAIL PROTECTED] tel:917-770-6565 http://alexjacobson.com ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] performance tuning Data.FiniteMap
S. Alexander Jacobson wrote:
Does FiniteMap used Arrays, Lists, or Algebraic Types?
when in doubt, RTFC:
http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/libraries/base/Data/FiniteMap.hs?rev=1.17
data FiniteMap key elt
= EmptyFM
| Branch key elt -- Key and elt stored here
IF_GHC(Int#,Int{-STRICT-}) -- Size = 1
(FiniteMap key elt) -- Children
(FiniteMap key elt)
the hugs distribution even says where this comes from:
This code is derived from that in the paper:
\begin{display}
S Adams
Efficient sets: a balancing act
Journal of functional programming 3(4) Oct 1993, pp553-562
\end{display}
--
-- Johannes Waldmann, Tel/Fax: (0341) 3076 6479 / 6480 --
-- http://www.imn.htwk-leipzig.de/~waldmann/ -
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] performance tuning Data.FiniteMap
S. Alexander Jacobson [EMAIL PROTECTED] writes: 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! I'm probably missing something, but how can you do this for general Ord types? Don't you need a linear search through the array to find the correct subtree? -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
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 ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] performance tuning Data.FiniteMap
as a tangent, for absurdly fast and optimal (optimized to the cache line) maps see http://judy.sourceforge.net/ the algorithms behind them are very cool. see http://judy.sourceforge.net/downloads/10minutes.htm for a quick discussion of why they are fast (there is a fewhundred page book too) heh. although I doubt any of the optimizations will be implementable in haskell any time soon. not ghc's Haskell# even... John -- --- John Meacham - California Institute of Technology, Alum. - [EMAIL PROTECTED] --- ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] performance tuning Data.FiniteMap
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:[EMAIL PROTECTED] 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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] performance tuning Data.FiniteMap
It seems like updates could be very fast because I assume // is implemented with a fast memcpy (//) is very slow _ S. Alexander Jacobson mailto:[EMAIL PROTECTED] 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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell -- Hal Daume III | [EMAIL PROTECTED] Arrest this man, he talks in maths. | www.isi.edu/~hdaume ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Use Radix for FiniteMap? (was Re: [Haskell] performance tuning Data.FiniteMap)
[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:[EMAIL PROTECTED] 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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] performance tuning Data.FiniteMap
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:[EMAIL PROTECTED] tel:917-770-6565 http://alexjacobson.com ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
