Самый быстрый способ объединить ReadOnlySpan <char>в C # - PullRequest
Новая
       12

Самый быстрый способ объединить ReadOnlySpan <char>в C #

0 голосов
/ 07 ноября 2018

Какой самый эффективный способ объединения строк, если у меня уже есть только фрагменты ReadOnlySpan?

Упрощенный пример: 

public class Program {
    public string ConcatSpans(string longstring) {
        var span = longstring.AsSpan();
        var sb = new StringBuilder(longstring.Length);
        sb.Append(span.Slice(40, 10));
        sb.Append(span.Slice(30, 10));
        sb.Append(span.Slice(20, 10));
        sb.Append(span.Slice(10, 10));
        sb.Append(span.Slice(0, 10));
        return sb.ToString();
    }

    [Benchmark]
    public void ConcatSpansBenchmark() {
        ConcatSpans("aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeee");
    }

    public static void Main(string[] args) {
        var summary = BenchmarkRunner.Run<Program>();
    }
}

Результаты: 

BenchmarkDotNet=v0.11.2, OS=Windows 10.0.17134.345 (1803/April2018Update/Redstone4)
Intel Core i5-2500K CPU 3.30GHz (Sandy Bridge), 1 CPU, 4 logical and 4 physical cores
.NET Core SDK=2.1.403
  [Host]     : .NET Core 2.1.5 (CoreCLR 4.6.26919.02, CoreFX 4.6.26919.02), 64bit RyuJIT
  DefaultJob : .NET Core 2.1.5 (CoreCLR 4.6.26919.02, CoreFX 4.6.26919.02), 64bit RyuJIT


               Method |     Mean |    Error |   StdDev | Gen 0/1k Op | Gen 1/1k Op | Gen 2/1k Op | Allocated Memory/Op |
--------------------- |---------:|---------:|---------:|------------:|------------:|------------:|--------------------:|
 ConcatSpansBenchmark | 126.6 ns | 1.712 ns | 1.601 ns |      0.0966 |           - |           - |               304 B |

Является ли StringBuilder действительно лучшим, что мы можем сделать? Есть ли способ пойти быстрее, чем это? С еще меньшими ассигнованиями? Ведь StringBuilder сам объект является кучей объектов.

Если бы существовал ref struct StringBuilder, который бы сохранял ссылки только на ReadOnlySpans, а в конечном ToString просто выделил бы один строковый объект?

1 Ответ

0 голосов
/ 07 ноября 2018

Сценарий с несколькими (но известными) входными диапазонами идеален для «предварительного выделения фиктивной строки, а затем делать вид, что строки являются изменяемыми, и перезаписать их перед тем, как открыть их миру». Это выглядит грубовато, но этот трюк очень распространен в коде ввода-вывода при работе со строками (особенно из непрерывных буферов и т. Д.), Поэтому он хорошо понят и поддерживается.

Здесь мы идем (правка: теперь с добавленным «гибридным» методом, который исключает все вызовы Slice(), без необходимости unsafe): 

                        Method |     Mean |     Error |    StdDev |   Median |
------------------------------ |---------:|----------:|----------:|---------:|
          ConcatSpansBenchmark | 97.17 ns | 2.1335 ns | 4.0072 ns | 97.20 ns |
       OverwiteStringBenchmark | 63.34 ns | 1.2914 ns | 2.0854 ns | 62.29 ns |
      UnsafeOverwriteBenchmark | 17.95 ns | 0.3697 ns | 0.3796 ns | 17.80 ns |
 OverwiteStringHybridBenchmark | 53.59 ns | 0.5534 ns | 0.5176 ns | 53.49 ns |

Примечание: все, что связано с MemoryMarshal.*, Unsafe.* или ключевым словом unsafe, явно "Я знаю, что делаю ... все, что взорвалось, вероятно, моя ошибка".

Код: 

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;

public class Program
{
    public string ConcatSpans(string longstring)
    {
        var span = longstring.AsSpan();
        var sb = new StringBuilder(longstring.Length);
        sb.Append(span.Slice(40, 10));
        sb.Append(span.Slice(30, 10));
        sb.Append(span.Slice(20, 10));
        sb.Append(span.Slice(10, 10));
        sb.Append(span.Slice(0, 10));
        return sb.ToString();
    }

    public string OverwiteString(string longstring)
    {
        var span = longstring.AsSpan();
        var s = new string('\0', longstring.Length);
        var writeable = MemoryMarshal.AsMemory(s.AsMemory()).Span;
        span.Slice(40, 10).CopyTo(writeable);
        writeable = writeable.Slice(10);
        span.Slice(30, 10).CopyTo(writeable);
        writeable = writeable.Slice(10);
        span.Slice(20, 10).CopyTo(writeable);
        writeable = writeable.Slice(10);
        span.Slice(10, 10).CopyTo(writeable);
        writeable = writeable.Slice(10);
        span.Slice(0, 10).CopyTo(writeable);
        return s;
    }

    public string OverwiteStringHybrid(string longstring)
    {
        var source = MemoryMarshal.AsBytes(MemoryMarshal.AsMemory(longstring.AsMemory()).Span);
        var s = new string('\0', longstring.Length);
        var target = MemoryMarshal.AsBytes(MemoryMarshal.AsMemory(s.AsMemory()).Span);

        Unsafe.CopyBlock(ref target[0], ref source[40 * sizeof(char)], 10 * sizeof(char));
        Unsafe.CopyBlock(ref target[10], ref source[30 * sizeof(char)], 10 * sizeof(char));
        Unsafe.CopyBlock(ref target[20], ref source[20 * sizeof(char)], 10 * sizeof(char));
        Unsafe.CopyBlock(ref target[30], ref source[10 * sizeof(char)], 10 * sizeof(char));
        Unsafe.CopyBlock(ref target[40], ref source[0], 10 * sizeof(char));

        return s;
    }

    public unsafe string UnsafeOverwrite(string longstring)
    {
        var s = new string('\0', longstring.Length);
        fixed (char* source = longstring)
        fixed (char* target = s)
        {
            Unsafe.CopyBlock(target, source + 40, 10 * sizeof(char));
            Unsafe.CopyBlock(target + 10, source + 30, 10 * sizeof(char));
            Unsafe.CopyBlock(target + 20, source + 20, 10 * sizeof(char));
            Unsafe.CopyBlock(target + 30, source + 10, 10 * sizeof(char));
            Unsafe.CopyBlock(target + 40, source, 10 * sizeof(char));
        }
        return s;
    }

    [Benchmark]
    public void ConcatSpansBenchmark()
        => ConcatSpans("aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeee");
    [Benchmark]
    public void OverwiteStringBenchmark()
    => OverwiteString("aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeee");
    [Benchmark]
    public void UnsafeOverwriteBenchmark()
    => UnsafeOverwrite("aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeee");

    [Benchmark]
    public void OverwiteStringHybridBenchmark()
    => OverwiteStringHybrid("aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeee");

    public static void Main(string[] args)
        => BenchmarkRunner.Run<Program>();
}

Примечание: в общем случае - получить unsafe код из среза:

с C # 7.3: 

fixed(char* p = theSpan)
{
    ...
}

в противном случае: 

fixed(char* p = &MemoryMarshal.GetReference(theSpan))
{

}
...