elixir-toniq / circular_buffer

18 stars 2 forks source link

Manage circular buffer using lists #4

Closed fhunleth closed 3 years ago

fhunleth commented 3 years ago

This switches the implementation from using the general purpose :queue module to enable optimizations for the circular buffer use case. At a high level, an Okasaki queue is still used. Since insertion to a circular buffer always requires a removal once the buffer reaches its max size, this change makes it possible to do this in one step. Previously, this was a call to :queue to remove one element and then a call to insert the new one.

With the general caveat on microbenchmarks, the new implementation is a small performance improvement and reduces the garbage created when managing the structure. The following results are from inserting items repeatedly into a CircularBuffer. "cb2" is the new implementation and "cb" is the :queue implementation in the results below.

Name                 ips        average  deviation         median         99th %
cb2 insert        236.18        4.23 ms     ±3.01%        4.31 ms        4.39 ms
cb insert         140.35        7.13 ms     ±3.27%        7.14 ms        7.66 ms

Comparison:
cb2 insert        236.18
cb insert         140.35 - 1.68x slower +2.89 ms

Memory usage statistics:

Name          Memory usage
cb2 insert         9.12 MB
cb insert         16.24 MB - 1.78x memory usage +7.12 MB
fhunleth commented 3 years ago

As a side note, we've been using this on Nerves with RingLogger for a really long time. I've been meaning to contribute back, but never got to it (super sorry about that). I have a couple minor follow-up PRs based on how this one turns out.