Warum ist es schneller, wenn ich vor ToLookup ein zusätzliches ToArray platziere?

10

Wir haben eine kurze Methode, die CSV-Datei zu einer Suche analysiert:

ILookup<string, DgvItems> ParseCsv( string fileName )
{
    var file = File.ReadAllLines( fileName );
    return file.Skip( 1 ).Select( line => new DgvItems( line ) ).ToLookup( item => item.StocksID );
}

Und die Definition von DgvItems:

public class DgvItems
{
    public string DealDate { get; }

    public string StocksID { get; }

    public string StockName { get; }

    public string SecBrokerID { get; }

    public string SecBrokerName { get; }

    public double Price { get; }

    public int BuyQty { get; }

    public int CellQty { get; }

    public DgvItems( string line )
    {
        var split = line.Split( ',' );
        DealDate = split[0];
        StocksID = split[1];
        StockName = split[2];
        SecBrokerID = split[3];
        SecBrokerName = split[4];
        Price = double.Parse( split[5] );
        BuyQty = int.Parse( split[6] );
        CellQty = int.Parse( split[7] );
    }
}

Und wir haben festgestellt, dass, wenn wir ToArray()vorher ein Extra hinzufügen, ToLookup()wie folgt:

static ILookup<string, DgvItems> ParseCsv( string fileName )
{
    var file = File.ReadAllLines( fileName  );
    return file.Skip( 1 ).Select( line => new DgvItems( line ) ).ToArray().ToLookup( item => item.StocksID );
}

Letzteres ist deutlich schneller. Wenn Sie eine Testdatei mit 1,4 Millionen Zeilen verwenden, dauert die erste ungefähr 4,3 Sekunden und die zweite ungefähr 3 Sekunden.

Ich gehe davon aus ToArray(), dass es etwas länger dauern sollte, damit letzteres etwas langsamer wird. Warum ist es eigentlich schneller?


Zusatzinformation:

  1. Wir haben dieses Problem gefunden, weil es eine andere Methode gibt, die dieselbe CSV-Datei in ein anderes Format analysiert. Sie dauert ungefähr 3 Sekunden. Wir sind daher der Meinung, dass diese Methode in 3 Sekunden dasselbe tun sollte.

  2. Der ursprüngliche Datentyp ist Dictionary<string, List<DgvItems>>und der ursprüngliche Code hat linq nicht verwendet und das Ergebnis ist ähnlich.


BenchmarkDotNet-Testklasse:

public class TestClass
{
    private readonly string[] Lines;

    public TestClass()
    {
        Lines = File.ReadAllLines( @"D:\20110315_Random.csv" );
    }

    [Benchmark]
    public ILookup<string, DgvItems> First()
    {
        return Lines.Skip( 1 ).Select( line => new DgvItems( line ) ).ToArray().ToLookup( item => item.StocksID );
    }

    [Benchmark]
    public ILookup<string, DgvItems> Second()
    {
        return Lines.Skip( 1 ).Select( line => new DgvItems( line ) ).ToLookup( item => item.StocksID );
    }
}

Ergebnis:

| Method |    Mean |    Error |   StdDev |
|------- |--------:|---------:|---------:|
|  First | 2.530 s | 0.0190 s | 0.0178 s |
| Second | 3.620 s | 0.0217 s | 0.0203 s |

Ich habe eine weitere Testbasis auf Originalcode durchgeführt. Scheint, dass das Problem nicht bei Linq liegt.

public class TestClass
{
    private readonly string[] Lines;

    public TestClass()
    {
        Lines = File.ReadAllLines( @"D:\20110315_Random.csv" );
    }

    [Benchmark]
    public Dictionary<string, List<DgvItems>> First()
    {
        List<DgvItems> itemList = new List<DgvItems>();
        for ( int i = 1; i < Lines.Length; i++ )
        {
            itemList.Add( new DgvItems( Lines[i] ) );
        }

        Dictionary<string, List<DgvItems>> dictionary = new Dictionary<string, List<DgvItems>>();

        foreach( var item in itemList )
        {
            if( dictionary.TryGetValue( item.StocksID, out var list ) )
            {
                list.Add( item );
            }
            else
            {
                dictionary.Add( item.StocksID, new List<DgvItems>() { item } );
            }
        }

        return dictionary;
    }

    [Benchmark]
    public Dictionary<string, List<DgvItems>> Second()
    {
        Dictionary<string, List<DgvItems>> dictionary = new Dictionary<string, List<DgvItems>>();
        for ( int i = 1; i < Lines.Length; i++ )
        {
            var item = new DgvItems( Lines[i] );

            if ( dictionary.TryGetValue( item.StocksID, out var list ) )
            {
                list.Add( item );
            }
            else
            {
                dictionary.Add( item.StocksID, new List<DgvItems>() { item } );
            }
        }

        return dictionary;
    }
}

Ergebnis:

| Method |    Mean |    Error |   StdDev |
|------- |--------:|---------:|---------:|
|  First | 2.470 s | 0.0218 s | 0.0182 s |
| Second | 3.481 s | 0.0260 s | 0.0231 s |
Leisen Chang
quelle
2
Ich vermute sehr den Testcode / die Messung. Bitte posten Sie den Code, der die Zeit berechnet
Erno
1
Ich vermute, dass ohne das .ToArray()der Aufruf von .Select( line => new DgvItems( line ) )eine IEnumerable vor dem Aufruf von zurückgibt ToLookup( item => item.StocksID ). Das Nachschlagen eines bestimmten Elements ist mit IEnumerable schlechter als mit Array. Wahrscheinlich schneller in ein Array zu konvertieren und nachzuschlagen als mit einer ienumerable.
Kimbaudi
2
Randnotiz: setzen var file = File.ReadLines( fileName );- ReadLinesstatt ReadAllLinesund Sie Code wird wahrscheinlich schneller sein
Dmitry Bychenko
2
Sie sollten BenchmarkDotnetfür die eigentliche Leistungsmessung verwenden. Versuchen Sie außerdem, den tatsächlichen Code zu isolieren, den Sie messen möchten, und schließen Sie E / A nicht in den Test ein.
JohanP
1
Ich weiß nicht, warum dies abgelehnt wurde - ich denke, es ist eine gute Frage.
Rufus L

Antworten:

2

Ich habe es geschafft, das Problem mit dem folgenden vereinfachten Code zu replizieren:

var lookup = Enumerable.Range(0, 2_000_000)
    .Select(i => ( (i % 1000).ToString(), i.ToString() ))
    .ToArray() // +20% speed boost
    .ToLookup(x => x.Item1);

Es ist wichtig, dass die Mitglieder des erstellten Tupels Zeichenfolgen sind. Das Entfernen der beiden .ToString()aus dem obigen Code beseitigt den Vorteil von ToArray. Das .NET Framework verhält sich etwas anders als .NET Core, da es ausreicht, nur das erste zu entfernen.ToString() zu , um den beobachteten Unterschied zu beseitigen.

Ich habe keine Ahnung, warum das passiert.

Theodor Zoulias
quelle
Mit welchem ​​Framework haben Sie dies bestätigt? Ich kann mit .net Framework 4.7.2 keinen Unterschied feststellen
Magnus
@Magnus .NET Framework 4.8 (VS 2019, Release Build)
Theodor Zoulias
Anfangs habe ich den beobachteten Unterschied übertrieben. In .NET Core sind es ungefähr 20% und in .NET Framework ungefähr 10%.
Theodor Zoulias
1
Netter Repro. Ich habe keine genauen Kenntnisse darüber, warum dies geschieht, und habe keine Zeit, es herauszufinden, aber ich würde vermuten , dass das ToArrayoderToList Daten gezwungen sind, sich in einem zusammenhängenden Speicher zu befinden. Wenn Sie dies zu einem bestimmten Zeitpunkt in der Pipeline erzwingen, kann dies dazu führen, dass bei einem späteren Vorgang weniger Prozessor-Cache-Fehler auftreten, obwohl dies zusätzliche Kosten verursacht. Prozessor-Cache-Fehler sind überraschend teuer.
Eric Lippert