manopapad/proper — pull request #32 by yrashk (2012-04-13 17:31:59+00:00)
Title: Improves performance by avoiding orddict

Vanilla PropEr:

```erlang
1> G = proper_types:vector(100000, proper_types:integer()).
2> timer:tc(proper_gen,pick,[G]).
{2001564,
{ok,[-2,-20,7,11,-8,3,34,14,1,15,-4,5,-13,-9,-3,25,10,-8,12,
9,2,12,7,0,-1|...]}}
3> timer:tc(proper_gen,pick,[G]).
{1938967,
{ok,[16,1,5,0,1,-29,2,4,-4,-5,-3,10,-5,2,24,-2,0,-2,1,-9,13,
8,-3,-8,-6|...]}}
4>
4> timer:tc(proper_gen,pick,[G]).
{1943552,
{ok,[-2,4,1,-174,-10,-3,5,-4,2,8,-6,-7,5,1,-22,-1,-3,5,5,-1,
1,-24,4,15,12|...]}}
```

After the patch:

```erlang
2> G = proper_types:vector(100000, proper_types:integer()).
3> timer:tc(proper_gen,pick,[G]).
{1564630,
{ok,[52,-7,10,8,-5,28,3,4,-3,6,0,-20,0,-7,1,7,-25,-20,7,-10,
-13,-1,21,47,9|...]}}
4> timer:tc(proper_gen,pick,[G]).
{1476718,
{ok,[10,-120,6,-1,-15,-7,-4,-12,10,-13,-31,0,3,-6,-4,-17,4,
0,6,-1,-5,-2,1,-13,37|...]}}
5> timer:tc(proper_gen,pick,[G]).
{1531201,
{ok,[-5,2,-45,5,6,-4,-7,-1,-5,5,-3,-14,-5,-14,0,4,-5,9,32,4,
22,1,-11,-17,-17|...]}}
```

In this particular case, we can see a 1.2x speedup. In some of our (more complex) test cases we see speedups up to 2.5x.

This finding is supported by @okeuday's findings as published on his blog (http://okeuday.livejournal.com/). In particular, this bit is important:

```
The orddict data structure is the fastest data structure for storing data with integer keys. However, all other operations on an orddict are very slow compared to any of the other data structures. Storing data with an integer key is slowest in a tuple, but the integer key lookup of data within a tuple is the fastest among all the data structures. The process dictionary is the fastest for storing data if you ignore an orddict with an integer key (since a lookup in an orddict is painfully slow)
```