5
\$\begingroup\$

Based upon a question from Stack Overflow, I wanted to expand on the answer I wrote and define a solution that would support ordering the strings (after processing).

So this starts off with a basic struct, and you can guess what it's going to do:

public struct Line<T>
{
    public int Order { get; set; }
    public T Value { get; set; }
}

I am using it to track a Value and the order the value goes in.

Next, we have to have some way of taking a UTF-8 array and determining, at any given index, where does that character start?

public static int GetCharStart(ref byte[] arr, int index)
{
    if (index > arr.Length)
    {
        index = arr.Length - 1;
    }

    return (arr[index] & 0xC0) == 0x80 ? GetCharStart(ref arr, index - 1) : index;
}

Now I used ref here to help performance: it doesn't modify the array so there's no need to pass anything special around, just reference it as a "pointer". (Though, in reality, ref here is superfluous as the array is a reference already, but it's good to be explicit when possible.)

Next, we need to take a byte[] and get a section from it, so I wrote a helper-method:

public static byte[] GetSection(ref byte[] array, int start, int end)
{
    var result = new byte[end - start];
    for (var i = 0; i < result.Length; i++)
    {
        result[i] = array[i + start];
    }
    return result;
}

Then, finally, we need to be able to return the byte[] array sections, one-by-one, to pass to our parsing. This uses IEnumerable and yield return to be lazy (I'm a lazy dev, so I may-as-well write lazy code).

public static IEnumerable<Line<byte[]>> GetByteSections(byte[] utf8Array, int sectionCount)
{
    var sectionStart = 0;
    var sectionEnd = 0;
    var sectionSize = (int)Math.Ceiling((double)utf8Array.Length / sectionCount);

    for (var i = 0; i < sectionCount; i++)
    {
        if (i == (sectionCount - 1))
        {
            var lengthRem = utf8Array.Length - i * sectionSize;
            sectionEnd = GetCharStart(ref utf8Array, i * sectionSize);
            yield return new Line<byte[]> { Order = i, Value = GetSection(ref utf8Array, sectionStart, sectionEnd) };
            sectionStart = sectionEnd;
            sectionEnd = utf8Array.Length;
            yield return new Line<byte[]> { Order = i + 1, Value = GetSection(ref utf8Array, sectionStart, sectionEnd) };
        }
        else
        {
            sectionEnd = GetCharStart(ref utf8Array, i * sectionSize);
            yield return new Line<byte[]> { Order = i, Value = GetSection(ref utf8Array, sectionStart, sectionEnd) };
            sectionStart = sectionEnd;
        }
    }
}

The if block in this just prevents the last line from being ~2x the size of previous lines (which can be the case if there are high-code-point UNICODE glyphs.

Finally, I assemble the entire result in a GetStringParallel method:

public static string GetStringParallel(byte[] utf8ByteArray, int sections = 10, int maxDegreesOfParallelism = 1)
{
    var results = new ConcurrentBag<Line<string>>();
    Parallel.ForEach(GetByteSections(utf8ByteArray, sections),
                     new ParallelOptions { MaxDegreeOfParallelism = maxDegreesOfParallelism },
                     x => results.Add(new Line<string> { Order = x.Order, Value = Encoding.UTF8.GetString(x.Value) }));
    return string.Join("", results.OrderBy(x => x.Order).Select(x => x.Value));
}

This does the parallelization, handles parsing the results, and joins everything together.


Now, ignoring the lack of a class that does this work, I'd love any suggestions. It would be a class in the real-world, and I understand that, I just didn't make it a class because (again) I'm lazy. Also note that this is probably a hell-of-a-lot-slower than the built-in decoding, and I make no claims for either case. This is just a really cool experiment that also demonstrates the self-synchronicity of UTF-8.

Test case:

var sourceText = "Some test 平仮名, ひらがな string that should be decoded in parallel, this demonstrates that we work flawlessly with Parallel.ForEach. The only downside to using `Parallel.ForEach` the way I demonstrate is that it doesn't take order into account, but oh-well. We can continue to increase the length of this string to demonstrate that the last section is usually about double the size of the other sections, we could fix that if we really wanted to. In fact, with a small modification it does so, we just have to remember that we'll end up with `sectionCount + 1` results.";
var source = Encoding.UTF8.GetBytes(sourceText);
Console.WriteLine("Source:");
Console.WriteLine(sourceText);

Console.WriteLine();
Console.WriteLine("Assemble the result:");
Console.WriteLine(GetStringParallel(source, 20, 4));
Console.ReadLine();

Result:

Source:
Some test ???, ???? string that should be decoded in parallel, this demonstrates that we work flawlessly with Parallel.ForEach. The only downside to using `Parallel.ForEach` the way I demonstrate is that it doesn't take order into account, but oh-well. We can continue to increase the length of this string to demonstrate that the last section is usually about double the size of the other sections, we could fix that if we really wanted to. In fact, with a small modification it does so, we just have to remember that we'll end up with `sectionCount + 1` results.

Assemble the result:
Some test ???, ???? string that should be decoded in parallel, this demonstrates that we work flawlessly with Parallel.ForEach. The only downside to using `Parallel.ForEach` the way I demonstrate is that it doesn't take order into account, but oh-well. We can continue to increase the length of this string to demonstrate that the last section is usually about double the size of the other sections, we could fix that if we really wanted to. In fact, with a small modification it does so, we just have to remember that we'll end up with `sectionCount + 1` results.
\$\endgroup\$
4
\$\begingroup\$

Well, using ref as a way to improve performance doesn't sit well with me, as it kind of violates the contract. I doubt the gains (if any) justify it. Micro-optimizations should probably begin with replacing recursion with a loop.

Another thing to optimize is your partitioning logic: Encoding.GetString has an overload that takes start index and count. If you use it instead, you can avoid new byte[end - start]; call and subsequent copying. If you do need a copy for some reason, then you should use Buffer.BlockCopy method. Element-by-element copying in for loop is considerably slower for larger arrays.

GetByteSections is a bit counter-intuitive as it apparently returns sectionCount + 1 items. That's not what I would expect. There is also a little bit of copy-paste in for loop's body, that can probably be avoided.

You can use Line<string>[] instead of ConcurrentBag and put results in correct order straight away using indexer: results[resultLine.Order] = resultLine;. No additional synchronization is needed as long as Order values are unique, which seems to be the case.

Everything else looks alright to me.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.