On 11/8/05, Jan-Willem Maessen wrote:

On Nov 7, 2005, at 9:02 AM, Bulat Ziganshin wrote:

...

...Simon, can you please write some docs about all these foreign stuff and their interaction with pure Haskell code? i see some bits of this information in these newsgroups regularly (for example, are you remember discussion about using lots of hashtables in program?), but there is no definitive source

Just wanted to let people know that I've been working on improving Data.HashTable, with the help of Ketil Malde's badly performing code and a bunch of locally-rolled tests. Things are looking much better now, but will look better still when Simon M's GC fixes are more widely deployed (which ought to make the extant code perform much better). I'm still not satisfied with any of the solutions, in part because I don't know whether they will also improve when I apply the GC fixes; if they don't ehy'll merely be on a par with the current library, and I only intend to release something which actually appears to work better in practice.

That said, none of the HashTable problems had anything to do with foreign code.

I've also created a QuickCheck suite for testing Data.HashTable. Very handy. I don't know if there's a standard way to release testing code for extant libraries...

Request: Data.HashTable.Immutable Really an immutable version should be standard (like for Array). Lots of places where you use a Map could be improved by using a HashTable instead (a lot of times you just fill it up once and then use it exclusively for querying). /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

On Nov 9, 2005, at 4:46 AM, Ketil Malde wrote:

Sebastian Sylvan wrote:

...

On 11/8/05, Jan-Willem Maessen wrote:

...

Just wanted to let people know that I've been working on improving Data.HashTable, with the help of Ketil Malde's badly performing code

Always happy to help, of course - bad performance R us:-)

I think that if I can get unsafeFreeze/unsafeThaw to work reliably, it'll finally outperform Data.Map on your example. I haven't yet played with the hash function, which looks kind of bad; there may be hope for improvement there as well.

...

Request: Data.HashTable.Immutable

I'm not sure you really want that - do you wish to copy a large array each time you do an update? Freezing and thawing might be a good idea, though.

A true read-only hash table, with a freeze for the mutable version, but NO THAW, could potentially be useful. I seem to recall that hbc had an immutable hash table (along with a derivable Hashable class), where the content was specified as in an array comprehension. User-level Thaw is a bad idea, and I will resist it, even if the library ends up using Freeze/Thaw internally to work around GC shortcomings.

HashTable's interface is rather impoverished, compared to Map and even Array. Ideally, it should support many of the same operations, and presumably it could work with the ST monad as well as IO.

It's certainly possible to code many of these up---the cleanest code I've gotten so far would even make it easy, as everything but lookup goes through 2 higher-order INLINE functions (a generic insert/delete and a map/reduce, each on a list of pairs). But I'm going to focus for the moment on the most pressing need, which is acceptable performance for what we've got. I hope the result will make new functionality easier to provide. -Jan

-k _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 11/9/05, Ketil Malde wrote:

Sebastian Sylvan wrote:

...

On 11/8/05, Jan-Willem Maessen wrote:

...

Just wanted to let people know that I've been working on improving Data.HashTable, with the help of Ketil Malde's badly performing code

Always happy to help, of course - bad performance R us:-)

...

Request: Data.HashTable.Immutable

I'm not sure you really want that - do you wish to copy a large array each time you do an update?

Well if you want a mutable hashtable you use the mutable one. In many cases you want to have a map from generic keys to values that never (or very seldom) change. A Data.Map is usually used in this case, but if you do a lot of lookups it would be nice to have a hashmap that can still be used in pure code. It's basically analogue to Arrays. Sometimes you use IArray and sometimes MArray. In fact the hashmap could be parameterized on an internal Array representation so you could have DiffArray based Hashmaps which support O(1) updates, but still has an immutable interface. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862