elm-explorations / benchmark

BSD 3-Clause "New" or "Revised" License
26 stars 4 forks source link

Scale use case: data structure benchmark #9

Open BrianHicks opened 6 years ago

BrianHicks commented 6 years ago

Issue by mpizenberg Saturday Jan 06, 2018 at 08:44 GMT Originally opened as https://github.com/BrianHicks/elm-benchmark/issues/45


Hi and first of all, thanks for this package!

Context

As suggested in scale documentation and in this discourse post here is my use case for scale. I'm currently working on making JavaScript TypedArray API available in elm. My reasons are two-fold:

  1. Grow the cover of Web API in elm. Typed arrays are use for ArrayBuffers, Blobs, Files, network exchange, canvas data etc. So having them in elm is important in my opinion.
  2. They are the only fixed-size, typed structures in JS. Due to this, I'm convinced they can be used as a solid ground for fixed size efficient mathematical (Linear Algebra) library.

The code is on github: mpizenberg/elm-js-typed-array. To make this happen, I'm benchmarking all key functions of the package (initialize, map, foldl, append, ...). Benchmarks are in the benchmarks/ directory.

Benchmark Structure

The goal of the benchmarks are to make sure that typed arrays are fast for all potential use cases, ranging from small array manipulation, to big image-like (~10^6 pixels) matrices. Therefore, I'm comparing each key function at different scales (set in Constants.sizeScales) with three data structures, List, Array and JsTypedArray (4 actually since testing both JsTypedArray Uint8 and JsTypedArray Float64).

Therefore, every benchmark file looks like the following:

module Append exposing (..)

-- imports

main : BenchmarkProgram
main =
    program <|
        describe "Append" <|
            [ lists
            , hamtArrays
            , uint8Arrays
            , float64Arrays
            ]

lists : Benchmark
lists =
    -- scale benchmark
    Constants.sizeScales
        |> List.map (\size -> ( size, List.repeat size 0 ))
        |> List.map (\( size, list ) -> ( toString size, \_ -> List.append list list ))
        |> scale "List"

hamtArrays : Benchmark
-- scale benchmark

uint8Arrays : Benchmark
-- scale benchmark

float64Arrays : Benchmark
-- scale benchmark

Results / Wished Features

At the end of the day, what I'd like to visualize is a plot comparing the different data structures at different scales. With the hypothesis that the benchmark went well and I can rely on the timing measures, I'd do a plot similar to the one below. Using logarithmic scale to make it more understandable. Plot source on this google document. With this plot, you immediately see for example that at large scale, the appending operation with JsTypedArray Uint8 is one order of magnitude faster than with other data structures.

benchmark-append-chart