I’m very excited to get selected for GSoC 2020 / Chapel / Sequential Data Structures. This post is to document the journey.
- Setup Blog
- Make related issues on GitHub
- Look into
List.chpland compare with
- Look into
domainand decide whether to add
*Mapinto to-do list.
- Find about different data structures in other languages
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.
- Go through the Buffers module and check out the source
- Update issues with latest finding
- Come back to the source of List.chpl
This week most of the work is reading, updating issues, and discussing about the interfaces in related issues. Coding period is coming!
- Send e-mails about Heap and Vector for feedbacks
- Change from
- 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
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.
- Complete tests for Heap
- About half of Implementation of 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.
- Complete tests for Vector
- Complete Implementation of Vector
- Make a prototype of the unified interface with different implementations.
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.
- Discuss OrderedSet, OrderedMap
- Discuss the unified interface more thoroughly
- Discuss the location of the project outcome
- Make Vector more robust
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
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.
- Complete a basic implementation of 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.