DOCSEARCHbyAlgolia
Submit Docs

haskell-vector

repository·master·Indexed 18 days ago

https://github.com/haskell/vector

A collection of efficient Int-indexed array implementations in Haskell, providing mutable and immutable versions of boxed, unboxed, storable, and primitive vectors. The library features a generic API and a stream fusion optimization framework that eliminates intermediate data structures during function composition.

Tokens
865
Snippets
1
Records
8
Agent score
64%

What's inside vector

  1. Overview of the vector-stream package

    master
    The vector-stream package provides an efficient implementation of monadic streams. These streams are specifically designed to be used for stream fusion within the main vector package, allowing for high-performance array operations by combining multiple transformations into a single pass.

  2. Overview of the vector package

    master
    The vector package provides a collection of efficient Int-indexed array implementations in Haskell. It offers both mutable and immutable versions of several vector types and features a generic API that is polymorphic across vector types. A key feature is the implementation of stream fusion, an optimization framework that eliminates intermediate data structures during function composition.

  3. How stream fusion works in vectors

    master

    Stream fusion is an optimization framework used by the vector package to merge multiple function calls into a single loop, preventing the allocation of intermediate data structures.

    For example, a composition like sum . filter g . map f will be optimized during compilation to avoid creating temporary vectors between the map and filter steps.

  4. Vector vs Array

    master

    While Haskell has a built-in Data.Array module, vectors are generally preferred for modern Haskell development because:

    • They provide $O(1)$ access to elements (similar to arrays).
    • They offer a much friendlier API, similar to lists.
    • They support framework optimizations like loop fusion (stream fusion) for better efficiency.

  5. Choose the right vector type

    master

    The package provides different vector implementations depending on your performance and memory requirements. Choose based on the following characteristics:

    • Lazy boxed vectors (Data.Vector): Store elements as pointers to heap-allocated values. They involve indirection and are generally slower than unboxed vectors.
    • Strict boxed vectors (Data.Vector.Strict): Contain elements that are strictly evaluated.
    • Unboxed vectors (Data.Vector.Unboxed): Highly efficient. They determine representation based on the element type (e.g., primitive types use primitive arrays, while product types use a structure of arrays).
    • Storable vectors (Data.Vector.Storable): Backed by pinned memory that cannot be moved by the garbage collector. These are primarily used for C FFI (Foreign Function Interface).
    • Primitive vectors (Data.Vector.Primitive): Backed by simple byte arrays. They can only store types belonging to the Prim type class (e.g., Int, Double) that are represented as sequences of bytes without pointers. Use Data.Vector.Unboxed if you want similar performance with more versatility.

  6. Manage random number seeds in benchmarks

    master

    The benchmarks in benchlib depend on random numbers. By default, these are generated using a static seed. To ensure benchmark results are not misleading due to specific data distributions, follow these steps:

    1. Run the benchmarks using the default static seed for an initial approximation.
    2. Verify the consistency of your results by running the benchmarks multiple times with different seeds.

    You can change the seed used by the benchmarks by modifying the Main.useSeed function.

  8. Visually inspect fusion performance with microsuite

    master
    The microsuite contains a set of small programs designed to visually inspect whether stream fusion is working correctly. Many of these programs have runtimes that increase significantly (explode) if fusion fails, making them effective indicators of fusion status.