Skip to content

Instantly share code, notes, and snippets.

@diparthshah
Last active August 23, 2019 19:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save diparthshah/2b3aa56d20fb43b72a0024839907b59a to your computer and use it in GitHub Desktop.
Save diparthshah/2b3aa56d20fb43b72a0024839907b59a to your computer and use it in GitHub Desktop.
Google Summer of Code 2019 - Work Product Submission

Google Summer of Code 2019 - Work Product Submission

Title: NetLogo Compiler: Implementing Peephole Optimizations

Organization: The Center for Connected Learning and Computer-Based Modeling

Student: Diparth Shah

Mentor: Jeremy Baker

Project Abstract

The main aim of the project is to implement peephole optimizations for NetLogo Compiler on Desktop and Tortoise.

Work Completed

  • 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.

Short Explanation

  • On Desktop version, turtles and links are stored in TreeAgentSet by default. Impact of this optimization isn't much on TreeAgentSet since turtles and links are stored in a specialized data structure called TreeMap, 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 into ArrayAgentSet, we can use with 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 agentset red-turtles which is of type ArrayAgentSet. 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 of red-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.

Benchmarking Results

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

Link to commits

Work Pending

Acknowledgments

  • 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment