[erlang-questions] A bug? - bloom filters - and loadable BIFs
Joe Armstrong
I recent got mail from Steve Kirsch (Hello Steve) - asking a number
of questions about representation of bit vectors for writing Bloom filters.
Having read my book he thought I could answer all questions about Erlang
little did he know that the collective intelligence of the people reading this
list far exceeds what I could contribute :-)
So he sent me a program, which crashes his machine (out of memory)
which he thought
should work - to my eye it looks ok - It will not be blindingly fast,
but it looks properly
tail-recursive so the garbage collector should not have any problems.
I've appended at the end of this mail - so you can see for yourself.
It is a GC bug
or a user error?
The next question is "what is a suitable data structure for
representing a large bit vector"
(we want to flip specific bits) - the "pure" answer I guess is a tuple
of tuples of binaries
(say 32x32xB) where B is a 128 byte binary for 2^20 bits.
The "tuple of tuple of tuple ..." representation is commonly used to
implement array and dicts
Possibly we could just use array.erl creating an array of 32x32
elements containing 128 byte binaries.
If this is not efficient enough we would turn to C.
A linked-in driver seems overkill here - we can't send a
large binary back and forth over an I/O interface - so this needs a BIF.
What I'd like is a "linked in BIF" - it seems to me to be a bit of a
pain in the whatnot
to have to mess around with the Erlang internals every time you want
to write a new BIF.
Much nicer to have a linked-in BIF - on demand loading of C code is pretty easy
so this should not be a problem. One could also impose a measure of
stack discipline
for linked-in BIFs (as in the JVM) - this would make it pretty easy to
write extensions.
Nuff said ...
/Joe
Now the origonal post that sparked this thread ..
------ cut --- below this line is from Steve's post-----
...
i tested the erlang bloom filter I found in google code which i've
included below.
Doing 10,000 inserts per my test routine (which allocates a 1M key
bitmap to start to make it "tough" for erlang) took 423 cpu seconds,
which is only 23 inserts/sec!?!?! That is ludicrous as I'm sure you'd
agree
And if you tried only 100,000 inserts into my 1.8MB table, erlang
crashes:
%% binary_alloc: Cannot allocate 3594429 bytes of memory (of type
"binary").
The book is pretty much silent on how you'd implement this important
class of functions.
Nor does it talk about why this code fails, though I'd imagine it is
copying and gc'ing large binaries like crazy every time you change 1
bit.
I think the book should talk about is there a way to write this code
with binaries and work? Or do you have to use arrays or some other
means?
%% @doc Implementation of the Bloom filter data structure.
%% @reference [http://en.wikipedia.org/wiki/Bloom_filter]
-module(bitmap).
-export([test/1, new/1, new/2, is_bloom/1, is_element/2,
add_element/2]).
-import(math, [log/1, pow/2]).
-import(erlang, [phash2/2]).
% B0 = bloom:new(2000, 0.001).
% bloom:is_bloom(B0).
% B1 = bloom:add_element(Key, B0).
% bloom:is_element(Key, B1).
-record(bloom, {
m = 0, % The size of the bitmap in bits.
bitmap = <<>>, % The bitmap.
k = 0, % The number of hashes.
n = 0, % The maximum number of keys.
keys = 0 % The current number of keys.
}).
%% @spec new(capacity) -> bloom()
%% @equiv new(capacity, 0.001)
new(N) -> new(N, 0.001).
%% @spec new(integer(), float()) -> bloom()
%% @doc Creates a new Bloom filter, given a maximum number of keys and a
%% false-positive error rate.
new(N, E) when N > 0, is_float(E), E > 0, E =< 1 ->
{M, K} = calc_least_bits(N, E),
#bloom{m=M, bitmap = <<0:((M+7) div 8 * 8)>>, k=K, n=N}.
%% @spec is_bloom(bloom()) -> bool()
%% @doc Determines if the given argument is a bloom record.
is_bloom(#bloom{}) -> true;
is_bloom(_) -> false.
%% @spec is_element(string(), bloom()) -> bool()
%% @doc Determines if the key is (probably) an element of the filter.
is_element(Key, B) -> is_element(Key, B, calc_idxs(Key, B)).
is_element(_, _, []) -> true;
is_element(Key, B, [Idx | T]) ->
ByteIdx = Idx div 8,
<<_:ByteIdx/binary, Byte:8, _/binary>> = B#bloom.bitmap,
Mask = 1 bsl (Idx rem 8),
case 0 =/= Byte band Mask of
true -> is_element(Key, B, T);
false -> false
end.
%% @spec add_element(string(), bloom()) -> bloom()
%% @doc Adds the key to the filter.
add_element(Key, #bloom{keys=Keys, n=N, bitmap=Bitmap} = B) when Keys <
N ->
Idxs = calc_idxs(Key, B),
Bitmap0 = set_bits(Bitmap, Idxs),
case Bitmap0 == Bitmap of
true -> B; % Don't increment key count for duplicates.
false -> B#bloom{bitmap=Bitmap0, keys=Keys+1}
end.
set_bits(Bin, []) -> Bin;
set_bits(Bin, [Idx | Idxs]) ->
ByteIdx = Idx div 8,
<<Pre:ByteIdx/binary, Byte:8, Post/binary>> = Bin,
Mask = 1 bsl (Idx rem 8),
Byte0 = Byte bor Mask,
set_bits(<<Pre/binary, Byte0:8, Post/binary>>, Idxs).
% Find the optimal bitmap size and number of hashes.
calc_least_bits(N, E) -> calc_least_bits(N, E, 1, 0, 0).
calc_least_bits(N, E, K, MinM, BestK) ->
M = -1 * K * N / log(1 - pow(E, 1/K)),
{CurM, CurK} = if M < MinM -> {M, K}; true -> {MinM, BestK} end,
case K of
1 -> calc_least_bits(N, E, K+1, M, K);
100 -> {trunc(CurM)+1, CurK};
_ -> calc_least_bits(N, E, K+1, CurM, CurK)
end.
% This uses the "enhanced double hashing" algorithm.
% Todo: handle case of m > 2^32.
calc_idxs(Key, #bloom{m=M, k=K}) ->
X = phash2(Key, M),
Y = phash2({"salt", Key}, M),
calc_idxs(M, K - 1, X, Y, [X]).
calc_idxs(_, 0, _, _, Acc) -> Acc;
calc_idxs(M, I, X, Y, Acc) ->
Xi = (X+Y) rem M,
Yi = (Y+I) rem M,
calc_idxs(M, I-1, Xi, Yi, [Xi | Acc]).
test(N)->
B0 = new(1000000, 0.001),
F=fun(Key, Bloom)-> add_element(Key, Bloom) end,
lists:foldl(F, B0, lists:seq(1,N)).
%% to test: B1=bitmap:test(1000000).
%% which crashes erlang even if only 100,000 entries
%% Crash dump was written to: erl_crash.dump
%% binary_alloc: Cannot allocate 3594429 bytes of memory (of type
"binary").
%% This application has requested the Runtime to terminate it in an
unusual way.
%% Please contact the application's support team for more information.
%% Process inferior-erlang exited abnormally with code 3
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Jachym Holecek
# Joe Armstrong 2009-04-29:
> So he sent me a program, which crashes his machine (out of memory)
> which he thought should work - to my eye it looks ok - It will not
> be blindingly fast, but it looks properly tail-recursive so the
> garbage collector should not have any problems.
>
> I've appended at the end of this mail - so you can see for yourself.
> It is a GC bug or a user error?
UNIX heap size limit is certainly one of the factors. During the
test (doesn't crash on my system -- my user is allowed to consume
up to 2GB RAM) 'erl' consumes anywhere between 20MB to 1GB of RAM.
> What I'd like is a "linked in BIF" - it seems to me to be a bit of a
> pain in the whatnot to have to mess around with the Erlang internals
> every time you want to write a new BIF.
Doesn't the FFI EEP solve this?
> ------ cut --- below this line is from Steve's post-----
> [...]
> Nor does it talk about why this code fails, though I'd imagine it is
> copying and gc'ing large binaries like crazy every time you change 1
> bit.
It seems more like it's building new binaries with references to the
old binaries, the structure seems to be flattened on GC. Indeed,
adding a call to erlang:garbage_collect/0 into bitmap:set_bits/2
makes the test run in pretty much constant 30MB of RAM.
Mostly guessing here (based on bitmap.beam disassembly), but I'm
sure someone will correct me if I'm wrong ;-).
Regards,
-- Jachym
Mikael Pettersson
> Hi,
>
> I recent got mail from Steve Kirsch (Hello Steve) - asking a number
> of questions about representation of bit vectors for writing Bloom filters.
> So he sent me a program, which crashes his machine (out of memory)
> new(N, E) when N > 0, is_float(E), E > 0, E =< 1 ->
> {M, K} = calc_least_bits(N, E),
> #bloom{m=M, bitmap = <<0:((M+7) div 8 * 8)>>, k=K, n=N}.
Large bitmaps are problematic in Erlang.
You can do chunked representations, which will work but will incur
high overheads on both reads and writes.
Using large binaries as the code above does is fragile and inefficient.
Large binaries are allocated outside of the GCd heaps in a global shared
area and are accessed via small heap-allocated and GCd handles. Frequent
updates will require frequent new allocations and copies in the shared
area. Old versions of these binaries are only deallocated in response to
local (per-process) GCs when their handles die.
So creating a series of large binaries in rapid succession without
intervening GCs is a fairly reliable way of running out of memory.
HiPE needs large bitmaps for its register allocator, so we added our
own bitarray BIFs since all alternatives suck. As much as _I_ like them,
I cannot recommend them for application developers:
- they're only present in HiPE-enabled systems
- they're not documented or official in any way, and may change at any time
- the effect of sending a bitarray to another process is unspecified
(the processes may or may not share the object)
- Erlang is _supposed_ to protect application programmers from the perils
of mutable data :-/
Richard Andrews
> From: Mikael Pettersson <mi...@it.uu.se>
...
> So creating a series of large binaries in rapid succession without
> intervening GCs is a fairly reliable way of running out of memory.
+1
I haven't tested the program but have recently seen similar pathological cases.
You might mitigate the OoM problem with {fullsweep_after,0} in spawn_opt(). As you said Joe, this won't be fast and using the above fullsweep option will slow it down further.
Enjoy a better web experience. Upgrade to the new Internet Explorer 8 optimised for Yahoo!7. Get it now.
Paulo Sérgio Almeida
Joe Armstrong wrote:
> So he sent me a program, which crashes his machine (out of memory)
> which he thought
> should work - to my eye it looks ok - It will not be blindingly fast,
> but it looks properly
> tail-recursive so the garbage collector should not have any problems.
>
> I've appended at the end of this mail - so you can see for yourself.
> It is a GC bug
> or a user error?
I have looked at the program. It basically uses a single large binary,
which means that in each insertion K (for K hashes) new large binaries
are generated. Each one will be fully copied (right? this would be an
interesting case for aggressive optimizations in binary handling).
One easy improvement would be to use a variant of bloom filters that
uses K bitvectors instead of one single vector. But it would not be
enough. As Joe says:
> (we want to flip specific bits) - the "pure" answer I guess is a tuple
> of tuples of binaries
> (say 32x32xB) where B is a 128 byte binary for 2^20 bits.
>
> The "tuple of tuple of tuple ..." representation is commonly used to
> implement array and dicts
something like the above. But I would add one more twist. Use an array
not of binaries but of integers. I have once implemented a data type for
representing sets with bitmaps. (There I used ets instead of array, but
that is orthogonal.) First I used binaries but later I switched to
integers, exploiting the fact that erlang gives us arbitrary size
integers. It has some advantages:
- the space overhead is smaller than for binaries (specially for
smallish entries).
- for structures that may contain many zeroes, like in this case, a
single word for each 0 would be used. This means we could overdimension
the filter with less impact if it was very little used (again I am
thinking about small entries in the array, much less that the 128 bytes
example).
If I have time I will see If I can write a new version. Better, there is
a nice variant "Scalable Bloom Filters" [1] (shameless self promotion
:)) that can scale arbitrarily without forcing us dimension the filter.
It can be trivially implemented on top of a standard one (the
bidimensional variant).
Regards,
Paulo
1.
Scalable Bloom Filters
Information Processing Letters
Volume 101, Issue 6, 31 March 2007, Pages 255-261
Steve Kirsch
All your caveats are duly noted. We promise to be careful.
So now can you tell us how to use these functions that are already
there?
Our system is very RAM intensive and I'd love to be able to stay inside
erlang to do this.
thanks!
Bjorn Gustavsson
> Great, that explains the crash.
>
> All your caveats are duly noted. We promise to be careful.
>
> So now can you tell us how to use these functions that are already
> there?
>
Maybe you should first try the suggestion by Paulo Almeida above? That is,
use an array (as provided by the 'array' module) to store big integers in.
For instance, each entry in the array could could store an integer that can
hold 256 bits. That would most definitely be an improvement over using
binaries and might work good enough to work in your application.
/Bjorn
--
Björn Gustavsson, Erlang/OTP, Ericsson AB
Steve Kirsch
MFA every 10 msec for 100 samples using process_info(Pid,
current_function)
that's pretty cool.
But way cooler is to include:
-compile({parse_transform,ct_line}).
in the module I want to statistically profile.
This essentially pushes your M, F, line number in the process dictionary
(under key test_server_loc) each time you execute a line of code
(replacing it if in the same function so you get a call stack more or
less to a max depth of 10).
That's way cool.
So I'd like to access that key (test_server_loc) from my statistical
profiler which is running in another process.
How can I access that key? there isn't a get(test_server_loc, Pid) BIF.
=====================================
P.S. Here's my statistical profiler and test function... this all works
fine.
% statistical profiler. Spawns the MFA and then takes 100 samples, 10
msec apart.
sprof(M, F, A)->
Pid=spawn_link(M,F,A),
Time=10,
L=lists:seq(1,100),
GetCurrentMFA=fun()->
timer:sleep(Time),
case process_info(Pid, current_function) of
{_, MFA}->MFA;
undefined -> x
end
end,
OutList=[GetCurrentMFA()||_X<-L],
io:format("~p~n", [OutList]).
t1()->
ok.
t2()->
bye.
t3()->
fooey.
sprof_test(0)->
ok;
sprof_test(N)->
t1(),
t2(),
t3(),
sprof_test(N-1).
sprof_test()->
sprof(?MODULE, sprof_test, [100000000]).
Steve Kirsch
So what is the undocumented BIF?
-----Original Message-----
From: Bjorn Gustavsson [mailto:bgust...@gmail.com]
Sent: Thursday, April 30, 2009 12:14 AM
To: Steve Kirsch
Cc: Mikael Pettersson; Joe Armstrong; Erlang
Subject: Re: [erlang-questions] A bug? - bloom filters - and loadable BIFs
mats cronqvist
> I wrote a simple statistical profiler that basically snapshots a spawned
> MFA every 10 msec for 100 samples using process_info(Pid,
> current_function)
>
> that's pretty cool.
>
> But way cooler is to include:
>
> -compile({parse_transform,ct_line}).
>
> in the module I want to statistically profile.
>
> This essentially pushes your M, F, line number in the process dictionary
> (under key test_server_loc) each time you execute a line of code
> (replacing it if in the same function so you get a call stack more or
> less to a max depth of 10).
>
> That's way cool.
>
> So I'd like to access that key (test_server_loc) from my statistical
> profiler which is running in another process.
process_info(Pid,dictionary).
allow me to point out that what you're trying to accomplish can be
done (without recompiling/parse transforms) through tracing.
mats
Mikael Pettersson
> I've tried that and you still get about 100% storage overhead.
>
> So what is the undocumented BIF?
>
> -----Original Message-----
> From: Bjorn Gustavsson [mailto:bgust...@gmail.com]
> Sent: Thursday, April 30, 2009 12:14 AM
> To: Steve Kirsch
> Cc: Mikael Pettersson; Joe Armstrong; Erlang
> Subject: Re: [erlang-questions] A bug? - bloom filters - and loadable BIFs
>
> On Wed, Apr 29, 2009 at 8:09 PM, Steve Kirsch <steve....@propel.com> wrote:
> > Great, that explains the crash.
> >
> > All your caveats are duly noted. We promise to be careful.
> >
> > So now can you tell us how to use these functions that are already
> > there?
> >
>
> Maybe you should first try the suggestion by Paulo Almeida above? That is, use an array (as provided by the 'array' module) to store big integers in.
> For instance, each entry in the array could could store an integer that can hold 256 bits. That would most definitely be an improvement over using binaries and might work good enough to work in your application.
hipe_bifs:bitarray(NrArrayBits, InitialBitValue) -> BitArray
hipe_bifs:bitarray_sub(BitArray, BitNr) -> BitValue
hipe_bifs:bitarray_update(BitArray, BitNr, BitValue) -> BitArray
Bit values are the booleans true and false.
Array indexing is 0-based (1-based indexing is just sooo wrong).
The update operation returns the updated array.
The number of elements in a bit array is limited to what can be
described by non-negative fixnums (immediate "small" integers),
which is something like 2^27 - 1 on 32-bit machines. Larger bitarrays
than that must be emulated using a chunked representation.
See lib/hipe/regalloc/hipe_ig.erl for an example (look for
the USE_NEW_BITARRAY_BIFS define and the adjset code following it).
/Mikael
Steve Kirsch
passed by reference in a message. Awesome.
So is there a way to set a byte or word at a time??
Steve Kirsch
This is in the VM, but the compiler rarely generates it.
Is there a way to force this?
Steve Kirsch
trace can do lots of things, but it won't tell you line numbers unless
I'm mistaken (assuming you've inserted them).
but i do agree that line numbers might be useless for profiling in many
cases, but it can be very very useful.
-----Original Message-----
From: mats cronqvist [mailto:ma...@kreditor.se]
Sent: Thursday, April 30, 2009 2:44 AM
To: Steve Kirsch
Thomas Lindgren
----- Original Message ----
> From: Steve Kirsch <steve....@propel.com>
> To: Mikael Pettersson <mi...@it.uu.se>
> Cc: Erlang <erlang-q...@erlang.org>
> Sent: Thursday, April 30, 2009 6:25:28 PM
> Subject: Re: [erlang-questions] A bug? - bloom filters - and loadable BIFs
>
> is there a way to do a destructive setelement?
>
> This is in the VM, but the compiler rarely generates it.
>
> Is there a way to force this?
>
Practically speaking, for this to work in general, the VM needs a generational collector that tracks and handles pointers from the old generation to the new, which the current one does not. Philosophically speaking, just throwing destructive updates into the language is the quick road out of functional programming and into the grottier parts of Lisp. A general user mechanism for Erlang has to be cleaner than that.
(NB: I say this as the original proponent of and user of destructive updates in Hipe :-)
Best,
Thomas
Mikael Pettersson
> Wow. That is very cool. And if the bitarray is large enough, it is
> passed by reference in a message. Awesome.
>
> So is there a way to set a byte or word at a time??
No, and yes.
No, because the bitarray API really is like a plain array API
with the element size being a single bit, so there's no concept
of "multiple elements" in it.
Yes, because HiPE also adds a bytearray API similar to the bitarray
API I've described, and although bitarrays and bytearrays are unrelated
at the API level they happen to have the same representation, so it's
possible to (ab)use bytearray ops on bitarray objects and vice versa.
I'm only mentioning this because you've indicated a willingness to
accepts the caveats of relying on undocumented features. If you do
start using these features you should really have pure Erlang fallbacks
in place if/when these undocumented BIFs change.
Mikael Pettersson
> is there a way to do a destructive setelement?
>
> This is in the VM, but the compiler rarely generates it.
>
> Is there a way to force this?
Not really. Destructive setelement/3 is not trivial.
First there's the general avoidance of mutable data structures in
Erlang, and destructive setelement/3 in that setting is a step in
the wrong direction.
Second, having destructive updates of general collection-like objects
(cons cells, tuples) in any system with a generational garbage collector,
such as Erlang/OTP, _requires_ specific support from the garbage collector
(for handling so-called wrong-way pointers). Since the Erlang language
doesn't support mutable general collection-like objects, the Erlang/OTP VM
garbage collector doesn't either.
The BEAM Erlang compiler is able to identify certain kinds of
setelement/3 operations which can safely use destructive updates
(mainly record initialisations as I recall), and for those it uses
the VM's destructive setelement/3 operation.
However, giving programmers direct access to destructive setelement/3
is both unsafe and against the spirit of Erlang, so it's not going to
happen any time soon.
tsuraan
> not of binaries but of integers. I have once implemented a data type for
> representing sets with bitmaps. (There I used ets instead of array, but
> that is orthogonal.) First I used binaries but later I switched to
> integers, exploiting the fact that erlang gives us arbitrary size
> integers. It has some advantages:
I have a bitset implementation at
http://github.com/tsuraan/bitset/tree/master that uses tuples of
smallints (ints with only the lower 27 bits in use). It's growable,
and seems fast and correct. If anybody wants to take a look at it,
feel free to do so.
The included bstest.erl shows various useful things that the library
is capable of, and also generates random data using the bitset and
gb_sets to ensure that the two give the same results. For speed, the
test is somewhat stupid because it builds the set starting with bit 0
and going to bit 1,000,000, which is the most optimistic possible use
case, but it can do that in under a second on my machine. For actual
use cases it does perform very well, especially w.r.t boolean
operations like unions and intersections.