|Subject:||Re: [Haskell-cafe] Boxed Mutable Arrays|
|Date:||Wed, 16 Dec 2009 14:58:02 -0500|
On Wed, Dec 16, 2009 at 2:42 PM, Richard Kelsall <[email protected]> wrote:
Your asymptotics will take a hit if the height of the tower is logarithmic in the array size, and you'll take a constant hit for bounded-height towers.
Consider that if you have density such that the biggest array has an expected population, then your smaller arrays will be relatively drastically over populated, so you'll bump up to the next largest array in more cases, paying extra seeks against disproportionally heavily loaded buckets, whereas the time could have been more gainfully employed seeking against the more uniformly distributed larger bucket.
If you have a decent hash function, you won't have lumps in your distribution, so having lumps in your bucket densities is purely a pessimization. Especially when you've ensured that those buckets that are going to be overpopulated are exactly the ones you are checking first.
You might consider looking at Witold Litwin's Sorted Linear Hash Table. I have a hackish implementation on hackage somewhere, but bear in mind it was the first piece of Haskell I'd ever written and the STM version I have bottlenecks on the root of the tree, so would be better served by multiple root TVars.
I can't find it on Hackage, but here it is:
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
|<Prev in Thread]||Current Thread||[Next in Thread>|
|Previous by Date:||Re: [Haskell-cafe] Boxed Mutable Arrays, Richard Kelsall|
|Next by Date:||[Haskell-cafe] Reading from a process, Mitar|
|Previous by Thread:||Re: [Haskell-cafe] Boxed Mutable Arrays, Richard Kelsall|
|Next by Thread:||Re: Re: [Haskell-cafe] Boxed Mutable Arrays, Don Stewart|
|Indexes:||[Date] [Thread] [Top] [All Lists]|