Benchmarking algebraic effect handler implementations

Overview

Benchmarking Effect handlers.

Currently supported libraries and languages are:

  • kk (extension .kk), Koka.
  • ml (extension .ml), multi-core OCaml.
  • hs (extension .mp.hs), Mp.Eff Haskell library.
  • ev (extension .ev.hs), Ev.Eff Haskell library.
  • hia (extension .hia.hs), Handers-in-Action Haskell library.
  • lh (extension .lh.c), libhandler C library.
  • lmp (extension .lmp.c), libmprompt C library.
  • base (extension base.ml), a plain baseline version without using effect handlers directly in OCaml.

And the variants without tail-resumptive optimization.

  • kknt (extension .nt.kk), Koka.
  • hsnt (extension .nt.mp.hs), Mp.Eff.
  • evnt (extension .nt.ev.hs), Ev.Eff.
  • lhnt (extension .nt.lh.c), libhandler.
  • lmpnt (extension .nt.lmp.c), libmprompt.

The benchmark sources are in the src directory and consist of:

  • counter: tight loop with state effect handler doing a get and put (tail-resumptive) operation per iteration (100M).
  • counter1: as counter but with an unused reader handler in between.
  • counter10: as counter but with 10 unused reader handlers in between.
  • mstate: as counter, but using a monadic non-tail-resumptive state handler (and only 10M iterations).
  • nqueens: the nqueens 12 problem using a multiple resumes to implement backtracking.

The benchmarks are small and targeted by design, and effect handler operations should dominate the run times. To make the benchmarks as "equal" as possible, we note:

  • We use native ints when possible (Int in Haskell, int in ML and C, and int32 in Koka)
  • Koka uses sometimes rcontrol (raw control) to avoid running finally clauses automatically (in mstate)

A detailed description of the benchmarks and comparison can be found in the following tech report:

  • Generalized Evidence Passing for Effect Handlers, Ningning Xie and Daan Leijen, MS-TR-2021-5, Mar 2021, (pdf)

Enjoy, Daan and Ningning

Note: the benchmarks come with no support, please submit any improvements as a PR :-) If you add your own system to the benchmarks, or add more benchmarks please add detailed installation instructions to the readme and submit it as a PR (or become a dev on the repo).

Installing Prerequisites

This is tested on Ubuntu 20.04 and macOS Catalina. Follow the installation instructions carefully.

Koka

Install koka:

$ curl -sSL https://github.com/koka-lang/koka/releases/latest/download/install.sh | sh
$ koka --version
Koka 2.1.1, 17:46:03 Mar  8 2021 (ghc release version)

Haskell

Install Ghc and Cabal:

$ sudo apt-get install ghc cabal      # on macOS: > brew install ghc cabal-install
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.6.5    # 8.10.4 is also good

Install the primitive and eveff package:

$ cabal update
$ cabal install primitive eveff    # use cabal install --lib on ghc 8.10+
$ cabal info primitive eveff | grep installed:
Versions installed: 0.7.1.0  # primitive
Versions installed: 0.1.0.0  # eveff

Ev.Eff

Already installed as the package eveff

Mp.Eff

Clone from the benchmark root directory (into the mpeff sub-directory).

$ git clone https://github.com/xnning/mpeff

Handlers-in-Action

Tested with ghc 8.6.5. Clone from the benchmark root directory (into the effect-handlers sub-directory).

$ git clone https://github.com/slindley/effect-handlers -b ghc865
$ cabal update
$ cabal install random pipes haskell-src-meta haskell-src-exts network

(again, use cabal install --lib on ghc 8.10+)

Libhandler

Install libhandler from the benchmark root directory (into the libhandler sub-directory).

$ git clone https://github.com/koka-lang/libhandler
$ cd libhandler

Build the library:

libhandler$ ./configure
libhandler$ make depend
libhandler$ make VARIANT=release
libhandler$ make tests VARIANT=release

and copy the final library to the out directory:

libhandler$ cp out/gcc-amd64-linux-gnu/release/libhandler.a  out    # use platform specific path

(this is out/gcc-amd64-apple-darwin19.6.0/release/libhandler.a on macOS)

and move back up to the parent directory:

libhandler$ cd ..

Libmprompt

Install libmprompt (tested with v0.6.2) from the benchmark root directory (into the libmprompt sub-directory).

$ git clone https://github.com/koka-lang/libmprompt
$ cd libmprompt

Build the library:

libmprompt$ mkdir -p out/crelease            # must be `out/crelease`
libmprompt$ cd out/crelease
libmprompt/out/crelease$ cmake ../.. -DMP_USE_C=ON
libmprompt/out/crelease$ make

and move back up to the parent benchmark directory:

libmprompt/out/crelease$ cd ../../..

Multi-core OCaml

Install Opam: https://opam.ocaml.org/doc/Install.html:

$ sh <(curl -sL https://raw.githubusercontent.com/ocaml/opam/master/shell/install.sh)

Install Multi-core OCaml with new parallel_minor_gc:

$ opam init    # if this is the first time running opam, and maybe you need to run: > eval $(opam env)
$ opam update  
$ opam switch create 4.10.0+multicore --packages=ocaml-variants.4.10.0+multicore --repositories=multicore=git+https://github.com/ocaml-multicore/multicore-opam.git,default
$ eval $(opam env)  # ensure the right variant is used

Install Dune (and lwt (not sure if required for the benchmarks))

$ opam install dune lwt

Test installation:

$ ocamlopt --version
4.10.0+multicore

If it does not say +multicore you need to probably use:

$ eval $(opam env)

to switch to the right version. (Use opam switch list to see the installed variants)

Building the Benchmarks

After installing the pre-requisites, the benchmarks should all build:

$ chmod +x ./build.sh
$ ./build.sh

...

--------------------------------------------------
run benchmarks as:

$ out/kk/bench

usage:
 out/kk/bench [options]

options:
 -t  --test=test  comma separated list of tests
 -l  --lang=lang  comma separated list of languages
 -i     --iter=N     use N (=1) iterations per test
 -c        --chart      generate latex chart
 -n        --norm       normalize results relative to Koka
 -h        --help       show this information

notes:
  tests    : counter, counter1, counter10, mstate, nqueens
  languages: kk, ml, mp, ev, hia, lh, lm, kknt, lmnt, base

all builds successful.

Running the Benchmarks

Run all benchmarks by running the out/kk/bench program that was build in the previous step:

$ ./out/kk/bench 

Median over 10 runs with LaTeX graph:

$ ./out/kk/bench -i10 -c

Run a particular benchmark:

$ ./out/kk/bench --test=counter,nqueens

Run for a particular language:

$ ./out/kk/bench --test=counter --lang=c,kk,ev

When generating an LaTeX graph (-c), you can copy-and-paste the LaTeX (in between the ~ begin snippet blocks) into the graph/bench.tex file, and then use

$ cd graph
graph$ pdflatex graph.tex

to generate a nice bar graph.

Owner
Daan
Daan
matrix-effect This is a dumb matrix effect type thing

matrix-effect This is a dumb matrix effect type thing. It's only like one source file which should compile... Define __POSIX or __WIN though, for posi

null 41 Jun 8, 2022
Mimalloc-bench - Suite for benchmarking malloc implementations.

Mimalloc-bench Suite for benchmarking malloc implementations, originally developed for benchmarking mimalloc. Collection of various benchmarks from th

Daan 154 Jun 25, 2022
Argh! A minimalist argument handler.

Frustration-free command line processing So many different command line processing libraries out there and none of them just work! Some bring their wh

Adi Shavit 1k Jun 27, 2022
C++ library for solving large sparse linear systems with algebraic multigrid method

AMGCL AMGCL is a header-only C++ library for solving large sparse linear systems with algebraic multigrid (AMG) method. AMG is one of the most effecti

Denis Demidov 528 Jun 22, 2022
C++ library for solving large sparse linear systems with algebraic multigrid method

AMGCL AMGCL is a header-only C++ library for solving large sparse linear systems with algebraic multigrid (AMG) method. AMG is one of the most effecti

Denis Demidov 529 Jul 4, 2022
A simple C++ 03/11/etc timer class for ~microsecond-precision cross-platform benchmarking. The implementation is as limited and as simple as possible to create the lowest amount of overhead.

plf_nanotimer A simple C++ 03/11/etc timer class for ~microsecond-precision cross-platform benchmarking. The implementation is as limited and simple a

Matt Bentley 88 Jun 20, 2022
A C++ micro-benchmarking framework

Nonius What is nonius? Nonius is an open-source framework for benchmarking small snippets of C++ code. It is very heavily inspired by Criterion, a sim

Nonius 334 Jun 27, 2022
C++ benchmarking framework

hayai - the C++ benchmarking framework. hayai is a C++ framework for writing benchmarks for pieces of code along the lines of the normal approach for

Nick Bruun 360 Jun 15, 2022
A C++ micro-benchmarking framework

Nonius What is nonius? Nonius is an open-source framework for benchmarking small snippets of C++ code. It is very heavily inspired by Criterion, a sim

Nonius 334 Jun 27, 2022
Benchmarking a trivial replacement for std::vector

std::vector replacement benchmark Dependencies You'll need gnuplot and bash to run ./bench.sh. In addition to that, you'll need to have gcc and clang

Dale Weiler 7 May 23, 2022
Colorful Logging is a simple and efficient library allowing for logging and benchmarking.

Colorful-Logging "Colorful Logging" is a library allowing for simple and efficient logging as well for benchmarking. What can you use it for? -Obvious

Mateusz Antkiewicz 1 Feb 17, 2022
CPU Performance Evaluation and Execution Time Prediction Using Narrow Spectrum Benchmarking

This is a simple implementation of Saavedra-Barrera's paper SAAVEDRA-BARRERA R H. CPU Performance Evaluation and Execution Time Prediction Using Narrow Spectrum Benchmarking[D/OL]. UCB/CSD92-684. EECS Department, University of California, Berkeley, 1992.

null 9 Jan 27, 2022
Alloc-test - Cross-platform benchmarking for memory allocators, aiming to be as close to real world as it is practical

Alloc-test - Cross-platform benchmarking for memory allocators, aiming to be as close to real world as it is practical

null 36 Mar 17, 2022
A C++ micro-benchmarking framework

Nonius What is nonius? Nonius is an open-source framework for benchmarking small snippets of C++ code. It is very heavily inspired by Criterion, a sim

R. Martinho Fernandes 90 Apr 13, 2022
Robust multi-prompt delimited control and effect handlers in C/C++

libmprompt Note: The library is under development and not yet complete. This library should not be used in production code. Latest release: v0.2, 2021

Koka Language and Related Tools 81 Jun 6, 2022
No loss LV2 sound effect plugin

B.Spacr Description: LV2 sound effect plugin B.Spacr is a unique LV2 effect plugin that enables a clear and brilliant audibility of your music product

null 13 Nov 28, 2021
A small proxy DLL which enables dev. console in Mass Effect 1, 2 and 3 (Legendary Edition).

LEBinkProxy A small proxy DLL which enables dev. console in Mass Effect 1, 2 and 3 (Legendary Edition). Usage In your game binary directory (Game\ME?\

null 10 Jan 6, 2022
Typewriter Effect with Rich Text + *Correct* Text Wrapping

Typewriter Effect with Rich Text + Correct Text Wrapping I've spent way too long getting this right. This is meant as a base class for a UMG dialogue

Sam Bloomberg 25 Jun 26, 2022
Acrylic & aero blur effect on Flutter Windows 💙.

flutter_acrylic Acrylic & aero blur effect on Flutter Windows. Installation Mention in your pubspec.yaml.

Hitesh Kumar Saini 356 Jun 20, 2022
This is a single-header, multithreaded C++ library for simulating the effect of hydraulic erosion on height maps.

TinyErode This is a single-header, multithreaded C++ library for simulating the effect of hydraulic erosion on height maps. The algorithm is based on

Taylor 40 Jun 15, 2022
Demonstrates implementation of the Windows 10 Acrylic Effect on C++ Win32 Apps using DWM Private APIs and Direct Composition

Win32 Acrylic Effect A Demonstration of Acrylic Effect on C++ Win32 applications using Direct Composition and DWM private APIs. Table of Contents Over

Selastin 92 Jun 29, 2022
Create a firework effect with WS2812b LED and a MCU

LED-Fireworks Firework effect with WS2812b LED and a MCU This project uses FastLED library to control the LED strip. WS2812b IC is embedded into each

null 76 Jun 10, 2022
digital audio workstation, instrument and effect plugins, wave editor

Stargate Stargate is a holistic audio production solution, everything you need to make music on a computer. To understand what Stargate is, and why, r

null 241 Jun 30, 2022
Acrylic effect for all existing Win32 context menus

AcrylicMenus This is a proof-of-concept tiny application that applies acrylic effect to almost all existing Win32 context menus on Windows 10 and Wind

null 265 Jun 27, 2022
IPlug "Tale" edition example (tremolo effect).

IPLUG EXAMPLE A simple tremolo audio effect plugin (AU/VST2), serving as an example for the IPlug "Tale" edition plugin framework. GETTING STARTED

null 2 Nov 22, 2021
A fork of the kwin blur effect that solve the corners bug.

Kwin blur effect - Respect rounded corners This kwin effect is a fork of the default kwin blur effect, with minimal changes to solve the "plasma korne

Alban Boissard 96 Jul 1, 2022
This is no malware, This is no virus. This is my implementation of the effect from Mrs.Major3.

BloodMelter This is no malware, This is no virus. This is a very small effect of very small blood for a some PC. Table Of Contents Preview About Warni

SonicTheHedgehog 4 Jul 3, 2022
Project to create a teensy based gamecube controller with hall effect sensors, snapback filtering, and notch calibration

PhobGCC Gamecube controller motherboard using a teensy as the microcontroller. Aim is to make an accessible and consistent controller. Has the option

null 75 Jun 26, 2022
Bolt is a C++ template library optimized for GPUs. Bolt provides high-performance library implementations for common algorithms such as scan, reduce, transform, and sort.

Bolt is a C++ template library optimized for heterogeneous computing. Bolt is designed to provide high-performance library implementations for common

null 355 Jun 27, 2022