Optimize DataFlowAnalyzer with a work list #85

Closed
opened 4 years ago by gpe · 4 comments
gpe commented 4 years ago
Owner
See https://en.wikipedia.org/wiki/Data-flow_analysis#The_work_list_approach
gpe added the
improvement
deobfuscator
labels 4 years ago
Poster
Owner

Surprisingly, this makes it 3x slower!

There might be other things we can optimize though - e.g. using mutable collections? We might need to make DataFlowAnalyzer aware of Sets in that case though - i.e. its T will be the elemnt, rather than the set type.

Surprisingly, this makes it 3x slower! There might be other things we can optimize though - e.g. using mutable collections? We might need to make DataFlowAnalyzer aware of Sets in that case though - i.e. its T will be the elemnt, rather than the set type.
Poster
Owner

I think we might also want to consider the iteration order. (This would be easier to do if we switched to jgrapht.)

I think we might also want to consider the iteration order. (This would be easier to do if we switched to jgrapht.)
Poster
Owner

I've tried the work list approach again and it seems much faster (did I make a mistake before?) but it'd be good to confirm it with some benchmarking.

I also wonder if we can improve the performance by changing the order we add nodes to the work list in initially (before we enter the loop).

I've tried the work list approach again and it seems much faster (did I make a mistake before?) but it'd be good to confirm it with some benchmarking. I also wonder if we can improve the performance by changing the order we add nodes to the work list in initially (before we enter the loop).
Poster
Owner

The work list approach is definitely faster - by about 6x!

The work list approach is definitely faster - by about 6x!
gpe closed this issue 4 years ago
Sign in to join this conversation.
Loading…
There is no content yet.