Title: NetLogo Compiler: Implementing Peephole Optimizations
Organization: The Center for Connected Learning and Computer-Based Modeling
Student: Diparth Shah
Mentor: Jeremy Baker
The main aim of the project is to implement peephole optimizations for NetLogo Compiler on Desktop and Tortoise.
- Optimization for count primitive with mortal agentsets: This optimization removes the need of iterating the whole agentset unnecessarily when count value is less than the size of the agentset, thus making an early exit from the iterative loop. This is particularly useful for mortal agentsets (Turtles and Link) where the size of the agentset changes dynamically and compared count value is small, thereby saving time by making an early exit when a specific condition is satisfied.
-
On Desktop version, turtles and links are stored in
TreeAgentSet
by default. Impact of this optimization isn't much onTreeAgentSet
since turtles and links are stored in a specialized data structure calledTreeMap
, where size of the agentset can be easily calculated and not many iterations are involved. -
This optimization specifically targets agentsets which are stored in
ArrayAgentSet
, where each agent is individually iterated to obtain final size of the agentset. To specifically store agents intoArrayAgentSet
, we can usewith
clause. -
with
takes two inputs: on the left, an agentset (usually "turtles" or "patches"); on the right, a boolean reporter. It reports a new agentset containing only those agents that reported true -- in other words, the agents satisfying the given condition. -
Example:
let red-turtles turtles with [ color = red ]
It creates temporary agentsetred-turtles
which is of typeArrayAgentSet
. Every turtle stored into that agentset is of color red.
1. create-turtles 1000 [ ifelse random 2 = 0 [ set color red ] [ set color blue ] ]
2. let red-turtles turtles with [ color = red ]
3. if count red-turtles > 25 [show "There are more than 25 red turtles"]
-
The first line of the above code creates 1000 turtles. If random value generated is 0, then the turtle is assigned color red or else color blue. Second line creates temporary agentset
red-turtles
which holds all turtles having color red. Third line compares number ofred-turtles
and numeric constant 25. If the comparison turns out to be true,show
block is executed. -
When optimization is disabled:
count
primitive is executed where it iterates till the end of an agentset and returns size of the agentset. Once the size is known, it is compared with constant 25 and boolean result true is returned (in the above case). -
When optimization is enabled: Instead of iterating till the end of an agentset, we make an early exit if the count exceeds the compared constant value, thereby saving time of iterating till the end of the agentset.
-
Model used for Benchmarking: https://gist.github.com/diparthshah/1f7dcc668aedf2830d1111d8cbc7a5b0
-
Desktop Result:
Warmup: 30 seconds
Max: 120 seconds
Repeats: 200
// Optimization Disabled
[success] Total time: 2633 s, completed 20 Aug, 2019 10:50:42 PM
// Optimization Enabled
[success] Total time: 1587 s, completed 20 Aug, 2019 9:57:47 PM
- Tortoise Result:
Iterations: 20
// Optimization Disabled
CountBench Benchmark (GraalJS 1.0.0-rc12):
--Average: 5.599 seconds
--Min: 4.506 seconds
--Max: 11.152 seconds
// Optimization Enabled
CountBench Benchmark (GraalJS 1.0.0-rc12):
--Average: 3.859 seconds
--Min: 3.446 seconds
--Max: 5.273 seconds
-
Desktop [Merged] : https://github.com/NetLogo/NetLogo/pull/1771/commits
-
Tortoise [Merged] : https://github.com/NetLogo/Tortoise/pull/208/commits
-
_any(breedon) => _anybreedon
-
_any(turtleson) => _anyturtleson
-
Progress on Pending Work: https://github.com/diparthshah/NetLogo/commits/gsoc2019
-
Jeremy Baker, my amazing and extremely helpful mentor from CCL who helped me throughout the project right from setup, architecture, implementation, testing and benchmarking process. His suggestions on every topic were invaluable and discussions with him helped me to expand my knowledge on various topics.
-
CCL Organization, providing me an opportunity to demonstarte my skills and helping me to enhance my knowledge on compilers.
-
Google, to host this program and encouraging open source software development.