GSoC 2020 - Chapel

I’m very excited to get selected for GSoC 2020 / Chapel / Sequential Data Structures. This post is to document the journey.

Links

Notes on DS

Week 0 (May 15 - May 22)

• Setup Blog
• Make related issues on GitHub
• Look into List.chpl and compare with std::vector
• Look into domain and decide whether to add *Map into to-do list.
• Find about different data structures in other languages

Rethink the proposal

In the first meeting, mentors told me that the structures listed in the idealist didn’t mean that they have to be in the actual project. They were just examples. Actually I had misunderstood the intent of the original idealist and put all of the stuff into my proposal, some of which even I didn’t understand why we need.

So I need to look into other languages and Chapel itself to get an idea about what is really in need and what is not. I have done lots of searching and compared them, and listed pros&cons. The outcome seems very nice to me and my mentor Krishna. I have got a deeper understanding about what other languages have and what Chapel needs. It makes me feel more certain about what I’m going to do this summer. With more confidence, I think some of the structures are thoughtful enough to ask the core developers of Chapel for feedback.

Week 1 (May 22 - May 29)

• Go through the Buffers module and check out the source
• Update issues with latest finding
• Come back to the source of List.chpl

Stand by

This week most of the work is reading, updating issues, and discussing about the interfaces in related issues. Coding period is coming!

Week 2 (May 29 - June 5)

• Send e-mails about Heap and Vector for feedbacks
• Change from type comparator to record comparator
• Migration from 1-based to 0-based index
• Migration from UnitTest to TestSystem
• Adding tests about types, mostly adapting from List
• Fix some (about half) of the type bugs

Start Coding

Last week is the first week of the coding period. I’m kind of busy to reading the Chapel documents and coding. The time when I looked back, I realized I had done lots of work this week. The Class management and the lifetime checker of Chapel is more challenging than I expected. However, I’m still making progress by reading, searching and experimenting.

Week 3 (June 5 - June 12)

• Complete tests for Heap
• About half of Implementation of Vector

The Vector

I have managed to fix some tricky bugs of Heap related to types and lifetime. Heap is completed and waiting for feedback. For Vector, it’s not difficult to follow List.chpl and write code in a similar structure, which makes the development fast.

Week 4 (June 12 - June 19)

• Complete tests for Vector
• Complete Implementation of Vector
• Make a prototype of the unified interface with different implementations.

The Unified Interface

Another busy week. After lots of testing and experimenting, the outcome is very exciting. A new list interface can be made to allow users to choose the implementation they prefer. This is a very useful and powerful feature that I’ve never seen in other languages. All of this has to thank my mentors’ guidance and the power of Chapel. I feel like I’m really building an important part of Chapel and it will be very useful. Also I’ve got a new idea for the upcoming SearchTree and SkipList. They can be unified, too. Maybe a structure called OrderedSet.

Week 5 (June 19 - June 26)

• Discuss OrderedSet, OrderedMap
• Discuss the unified interface more thoroughly
• Discuss the location of the project outcome
• Make Vector more robust

Last Week of the First Stage

I have taken two exams this week so not much coding has been done. It’s worth note that after some thoughts, I managed to narrow down the range of types that Vector doesn’t support. It now supports all types that isDefaultInitializable .

Moreover, I put forward the idea about OSet/OMap that occurred to me last week as a issue. Surely, they should be unified. I suppose nobody is against that. The debate is whether they should be put together with the existing Set/Map. There’s a similar debate about UnrollLinkedList.

Luckily, we don’t have to reach a agreement on that immediately. It’s fine to focus on the implementation for the next week. However, at some point, I must drive the discussion to a finalized state. I don’t have a clear idea about how to do that. Maybe I should read more the past design issues of Chapel to see the process, or ask my mentors for suggestions when needed.

Data structure is an area I’m very familiar with. So coding is easy and testing is not difficult (though boring). The big question is to design and discuss. I feel lucky to learn about that from working with skilled developers of Chapel.

Week 5 (June 26 - July 3)

• Complete a basic implementation of Treap

Treap

This week I’m too busy with my final school assignment to work for GSoC. However, I manage to find time to finish a basic Treap in Chapel, with insertion and deletion. I think next week I can get Treap done.

Week 6 (July 3 - July 10)

• Finish Treap and the interface of OrderedSet
• Add tests for OrderedSet
• Follow up Vector and Heap’s PR

OrderedSet

I have finished Treap and added lots of tests for OrderedSet. When writting the OrderedSet I came across a few compiler bugs and it took some time. In the end, OrderedSet built on Treap is mostly finished and only a few more tests are needed.

Week 7 (July 10 - July 17)

• Finish the tests about OrderedSet
• Follow up Vector and Heap’s PR

OrderedSet Testing

There are lots of stuff that need testing in orderedSet. I’ve added many tests and fixed some bugs of OrderedSet.

Week 8 (July 17 - July 24)

• Follow up Vector and Heap’s PR
• Finish OrderedMap and its tests
• Fix bugs of OrderdSet

OrderedMap

Progress in the week 7 is kind of unsatisfying so I work harder this week to make up. One week for OrderedMap, it’s functional and tested but I don’t know whether someone will have doubts on the code. I have to admit that the implementation is not that neat, though it works. Also I’ve added lots of tests and tried to cover every procedures.

Week 9 (July 24 - July 31)

• Follow up PRs
• Finish ~70% of UnrolledLinkedList

UnrolledLinkedList

I have been working on UnrolledLinkedList this week. However, I think it’s better to finish the new List interface before UnrolledLinkedList is taken seriously. Lots of repeated work can be saved by the new interface. Unfortunately, there are 3 PRs waiting for review and core developers seem busy.

Week 10 (July 31 - Augest 7)

• Follow up PRs
• Finish UnrolledLinkedList

Week 11 (Augest 7 - Augest 14)

• Follow up PRs
• Migrate tests for UnrolledLinkedList
• Start working on the new List interface

Finally Heap is merged.

The discussion about the new List interface is still not settled. Also there could be some doubts about whether adding UnrolledLinkedList under List. So I think it’s appropriate to open a PR for ULL as a separated package module to avoid blocking. To be honest, migrating tests is a boring and time-consuming job. Anyway it’s always good to get at least some code reviewed and locked into the master.

Week 12 (Augest 14 - Augest 21)

• Discuss the new List interface
• Migrate some tests for the new List interface
• Update OrderedSet to drop implType
• Follow up PRs

Finally OrderedSet is merged. Then I can open the PR for OrderedMap.

Though all the work on the new List interface, the conclusion is that it may be not the best for Chapel. A better solution could be something like the interface in Java, or contrainted generics.

I think this kind of things happens, when a large project like Chapel encounters a big design decision.

Week 13 (Augest 21 - Augest 28)

• Follow up UnrolledLinkedList and UnorderedMap

Final

This is the last week of GSoC as well as my summer vaction. I’m mainly busy with the schoolwork and traveling back to the school.

To sum up

It has been a AMAZING journey contributing to Chapel and the open source. Chapel is not a large community but I still get a lot from the cooperation. Like writting tests, getting invovled in the discussion, they’re the missing part in the school or my own side projects.