ke

Queue implementation
README

Queue or FIFO is one of the most famous data-structure used in several
algorithms. Ke provides some implementations of it in a functionnal or
imperative way.

It is a little library with benchmark
(bechamel or core_bench),
fuzzer and tests.

From what we know, Ke.Rke is the faster implementation than Queue from the
standard library or the base package. It is limited by some kind of data (see
Bigarray.kind) but enough for a large amount of algorithms. The fast
operation is to put some elements faster than a sequence of Queue.push, and
get some elements faster than a sequence of Queue.pop.

Then we provide a functionnal interface Fke or an imperative interface Rke.

We extended implementations to have a limit of elements to store (see
Rke.Weighted and Fke.Weigted). The purpose of it is to limit memory
consumption of queue when we use it in some contexts (like encoder).

Again, as a part of the MirageOS project, Ke does not rely on C stubs,
Obj.magic and so on.

Author: Romain Calascibetta romain.calascibetta@gmail.com

Documentation: https://mirage.github.io/ke/

Notes about Implementations

The functionnal implementation Fke is come from the Okazaki's queue
implementation with GADT to discard impossible case.

Rke, Rke.Weighted and Fke.Weighted was limited by kind and follow Xen's
implementation of the shared memory ring-buffer. Length of the internal buffer
is, in any case, a power of two - that means, in some context, for a large
amount of elements, this kind of queue does not fit on your request.

Fuzzer was made to compare the standard Queue (as an oracle) with Rke and
Fke. We construct a set of actions (push and pop) and ensure (by GADT) to
never pop an empty queue.

Install
Published
07 Apr 2022
Sources
ke-0.6.tbz
sha256=61217207e2200b04b17759736610ff9208269a647f854cb5ae72cdac0d672305
sha512=be277780a7a6c9109068b6c8d54fa88c35180802ff86951516a32a6b7c0335fd6584753d1c670e02632b3956c09ae31bfec70e3dd5ea94697e9e032ba3b9248b
Dependencies
cmdliner
>= "1.1.0" & with-test
psq
with-test
jsonm
with-test
rresult
with-test
crowbar
with-test
lwt
with-test
core_bench
with-test & >= "v0.15"
bechamel-perf
with-test
bechamel
with-test
bigstringaf
with-test
alcotest
with-test
fmt
>= "0.8.7"
dune
>= "2.0"
ocaml
>= "4.08.0"
Reverse Dependencies