aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/src/orddict.erl
AgeCommit message (Collapse)Author
2014-01-09Merge branch 'sv/faster-orddict-from_list/OTP-11552'Björn Gustavsson
* sv/faster-orddict-from_list/OTP-11552: improve performance for orddict:from_list/1
2013-12-19improve performance for orddict:from_list/1Steve Vinoski
Improve the performance of orddict:from_list/1 by reimplementing it using the lists module in a way that preserves backward compatibility. The QuickCheck programs linked below were used to verify backward compatibility: * https://gist.github.com/vinoski/3bd216efa421c581174a * https://gist.github.com/vinoski/c6db70e8dc725083843d Both tests, which were run on R16B03, require the original orddict module to be renamed to olddict, and that code:unstick_mod/1 be applied to orddict in order to allow it to be replaced with the revised orddict. The first QuickCheck test first generates a list of pairs of terms, then uses the list to create both an original and revised orddict using from_list/1, then verifies that the results of the operation are the same for both instances. The second QuickCheck test is similar except that it first creates an instance of the original and revised orddicts and then folds over a randomly-generated list of orddict functions, applying each function to each orddict instance and verifying that the results match. The revised orddict:from_list/1 function was also tested to assess performance against the original orddict implementation. The test program used is available here: * https://gist.github.com/vinoski/61772a052f3501e1e128 Since an orddict instance is implemented as a list, the test program creates ordicts of length 1, 10, 100, and 1000 and uses them to assess performance at each length. Performance was measured using timer:tc/3 to time a number of iterations of various tests against the original orddict and against the revised orddict. To test from_list/1, orddicts of lengths 1, 10, 100, and 1000 are created from a list of random pairs with integer keys. For lengths greater than 1, two different tests are performed: one passing a list of pairs in sorted key order, and the other passing a list of pairs in reverse sorted key order. Since orddicts are ordered, these orderings effect worst-case and best-case behavior of the original orddict:from_list/2 implementation respectively. These tests were performed against R16B02 on a Macbook Pro with an Intel Core i7 processor running at 2.7GHz and 16GB of RAM running OS X 10.8.5, and on a Dell system with a 3.4GHz Intel Core i7 and 16GB of RAM running Ubuntu Linux 12.04. The tables below show results for OS X and Linux respectively. Each table lists the name of each test followed by two numbers, each a time in microseconds of the average of 10 runs of the test. The first number is the result for the original orddict, the second for the revised orddict. As the numbers for both platforms show, the revised from_list/1 function is always faster than the original version, in some cases quite a bit faster. Results from OS X: ------------------ from_list length 1: 1.789 0.116 from_list length 10 ordered: 10.082 3.040 from_list length 10 reverse ordered: 4.853 3.604 from_list length 100 ordered: 397.213 20.134 from_list length 100 reverse ordered: 25.473 20.745 from_list length 1000 ordered: 37490.26 251.46 from_list length 1000 reverse ordered: 307.94 215.96 Results from Linux: ------------------- from_list length 1: 0.146 0.025 from_list length 10 ordered: 4.729 0.815 from_list length 10 reverse ordered: 1.687 0.956 from_list length 100 ordered: 144.467 5.896 from_list length 100 reverse ordered: 6.694 5.816 from_list length 1000 ordered: 13755.19 79.413 from_list length 1000 reverse ordered: 91.54 64.308
2013-09-13Add dict:is_empty/1 and orddict:is_empty/1Magnus Henoch
dict:size/1 runs in constant time, but orddict:size/1 does not. With this change, the two modules stay API compatible and gain a constant-time function for checking whether a dictionary is empty.
2011-05-12Types and specifications have been modified and addedHans Bolinder
2011-03-11Update copyright yearsBjörn-Egil Dahlberg
2010-09-24Correct erroneous specs; strengthen some othersKostis Sagonas
2009-11-20The R13B03 release.OTP_R13B03Erlang/OTP