Don, On Mon, Dec 14, 2009 at 4:16 PM, Don Stewart wrote:

brad.larsen:

...

Is anyone working on fixing ticket #650 http://hackage.haskell.org/trac/ghc/ticket/650?  In short, STArray and the garbage collector don't play well together, resulting in array updates being non-constant time operations.  This bug makes it very difficult/impossible to write efficient array algorithms that depend upon mutation in Haskell.

On another note, does this (or perhaps better phrased, will this) bug also affect Data Parallel Haskell?

What are you using boxed arrays for?

Two immediate examples come to mind: a generic, heap-based priority queue using an array, or a generic hash table that has acceptable performance.

(DPH, vector, uvector, are all for unboxed arrays, which are not affected, obviously).

-- Don

The vector package on haskell has boxed arrays. Is DPH *really* only for primitive, unboxed types? If so, that's unfortunate. Sincerely, Brad

On Mon, Dec 14, 2009 at 4:34 PM, Don Stewart wrote:

brad.larsen:

...

The vector package on haskell has boxed arrays.  Is DPH *really* only for primitive, unboxed types?  If so, that's unfortunate.

No, it's not only, but all the uses I've seen have been related to numerics, represented with unboxed types.

I'm just curious if you have a current use case -- since that would help get interest in the ticket.

-- Don

How about a fast STHashTable? Or a fast priority queue in ST where priorities are integers of a known size? Such a priority queue can be implemented as an array of sequences---int priority is array index. I want to use such data structures for research in heuristic search algorithms, to get top performance, more than from using an IntMap / Map / whatever-other-persistent-data-structure. I'm trying to at least be ballpark competitive with C implementations of certain heuristic search algorithms, which use the forbidden magic of mutable data structures. I'd prefer to work in Haskell rather than rewrite in C. Right now, in Haskell, it doesn't seem possible to write the kind of algorithms I am working with, using high-performance mutable data structures, because of the boxed array/GC bugs. Sincerely, Brad

bulat.ziganshin:

Hello Brad,

Tuesday, December 15, 2009, 1:55:41 AM, you wrote:

...

How about a fast STHashTable?

you can use array of arrays instead of large array

Note to minmize the issue, but we get many of the same benefits via the associated type transformation (e.g. for arrays of pairs/complex/triples) -- Don

Bulat, On Tue, Dec 15, 2009 at 1:51 AM, Bulat Ziganshin wrote:

Hello Brad,

Tuesday, December 15, 2009, 1:55:41 AM, you wrote:

...

How about a fast STHashTable?

you can use array of arrays instead of large array

-- Best regards,  Bulat                            mailto:Bulat.Ziganshin@gmail.com

Can you elaborate?

On Tue, Dec 15, 2009 at 11:00 AM, Bulat Ziganshin wrote:

Hello Brad,

Tuesday, December 15, 2009, 6:53:14 PM, you wrote:

...

...

...

How about a fast STHashTable?

you can use array of arrays instead of large array

...

Can you elaborate?

what exactly? how to implement this or why it will be faster?

-- Best regards,  Bulat                            mailto:Bulat.Ziganshin@gmail.com

You said to use an array of arrays instead of a large array, in the context of a fast hash table in ST. Do you mean I should use an array for hash buckets, rather than a list? Is that what you meant? And why would it be faster? If the number of buckets was fixed, one could use an array of STRefs to lists. I believe this would avoid the bug from Ticket #650?

...

If the number of buckets was fixed, one could use an array of STRefs to lists.  I believe this would avoid the bug from Ticket #650? now i see what you mean. no, i mean trivial transformation. #650 says about slow GC. why it's slow? because once you made any update to the array, the entire array is marked as updated and scanned on next minor GC (which occurs after every 512 kbytes allocated, afaik). let's replace big array (say, of 10,000 elements) with array of 100 arrays of 100 elements each. now, between minor GCs only some of arrays will be changed and entire amount of memory to be scanned will become less

Data.IntMap?

...

...

now i see what you mean. no, i mean trivial transformation. #650 says about slow GC. why it's slow? because once you made any update to the array, the entire array is marked as updated and scanned on next minor GC (which occurs after every 512 kbytes allocated, afaik). let's replace big array (say, of 10,000 elements) with array of 100 arrays of 100 elements each. now, between minor GCs only some of arrays will be changed and entire amount of memory to be scanned will become less Data.IntMap? I want to implement a more-or-less traditional, mutable, imperative hash table in the ST monad.  Hence, I'm not considering Data.IntMap and other persistent tree structures for its implementation, although I have thought about it. The bug described in Ticket #650, AFAICS, prevents implementation of a reasonable, generic hash table in Haskell.  :-(

Data.IntMap is just a limit of what Bulat suggested. So what was you thoughts about Data.IntMap in mutable hashmap?

Brad Larsen wrote:

I have considered using Data.IntMap to implement a sort of faux hash table, e.g., introduce a Hashable class, and then use an IntMap to lists of Hashable. The result would be a pure, persistent ``hash table''. In such a case, however, lookup/insert/delete operations would have average complexity logarithmic in the number of buckets.

I'll throw in an idea that has been nagging me about hash tables. You could have a list of hash tables of increasing size. On an insert collision in a smaller table all the entries get put into the next one up. For a lookup you would have to check all the tables until you find the hash. e.g. With three hash table in the list of these example sizes. Table size 2^2 = 2 probable entries before collision. 2^4 = 4 2^6 = 8 h..h ...h.....h.h...h h......h.......h....h...........h......h.h..........h........... I expect if it's any good it has already been done. Richard.

brad.larsen:

On Tue, Dec 15, 2009 at 11:33 AM, Serguey Zefirov wrote:

...

...

...

If the number of buckets was fixed, one could use an array of STRefs to lists.  I believe this would avoid the bug from Ticket #650? now i see what you mean. no, i mean trivial transformation. #650 says about slow GC. why it's slow? because once you made any update to the array, the entire array is marked as updated and scanned on next minor GC (which occurs after every 512 kbytes allocated, afaik). let's replace big array (say, of 10,000 elements) with array of 100 arrays of 100 elements each. now, between minor GCs only some of arrays will be changed and entire amount of memory to be scanned will become less

Data.IntMap?

I want to implement a more-or-less traditional, mutable, imperative hash table in the ST monad. Hence, I'm not considering Data.IntMap and other persistent tree structures for its implementation, although I have thought about it.

The bug described in Ticket #650, AFAICS, prevents implementation of a reasonable, generic hash table in Haskell. :-(

You can certainly implement it, it just requires that you increase the heap size to a bit bigger than your hash to reduce the pressure on the GC. But note, Simon's making progress, http://hackage.haskell.org/trac/ghc/ticket/650#comment:17 -- Don

On Wed, Dec 16, 2009 at 11:27 AM, Don Stewart wrote: [...]

...

The bug described in Ticket #650, AFAICS, prevents implementation of a reasonable, generic hash table in Haskell.  :-(

You can certainly implement it, it just requires that you increase the heap size to a bit bigger than your hash to reduce the pressure on the GC.

But note, Simon's making progress,    http://hackage.haskell.org/trac/ghc/ticket/650#comment:17

-- Don

Nice! Even if it is only an improvement in the constant factor, and not a genuine fix for the problem, it sounds like a big improvement. Sincerely, Brad

On Tue, Dec 15, 2009 at 12:00 PM, Gregory Collins wrote:

Bulat Ziganshin writes:

...

now i see what you mean. no, i mean trivial transformation. #650 says about slow GC. why it's slow? because once you made any update to the array, the entire array is marked as updated and scanned on next minor GC (which occurs after every 512 kbytes allocated, afaik). let's replace big array (say, of 10,000 elements) with array of 100 arrays of 100 elements each. now, between minor GCs only some of arrays will be changed and entire amount of memory to be scanned will become less

I actually tried this, and modified Data.HashTable to use a two-tiered chunked dynamic array as you suggest. In some limited testing it was only about 5% faster, so I gave up on it -- you get some GC time back but you also pay a significant indirection penalty by adding an extra cache line miss for every operation.

G -- Gregory Collins

Indeed! A two-tiered implementation as Bulat describes is a big hack anyway. I don't want to have to dance around a bug! Sincerely, Brad

No, they are actually being mutated. ST is basically IO with a universal state thread (IO uses RealWorld) to prevent you from letting any of the mutable structures out (or any in) of the block. The whole point of ST is to have real mutable references/arrays that have a referentially transparent if you look at them from outside. Dan On Tue, Dec 15, 2009 at 9:23 AM, Alberto G. Corona wrote:

AFAIK, ST Arrays are pure data structures. They are not really mutable. They are destroyed and recreated on every update. The mutation is just simulated thanks to the hidden state in the state monad. Sure, the garbage collector must have a hard work in recycling all the "backbones" of the discarded arrays (not the elements).

2009/12/14 Brad Larsen

...

Is anyone working on fixing ticket #650 http://hackage.haskell.org/trac/ghc/ticket/650?  In short, STArray and the garbage collector don't play well together, resulting in array updates being non-constant time operations.  This bug makes it very difficult/impossible to write efficient array algorithms that depend upon mutation in Haskell.

On another note, does this (or perhaps better phrased, will this) bug also affect Data Parallel Haskell?

I would really like to see highly efficient, mutable, boxed arrays in Haskell!  Unfortunately, I don't have the know-how to fix Ticket 650.

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

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

On Dec 16, 2009, at 5:50 AM, Serguey Zefirov wrote:

2009/12/16 Matt Morrow :

...

What are peoples' thoughts on this? http://hackage.haskell.org/trac/ghc/ticket/650#comment:16

I think it won't get any better.

Either we have O(log(N)) updates because we have to update hierarchical structure to speed up GC scanning (to get it to O(Mlog(N)), where M is a number of updated cells), or we have O(N) scanning.

As far as I can tell, other systems (Java, for example) suffer from that problem as well.

The ticket suggests using VM protection to track writes. This has been tried a number of times over the years by the GC community, and has usually gone badly - it turns out getting the OS to tell you about the page fault in reasonable time is hard. It usually turns out to be cheaper just to make a cheap write barrier. There are tricks that let us avoid re-scanning an array frequently during generational GC (and in particular avoid the problem of re-scanning the entire array during minor GC just to catch a single write). But they require that we design appropriate read or write barriers for array accesses. This is a Simple Matter of Programming, but hasn't risen to the top of anyone's priority list (in spite of the fact that this bug has existed for over a decade now, as far as I know). It's fiddly coding and annoying to debug. For those who are curious, here's one trick that avoids repeated re-scanning of arrays during GC: * During post-allocation tracing, move all data pointed to by the array into contiguous chunks of memory. * Group together that memory logically with the memory containing the array itself. * Keep track of whether anything points in to this memory; if nothing does, free the lot of it (or use the bad old tracing method; you won't find the big array and won't pay anything). * If there are subsequent writes, trace those and move them to the region. * Re-scan the whole region only if there have been enough writes (presumably causing the region to fill with data that has been overwritten and thrown away). Here the cost is roughly proportional to the number of writes you perform. Haskell being lazy, that might be more than you would expect. There are (lots of) other tricks along the same lines with differing tradeoffs, and naturally I've skimmed over some important details. What you should take away is that GCing an array of pointers need not be expensive---we can do O(writes) scanning over its lifespan, rather than O(N) scanning work at every single GC. And note that in general we don't pay any GC costs at all unless we actually keep the array around for a while. -Jan-Willem Maessen

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