Collection library in Swift: GSoC2019


(Keita Nonaka) #1

This is my original proposal for Google Summer of Code 2019.
I'd happy if this proposal interests you. Please feel free to comment about this proposal.
Plus, I need mentor(s) start this proposal as a project, so I'm glad if you would be a mentor.

I'd like to implement basic collections, such as stack, queue, binary tree etc. because when I tried to use stack in swift, I couldn't use it. I know programmers can make own collections, but I think swift should have own collection library like Java or other languages.

Thank you

(Karoy Lorentey) #2

Hello @Gumichocopengin8,

We are definitely interested in adding new collection types to the standard library. Some of these would make great GSoC projects.

Of the collections you listed, I particularly like stack and queue. A double-ended queue type backed by a ring buffer would cover both of these, and it would have clear engineering applications. (It would also be a useful stepping stone towards tree-based collections -- in the form of in-memory B-trees, whose nodes could be represented by ring buffers.)

This wouldn't be an easy project -- I would put it somewhere between medium and hard. While the actual algorithms involved are relatively straightforward (I myself have a prototype dating back to Swift 2), successfully integrating a double-ended queue type into the standard library has some interesting challenges. It requires careful study of the API-level functionality provided by Collection protocols, as well as deep knowledge of the stdlib's internals. All functionality needs to be fully tested by newly written unit tests in the stdlib's test suite, including exhaustive tests covering baseline collection behavior. New benchmarks need to be written to allow us to track the performance of the implementation across releases. And, of course, the new public APIs must be discussed on the evolution forums, concerns raised by peers need to be addressed, culminating in a proposal that (hopefully) passes review and is accepted by the Core Team.

All this needs a level of determination to see things through, even if the lists of tasks seems daunting at first. That said, I do believe implementing a standard deque would be possible within the constraints of a GSoC project, and I'd be happy to mentor it.

(If you'd prefer a less high-profile, lower risk project, check out the project idea for "Scalability benchmarks for the Swift Standard Library"!)

(Keita Nonaka) #3

Hello @lorentey,

Thank you for being interested in my proposal.
I understand the difficulty of the project, but I am still interested in doing the project because I want to use these collections in my iOS applications and learn swift deeply.
What am I supposed to do to write a proposal for GSoC to get knowledge of stdlib and so on?

Thank you

(Karoy Lorentey) #4

That's good motivation!

I believe the first task for a prospective GSoC student is to come up with a convincing project proposal.

But before we get to that, if I were you, I would want to make sure I'd enjoy working with the stdlib. A GSoC project takes a lot of commitment. So get some practice -- download and compile Swift, and start breaking things! Some ideas:

  • Can you make sense of the code? (The stdlib is written in a somewhat unusual Swift dialect, and it may take some getting used to. It deals a lot with low-level builtins and even some language-level constructs that don't typically occur in regular Swift development. Not to mention gyb!)
  • Try adding a new public type, or some extension method -- figure out what the editing/recompiling experience is like. (You'd probably spend a good chunk of time doing it during the project.)
  • Try running the test suite; can you figure out where/how it is implemented? Find and look through the tests we run for collection types. Is it easy to make sense of them? Think about how a new Collection type like a deque could be integrated into the existing tests. What tests can we reuse? What new tests will we need to add?
  • Make some changes to an existing stdlib method that will obviously break it; does it cause a test failure in the test suite? (If not, please submit a PR with a new test!) What does a test failure look like? Try debugging it while pretending you don't know the cause.
  • If you come across a bug you're able to fix, submit a PR for it! This will give you a feel for what our review process is like.
  • Select some stdlib algorithm and find its benchmark(s). Try to optimize the algorithm by tweaking its code, and see if it improves benchmark results. (Submit a PR if so!) If you don't find benchmarks for the algorithm you selected, try writing a PR to add one.
  • For a more esoteric task: can you figure out how the debugger interprets Swift's collections? It is able to print Arrays, Dictionaries etc without actually running Swift code in the target process. What would it take to add support for a new stdlib type?

(Feel free to ask me to review any PRs you might submit. If you hit a stumbling block, let me know -- I can help (or we can figure it out together), and we may want to add documentation or make changes to smooth it out for the next person. These things make great starter PRs, too.)

Obviously this isn't part of the proposal process, but these experiments will probably tell you whether you'd enjoy spending a few months (or more!) on our codebase, and they will give you a great start on scoping out the potential deliverables in the proposal. As I said, implementing a collection type is just a start -- integrating it into the standard library takes a lot more effort! You need to be aware of the areas that need to be touched, and you need to figure out how much you can reasonably achieve in the time available. Then you need to convincingly communicate this in the proposal.

It would be impressive if the proposal included a draft of the public API for the type you'd like to implement -- just as if you were writing the Motivation and Design Details parts of a Swift Evolution proposal. By doing this well, you'd demonstrate proficiency with Swift's conventions, and a sense of good taste in API design. Naturally the interface you propose would be just a rough draft -- we'd refine it together during the project, and it will evolve even further when we pitch it on the evolution forums.

Please don't hesitate to write; I'm happy to answer questions and to discuss ideas.

(Keita Nonaka) #5

Thank you very much for your advice!

I pulled swift code from GitHub, so I'll practice with the idea you gave me.

Please don't hesitate to write; I'm happy to answer questions and to discuss ideas.

I appreciate it. I will definitely ask you some questions.

Again, thank you very much.
I am really looking forward to contributing to swift with you.
I'll email you about me soon.

(Shreyas Papinwar) #6

Hey @lorentey ,

The idea of adding a stack, queue, circular linked list, 2-way linked list in collection library is great.
If possible I would also like to work on this in GSoC 2019. Is it possible for 2 people work on the same project?

Please help me proceed.

Thank You

(Karoy Lorentey) #7

As I understand it, projects are limited to a single student. There is a limited number of students accepted each year, and having more than one student working on a project would be excessive. It also makes it difficult to evaluate each student on their own merits, and potentially changes the one-to-one mentor--mentee dynamic into a team environment.

However, I believe it's okay to have students propose similar projects. Obviously, competing like that does add another level of difficulty -- so it's worth exploring other potential projects before settling on this. However, if you're confident you'd be the right person to work on something, then by all means, go for it!