Thanks a lot for this advice, Steve! I think it is the best solution so far. Will update the performance results once extra experiments are done later.
The experimental result shows the words-based approach, as advised by @scanon , appears to be the most satisfactory solution for the default implementation so far. I had the PR updated.
While it is good enough to be the default implementation, when it comes to some custom integer type who doesn't have a native 2's complement representation (e.g., BigInt), it incurs overheads to query the words. It would be more efficient to operate directly on its native representation when possible. On BigInt, for example, _isPowerOfTwo_BigInt is more performant than _isPowerOfTwo_words as per the results in Table 3.
As a result, I think it worth to reserver the future flexibility by making isPower(of:) as a protocol requirement.
2 Likes
How much of this is due to the limitations of the method, and how much is due to no one having paid any attention to how efficient the .words property on that BigInt is, though? (Hint: no one has paid any attention to how efficient it is).
3 Likes
As much as the fact of .words' inefficiency, for whatever reason. The fact may be a result of lack of attention; it may also be a result of the trade-off strategy applied deliberately.
In the case of BigInt, I think it is implemented in such a way that the performance of arithmetic operations is prioritized over the bitwise operations. Of course, we can try to optimize the .words property. However, as long as its native representation is not 2's complement representation, querying .words is always a kind of indirect approach where overheads are introduced. So we'd rather directly access its native representation.
Another (extreme) case I can figure out is something like CompressedInt, which is designed for space efficiency. The bits of the corresponding 2's complement representation are encoded in its native (compressed) representation somehow. For example, consider the bits 100...a_large_amount_of...000, and let's say its native representation is something like 1*1,some_amount*0, which is space efficient. It should be easier to identify if it is a power of 2 directly, rather than transform it to .words and then perform the checking.
Anyway, I am not questioning the benefits of the words-based approach. Instead, we all love it and it is the best solution for the default implementation so far. I am just not confident whether we'd make the public API a protocol requirement. What I am trying to express is such limitation should be considered when making the decision. It seems some senior community members (like Jordan and you as Apple's staff) prefer just making the API an extension method, and your opinions are very important.
I don't have a clear preference yet, FWIW. Rather, the bar to making things protocol requirements (especially on heavily-used protocols like BinaryInteger) is somewhat higher than making them extensions, so I want to make sure that we really do need it to be a protocol requirement before doing so.
2 Likes
I had the PR updated. Let's make it an extension method at this point to minimize the interface complexity of the protocol. If there are serious performance troubles observed in real world applications, we can then decide how to fix it, FWIW.
Looks like we have converged at this point. Let's wait for a while and if there isn't any essential objection, I am going to write a proposal then.
1 Like
Be sure to discuss and come up with some good use-cases for the operations.
Will do. Thanks Steve!
I composed a proposal as a PR to swift-evolution. Thanks to everyone's attention and feedbacks. It couldn't have gone this far without your help.