5
\$\begingroup\$

Some people are telling me that using string.Split is very inefficient since it creates a lot of arrays in the heap. So, what are the alternatives if its real?

The challenge? Taking a large string that values are delimited by ',' and rows separated by ',\r\n' and trying to create class instances with no string.split!!!

My first thought was to use string.Substring and compare it against string.Split. I don't know if my Substring implementation is the most efficient but at first, string.Split seems to be at least 3x faster... 

public class SubstringVsSplitPerformanceTests
{
    private const string Data = @"2018-05-18 11:43:18.180193,187.6685,25,8864490,187.6600,187.6700,12622,O,19,87,\r\n2018-05-18 11:43:17.443529,187.6650,80,8864465,187.6600,187.6700,12621,O,19,87,\r\n2018-05-18 11:43:16.264124,187.6600,5,8864385,187.6600,187.6700,1994,O,24,87,\r\n2018-05-18 11:43:15.408445,187.6700,100,8864380,187.6600,187.6700,5778,C,11,3D,\r\n2018-05-18 11:43:15.407881,187.6700,6,8864280,187.6600,187.6700,17077,O,5,87,\r\n2018-05-18 11:43:12.223185,187.6800,100,8864274,187.6700,187.6800,5777,C,11,3D,\r\n2018-05-18 11:43:12.222945,187.6800,100,8864174,187.6700,187.6800,17076,C,5,3D,\r\n2018-05-18 11:43:10.591804,187.6800,86,8864074,187.6800,187.6900,17075,O,5,87,\r\n2018-05-18 11:43:10.589834,187.6900,100,8863988,187.6800,187.6900,17074,C,5,01,\r\n2018-05-18 11:43:10.587481,187.6800,44,8863888,187.6800,187.6900,12620,O,19,87,\r\n2018-05-18 11:43:10.584121,187.7000,40,8863844,187.6800,187.6900,6254,O,18,87,\r\n2018-05-18 11:43:10.583864,187.7000,22,8863804,187.6800,187.6900,12619,O,19,87,\r\n2018-05-18 11:43:10.583805,187.6800,100,8863782,187.6800,187.6900,17073,C,5,01,\r\n2018-05-18 11:43:10.583786,187.6800,200,8863682,187.6800,187.6900,17072,C,5,01,\r\n2018-05-18 11:43:10.582243,187.7000,40,8863482,187.6800,187.6900,6253,O,18,87,\r\n2018-05-18 11:43:10.582190,187.6800,50,8863442,187.6800,187.6900,17071,O,5,87,\r\n2018-05-18 11:43:10.581987,187.7000,100,8863392,187.6800,187.6900,6252,C,18,3D,\r\n2018-05-18 11:43:10.581908,187.6800,100,8863292,187.6800,187.6900,17070,C,5,3D,\r\n2018-05-18 11:43:10.581888,187.6800,100,8863192,187.6800,187.6900,17069,C,5,3D,\r\n2018-05-18 11:43:10.580283,187.6800,50,8863092,187.6800,187.6900,17068,O,5,87,\r\n2018-05-18 11:43:10.580153,187.6800,50,8863042,187.6800,187.6900,17067,O,5,87,\r\n2018-05-18 11:43:10.579256,187.7000,100,8862992,187.6800,187.6900,6251,C,18,01,\r\n2018-05-18 11:43:10.579132,187.6800,100,8862892,187.6800,187.6900,17066,C,5,01,\r\n2018-05-18 11:43:10.579068,187.6800,100,8862792,187.6800,187.6900,17065,C,5,01,\r\n2018-05-18 11:43:10.578987,187.7000,100,8862692,187.6800,187.6900,6320,C,26,3D,\r\n2018-05-18 11:43:10.578867,187.6800,200,8862592,187.6800,187.6900,17064,C,5,3D,\r\n2018-05-18 11:43:10.578566,187.7000,100,8862392,187.6800,187.6900,1368,C,7,3D,\r\n2018-05-18 11:43:10.578300,187.6800,50,8862292,187.6800,187.7000,17063,O,5,87,\r\n2018-05-18 11:43:10.578241,187.6800,100,8862242,187.6800,187.7000,17062,C,5,3D,\r\n2018-05-18 11:43:10.577560,187.6900,200,8862142,187.6800,187.7000,1367,C,7,3D,\r\n2018-05-18 11:43:10.577275,187.6900,100,8861942,187.6800,187.7000,6250,C,18,3D,\r\n2018-05-18 11:43:10.577264,187.6900,100,8861842,187.6800,187.7000,6249,C,18,3D,\r\n2018-05-18 11:43:10.577197,187.6800,1,8861742,187.6800,187.7000,6248,O,18,3D87,\r\n2018-05-18 11:43:10.577118,187.6800,100,8861741,187.6800,187.7000,6247,C,18,3D,\r\n2018-05-18 11:43:10.577013,187.6800,100,8861641,187.6800,187.7000,17061,C,5,3D,\r\n2018-05-18 11:43:10.576904,187.6800,100,8861541,187.6800,187.7000,17060,C,5,3D,\r\n2018-05-18 11:43:10.576819,187.6800,100,8861441,187.6800,187.7000,17059,C,5,01,\r\n2018-05-18 11:43:08.646771,187.6800,8,8861341,187.6700,187.6800,1993,O,24,87,\r\n2018-05-18 11:43:08.194124,187.6800,100,8861333,187.6700,187.6800,6246,C,18,3D,\r\n2018-05-18 11:43:08.194122,187.6800,100,8861233,187.6700,187.6800,17058,C,5,3D,\r\n2018-05-18 11:43:08.193421,187.6900,100,8861133,187.6700,187.6800,6245,C,18,01,\r\n2018-05-18 11:43:08.193296,187.6900,100,8861033,187.6700,187.6800,6319,C,26,3D,\r\n2018-05-18 11:43:08.190427,187.6900,100,8860933,187.6700,187.6800,12618,C,19,01,\r\n2018-05-18 11:43:08.188842,187.6800,43,8860833,187.6700,187.6800,6318,O,26,3D87,\r\n2018-05-18 11:43:08.188701,187.6800,100,8860790,187.6700,187.6800,5776,C,11,3D,\r\n2018-05-18 11:43:07.085388,187.6800,100,8860690,187.6700,187.6800,1366,C,7,01,\r\n2018-05-18 11:43:07.079173,187.6750,500,8860590,187.6700,187.6800,12617,C,19,01,\r\n2018-05-18 11:43:07.076408,187.6700,15,8860090,187.6700,187.6800,6244,O,18,87,\r\n2018-05-18 11:43:07.076398,187.6700,300,8860075,187.6700,187.6800,17057,C,5,01,\r\n2018-05-18 11:43:07.076394,187.6700,100,8859775,187.6700,187.6800,17056,C,5,01,\r\n2018-05-18 11:43:07.071866,187.6700,100,8859675,187.6700,187.6800,6317,C,26,3D,\r\n2018-05-18 11:43:07.071847,187.6700,100,8859575,187.6700,187.6800,6316,C,26,3D,\r\n2018-05-18 11:43:07.071471,187.6700,100,8859475,187.6700,187.6800,17055,C,5,01,\r\n2018-05-18 11:43:06.058356,187.6799,20,8859375,187.6700,187.6800,12616,O,19,87,\r\n2018-05-18 11:43:04.841552,187.6700,8,8859355,187.6700,187.6800,1365,O,7,3D87,\r\n2018-05-18 11:43:04.029085,187.6700,100,8859347,187.6700,187.6800,12615,C,19,01,\r\n2018-05-18 11:43:03.143338,187.6800,300,8859247,187.6700,187.6800,12614,C,19,01,\r\n2018-05-18 11:43:03.143044,187.6700,900,8858947,187.6700,187.6800,5775,C,11,01,\r\n2018-05-18 11:43:03.142702,187.6700,100,8858047,187.6700,187.6800,409,C,80,01,\r\n2018-05-18 11:43:03.142646,187.6700,50,8857947,187.6700,187.6800,17054,O,5,87,\r\n2018-05-18 11:43:03.142642,187.6700,100,8857897,187.6700,187.6800,17053,C,5,01,\r\n2018-05-18 11:43:03.141786,187.6800,100,8857797,187.6700,187.6800,17052,C,5,01,\r\n2018-05-18 11:43:03.141783,187.6800,100,8857697,187.6700,187.6800,17051,C,5,01,\r\n2018-05-18 11:43:03.141779,187.6800,100,8857597,187.6700,187.6800,17050,C,5,01,\r\n2018-05-18 11:43:03.141775,187.6900,100,8857497,187.6700,187.6800,17049,C,5,01,\r\n2018-05-18 11:43:03.141291,187.6800,100,8857397,187.6700,187.6800,6315,C,26,3D,\r\n2018-05-18 11:43:03.141267,187.6800,100,8857297,187.6700,187.6800,6243,C,18,3D,\r\n2018-05-18 11:43:03.141258,187.6800,100,8857197,187.6700,187.6800,6242,C,18,3D,\r\n2018-05-18 11:43:03.141189,187.6800,100,8857097,187.6700,187.6800,17048,C,5,3D,\r\n2018-05-18 11:43:03.141185,187.6800,100,8856997,187.6700,187.6800,17047,C,5,3D,\r\n2018-05-18 11:43:03.141183,187.6800,100,8856897,187.6700,187.6800,17046,C,5,3D,\r\n2018-05-18 11:43:03.141180,187.6800,100,8856797,187.6700,187.6800,17045,C,5,3D,\r\n2018-05-18 11:43:03.140603,187.6800,100,8856697,187.6700,187.6800,17044,C,5,3D,\r\n2018-05-18 11:43:03.140600,187.6800,100,8856597,187.6700,187.6800,17043,C,5,3D,\r\n2018-05-18 11:43:03.140596,187.6800,100,8856497,187.6700,187.6800,17042,C,5,3D,\r\n2018-05-18 11:43:02.876488,187.6701,100,8856397,187.6800,187.6900,12613,O,19,3E05,\r\n2018-05-18 11:43:02.386256,187.6900,100,8856297,187.6800,187.6900,12612,C,19,01,\r\n2018-05-18 11:43:02.385060,187.6900,100,8856197,187.6800,187.6900,1364,C,7,3D,\r\n2018-05-18 11:43:02.384873,187.6900,14,8856097,187.6800,187.6900,6314,O,26,3D87,\r\n2018-05-18 11:43:02.384667,187.6900,100,8856083,187.6800,187.6900,17041,C,5,3D,\r\n2018-05-18 11:43:02.192495,187.6900,100,8855983,187.6900,187.7000,12611,C,19,01,\r\n2018-05-18 11:43:02.015327,187.7000,100,8855883,187.6900,187.7000,6241,C,18,01,\r\n2018-05-18 11:43:02.003358,187.6900,100,8855783,187.6900,187.7000,12610,C,19,01,\r\n2018-05-18 11:43:01.995383,187.6900,100,8855683,187.6900,187.7000,12609,C,19,01,\r\n2018-05-18 11:43:01.994896,187.6900,100,8855583,187.6900,187.7000,1934,C,153,01,\r\n2018-05-18 11:43:01.993744,187.6900,100,8855483,187.6900,187.7000,6313,C,26,3D,\r\n2018-05-18 11:43:01.993726,187.6900,100,8855383,187.6900,187.7000,6240,C,18,3D,\r\n2018-05-18 11:43:01.993374,187.6900,100,8855283,187.6900,187.7000,17040,C,5,3D,\r\n2018-05-18 11:43:01.993369,187.6900,100,8855183,187.6900,187.7000,17039,C,5,3D,\r\n2018-05-18 11:43:00.821292,187.6600,100,8855083,187.6700,187.6900,12608,C,19,01,\r\n2018-05-18 11:43:00.820462,187.6700,100,8854983,187.6700,187.6900,6312,C,26,01,\r\n2018-05-18 11:43:00.820195,187.6700,100,8854883,187.6700,187.6900,293,C,25,01,\r\n2018-05-18 11:42:59.885242,187.6600,100,8854783,187.6500,187.6600,1363,C,7,3D,\r\n2018-05-18 11:42:59.884840,187.6600,100,8854683,187.6500,187.6600,6311,C,26,3D,\r\n2018-05-18 11:42:59.884826,187.6600,100,8854583,187.6500,187.6600,6239,C,18,3D,\r\n2018-05-18 11:42:59.884755,187.6600,100,8854483,187.6500,187.6600,17038,C,5,3D,\r\n2018-05-18 11:42:59.884751,187.6600,100,8854383,187.6500,187.6600,17037,C,5,3D,\r\n2018-05-18 11:42:59.461521,187.6700,90,8854283,187.6600,187.6700,5774,O,11,3D87,\r\n2018-05-18 11:42:59.461007,187.6700,100,8854193,187.6600,187.6700,17036,C,5,3D,\r\n2018-05-18 11:42:59.460950,187.6700,100,8854093,187.6600,187.6700,17035,C,5,3D,\r\n";
    private const int DelimiterCount = 10;
    private const char DelimiterChar = ',';
    private const int LastDelimiterSkip = 5;

    private static readonly string[] LineSplitDelimiter = { ",\r\n" };

    [Test]
    public void TickMessages_From_Substring()
    {
        var sw = Stopwatch.StartNew();
        for (int i = 0; i < 10000; i++)
        {
            var indexes = GetStringIndexes(DelimiterChar, Data, DelimiterCount, LastDelimiterSkip);
            var tickMessages = GetTickMessages(Data, indexes);
        }
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds);
    }

    [Test]
    public void TickMessages_From_Split()
    {
        var sw = Stopwatch.StartNew();
        for (int i = 0; i < 10000; i++)
        {
            var tickMessages = GetTickMessages(Data);
        }
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds);
    }

    static List<TickMessage> GetTickMessages(string data)
    {

        var convertedMessages = new List<TickMessage>();
        var messages = data.Split(LineSplitDelimiter, StringSplitOptions.RemoveEmptyEntries);
        for (var i = 0; i < messages.Length; i++)
        {
            // check for last message

            var values = messages[i].Split(',');
            var tick = new TickMessage(
                DateTime.Parse(values[0]),
                float.Parse(values[1]),
                int.Parse(values[2]),
                int.Parse(values[3]),
                float.Parse(values[4]),
                float.Parse(values[5]),
                int.Parse(values[6]),
                char.Parse(values[7]),
                int.Parse(values[8]),
                values[9]);

            convertedMessages.Add(tick);
        }

        return convertedMessages;
    }

    static List<TickMessage> GetTickMessages(string data, List<Tuple<int, int>> indexes)
    {
        var ticks = new List<TickMessage>(indexes.Count / 10);

        var count = 0;
        var index = indexes[count];

        do
        {
            var v1 = data.Substring(index.Item1, index.Item2 - index.Item1); index = indexes[++count];
            var v2 = data.Substring(index.Item1, index.Item2 - index.Item1); index = indexes[++count];
            var v3 = data.Substring(index.Item1, index.Item2 - index.Item1); index = indexes[++count];
            var v4 = data.Substring(index.Item1, index.Item2 - index.Item1); index = indexes[++count];
            var v5 = data.Substring(index.Item1, index.Item2 - index.Item1); index = indexes[++count];
            var v6 = data.Substring(index.Item1, index.Item2 - index.Item1); index = indexes[++count];
            var v7 = data.Substring(index.Item1, index.Item2 - index.Item1); index = indexes[++count];
            var v8 = data.Substring(index.Item1, index.Item2 - index.Item1); index = indexes[++count];
            var v9 = data.Substring(index.Item1, index.Item2 - index.Item1); index = indexes[++count];
            var v10 = data.Substring(index.Item1, index.Item2 - index.Item1);

            count++;

            if (count < indexes.Count)
                index = indexes[count];

            var x = new TickMessage(
                DateTime.Parse(v1),
                float.Parse(v2),
                int.Parse(v3),
                int.Parse(v4),
                float.Parse(v5),
                float.Parse(v6),
                int.Parse(v7),
                char.Parse(v8),
                int.Parse(v9),
                v10);

            ticks.Add(x);

        } while (count < indexes.Count);

        return ticks;
    }

    static List<Tuple<int, int>> GetStringIndexes(char delimeter, string value, int repeat, int skip)
    {
        int begin = 0;
        int count = 0;
        var locations = new List<Tuple<int, int>>();

        for (int i = 0; i < value.Length; i++)
        {
            if (value[i] == delimeter)
            {
                locations.Add(new Tuple<int, int>(begin, i));
                begin = i + 1;
                count++;
            }

            if (count == repeat)
            {
                count = 0;
                begin = i = i + skip;
            }
        }
        return locations;
    }
}

public class TickMessage
{
    public TickMessage(DateTime timestamp, float last, int lastSize, int totalVolume, float bid, float ask, 
        int tickId, char basisForLast, int tradeMarketCenter, string tradeConditions)
    {
        Timestamp = timestamp;
        Last = last;
        LastSize = lastSize;
        TotalVolume = totalVolume;
        Bid = bid;
        Ask = ask;
        TickId = tickId;
        BasisForLast = basisForLast;
        TradeMarketCenter = tradeMarketCenter;
        TradeConditions = tradeConditions;
    }

    public DateTime Timestamp { get; }
    public float Last { get; }
    public int LastSize { get; }
    public int TotalVolume { get; }
    public float Bid { get; }
    public float Ask { get; }
    public int TickId { get; }
    public char BasisForLast { get; }
    public int TradeMarketCenter { get; }
    public string TradeConditions { get; }
}

Full version: source code

\$\endgroup\$
7
  • \$\begingroup\$ But you do have string.split. Not sure this qualifies as working code. You if want no split then read it character by character. Return an iEnumverable (don't store a List). \$\endgroup\$
    – paparazzo
    May 18, 2018 at 18:39
  • 2
    \$\begingroup\$ You mentioned that you wanted to avoid string.split because it allocates a bunch of new strings on the heap, and then you use Substring to allocate a bunch of new strings on the heap. If you need perfomance boosts here you may need to look into treating the string as a char[], and using Span<T> to splice the char array without copies or heap allocations - which may require implementing your own parse methods that take Span<char> But my guess is for most types of applications one would write in C#, that kind of optimization is unnecessary \$\endgroup\$
    – Kelson Ball
    May 18, 2018 at 18:40
  • 1
    \$\begingroup\$ Here is some great info on Span<T> if you do end up needing high performance managed code here: msdn.microsoft.com/en-us/magazine/mt814808.aspx \$\endgroup\$
    – Kelson Ball
    May 18, 2018 at 18:43
  • 4
    \$\begingroup\$ What exactly does "inefficient" mean here? I have used it my whole life as a developer and never had issues with it. This to me sounds like premature optimization. \$\endgroup\$
    – CodingYoshi
    May 18, 2018 at 19:20
  • \$\begingroup\$ @CodingYoshi I feel the same but I just wanted to clear my mind with it since I'm claiming that my library that using it if the most efficient one :) \$\endgroup\$
    – Mathieu Paquette
    May 18, 2018 at 19:45

1 Answer 1

Reset to default
8
\$\begingroup\$

So after a couple hours of tinkering around I've come to the conclusion that 'people' are wrong and string.Split has been optimized into oblivion by microsoft.

Here is a gist with my code for parsing the data from Spans

CharSpanExtensions.cs

The idea is that it uses ReadOnlySpan to represent a string and enumerates over it exactly once. The data is only ever copied to create new (small) strings in ConsumeDateTime and ConsumeString, and that is done with a direct unsafe pointer into the data of the span.

Adding a test for the span implementation to your code looked like this

static List<TickMessage> GetTickMessages(ReadOnlySpan<char> data)
{
    var ticks = new List<TickMessage>();
    while (data.Length > 0)
    {
        ticks.Add(new TickMessage(
            data.ConsumeDateTime(out data),
            data.ConsumeFloat(out data),
            data.ConsumeInt(out data),
            data.ConsumeInt(out data),
            data.ConsumeFloat(out data),
            data.ConsumeFloat(out data),
            data.ConsumeInt(out data),
            data.ConsumeChar(out data),
            data.ConsumeInt(out data),
            data.ConsumeString(out data)));
    }
    return ticks;
}

Benchmarks were as follows

dotnet core 2.1
| Method    | Milliseconds |
| --------- | ------------ |
| Substring | 2616         |
| Split     | 703          |
| Span      | 1757         |

netframework 4.6.2
| Method    | Milliseconds |
| --------- | ------------ |
| Substring | 3562         |
| Split     | 841          |
| Span      | 2602         |

Something string.Split is doing is making it faster to enumerate over all the data twice (at least once to split the data, then at least once for each parsed item to parse it) than to use direct pointers on the stack (Span) and enumerate over the data once.

Creating strings and using the frameworks float.Parse and int.Parse methods made my Span crawling code significantly slower, probably because of the additional heap allocations from creating the strings to use the parse methods.

There is almost certainly more room for optimization in my code, but I doubt it'd get near the huge lead that string.Split has.

\$\endgroup\$
2
  • \$\begingroup\$ Hi @Kelson Ball and Mathieu Paquette did you run your test cases on big chunks of data? Thanks. \$\endgroup\$
    – Adrian Stanculescu
    Jul 8, 2019 at 13:16
  • \$\begingroup\$ @AdrianStanculescu sorry for the late response - I'm pretty sure I used the same data for this that the question author posted above \$\endgroup\$
    – Kelson Ball
    Jan 4, 2020 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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