Category: Uncategorized

  • Migrating from uvector to vector

    Roman Leschinkskiy has released the 0.5 version of vector, the future standard non-parallel arrays library forGHC Haskell. This post covers some of the differences between it and uvector, and what to watch for when migrating code to use vector.

    The summary is — as of Feb 15, 2010 — you can move to vector now.  In almost all cases you will get identical performance to uvector, but with a nicer interface. There are currently a few small gaps in the API, and a couple of performance tweaks are needed to particular functions, but they should not affect most people (and likely will be fixed in coming days). Note that you should use the -Odph optimization flag for the most reliable results.

    Background

    vector is one of the results of the multi-year Data Parallel Haskell project, to develop high performance parallel bulk array processing for Haskell, allowing us to do very fast arrays (that is, transparently multicore parallel array processing, outperforming C or C++ by using cores more efficiently.)

    While this project concentrates on data parallelism, it has also lead to new approaches to flat, sequential arrays for Haskell. The code has been spun-off in two different packages, which replace the fifteen year old array package with faster, more flexible types and functions:

    These two libraries share a common origin, but have different engineering goals. Both libraries make heavy use of loop fusion based on streams to achieve excellent performance. (You can read more about that in a separate post).

    uvector is a conservative attempt to develop fast, unboxed arrays with a flexible interface based on fusion, to replace Data.Array in the short term, while vector was immature. uvector has been in active service for about two years now, filling a gap while we waited for vector to mature. uvector has several users now, including haskell-criterion haskell-histogram-fill haskell-hnn haskell-monte-carlo haskell-mwc-random haskell-pqueue-mtlhaskell-safe-freeze haskell-statistics haskell-statistics-fusion haskell-uvector-algorithms. These packages in the medium term should consider moving to vector.

    The vector library is far more ambitious, aiming to be the standard array library for high performance problems in all circumstances. It cleanly supports:

    • mutable arrays
    • immutable arrays
    • boxed
    • unboxed
    • storable types

    As for uvector, unboxed representations are specialized at compile time via type families, and fusion is used throughout the interface. Unlike uvector, vector supports boxed arrays, and provides inplace fusion of mutable array operations.

    If you need transparently parallel arrays, you should consider the dph package, distributed with GHC.

    Current status

    uvector is stable, and has gone into maintainance mode only. If you like it, you can safely continue to use it for  the foreseeable future, though any performance improvements in the fusion or array types developed in vector will not be backported to uvector.

    vector, as of 0.5, has been declared “beta”. You can begin migrating code to use it.

    Migrating your code

    I’ve just finished porting the uvector micro benchmark suite to vector, and have the following notes on how to migrate your code to use unboxed arrays in the vector package.

    Namespaces

    The old uvector namespace was Data.Array.Vector with U suffix appended to names. That goes away, and instead you should:

    import qualified Data.Vector as U

    Most function names are identical, so we have in vector the obvious counterparts to uvector. All these are basically unchanged:

    U.length U.null U.empty U.cons U.snoc U.replicate U.head
    U.last U.init U.tail U.take U.drop U.map U.filter U.elem U.notElem
    U.product U.sum U.maximum U.minimum U.foldl1 U.foldl U.dropWhile U.break
    U.find U.all U.any U.and U.or U.maximumBy U.minimumBy
    U.enumFromTo

    Some function names have changed:

    U.++ replaces appendU
    U.! replaces indexU

    Some functions are missing:

    lookupU repeatU

    There are many new functions on vectors, in particular, on mutable arrays, and for bulk operations (backpermute, reverse, accum).

    Better types

    Notably, vector supports boxed types, so you can more easily store Haskell values in fusible arrrays (so you can have, e.g. Integer arrays).

    Performance Wibbles

    I found only a few differences in performance compared to uvector, and have notified Roman. These shouldn’t affect many users currently, and will likely disappear in coming days.

    First, compile with -Odph instead of -O2, this fixes some optimization issues with zips, and probably other things.

    Functions to watch out for:

    • zip, zipwith, zipwith3 — uvector was a lot faster (10x) in simple programs — however, moving to -Odph fixes zips entirely.
    • Different fusion results for ’empty’ (kind of a corner case)
    • eq seems to be about twice as slow. Unsure why.
    • Bools don’t seem to be bit packed? At least, Bool unboxed arrays seem a bit slower than in uvector.
    • U.last appears to be optimized differently, though doesn’t affect performance.
    • Pipelines ending in ‘null’ (another corner case) are fused differently (slightly worse performance).

    And that’s about it.

    As of this post, I’m officially declaring uvector to be in maintainance-only mode, and will be working to improve vector.

  • Playing with the new Haskell epoll event library

    Bryan and Johan have been working hard on replacing the GHC runtime’s concurrency mechanism based on select, with a new one based on epoll. This should improve scalability of Haskell server code in a number of ways — more connections sec, more concurrent connections, and so on.

    You can read about their work in a series of posts:

    And you can find the current code for haskell-event on github: http://github.com/tibbe/event

    After reading this post, on how epoll-based user land callbacks can outperform general purpose preemptive threads for non-compute bound IO work, I wanted to see what improvements we can hope for from an epoll-based version in Haskell.

    The full code, which shows how to set up simple socket event notification using the event lib, is on the Haskell wiki, and will be useful for getting a flavor of the event lib use.

    The results:

    So while a simple forkIO/accept version, doing Handle and String IO would peak out around 7k req/sec, the epoll based version reached over 15k req/sec.

    So that’s useful: good epoll-based event code for Haskell. The next step will be to see the redesign of Control.Concurrent based on epoll being merged into GHC.