The Joys of “perl -d:DProf”

I am working on my thesis for an MS in computer science, and my topic is finite automata. It is being done in Perl, and once I finish what I am doing I will be sure to release the details. I promise it is not Earth shattering. It seems like the more low level I get into CS the more I like it....anyway, on to the subject.

I discovered the joys of perl -d:DProf, and was able to drastically improve performance for RE->to_nfa by only changing state names if there was a clash and only sync’ing the epsilon symbol if they were different. This netted a 300% peformance gain when converting fifty 32-character regexes. Granted they were randomly generated and contained varying degrees of nested expressions, but it is still a great result!

Check out the profiles below showing the improvement:

BEFORE:

Total Elapsed Time = 14.75619 Seconds  #—-!!
  User+System Time = 14.82619 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c  Name
 59.0   8.753 13.007  30974   0.0003 0.0004  NFA::rename_state #—-!!
 14.9   2.213  2.213 186601   0.0000 0.0000  FA::is_member
 11.6   1.721  1.721 123476   0.0000 0.0000  FA::get_states
 5.73   0.849  1.706  41571   0.0000 0.0000  NFA::add_transition
 3.53   0.524 11.198   1406   0.0004 0.0080  NFA::append_nfa
 1.65   0.245  0.245  41914   0.0000 0.0000  FA::get_final
 1.57   0.233  3.099  84890   0.0000 0.0000  FA::is_state
 1.47   0.218  0.547  48447   0.0000 0.0000  FA::is_symbol
 1.21   0.180  0.180   3937   0.0000 0.0000  RE::get_terminals
 1.15   0.171  0.171   3648   0.0000 0.0000  RE::is_member
 1.14   0.169  0.882  17619   0.0000 0.0001  FA::add_state
 1.05   0.156  0.704  46634   0.0000 0.0000  FA::add_symbol
 0.93   0.138  0.381   1975   0.0001 0.0002  RE::L
 0.92   0.136 13.205   3241   0.0000 0.0041  FA::append_state_names
 0.82   0.121 15.850   3391   0.0000 0.0047  RE::thompson

AFTER:

Total Elapsed Time = 4.336713 Seconds  #—-!!
  User+System Time = 4.276713 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c  Name
 24.7   1.060  1.060 100111   0.0000 0.0000  FA::is_member
 12.8   0.550  0.550  65038   0.0000 0.0000  FA::get_states
 12.5   0.535  0.832   3116   0.0002 0.0003  NFA::rename_state  #—-!!
 8.63   0.369  1.927   1558   0.0002 0.0012  FA::ensure_unique_states  #—-!!
 6.76   0.289  0.651  14560   0.0000 0.0000  NFA::add_transition
 6.64   0.284  1.540  56014   0.0000 0.0000  FA::is_state
 6.10   0.261  3.173   1396   0.0002 0.0023  NFA::append_nfa
 5.05   0.216  0.869  16413   0.0000 0.0001  FA::add_state
 3.79   0.162  0.162   3895   0.0000 0.0000  RE::get_terminals
 3.58   0.153  0.153   3626   0.0000 0.0000  RE::is_member
 2.92   0.125  0.334   1926   0.0001 0.0002  RE::L
 2.76   0.118  0.552   1396   0.0001 0.0004  NFA::clone
 2.50   0.107  4.524   3416   0.0000 0.0013  RE::thompson
 2.36   0.101  0.322  19589   0.0000 0.0000  FA::add_symbol
 2.15   0.092  0.092  14069   0.0000 0.0000  FA::get_final