[ruby-core:99865] [Ruby master Feature#16989] Sets: need ♥️

[knu@ruby-lang.org]

Issue #16989 has been updated by knu (Akinori MUSHA).


OK, I think it's good for us now to diverge from the original philosophy of Set when I first wrote it and pursue the performance and integrity with other parts of Ruby.  There are many parts in Set where I avoided optimization in order to retain extensibility (like subclassing and stuff), but I'll unlock the bar.

I'm also planning to remove SortedSet and leave it to an external gem because of the partial dependency on rbtree and the fallback implementation which performs quite poorly.

I'm not absolutely sure about introducing literals in the form of `{ a, b, c }`  because I myself is the one who is quite familiar with the shorthand notation introduced in ES6 and would like to have something similar in Ruby. 😆

----------------------------------------
Feature #16989: Sets: need ♥️
https://bugs.ruby-lang.org/issues/16989#change-87392

* Author: marcandre (Marc-Andre Lafortune)
* Status: Assigned
* Priority: Normal
* Assignee: knu (Akinori MUSHA)
----------------------------------------
I am opening a series of feature requests on `Set`, all of them based on this usecase.

The main usecase I have in mind is my recent experience with `RuboCop`. I noticed a big number of frozen arrays being used only to later call `include?` on them. This is `O(n)` instead of `O(1)`.

Trying to convert them to `Set`s causes major compatibility issues, as well as very frustrating situations and some cases that would make them much less efficient.

Because of these incompatibilities, `RuboCop` is in the process of using a custom class based on `Array` with optimized `include?` and `===`. `RuboCop` runs multiple checks on Ruby code. Those checks are called cops. `RuboCop` performance is (IMO) pretty bad and some cops  currently are in `O(n^2)` where n is the size of the code being inspected. Even given these extremely inefficient cops, optimizing the 100+ such arrays (most of which are quite small btw) gave a 5% speed boost.

RuboCop PRs for reference: https://github.com/rubocop-hq/rubocop-ast/pull/29
https://github.com/rubocop-hq/rubocop/pull/8133

My experience tells me that there are many other opportunities to use `Set`s that are missed because `Set`s are not builtin, not known enough and have no shorthand notation.

In this issue I'd like to concentrate the discussion on the following request: `Set`s should be core objects, in the same way that `Complex` were not and are now. Some of the upcoming feature requests would be easier (or only possible) to implement were `Set`s builtin.



-- 
https://bugs.ruby-lang.org/