Improve performance

[dkamm]

Current implementation is too slow beyond just python.

T=3, 100 programs

their implementation:
dfs - 500us
sort-and-add - 1ms

mine:
dfs - 38s
sort-and-add - 2640s

dfs slowdown: 76000x
sort-and-add slowdown: 2640000x

Want to get the slowdown to ~100x range (just python)

possible reasons:

1. not caching partial results
2. unnecessary object creations

[dkamm]

profile results:

Sun Oct 22 11:05:26 2017    profile.out

         146756150 function calls (145116825 primitive calls) in 73.000 seconds

   Ordered by: internal time
   List reduced from 1268 to 10 due to restriction <10>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  4504537    7.587    0.000   31.839    0.000 function.py:9(__call__)
  1580537    7.151    0.000   41.363    0.000 program.py:114(__call__)
1410769/100    5.208    0.000   72.835    0.728 search.py:68(dfshelper)
  5703616    5.193    0.000    6.054    0.000 {method 'join' of 'str' objects}
  1440318    4.946    0.000   11.771    0.000 program.py:61(toprefix)
  1440318    3.027    0.000   17.003    0.000 program.py:55(__init__)
  4505767    2.725    0.000    6.645    0.000 value.py:29(construct)
  4504537    2.693    0.000    3.676    0.000 function.py:10(<listcomp>)
  1410769    2.193    0.000   43.671    0.000 search.py:56(is_solution)
 15290006    1.918    0.000    1.918    0.000 value.py:12(val)

[dkamm]

I read their benchmark wrong- it's a per task timeout (what timeout solves 20%, 40%, 60%, etc of the test set).

For T=3, they had

20% - 41ms
40% - 126ms
60% - 314ms

Depending on the # of inputs, my numbers are pretty close.

Here is # inputs = 2 (my numbers are actually faster)

(deep) Davids-MacBook-Pro:deepcoder dkamm$ python deepcoder/scripts/solve-examples.py --samples deepcoder/dataset/programs_T=3_inputs=2_test_examples.txt --T 3
100%|████████████████████████████████████████████████████████████████████████| 100/100 [00:19<00:00,  5.01it/s]
solved 100/100 (100.00%)
        wall (ms)   # steps
0.2      1.984119      18.6
0.4      5.795240      58.6
0.6    226.371956    2358.6
0.8   1799.160671   19767.0
1.0  11683.340073  110009.0

Here is # inputs = 3 (my numbers are much slower, max 100k nodes expanded)

(deep) Davids-MacBook-Pro:deepcoder dkamm$ python deepcoder/scripts/solve-examples.py --samples deepcoder/dataset/programs_T=3_inputs=3_test_examples.txt --T 3
100%|████████████████████████████████████████████████████████████████████████| 500/500 [07:01<00:00,  1.19it/s]
solved 190/500 (38.00%)
        wall (ms)   # steps
0.2    378.281355    3787.8
0.4   9010.549879  100000.0
0.6   9605.433035  100000.0
0.8  10117.793131  100000.0
1.0  13014.326096  100000.0

I'm curious to know the median number of nodes expanded in their datasets. Also I'm exploring roughly 10k nodes per second.