major missing piece to arrays?
Perhaps I am just missing something, but a major piece of efficient array functionality seems to be missing. Namely the ability to efficiently copy spans of arrays into one another and/or compare spans of memory. (basically memcpy and memcmp from C). any particular reason these basic building blocks were left out? I am trying to write an efficient packed string library and having to go through intermediate lists kills the garbage collector as well as the overall speed of my program. Ideally concatination should be a simple alloc + pair of memcpys. (yeah, I know they are both of linear order, but the constant factor on a system tuned assembler memcpy vs. chugging of the STG-machine is absurdly different when cache is taken into account) So, my question is also, as a workaround for the moment, how might I implement these rountines (without resorting to rewriting all the array functionality with Foreign)? Looking at the implementations of arrays, they all seem to be built on ByteArray#'s, if I could get a (Ptr a) out of them, that would be ideal, but I imagine that might be problematic without some mechanism to temporarily pin the address in place so the GC doesn't move it. I am thinking a family of routines. (with psuedosignatures) copySpan: range -> MArray -> whereto -> MArray -> m () extractSpan : range -> IArray -> IArray extractSpanM : range -> MArray -> m IArray saveSpan : range -> IArray -> whereto -> MArray -> m () hopefully the meaning of all is clear... perhaps better names can be come up with though. A similar set of routines which perform 'memcmp' would also be useful, but less vital at the moment. Sorry if I am just blind and missing these rountines... John -- John Meacham - ⑆repetae.net⑆john⑈
On Thu, Jul 15, 2004 at 04:26:27AM -0700, John Meacham wrote:
I am thinking a family of routines. (with psuedosignatures)
copySpan: range -> MArray -> whereto -> MArray -> m () extractSpan : range -> IArray -> IArray extractSpanM : range -> MArray -> m IArray saveSpan : range -> IArray -> whereto -> MArray -> m ()
I would like to have these, too. I would especially like to have saveSpan :: (Int, Int) -> UArray Int Word8 -> (Int, Int) -> IOUArray Int Word8 -> IO () copySpan :: (Int, Int) -> IOUArray Int Word8 -> (Int, Int) -> IOUArray Int Word8 -> IO () to use these in conjunction with hGetArray and hPutArray. In the hope of advancing the discussion, I have taken up the trivial task of implementing the above on top of the usual array functions. (I have not done any testing, though.) Maybe some kind soul with knowledge of the ghc innards can provide an implementation that reduces to a memcpy call, at least for some specializations. 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.
On Tue, Jul 20, 2004 at 02:56:15AM +0200, Carsten Schultz wrote:
On Thu, Jul 15, 2004 at 04:26:27AM -0700, John Meacham wrote:
I am thinking a family of routines. (with psuedosignatures)
copySpan: range -> MArray -> whereto -> MArray -> m () extractSpan : range -> IArray -> IArray extractSpanM : range -> MArray -> m IArray saveSpan : range -> IArray -> whereto -> MArray -> m ()
I would like to have these, too. I would especially like to have
saveSpan :: (Int, Int) -> UArray Int Word8 -> (Int, Int) -> IOUArray Int Word8 -> IO () copySpan :: (Int, Int) -> IOUArray Int Word8 -> (Int, Int) -> IOUArray Int Word8 -> IO ()
to use these in conjunction with hGetArray and hPutArray.
In the hope of advancing the discussion, I have taken up the trivial task of implementing the above on top of the usual array functions. (I have not done any testing, though.) Maybe some kind soul with knowledge of the ghc innards can provide an implementation that reduces to a memcpy call, at least for some specializations.
Cool, I can build more efficient versions on these now that I know the ByteArray# as Addr# trick. I am curious what the best way to go about writing specialized versions is, placing the copying functions in a class, with (slow) default methods for everything and special instances for (IO)UArrays? or relying on RULES pragmas to do the appropriate specialization? anyone have any intuition on which would be a better approach to take? The class is more straightforward, but since we are not changing behavior, just doing a pure type based optimization, perhaps RULES is the better way to go. (can RULES even be used in this way? it looks like they are already to implement unsafeFreeze and unsafeThaw) John -- John Meacham - ⑆repetae.net⑆john⑈
(I am not sure, if keeping the cc to libraries is ok, apologies in case it is not.) On Mon, Jul 19, 2004 at 06:23:21PM -0700, John Meacham wrote:
I am curious what the best way to go about writing specialized versions is, placing the copying functions in a class, with (slow) default methods for everything and special instances for (IO)UArrays? or relying on RULES pragmas to do the appropriate specialization?
I would vote for RULEs.
anyone have any intuition on which would be a better approach to take? The class is more straightforward, but since we are not changing behavior, just doing a pure type based optimization, perhaps RULES is the better way to go.
Exactly.
(can RULES even be used in this way?
I think so: http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html#SPECIAL... 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.
participants (2)
-
Carsten Schultz -
John Meacham