Phobos' std.conv.to-conversion from enum to string doesn't scale beyond hundreds of enumerators

[Stefan Koch]

On Friday, 22 June 2018 at 00:50:05 UTC, Steven Schveighoffer 
wrote:
> On 6/21/18 6:46 PM, Per Nordlöw wrote:
>> I've discovered the annoying fact that std.conv.to doesn't 
>> scale for enum to string conversion when the enum has hundreds 
>> of members. This because of a call to `NoDuplicates` which has 
>> (at least) O(n*log(n) time and space complexity.
>> 
>> So I've come up with
>> 
>> 
>> /** Faster implementation of `std.conv.to`.
>>   */
>> string toString(T)(T value) @safe pure nothrow @nogc
>> if (is(T == enum))
>> {
>>      final switch (value)
>>      {
>>          static foreach (member; __traits(allMembers, T))
>>          {
>>          case __traits(getMember, T, member):
>>              return member;
>>          }
>>      }
>> }
>> 
>> ///
>> @safe pure nothrow @nogc unittest
>> {
>>      enum E { unknown, x, y, z, }
>>      assert(E.x.toString == "x");
>>      assert(E.y.toString == "y");
>>      assert(E.z.toString == "z");
>> }
>> 
>> 
>> The question know is: How do I make this support enums with 
>> enumerator aliases without needing to call `NoDuplicates`?
>
> You can't. That's why it's in there. And I can't think of a 
> better algorithm than O(nlgn). That's what it would cost to 
> sort anyway.
>
> The sucky thing is, the compiler is *already* doing a sort on 
> the items in the switch, and *already* doing the duplicate 
> check. It would be cool to be able to leverage this mechanism 
> to avoid the library solution, but I don't know how we can do 
> that, as the semantics for switch are well defined, and there's 
> no other way to hook this builtin functionality.
>
> One thing that may be worthwhile is checking to see if a CTFE 
> solution is better than a template solution. In other words:
>
> string[] dedup(string[] identifiers) { ... }
>
> enum items = dedup(__traits(allMembers, T));
>
> static foreach(member; items) ...
>
> Just avoiding all the template symbol generation may make it 
> worth it, even if the dedup function is O(n^2) complexity.
>
> -Steve


I do have my own ctfe utils for this
{https://forum.dlang.org/post/bfnwstkafhfgihavtzsz@forum.dlang.org}, however without dedup (because I'd rather be alerted when it happens) what you have to do is to sort the enum values.
(I'd suggest a non-recursive mergesort.)
However if there are no duplicates there's no need to 
deduplicate, the reason it is deduplicated it because the 
switch_statement forbids duplicates.

I may add that this performs very well with newCTFE I don't know 
about the old engine, but I'd assume even there it's faster.