Erlang lists:keyfind or proplists:get_value?

Some days ago I quickly went through a post by Sergio Veiga, stating an interesting difference in speed between two Erlang functions which basically have the same functionality of retrieving a value from a list: lists:keyfind/3 and proplists:get_value/2.

Intrigued, I decided to perform additional testing, by performing a small benchmark of a random key retrieval on lists of different sizes, using those two different functions.

Here’s the code I used:

-module(pvsl).
-define(LIST_SIZES, [10000, 100000, 1000000]).
-define(RETRIES, 1000).
-compile(export_all). start() -> % test for different list sizes lists:foreach(fun(N) -> test_list(N) end, ?LIST_SIZES). test_list(ListSize) -> % generate a list of size ListSize of {Key, Val} entries KeyList = [{K, K} || K <- lists:seq(1, ListSize)], % test this list against both functions lists:foreach(fun(Type) -> get_val(Type, now(), KeyList, ListSize, ?RETRIES) end, [proplists, lists]). % test getting values, compute necessary time and output print results
get_val(Type, Start, _KeyList, ListSize, 0) -> T = timer:now_diff(now(), Start), io:format("computed ~p random key searches on a ~p-sized list in ~p ms using ~p~n", [?RETRIES, ListSize, T/1000, Type]);
get_val(proplists, Start, KeyList, ListSize, Tries) -> proplists:get_value(random:uniform(ListSize), KeyList), get_val(proplists, Start, KeyList, ListSize, Tries - 1);
get_val(lists, Start, KeyList, ListSize, Tries) -> lists:keyfind(random:uniform(ListSize), 1, KeyList), get_val(lists, Start, KeyList, ListSize, Tries - 1).

I ran this test on my MacBook Pro, Intel Core i5 2.4GHz with 4GB Memory, and Erlang R13B04, with Kernel Polling enabled. These are the results.

roberto$ erl +K true +P 1000000
Erlang R13B04 (erts-5.7.5) [source] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:true] Eshell V5.7.5 (abort with ^G)
1> c(pvsl).
{ok,pvsl}
2> pvsl:start().
computed 1000 random key searches on a 10000-sized list in 323.373 ms using proplists
computed 1000 random key searches on a 10000-sized list in 12.897 ms using lists
computed 1000 random key searches on a 100000-sized list in 3273.973 ms using proplists
computed 1000 random key searches on a 100000-sized list in 130.592 ms using lists
computed 1000 random key searches on a 1000000-sized list in 34131.905 ms using proplists
computed 1000 random key searches on a 1000000-sized list in 2050.627 ms using lists
ok
3>

Of course, this is far from being a complete benchmark, however it does show that proplists:get_value/2 is considerably slower [up to 25 times on smaller lists on this benchmark run] than lists:keyfind.

Not sure why this is happening, though I would recommend using lists:keyfind/3 on all speed-critical parts of your code.

Comments

keyfind is internally implemented as a BIF

Posted by anon on 20 May 2010 at 21:32

I never apprehension that you could use prop lists with atom lists, pass4sure 640-822 acknowledgment for the correction. pass4sure 350-030 In the column i just did the case i was using, pass4sure VCP-410 but i absent a some time and i accept i accept a actual accomplishing of prop lists get value no 2 Default value.

Posted by Yeng2 on 11 Feb 2011 at 06:48

Thanks for the help. I’ve been trying to find a better way to retrieve values and the fact that proplists:get_value/2 is up to 25 times slower than lists:keyfind/3 is a huge difference maker. In the code I’ve been using for our fulfillment operations I keep having slow results. If this can speed up my time, I’ll be more than grateful.

Posted by Christopher on 15 Feb 2011 at 21:05

I proposed this several years ago, but now there seems to be
a little momentum to improve the drafting and implementation,
I’m reviewing. It’s a nip in the library, so no formal SAA. If someone
AEA wants a real let me know. recados para orkut

Posted by jenny on 26 Feb 2011 at 09:58

Wow that is very interesting I never would have thought that it would be so much slower but I will definitely be using keyfind from now on
passive niche profits

Posted by josh on 05 Jun 2011 at 04:18

This article is very interesting. Thank you very much for sharing .  video to flash converter \  MTV downloader !  flv to dvd converter | dvd creator

Posted by chinsg on 16 Nov 2011 at 18:47

Add comment