Yujia Qiao
Huazhong University of Science and Technology
Email: [email protected]
Organization: CHAPEL
Project: Sequential Data Structures
This project is aimed at adding various useful data structures missing in Chapel, including Heap, Treap, Vector, UnrolledLinkedList.
A heap is a specialized tree-based data structure that supports extracting the maximal or the minimal element quickly, which can serve as a priority queue.
Status: Merged into standard modules via chapel#15997.
Documentation: Heap Module
Vector called here is a list storing elements in contiguous memory area. Note that Chapel already has List but it's slower to index a List.
Status: Merged into /test/library via chapel#16048
Documentation: In code. No public web page available.
An orderedSet is a collection of unique and ordered elements, thus supporting more operations like lowerBound than Set.
Status: Merged into package modules via chapel#16124
Documentation: OrderedSet Module
An orderedMap is a container that stores key-value associations. OrderedSet supports searching for a certain key, insertion, and deletion in O(logN). The main difference between Map is that it has a different time complexity and space usage.
Status: Pull request open
An unrolled linked list is a linked list of small arrays, all of the same size where each is so small that the insertion or deletion is fast and quick, but large enough to fill the cache line.
Status: Pull request open
- Designed and implemented various modules
- Implementation
- Documentation
- Unit Tests
- Discussed and implemented a prototype for parameterizing different structures in one type.
- Reported bugs encountered while developing
- Notes on DS
~5k lines merged and ~3k lines pending
- Get open PR merged
- Add performance tests and fix anything that impacts performance unexpectedly.
- Move Vector out of
test, possibly when constraint generics is available in Chapel.