Current section
5 Versions
Jump to
Current section
5 Versions
Compare versions
12
files changed
+413
additions
-489
deletions
| @@ -1,5 +1,5 @@ | |
| 1 1 | # Hypex |
| 2 | - [](https://travis-ci.org/whitfin/hypex) [](https://coveralls.io/github/whitfin/hypex) [](https://hex.pm/packages/hypex) [](https://hexdocs.pm/hypex/) |
| 2 | + [](https://github.com/whitfin/hypex/actions) [](https://coveralls.io/github/whitfin/hypex) [](https://hex.pm/packages/hypex) [](https://hexdocs.pm/hypex/) |
| 3 3 | |
| 4 4 | Hypex is a fast HyperLogLog implementation in Elixir which provides an easy way to count unique values with a small memory footprint. This library is based on [the paper documenting the algorithm](http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf) written by Philippe Flajolet et al. |
| 5 5 | |
| @@ -7,78 +7,76 @@ Hypex is a fast HyperLogLog implementation in Elixir which provides an easy way | |
| 7 7 | |
| 8 8 | Hypex is available on [Hex](https://hex.pm/). You can install the package via: |
| 9 9 | |
| 10 | - 1. Add hypex to your list of dependencies in `mix.exs`: |
| 11 | - |
| 12 10 | ```elixir |
| 13 11 | def deps do |
| 14 | - [{ :hypex, "~> 1.1" }] |
| 15 | - end |
| 16 | - ``` |
| 17 | - |
| 18 | - 2. Ensure hypex is started before your application: |
| 19 | - |
| 20 | - ```elixir |
| 21 | - def application do |
| 22 | - [applications: [:hypex]] |
| 12 | + [{ :hypex, "~> 2.0" }] |
| 23 13 | end |
| 24 14 | ``` |
| 25 15 | |
| 26 16 | ## Usage |
| 27 17 | |
| 28 | - Hypex is extremely straightforward to use, you simply create a new Hypex instance and start adding values to it: |
| 18 | + Hypex is extremely straightforward to use, you simply create a new Hypex record and start adding values to it: |
| 29 19 | |
| 30 20 | ```elixir |
| 31 21 | iex> hypex = Hypex.new(4) |
| 32 | - {Hypex.Array, 4, {:array, 16, 0, 0, 100}} |
| 22 | + {:hypex, Hypex.Register.Array, 4, {:array, 16, 0, 0, 100}} |
| 33 23 | iex> hypex = Hypex.update(hypex, "my term") |
| 34 | - {Hypex.Array, 4, |
| 24 | + {:hypex, Hypex.Register.Array, 4, |
| 35 25 | {:array, 16, 0, 0, |
| 36 26 | {10, {0, 2, 0, 0, 0, 0, 0, 0, 0, 0}, 10, 10, 10, 10, 10, 10, 10, 10, 10}}} |
| 37 | - iex> hypex |> Hypex.cardinality |> round |
| 38 | - 1 |
| 27 | + iex> Hypex.cardinality(hypex) |
| 28 | + 1.0326163382011386 |
| 39 29 | ``` |
| 40 30 | |
| 41 | - The `4` being passed to `Hypex.new/1` is the width which determines the underlying memory structure of a Hypex instance. This value can be within the range `4 <= width <= 16`, per the HyperLogLog algorithm. If you don't provide a width, it defaults to `16`. Be aware that you should typically scale this number higher based upon the more unique values you expect to see. |
| 31 | + The `4` being passed to `Hypex.new/1` is the width which determines the underlying memory structure of a Hypex instance. This value can be within the range `4 <= width <= 16`, per the HyperLogLog algorithm. If you don't provide a width, it defaults to `8`. Be aware that you should typically scale this number higher based upon the more unique values you expect to see. |
| 32 | + |
| 33 | + You can control the underlying storage register via the second parameter of `Hypex.new/2`. This defaults to an `:array` implementation, but Hypex includes a few different implementations based on your use case. Please see the documentation to view the registers available in your current version of `Hypex`. |
| 42 34 | |
| 43 35 | For any other examples of how to use Hypex, please read [the documentation](https://hexdocs.pm/hypex/). |
| 44 36 | |
| 45 | - ## Memory Optimization |
| 37 | + ## Register Benchmarks |
| 46 38 | |
| 47 | - As of `v1.1.0`, the default implementation has moved from a Bitstring to an Erlang Array. This is mainly due to Arrays performing faster on all operations when compared with Bitstrings. However in the case that you're operating in a low-memory environment (or simply want predictable memory usage), you might still wish to use the Bitstring implementation. You can do this by simply using `Hypex.new(4, Bitstring)` when creating a Hypex. |
| 48 | - |
| 49 | - A rough memory estimate (in bytes) for a Bitstring Hypex can be calculated using the formula `((2 ^ width) * width) / 8` - although this will only include the memory of the registers and not the rest of the tuple structure (which should be minimal). This means that using the highest width available of `16`, your memory usage will still only be `131,072` bytes. |
| 50 | - |
| 51 | - At this point I don't know of a good way to measure the size of the Array implementation, but a rough estimate would suggest that it's probably within the range of 6-8 times more memory (if anyone can help measure, I'd appreciate it). Still, this amount of memory shouldn't pose an issue for most systems, and the throughput likely matters more to most users. |
| 52 | - |
| 53 | - ## Rough Benchmarks |
| 54 | - |
| 55 | - Below are some rough benchmarks for Hypex instances with the different underlying structures. Note that the `update/2` tests are inserting a unique value - in the case a duplicate value is inserted, the operation is typically constant across widths at under `0.5 µs/op`. |
| 56 | - |
| 57 | - These tests use a width of 4, so it should be noted that larger widths will have slower performance. However, these benchmarks are for reference only and you should gauge which widths work best for the data you're operating with, rather than the performance shown below. |
| 39 | + Below are some rough benchmarks for the different Hypex registers. Any tests with updates will be inserting a unique value; a duplicate value is significantly faster due to skipping modifications. These tests use a width of 8, and it should be noted that the width heavily impacts these numbers. The smallest widths (4) are measured in `ns` rather than `ÎĽs`, whereas the largest widths (16) are typically in the millisecond range for cardinality calculations. |
| 58 40 | |
| 59 41 | ``` |
| 60 | - ## Array Hypex |
| 42 | + ## Hypex (Array) |
| 61 43 | |
| 62 | - Array Hypex.new/1 0.53 µs/op |
| 63 | - Array Hypex.update/2 2.13 µs/op |
| 64 | - Array Hypex.cardinality/1 6.87 µs/op |
| 65 | - Array Hypex.merge/2 16.61 µs/op |
| 44 | + Array Hypex.new/1 0.09 ÎĽs/op |
| 45 | + Array Hypex.update/2 0.35 ÎĽs/op |
| 46 | + Array Hypex.cardinality/1 4.56 ÎĽs/op |
| 47 | + Array Hypex.merge/2 9.09 ÎĽs/op |
| 66 48 | |
| 67 | - ## Bitstring Hypex |
| 49 | + ## Hypex (Bitstring) |
| 68 50 | |
| 69 | - Bitstring Hypex.new/1 0.46 µs/op |
| 70 | - Bitstring Hypex.update/2 2.13 µs/op |
| 71 | - Bitstring Hypex.cardinality/1 6.70 µs/op |
| 72 | - Bitstring Hypex.merge/2 8.69 µs/op |
| 51 | + Bitstring Hypex.new/1 0.17 ÎĽs/op |
| 52 | + Bitstring Hypex.update/2 0.31 ÎĽs/op |
| 53 | + Bitstring Hypex.cardinality/1 8.47 ÎĽs/op |
| 54 | + Bitstring Hypex.merge/2 9.09 ÎĽs/op |
| 55 | + |
| 56 | + ## Hypex (List) |
| 57 | + |
| 58 | + List Hypex.new/1 0.74 ÎĽs/op |
| 59 | + List Hypex.update/2 1.13 ÎĽs/op |
| 60 | + List Hypex.cardinality/1 3.16 ÎĽs/op |
| 61 | + List Hypex.merge/2 5.53 ÎĽs/op |
| 73 62 | ``` |
| 74 63 | |
| 64 | + In most cases it won't matter which register you choose, so it's a good idea to start with the default until you see some reason to change. If you would like some very rough guidance, here are some simple rules: |
| 65 | + |
| 66 | + * If you're using low `width` values, use `Hypex.Register.List` |
| 67 | + * If you're trying to minimize memory, use `Hypex.Register.Bitstring` |
| 68 | + * For anything else, use `Hypex.Register.Array` (the current default) |
| 69 | + |
| 70 | + These guidelines are based on Elixir 1.19; it's possible that they display different characteristics on earlier Elixir/OTP versions. Make sure to measure inside your application using your real traffic and data! |
| 71 | + |
| 75 72 | ## Contributions |
| 76 73 | |
| 77 74 | If you feel something can be improved, or have any questions about certain behaviours or pieces of implementation, please feel free to file an issue. Proposed changes should be taken to issues before any PRs to avoid wasting time on code which might not be merged upstream. |
| 78 75 | |
| 79 76 | If you *do* make changes to the codebase, please make sure you test your changes thoroughly, and include any unit tests alongside new or changed behaviours. Hypex currently uses the excellent [excoveralls](https://github.com/parroty/excoveralls) to track code coverage. |
| 80 77 | |
| 81 | - ```elixir |
| 78 | + ``` |
| 82 79 | $ mix test |
| 83 80 | $ mix coveralls |
| 84 81 | $ mix coveralls.html && open cover/excoveralls.html |
| 82 | + ``` |
| @@ -1,15 +1,16 @@ | |
| 1 | - {<<"app">>,<<"hypex">>}. |
| 2 | - {<<"build_tools">>,[<<"mix">>]}. |
| 3 | - {<<"description">>,<<"Fast HyperLogLog implementation for Elixir/Erlang">>}. |
| 4 | - {<<"elixir">>,<<"~> 1.1">>}. |
| 5 | - {<<"files">>, |
| 6 | - [<<"lib">>,<<"lib/hypex">>,<<"lib/hypex.ex">>,<<"lib/hypex/array.ex">>, |
| 7 | - <<"lib/hypex/bitstring.ex">>,<<"lib/hypex/register.ex">>, |
| 8 | - <<"lib/hypex/util.ex">>,<<"mix.exs">>,<<"LICENSE">>,<<"README.md">>]}. |
| 9 | - {<<"licenses">>,[<<"MIT">>]}. |
| 10 1 | {<<"links">>, |
| 11 2 | [{<<"Docs">>,<<"http://hexdocs.pm/hypex">>}, |
| 12 3 | {<<"GitHub">>,<<"https://github.com/zackehh/hypex">>}]}. |
| 13 4 | {<<"name">>,<<"hypex">>}. |
| 5 | + {<<"version">>,<<"2.0.0">>}. |
| 6 | + {<<"description">>,<<"Fast HyperLogLog implementation for Elixir/Erlang">>}. |
| 7 | + {<<"elixir">>,<<"~> 1.12">>}. |
| 8 | + {<<"files">>, |
| 9 | + [<<"lib">>,<<"lib/hypex.ex">>,<<"lib/hypex">>,<<"lib/hypex/register.ex">>, |
| 10 | + <<"lib/hypex/register">>,<<"lib/hypex/register/list.ex">>, |
| 11 | + <<"lib/hypex/register/array.ex">>,<<"lib/hypex/register/bitstring.ex">>, |
| 12 | + <<"lib/hypex/utilities.ex">>,<<"mix.exs">>,<<"LICENSE">>,<<"README.md">>]}. |
| 13 | + {<<"app">>,<<"hypex">>}. |
| 14 | + {<<"licenses">>,[<<"MIT">>]}. |
| 14 15 | {<<"requirements">>,[]}. |
| 15 | - {<<"version">>,<<"1.1.1">>}. |
| 16 | + {<<"build_tools">>,[<<"mix">>]}. |
| @@ -9,26 +9,26 @@ defmodule Hypex do | |
| 9 9 | should only ever be constructed via `Hypex.new/2` otherwise you run the risk of |
| 10 10 | pattern matching errors throughout modification. |
| 11 11 | """ |
| 12 | + import Record |
| 12 13 | |
| 13 14 | # alias some internals |
| 14 | - alias Hypex.Util |
| 15 | + alias Hypex.Utilities |
| 15 16 | |
| 16 | - # cardinality error |
| 17 | - @card2_err "Hypex.cardinality/1 requires a valid Hypex instance" |
| 18 | - |
| 19 | - # merge error |
| 20 | - @merge_err "Merging requires valid Hypex structures of the same width and type" |
| 21 | - |
| 22 | - # invalid construction error |
| 23 | - @range_err "Invalid width provided, must be 16 >= width >= 4" |
| 24 | - |
| 25 | - # update error |
| 26 | - @update_err "Hypex.update/2 requires a valid Hypex instance" |
| 17 | + # record structure |
| 18 | + defrecord :hypex, |
| 19 | + mod: nil, |
| 20 | + width: nil, |
| 21 | + register: nil |
| 27 22 | |
| 28 23 | @typedoc """ |
| 29 24 | A Hypex interface structure |
| 30 25 | """ |
| 31 | - @opaque t :: { mod :: term, width :: number, register :: Register.t } |
| 26 | + @type t :: |
| 27 | + record(:hypex, |
| 28 | + mod: term(), |
| 29 | + width: number(), |
| 30 | + register: any() |
| 31 | + ) |
| 32 32 | |
| 33 33 | @doc """ |
| 34 34 | Create a new Hypex using a width when `16 >= width >= 4`. |
| @@ -37,32 +37,27 @@ defmodule Hypex do | |
| 37 37 | We normalize to ensure we have a valid module and then initialize the module |
| 38 38 | with the widths. |
| 39 39 | |
| 40 | - Once the registers are initialized, we return them inside a Tuple alongside |
| 40 | + Once the register are initialized, we return them inside a Tuple alongside |
| 41 41 | the width and module name. |
| 42 42 | |
| 43 43 | ## Examples |
| 44 44 | |
| 45 45 | iex> Hypex.new(4) |
| 46 | - { Hypex.Array, 4, { :array, 16, 0, 0, 100 } } |
| 46 | + {:hypex, Hypex.Array, 4, {:array, 16, 0, 0, 100}} |
| 47 47 | |
| 48 48 | iex> Hypex.new(4, Bitstring) |
| 49 | - { Hypex.Bitstring, 4, << 0, 0, 0, 0, 0, 0, 0, 0 >> } |
| 49 | + {:hypex, Hypex.Bitstring, 4, <<0, 0, 0, 0, 0, 0, 0, 0>>} |
| 50 50 | |
| 51 51 | """ |
| 52 | - @spec new(width :: number) :: hypex :: Hypex.t |
| 53 | - def new(width \\ 16, mod \\ nil) |
| 54 | - def new(width, mod) when is_integer(width) and width <= 16 and width >= 4 do |
| 55 | - impl = Util.normalize_module(mod) |
| 56 | - { impl, width, impl.init(width) } |
| 57 | - end |
| 58 | - def new(_width, _mod) do |
| 59 | - raise ArgumentError, message: @range_err |
| 60 | - end |
| 52 | + @spec new(width :: number(), mod :: term()) :: hypex :: Hypex.t() |
| 53 | + def new(width \\ 8, mod \\ Hypex.Register.Array) |
| 54 | + when is_integer(width) and width <= 16 and width >= 4, |
| 55 | + do: hypex(mod: mod, width: width, register: mod.init(width)) |
| 61 56 | |
| 62 57 | @doc """ |
| 63 58 | Calculates a cardinality based upon a passed in Hypex. |
| 64 59 | |
| 65 | - We use the reduce function of the module representing the registers, and track |
| 60 | + We use the reduce function of the module representing the register, and track |
| 66 61 | the number of zeroes alongside the initial value needed to create a raw estimate. |
| 67 62 | |
| 68 63 | Once we have these values we just apply the correction by using the `m` value, |
| @@ -78,20 +73,18 @@ defmodule Hypex do | |
| 78 73 | 3 |
| 79 74 | |
| 80 75 | """ |
| 81 | - @spec cardinality(hypex :: Hypex.t) :: cardinality :: number |
| 82 | - def cardinality({ mod, width, registers } = _hypex) do |
| 76 | + @spec cardinality(hypex :: Hypex.t()) :: cardinality :: number() |
| 77 | + def cardinality(hypex(mod: mod, width: width, register: register)) do |
| 83 78 | m = :erlang.bsl(1, width) |
| 84 79 | |
| 85 | - { value, zeroes } = mod.reduce(registers, width, { 0, 0 }, fn(int, { current, zeroes }) -> |
| 86 | - { 1 / :erlang.bsl(1, int) + current, int == 0 && zeroes + 1 || zeroes } |
| 87 | - end) |
| 80 | + {value, zeroes} = |
| 81 | + mod.reduce(register, width, {0, 0}, fn int, {current, zeroes} -> |
| 82 | + {1 / :erlang.bsl(1, int) + current, (int == 0 && zeroes + 1) || zeroes} |
| 83 | + end) |
| 88 84 | |
| 89 | - raw_estimate = Util.a(m) * m * m * 1 / value |
| 85 | + raw_estimate = Utilities.a(m) * m * m * 1 / value |
| 90 86 | |
| 91 | - Util.apply_correction(m, raw_estimate, zeroes) |
| 92 | - end |
| 93 | - def cardinality(_hypex) do |
| 94 | - raise ArgumentError, message: @card2_err |
| 87 | + Utilities.apply_correction(m, raw_estimate, zeroes) |
| 95 88 | end |
| 96 89 | |
| 97 90 | @doc """ |
| @@ -121,40 +114,19 @@ defmodule Hypex do | |
| 121 114 | 3 |
| 122 115 | |
| 123 116 | """ |
| 124 | - @spec merge([ hypex :: Hypex.t ]) :: hypex :: Hypex.t |
| 125 | - def merge([ { _mod, _width, _registers } = hypex ]), |
| 126 | - do: hypex |
| 127 | - def merge([ { mod, width, _registers } | _ ] = hypices) do |
| 128 | - unless Enum.all?(hypices, &(match?({ ^mod, ^width, _ }, &1))) do |
| 129 | - raise ArgumentError, message: @merge_err |
| 130 | - end |
| 131 | - |
| 132 | - registers = Enum.map(hypices, fn({ mod, _width, registers }) -> |
| 133 | - mod.to_list(registers) |
| 134 | - end) |
| 135 | - |
| 136 | - m_reg = |
| 137 | - registers |
| 138 | - |> Util.ziplist |
| 139 | - |> Enum.reduce([], &([ :lists.max(&1) | &2 ])) |
| 140 | - |> Enum.reverse |
| 141 | - |> mod.from_list |
| 142 | - |
| 143 | - { mod, width, m_reg } |
| 144 | - end |
| 145 | - def merge(_hypices) do |
| 146 | - raise ArgumentError, message: @merge_err |
| 147 | - end |
| 117 | + @spec merge([hypex :: Hypex.t()]) :: hypex :: Hypex.t() |
| 118 | + def merge(hypices) when is_list(hypices), |
| 119 | + do: Enum.reduce(hypices, &merge/2) |
| 148 120 | |
| 149 121 | @doc """ |
| 150 122 | Merges together two Hypex instances with the same seed. |
| 151 | - |
| 152 | - Internally this function just wraps the two instances in a list and passes them |
| 153 | - throguh to `merge/1`. |
| 154 123 | """ |
| 155 | - @spec merge(hypex :: Hypex.t, hypex :: Hypex.t) :: hypex :: Hypex.t |
| 156 | - def merge(h1, h2), |
| 157 | - do: merge([ h1, h2 ]) |
| 124 | + @spec merge(hypex :: Hypex.t(), hypex :: Hypex.t()) :: hypex :: Hypex.t() |
| 125 | + def merge( |
| 126 | + hypex(mod: mod, width: width, register: left), |
| 127 | + hypex(mod: mod, width: width, register: right) = hypex |
| 128 | + ), |
| 129 | + do: hypex(hypex, register: mod.merge(left, right)) |
| 158 130 | |
| 159 131 | @doc """ |
| 160 132 | Updates a Hypex instance with a value. |
| @@ -173,24 +145,22 @@ defmodule Hypex do | |
| 173 145 | { Hypex.Bitstring, 4, << 0, 0, 0, 0, 0, 0, 0, 2 >> } |
| 174 146 | |
| 175 147 | """ |
| 176 | - @spec update(hypex :: Hypex.t, value :: any) :: hypex :: Hypex.t |
| 177 | - def update({ mod, width, registers } = hypex, value) do |
| 178 | - max_uniques = Util.max_uniques() |
| 179 | - hash_length = Util.hash_length() |
| 148 | + @spec update(hypex :: Hypex.t(), value :: any) :: hypex :: Hypex.t() |
| 149 | + def update(hypex(mod: mod, width: width, register: register) = hypex, value) do |
| 150 | + max_uniques = Utilities.max_uniques() |
| 151 | + hash_length = Utilities.hash_length() |
| 180 152 | |
| 181 | - << idx :: size(width), rest :: bitstring >> = << :erlang.phash2(value, max_uniques) :: size(hash_length) >> |
| 153 | + <<idx::size(width), rest::bitstring>> = |
| 154 | + <<:erlang.phash2(value, max_uniques)::size(hash_length)>> |
| 182 155 | |
| 183 | - current_value = mod.get_value(registers, idx, width) |
| 156 | + current_value = mod.get(register, idx, width) |
| 184 157 | |
| 185 | - case max(current_value, Util.count_leading_zeros(rest)) do |
| 158 | + case max(current_value, Utilities.count_leading_zeros(rest)) do |
| 186 159 | ^current_value -> |
| 187 160 | hypex |
| 161 | + |
| 188 162 | new_value -> |
| 189 | - { mod, width, mod.set_value(registers, idx, width, new_value) } |
| 163 | + hypex(hypex, register: mod.put(register, idx, width, new_value)) |
| 190 164 | end |
| 191 165 | end |
| 192 | - def update(_hypex, _value) do |
| 193 | - raise ArgumentError, message: @update_err |
| 194 | - end |
| 195 | - |
| 196 166 | end |
| @@ -1,81 +0,0 @@ | |
| 1 | - defmodule Hypex.Array do |
| 2 | - @moduledoc """ |
| 3 | - This module provides a Hypex register implementation using an Erlang Array under |
| 4 | - the hood. |
| 5 | - |
| 6 | - Using an Array switches out the memory efficiency of the Bitstring implementation |
| 7 | - for performance, operating at 10x the throughput of Bitstring on updates. |
| 8 | - |
| 9 | - Even though this implementation uses higher amounts of memory, it's still pretty |
| 10 | - low-cost and as such is the default register module for Hypex. Typically only |
| 11 | - those working in memory-constrained environments should consider the Bitstring |
| 12 | - register. |
| 13 | - """ |
| 14 | - |
| 15 | - # define behaviour |
| 16 | - @behaviour Hypex.Register |
| 17 | - |
| 18 | - # define the Array typespec |
| 19 | - @type array :: :array.array(number) |
| 20 | - |
| 21 | - @doc """ |
| 22 | - Creates a new Array with a size of `2 ^ width` with all elements initialized to 0. |
| 23 | - """ |
| 24 | - @spec init(width :: number) :: array |
| 25 | - def init(width) do |
| 26 | - 1 |
| 27 | - |> :erlang.bsl(width) |
| 28 | - |> :array.new({ :default, 0 }) |
| 29 | - end |
| 30 | - |
| 31 | - @doc """ |
| 32 | - Takes a list of bits and converts them to an Array. |
| 33 | - |
| 34 | - The Array has it's size fixed before being returned just for some extra safety. |
| 35 | - """ |
| 36 | - @spec from_list([ bit :: number ]) :: array |
| 37 | - def from_list(bits) do |
| 38 | - bits |
| 39 | - |> :array.from_list(0) |
| 40 | - |> :array.fix |
| 41 | - end |
| 42 | - |
| 43 | - @doc """ |
| 44 | - Converts an Array register implementation to a list of bits. |
| 45 | - |
| 46 | - We can just delegate to the internal Array implementation as it provides the |
| 47 | - functionality we need built in. |
| 48 | - """ |
| 49 | - @spec to_list(array) :: [ bit :: number ] |
| 50 | - defdelegate to_list(registers), to: :array, as: :to_list |
| 51 | - |
| 52 | - @doc """ |
| 53 | - Returns a bit from the list of registers. |
| 54 | - """ |
| 55 | - @spec get_value(array, idx :: number, width :: number) :: result :: number |
| 56 | - def get_value(registers, idx, _width) do |
| 57 | - :array.get(idx, registers) |
| 58 | - end |
| 59 | - |
| 60 | - @doc """ |
| 61 | - Sets a bit inside the list of registers. |
| 62 | - """ |
| 63 | - @spec set_value(array, idx :: number, width :: number, value :: number) :: array |
| 64 | - def set_value(registers, idx, _width, value) do |
| 65 | - :array.set(idx, value, registers) |
| 66 | - end |
| 67 | - |
| 68 | - @doc """ |
| 69 | - Converts a list of registers into a provided accumulator. |
| 70 | - |
| 71 | - Internally we pass everything to `:array.foldl/3`, as there's already a native |
| 72 | - implementation for accumulation. |
| 73 | - """ |
| 74 | - @spec reduce(array, width :: number, accumulator :: any, (number, any -> any)) :: accumulator :: any |
| 75 | - def reduce(registers, _width, acc, fun) do |
| 76 | - :array.foldl(fn(_, int, acc) -> |
| 77 | - fun.(int, acc) |
| 78 | - end, acc, registers) |
| 79 | - end |
| 80 | - |
| 81 | - end |
| @@ -1,73 +0,0 @@ | |
| 1 | - defmodule Hypex.Bitstring do |
| 2 | - @moduledoc """ |
| 3 | - This module provides a Hypex register implementation using a Bitstring under |
| 4 | - the hood. |
| 5 | - |
| 6 | - Using this implementation provides several guarantees about memory, in that the |
| 7 | - memory cost stays constant and falls well below that of other registers. |
| 8 | - |
| 9 | - Unfortunately this efficiency comes at the cost of some throughput, although |
| 10 | - this module should be easily sufficient for all but the most write-intensive |
| 11 | - use cases. |
| 12 | - """ |
| 13 | - |
| 14 | - # define behaviour |
| 15 | - @behaviour Hypex.Register |
| 16 | - |
| 17 | - @doc """ |
| 18 | - Creates a new bitstring with a size of `(2 ^ width) * width` with all bits initialized to 0. |
| 19 | - """ |
| 20 | - @spec init(number) :: bitstring |
| 21 | - def init(width) do |
| 22 | - m = :erlang.bsl(1, width) * width |
| 23 | - << 0 :: size(m) >> |
| 24 | - end |
| 25 | - |
| 26 | - @doc """ |
| 27 | - Takes a list of bits and converts them to a bitstring. |
| 28 | - |
| 29 | - We can just delegate to the native Erlang implementation as it provides the |
| 30 | - functionality we need built in. |
| 31 | - """ |
| 32 | - @spec from_list([ bit :: number ]) :: bitstring |
| 33 | - defdelegate from_list(bit_list), to: :erlang, as: :list_to_bitstring |
| 34 | - |
| 35 | - @doc """ |
| 36 | - Takes a bitstring and converts it to a list of bits. |
| 37 | - |
| 38 | - We can just delegate to the native Erlang implementation as it provides the |
| 39 | - functionality we need built in. |
| 40 | - """ |
| 41 | - @spec to_list(bitstring) :: [ bit :: number ] |
| 42 | - defdelegate to_list(registers), to: :erlang, as: :bitstring_to_list |
| 43 | - |
| 44 | - @doc """ |
| 45 | - Returns a bit from the list of registers. |
| 46 | - """ |
| 47 | - @spec get_value(bitstring, idx :: number, width :: number) :: result :: number |
| 48 | - def get_value(registers, idx, width) do |
| 49 | - head_length = idx * width |
| 50 | - << _head :: bitstring-size(head_length), value :: size(width), _tail :: bitstring >> = registers |
| 51 | - value |
| 52 | - end |
| 53 | - |
| 54 | - @doc """ |
| 55 | - Sets a bit inside the list of registers. |
| 56 | - """ |
| 57 | - @spec set_value(bitstring, idx :: number, width :: number, value :: number) :: bitstring |
| 58 | - def set_value(registers, idx, width, value) do |
| 59 | - head_length = idx * width |
| 60 | - << head :: bitstring-size(head_length), _former :: size(width), tail :: bitstring >> = registers |
| 61 | - << head :: bitstring, value :: size(width), tail :: bitstring >> |
| 62 | - end |
| 63 | - |
| 64 | - @doc """ |
| 65 | - Converts a list of registers into a provided accumulator. |
| 66 | - |
| 67 | - Internally we pass everything to the binary reduction function in the utils |
| 68 | - module, as there's already a native implementation for accumulation. |
| 69 | - """ |
| 70 | - @spec reduce(bitstring, width :: number, accumulator :: any, (number, any -> any)) :: accumulator :: any |
| 71 | - defdelegate reduce(registers, width, acc, fun), to: Hypex.Util, as: :binary_reduce |
| 72 | - |
| 73 | - end |
Loading more files…