pattern matching vs proplists vs dict performance

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

pattern matching vs proplists vs dict performance

Mikhail Sobolev
Hi,

We have a lot of proplists, where the keys (atoms) need to be
converted to strings.

The first idea was to create another proplist with the necessary
mapping and write a function that would do the things.  After
considering it for a while (without actually writing any code :)),
Erlang pattern matching came to mind.  After looking around a bit I
saw statements like "for rather short proplists (10s of elements), the
speed will be pretty much the same".

We have 10s of thousands of documents that require this kind of
conversion and this conversion has to be done fast.  So I decided to
write a little benchmark[1], which gave the definitive answer: pattern
matching is much faster (times on the test machine):
  * proplists -- ~4.9s
  * dicts -- ~3.0s
  * case inside the function -- ~0.86s
  * case as a separate function -- ~0.89s

We have discussed the results and started to wonder:

1) are we doing something wrong? (we are all newbies in here)
2) why there's such a big difference in time? (proplists module
provides BIFs, right?)
3) are there any other ways to do what we want?

The current inclination is to generate a function based on the mapping
and then utilize the produced function to do the job.

Any answers/comments/suggestions? :)

--
Misha

[1]  https://gist.github.com/956717
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: pattern matching vs proplists vs dict performance

dmercer
On Thursday, May 05, 2011, Mikhail Sobolev wrote:

> We have 10s of thousands of documents that require this kind of
> conversion and this conversion has to be done fast.  So I decided to
> write a little benchmark[1], which gave the definitive answer: pattern
> matching is much faster (times on the test machine):
>   * proplists -- ~4.9s
>   * dicts -- ~3.0s
>   * case inside the function -- ~0.86s
>   * case as a separate function -- ~0.89s
>
> We have discussed the results and started to wonder:
>
> 1) are we doing something wrong? (we are all newbies in here)

I don't think so.  I'd expect pattern matching in a case or function to be
faster than iterating through a data structure, regardless of whether the
data structure is a proplist or dict.

> 2) why there's such a big difference in time? (proplists module
> provides BIFs, right?)

Again, I don't think so.  I consider proplists to be Erlang-only, and I'd be
surprised if it were implemented in C.  Regardless, I'd still expect pattern
matching to be faster.

> 3) are there any other ways to do what we want?

You could look them up in ETS tables.  ETS *is* in written in C, so it
*might* be faster than proplists and dicts, but I still wouldn't expect it
to be faster than pattern-matching.  Benchmark to prove me right or wrong.

> The current inclination is to generate a function based on the mapping
> and then utilize the produced function to do the job.

If 3-5s is unacceptable, but 0.9s is OK, that's the way I'd go, so long as
you're not changing the atom-to-string mapping very often (requiring
regeneration/recompilation of the function).  If 3-5s is OK, however, I'd
concentrate on other problems.

Cheers,

DBM

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: pattern matching vs proplists vs dict performance

Iñaki Garay
On Thu, May 5, 2011 at 11:25, David Mercer <[hidden email]> wrote:

> On Thursday, May 05, 2011, Mikhail Sobolev wrote:
>
>> We have 10s of thousands of documents that require this kind of
>> conversion and this conversion has to be done fast.  So I decided to
>> write a little benchmark[1], which gave the definitive answer: pattern
>> matching is much faster (times on the test machine):
>>   * proplists -- ~4.9s
>>   * dicts -- ~3.0s
>>   * case inside the function -- ~0.86s
>>   * case as a separate function -- ~0.89s
>>
>> We have discussed the results and started to wonder:
>>
>> 1) are we doing something wrong? (we are all newbies in here)
>
> I don't think so.  I'd expect pattern matching in a case or function to be
> faster than iterating through a data structure, regardless of whether the
> data structure is a proplist or dict.
>
>> 2) why there's such a big difference in time? (proplists module
>> provides BIFs, right?)
>
> Again, I don't think so.  I consider proplists to be Erlang-only, and I'd be
> surprised if it were implemented in C.  Regardless, I'd still expect pattern
> matching to be faster.

You can find the code to the proplists module in
/usr/lib/erlang/lib/stdlib-1.17.1/src/proplists.erl
(or the equivalent directory in your system).

--
Iñaki Garay.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: pattern matching vs proplists vs dict performance

Mikhail Sobolev
In reply to this post by Mikhail Sobolev
Hi Loïc,

On 5 May 2011 21:14, Loïc Hoguin <[hidden email]> wrote:

> On 05/05/2011 10:37 AM, Mikhail Sobolev wrote:
>> We have 10s of thousands of documents that require this kind of
>> conversion and this conversion has to be done fast.  So I decided to
>> write a little benchmark[1], which gave the definitive answer: pattern
>> matching is much faster (times on the test machine):
>>   * proplists -- ~4.9s
>>   * dicts -- ~3.0s
>>   * case inside the function -- ~0.86s
>>   * case as a separate function -- ~0.89s
>>
>> We have discussed the results and started to wonder:
>>
>> 1) are we doing something wrong? (we are all newbies in here)
>
> You should also try:
>  {atom, Value} lists:keyfind(atom, 1, List).
Thanks for the suggestion.  I tried it and it indeed wins over
proplists.  But loses to dict and the rest.

> And, possibly with a little more processing:
>  atom_to_list(atom).
Could you please elaborate?  Why converting an atom to a list might help?

> But pattern matching should still be faster because it can be optimized
> at compile-time.
Aha.

>> 2) why there's such a big difference in time? (proplists module
>> provides BIFs, right?)
>
> No. But lists:keyfind should be a BIF. The proplists module isn't
> designed to be fast.
Thank you.  So our understanding was wrong.  Good to know.

>> 3) are there any other ways to do what we want?
>>
>> The current inclination is to generate a function based on the mapping
>> and then utilize the produced function to do the job.
>
> If your keys are known in advance you should definitely use pattern
> matching.
In a sense, yes, they are.  So we'll go with this approach.

--
Misha
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: pattern matching vs proplists vs dict performance

Torben Hoffmann


On Thu, May 5, 2011 at 21:04, Mikhail Sobolev <[hidden email]> wrote:
Hi Loïc,

<snip>
 
>> 2) why there's such a big difference in time? (proplists module
>> provides BIFs, right?)

bifs_in_release() ->
    xref:start(s).
    xref:add_release(s,"c:/Program\ Files/erl5.7.4/",[{builtins,true}]).
    {ok,Bifs} = xref:q(s,"B").
    Bifs.

This will give you all BIFs in the release. Change the path according to your set-up or take the path as an argument to the function.

Cheers,
Torben
--
http://www.linkedin.com/in/torbenhoffmann

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions