Draft Proposal - Expanding the Swift Overlay [GSoC 2023] [C++ and Swift Interoperability]

Hey guys!

So following up my recent forums post regarding Expanding Swift Overlay and understanding it's practicality I suppose I have an idea for which I can make a good proposal.

Here's what I think can be a potential way of expanding the overlay, so as @egor.zhdan explained, std::string and it's use case from this snippet, I think we can extend this to the following STL containers which are quite useful, (some of them might have already been implemented):

  • std::priority_queue -> Quite useful container due to it's heap-based implementation.
  • std::deque -> Allows quick front() and back() operations when needed.
  • std::list -> Doubly Linked list based structure (more info below).
  • std::map -> Guaranteed quick access time (~log(n))
  • std::multiset -> Similar to set, allowing duplicate elements.
  • std::unordered_map
  • std::unordered_set
    (there might be some more useful ones which I may have missed out.)

The above containers are widely used, and quite useful in many ways, each of them have their own internal implementations of doubling linked list, pointers, hash tables, heaps, etc. Although 'expanding the overlay' is the primary goal of the project, I do have some ideas which I suppose would we quite beneficial, for example, most of them are quite common to use, often std::list can be quite useful to quickly insert, delete and modify elements in a certain array type (or equivalent Swift type), we can potentially also add a new functionality specifically to this type of container, regarding access of elements, as that's the only downside of std::list, which can be fixed by using a map of this kind std::unordered_map<std::iterator, <type>>, in that way, if the developer (or user) knows the STL iterator, we can get constant access time (O(1)).

Also particularly regarding the last 2 containers (i.e. unordered_*), I have a nice idea of improving the existing hash table issues and collisions in C++ as there are definitely cases where there's a significant slow down and could lead to long waiting times making the developer think it might be due to some other problems, while the typical std::map has it's implementation based on Red-Black trees delivering O(log(N)) time complexity, often languages do offer a quick access time and low storage hash tables. So while 'expanding the overlay' in Swift, we can make some changes or even offer a way for the user to use a custom hash table of their own.

We can also add std::tuple, for supporting multiple element types, compared to std::pair, making it more flexible to use in Swift.

I think this gives a brief idea of my thoughts and understanding of adding features and improving the overlay!

Request your view point, changes and recommendations @egor.zhdan!


1 Like

Hi Rajveer,

Changing the way C++ standard containers operate is out of scope of this project. We're only aiming to improve the usability of these types from Swift, not change the implementation of std::map or std::set.

Can you think of any improvements that you could apply to the C++ types you mentioned on the Swift side? This could be any change that makes it easier for Swift developers to work with a C++ library that exposes any of those types (e.g. provides a public method that returns std::set).

@egor.zhdan I recently noticed that CxxSet protocol doesn’t yet include an insert method and that you also can’t iterate over its elements (like you can with a CxxSequence). Are there technical limitations for this or are things coming to a point where these can be added?

Hey Egor,

Thanks for your review, will think of more such improvements if any on the Swift side for ease of use!

Maybe you could clarify Puyon's question as well, as in that case, there are several other methods which apply to such containers, which might need to be implemented too!

This is definitely something we'd like to have implemented in the future, possibly as part of the GSoC project!

We don't provide automatic conformances to CxxSequence and we also don't conform stdlib types to CxxSequence for performance reasons: CxxSequence.makeIterator() makes a copy of the original C++ container because CxxIterator needs to take ownership over the container to prevent it from being destroyed before the last use. This will be possible to implement efficiently in the future, but at the moment we don't want clients to suffer from hidden performance cost.

1 Like

Oh very nice, I was hoping for at least something like makeIterator. I think some folks on our end would be interested in getting insert working.

1 Like

In that case, there are various other methods many different containers similar to the 'insert' in the CxxSet protocol, I think we can possibly include in the GSoC project too!

1 Like