Java to the Limit

Running Erlang/OTP Tests

Here is just another update on Erjang progress. Two weeks ago I started looking seriously at running some of the OTP tests. There's a lot of them part of the standard otp distro, and so it's a great source of bug hunting context for Erjang.

A simpler test_server

But, but, but, ... the test_server is a big chunk of code and it was a bit too much to make it all run in one take; so I've written a small stand-alone version of test server that satisfies the same API as the real one to be able to run tests.

To run a test with Erjang, cd into the test_server subdirectoy, and copy a test into there (it's a file ending with _SUITE.erl), so e.g. the ets tests are in ets_SUITE.erl found in the lib/stdlib/tests directory. Then, compile the test and launch Erjang...

prompt$ cd $ERJANG/test_server
prompt$ cp $ERL_TOP/lib/stdlib/tests/ets_SUITE.erl .
prompt$ erlc ets_SUITE.erl
prompt$ java -Xss100m -jar ../erjang-0.1.jar -home $HOME 
Eshell V5.7.3  (abort with ^G)
1> ts:run(ets).

And off you go! I spent a few nights looking into the ets tests, and at present it passes close to half of the tests in the ets suite. Some of the ets tests are pretty scary exposing lots of detail about the implementation of ets.

The estone test suite

I've only been playing around with a few of the tests, but one of the more interesting ones is the estone suite, which gives some sort of performance measurement. Comparing BEAM to Erjang on my machine gives BEAM a score of ~140.000 so-called "estones", and Erjang a score of ~120.000 estones. Bigger is better, so BEAM is still a little ahead. The following is a graphical break-down of the components of the "estones" suite; and so here you can see where Erjang is slower or faster. The estones is the sum of these values; you can find the complete numbers in this Gist.

The areas where Erjang is particularly fast are "BIF dispatch", "Float arithmetics" and sending "Huge messages". "BIF dispatch" is fast (I guess) because BIF calls are generated as direct calls, and so the JVM can inline BIFs. "Floats" are fast because they can often be encoded directly as Java doubles so arithmetics is close to Java. For integer arithmetics Erjang looses because small integers have to overflow into big ints, and that calls for boxing all ints. But Erjang also shines in the categories "Alloc and dealloc" and "Links".

Not much has been done in terms of optimizing these, so there is plenty room for improvement. I still notice some congestion in the scheduler; which I have not tried to optimize. So there is lots of low hanging fruit.

In particular it is noticeable that Erjang falls behind in the "Function calls" category. I suspect this is because erlang:apply(M,F,A) is fairly slow as it is now; an inline cache per call-site could do wonders there.

Well, well...

Mnesia

Another thing I've been playing around with is to get mnesia to run. And it actually gets humping, ... look at this trace.

krab$ ./erl.sh -name erjang@`hostname`
Eshell V5.7.3  (abort with ^G)
(erjang@renaissance.local)1> mnesia:create_schema([node()]).
ok
(erjang@renaissance.local)2> application:start(mnesia).
ok
(erjang@renaissance.local)3> mnesia:create_table(users, 
    [{disc_copies, [node()]},{type, bag}]).
{atomic,ok}
(erjang@renaissance.local)4> mnesia:transaction(
    fun()-> mnesia:write({users,"krab",{"Kresten", "Thorup"}}) end).
{atomic,ok}
(erjang@renaissance.local)5> mnesia:transaction(
    fun()-> mnesia:read({users, "krab"}) end).
{atomic,[{users,"krab",{"Kresten","Thorup"}}]}
(erjang@renaissance.local)2> application:stop(mnesia).
ok
=INFO REPORT==== 18-May-2010::14:25:36 ===
    application: mnesia
    exited: stopped
    type: temporary

Given that distribution also "works" it should be possible to mix erjang and beam nodes in a mnesia cluster. Kind of cool, eh?

More on how to run tests...

Here are some more notes on how to use the test suite. You can use ts:list(ets) to get a list of the tests in the ets module as follows...

2> ts:list(ets).
[{new,[default,setbag,badnew,verybadnew,named,keypos2,
       privacy]},
 {insert,[empty,badinsert]},
 {lookup,[time_lookup,badlookup,lookup_order]},
 {delete,[delete_elem,delete_tab,delete_large_tab,
          delete_large_named_table,evil_delete,table_leak,baddelete,
          match_delete,match_delete3]},
 firstnext,firstnext_concurrent,slot,
 {match,[match1,match2,match_object,match_object2]},
 t_match_spec_run,
 {lookup_element,[lookup_element_mult]},
 {misc,[misc1,safe_fixtable,info,dups,tab2list]},
 {files,[tab2file,tab2file2,tab2file3,tabfile_ext1,
         tabfile_ext2,tabfile_ext3,tabfile_ext4]},
 {heavy,[heavy_lookup,heavy_lookup_element]},
 ordered,ordered_match,interface_equality,fixtable_next,
 fixtable_insert,rename,rename_unnamed,evil_rename,
 update_element,update_counter,evil_update_counter,
 partly_bound,match_heavy,
 {fold,[...]},
 member,t_delete_object|...]

And you can run a specific test (or a test set) using ts:run/2 as follows

3> ts:run(ets,match).
Running test category [match]


*** Running [ets_SUITE,match1]
*** SEED: {3172,9814,20125} ***
Calling with options [{write_concurrency,false}]
1 [{write_concurrency,false}]
2 [{write_concurrency,false}]
345Ets mem info: {notsup,undefined}Calling with options [{write_concurrency,true}]
1 [{write_concurrency,true}]
2 [{write_concurrency,true}]
345Ets mem info: {notsup,undefined}[{comment,"Incomplete or no mem leak testing"},{comment,"Incomplete or no mem leak testing"}]

*** [ets_SUITE,match1]: Succeeded
...

*** [ets_SUITE,match_object2]: Succeeded
[{success,{ets_SUITE,match_object2}},
 {success,{ets_SUITE,match_object}},
 {success,{ets_SUITE,match2}},
 {success,{ets_SUITE,match1}}]

For some tests you'll run into a stack overflow. That's often because the Erlang compiler generates code for list comprehensions which is not tail recursive; and so the stack need grows proportional to the size of the list being generated. To get around this you can run Erjang with -Xss100m to run with 100m stacks; one of these days somebody should write a transformation that rewrites the beam generated for list comprehensions into a tail recursive version (with a reverse in the end)... Some tests also need more async threads, whych you give it by passing -Derj.threads=X for some X. Ports that spawn external processes needs two async threads each, because Java has no non-blocking IO for that particular case.

It would be a great way to help the Erjang project to take one of the other Erlang/OTP tests and try to run it ... and let us know what you see. Perhaps you'll feel intrigued to go fix a bug; be my guest!

Triq: The Free QuickCheck for Erlang

Today I released the first version of Triq - Trifork QuickCheck (or triq for short), a free clone of QuviQ eqc. While triq is being developed for the purpose of testing Erjang it is "plain erlang" all the way, with no dependencies on Erjang in any way.

First I have to say that i feel a little uneasy releasing Triq, because the good guys at QuviQ are trying to make a business out of this. Never the less, I made the decision because an open source project is the only way for many people to try out quickcheck, and because eqc doesn't work on Erjang yet (I got a 30 day trial license, but failed to run in on Erjang). I have a lot of respect for John and Thomas, and I hope that Triq will have the effect of generating more interest for QuviQ eqc, which [at least for the time being] is a far superior product. I hope that Triq will make it easier for people to get started with quickcheck on the Erlang platform, and using the professional QuviQ eqc will be a natural progression for commercial users.

Enough disclaimers, now onto the action. In this blog post I'd like to explain how quick check works, because I think that it really needed to some extent to be able to envision what you can use it for. I'll followup with some more examples later on how I use it in context of Erjang.

Property Based Testing

Property based testing with QuickCheck is really nice, and very easy in context of a functional language like Erlang. QuickCheck properties are like unit tests, that are supposed to be true. A property is represented in Triq Check as an opaque value that you can give to triq:check/1 to have it tested, as in:

Prop = ?FORALL({X,Y}, 
               {int(),int()},
               (X==Y) == (Y==X)).

That is, for all two integers X and Y the (boolean) value of (X == Y) is equal to (Y == X). That may sound pretty moot, but for a VM implementation that is perhaps not so obvious.

To test the property, you call triq:check/1 like this:

1> triq:check(Prop).
.....................................................................
.................
Ran 100 tests
true
2> 

A more interesting case happens when a test fails. Here is one that typically fails:

prop_delete() ->
  ?FORALL(L,list(int()), 
    ?IMPLIES(L /= [],
       ?FORALL(I,elements(L), 
          not lists:member(I,lists:delete(I,L))))).

Which reads like this: For all values L in the domain "list of integers", if L is not an empty list, then for all values I, where I is an element of L; removing I from L yields a list of which I is not a member. Read that one more time.

When you run it, it fails if L happens to be a list that contains the same value twice. The lists:delete function only deletes the first occurrence of I in the list.

2> triq:check(prop_delete()).
x....Failed!

Failed after 5 tests with false
Simplified:
        L = [0,0]
        I = 0
false
3> 

The cool thing is that not only does Triq Check find some counter example for the property, it finds the minimal counter example.

But how does all this work?

To get started, let us take a closer look at the FORALL macro found in triq.hrl, in context of the first really simple example:

Prop = ?FORALL({X,Y}, 
               {int(),int()},
               (X==Y) == (Y==X)).

Here is an explanation of what you see:

• The first argument {X,Y} is a syntactic form used to assign value that will be bound in the body.
• The second argument {int(),int()} is a value domain, describing the domain of two-tuples containing integers at both position 1 and 2. The structure of the first two arguments must match, otherwise the check will fail with an exception.
• The third argument (the body) is an expression which is evaluated with X and Y bound to some random integers.

What actually happens is that FORALL saves a fun in a tuple ... the macro is defined something like this:

-define(FORALL(Args,Domain,Body), 
    { ..., body = fun( Args ) -> Body end, domain = Domain... }).

Later, when the test is executed, triq uses an internal (magic) function to generate some "random" member of the given domain, and pass it to the body:

test({ ..., body=Body, domain=Domain, ...}) ->
   Input = generate_member(Domain),
   Result = Body(Input).

The result of evaluating the body controls the how the test proceeds:

• If the body evaluates to true, then the test succeeds; (and triq will try again with another value of the given domain)
• if the body evaluates to a property then that property is checked recursively;
• otherwise the test fails.

Two concepts: properties, and value domains.

A property is an opaque value, which is the result of evaluating one of the macros FORALL, IMPLIES, WHENFAIL, TRAPEXIT, and TIMEOUT, or one of the functions in triq such as triq:fails/1 which inverts the success/failure of it's containing property.

A value domain can have one of several forms, some of which are opaque, and some are not:

• a tuple {VD1, ..., VDn} where each element VDi is itself a value domain generates N-tuples (i.e. the same size as the input), where each element is generated in the value domain of the corresponding tuple element.
• a list [VD1, ..., VDm] does the same thing, but for lists.
• all the functions exported from triq_domain, such as int/0, list/1, any/0, etc. yield value domains for specific kinds of values.
• any other value describes the domain of values that contain exatly the value itself as a member i.e., this domain can only generate said value, and can only be "shrunk" to said value too.

Thus, for instance:

{foo, int(), [x|choose(1,10)]}

Describes the domain of 3-tuples, for which the first element is always the atom foo, the 2nd element is an integer, and the 3rd element is a cons cell in which the head is always the atom x, and the tail can be any integer in the range 1..10. The functions int and choose are imported for you from the module triq_domain when you include triq.hrl.

Shrinking

QuickCheck will repeatedly try to test a property with increasingly complex/size input values, until it reaches a fixed number of runs (currently 100), or until it stops because it has found a counter example (i.e., an input value that makes the property fail).

The magic in QuickCheck happens when it is able to shrink a counter example to something comprehensible. Internally it does that by calling a function

SimplerValue = simplify_value(ValueDomain, Value).

Which will try its best to pick another value from said ValueDomain which is "simpler" than Value, for some definition of "simpler".

• For the int() value domain, values gravitate to zero: negative numbers gradually grow and positive numbers gradually shrink.
• For aggregate domains such as list(Dom), simplify_value will either replace one of the elements of the list with a simpler member, or remove one of the members of the list thus gravitating towards the empty list,
• ... and so on for other value domains.

The shrinking is done by performing a second run on the property, repeatedly shrinking and checking the property again; until it shrinks no further. That's it really -- pretty cool, eh?

Onwards from here...

Triq Check is early in its life, but to the best of my knowledge completely functional for what it does. I'm eager to receive reports from someone using it.

One of the areas that I have not explored is that it seems that QuviQ eqc has some advanced strategies for controlling the shrinking; kind of "pointing it in the right direction". Triq Check uses a pretty brute force method which seems to work fine on my small examples, but may prove totally inadequate for larger values.

Let me hear from you! Follow the project on GitHub github.com/krestenkrab/triq, or follow me on twitter: @drkrab.

Passing Fun's to Other Erlang Nodes

The last few days I've been working on completing Erjang's implementation of function object (fun's); specifically being able to pass fun values from one node to another, and I'd like to share some of the detail of how that works. Nothing breathtaking here, just some details that Erlangers might find interesting.

As you might know, Erlang distribution works by sending the binary encoding of terms; and so sending a fun is also essentially done by encoding it using erlang:term_to_binary/1; passing the resulting binary to another node, and then decoding it again using erlang:binary_to_term/1. (The truth is a bit more complex, because the distribution protocol have some extra tags and information stored in the binary format.) This is pretty obvious for most data types; but how does it work for function objects?

When you encode a fun, what is encoded is just a reference to the function, not the function implementation. The information passed on the wire corresponds largely to the information given by erlang:fun_info/1:

Eshell V5.7.3  (abort with ^G)
(erjang@127.0.0.1)1> erlang:fun_info(fun(X)->X*X end).
[{pid,<1.0.668>},
 {module,erl_eval},
 {new_index,2},
 {new_uniq,<<56,152,230,129,197,121,23,226,118,89,11,188,
             47,178,198,203>>},
 {index,6},
 {uniq,13229925},
 {name,'-expr/5-fun-2-'},
 {arity,1},
 {env,[[],
       {value,#Fun<shell.7.125426800>},
       {eval,#Fun<shell.24.80962049>},
       [{clause,1,
                [{var,1,'X'}],
                [],
                [{op,1,'*',{var,1,'X'},{var,1,...}}]}]]},
 {type,local}]

Some of these values are a bit strange, so let me explain: The first thing you notice is that a Fun object captures the PID, the current process when the fun was created. That's quite peculiar, and I have not been able to figure out why this information is part of the fun; nor what it is being used for.

The fun's identification consists of the values for module, new_index, new_uniq, index and uniq. The module is just the name of the module, and the new_uniq is an MD5 checksum of the module. new_index is an index into the BEAM file identifying the fun. At some point (distribution protocol version 5), the new_... elements were added; prior to that only module, index and uniq were passed (and this also applies when talking to pre R5 nodes). The old uniq is the hash code of the parse tree of the fun; index was some other index into the BEAM file. Finally, the value of the function's free variables env above, are passed in both versions of the distribution protocol.

The values of module, index and uniq are what is printed in the string representation of a string:

(erjang@127.0.0.1)2> fun(X)->X*X end.
#Fun<erl_eval.6.13229925>

But the definition of the function is not passed along; just exactly enough information to recreate the fun at an other node if the module is there.

So what happens if the function implementation is not there when the fun is decoded? Well, that depends.

If the module containing the fun has not yet been loaded, and the target node is running in interactive mode; then the module is attempted loaded using the regular module loading mechanism (contained in the module error_handler); and then it tries to see if a fun with the given id is available in said module. However, this only happens lazily when you try to apply the function.

If you never attempt to apply the function, then nothing bad happens. The fun can be passed to another node (which has the module/fun in question) and then everybody is happy.

Maybe the target node has a module loaded of said name, but perhaps in a different version; which would then be very likely to have a different MD5 checksum, then you get the error badfun if you try to apply it.

So you can see that functions are not resilient to module updates; and this is one of the reasons why you want to have the versions of your erlang nodes in sync. The Erlang runtime system makes sure that the function is only "applicable" if the real function is actually there. This version checking of funs was significantly strengthened with the update in erlang distribution protocol 5, because the the identity of the fun now includes an MD5 checksum of the entire module, not just the body of the fun itself.

But there is another kind of fun, a fun created with a direct reference to an exported function, such as this:

(erjang@127.0.0.1)6> fun erlang:display/1 .
#Fun<erlang.display.1>

Such function objects are transferred differently, carrying only the module, function and arity. And that makes such funs much more resilient to module updates; as they are applicable regardless of the version of the module. It's like an external function call is normally. So if you use these "external funs" carefully, you can use them to work with different versions of the same modules, such as in scenarios where you do code upgrades.

In the example above, the env does actually include the function definition because it exposes part of the Erlang interpreter which is part of the shell. So that's intersting too; it is kind of like passing a string to a remote site and doing "eval". You can use this yourself, to create funs that can be passed around, like this [Example due to Vladimir Sekissov]:

1> FunStr = "fun (A) -> A+B end.". 
2> {ok, Tokens, _} = erl_scan:string(FunStr).
3> {ok, [Form]} = erl_parse:parse_exprs(Tokens).
4> Bindings = erl_eval:add_binding('B', 2, erl_eval:new_bindings()).
5> {value, Fun, _} = erl_eval:expr(Form, Bindings).
6> Fun(1).
3

This will work as long as the version of erl_eval is the same on the sender and receiver node.

7>erlang:fun_info(Fun).
[{pid,<1.0.668>},
 {module,erl_eval},
 {new_index,2},
 {new_uniq,<<56,152,230,129,197,121,23,226,118,89,11,188,
             47,178,198,203>>},
 {index,6},
 {uniq,13229925},
 {name,'-expr/5-fun-2-'},
 {arity,1},
 {env,[[{'B',2}],
       none,none,
       [{clause,1,
                [{var,1,'A'}],
                [],
                [{op,1,'+',{var,1,'A'},{var,1,...}}]}]]},
 {type,local}]

This may work for you, but the resulting fun is obviously rather slow, since it is interpreted when applied. A better way might be to put your fun in a separate module which can then be force-loaded on the target node. Here is some code (from TrapExit) showing how to force load code remotely:

%% Find object code for module Mod 
{Mod, Bin, File} = code:get_object_code(Mod), 

%% and load it on all connected nodes including this one; 
%% the next time the code is called it will be using the new version
{Replies, _} = rpc:multicall(code, load_binary, [Mod, File, Bin]),

%% if this node were the "master/admin" node
%% then to push to everything but this node use:
%% {Replies, _} = rpc:multicall(nodes(), code, load_binary, [Mod, File, Bin]),

%% and then maybe check the Replies list.

This would force-load your local version of the code onto all connected nodes by passing the local beam code to the remote nodes; which assures that all the remote nodes have the correct version of your code.