Waarom is het verwerken van een gesorteerde array langzamer dan een ongesorteerde array?

Waarom is het verwerken van een gesorteerde array langzamer dan een ongesorteerde array?

Wanneer u de ongesorteerde lijst gebruikt, worden alle tuples geopend in geheugenvolgorde . Ze zijn achtereenvolgens toegewezen in RAM. CPU's houden ervan om achtereenvolgens toegang te krijgen tot het geheugen, omdat ze speculatief de volgende cacheregel kunnen opvragen, zodat deze altijd aanwezig zal zijn wanneer dat nodig is.

Wanneer u de lijst sorteert, plaatst u deze in willekeurige volgorde omdat uw sorteersleutels willekeurig worden gegenereerd. Dit betekent dat de geheugentoegangen tot tupelleden onvoorspelbaar zijn. De CPU kan geen geheugen prefetchen en bijna elke toegang tot een tuple is een cache-misser.

Dit is een mooi voorbeeld van een specifiek voordeel van GC-geheugenbeheer :datastructuren die samen zijn toegewezen en samen worden gebruikt, presteren erg goed. Ze hebben een geweldige referentieplaats .

De straf uit de cache mist opweegt tegen de bewaarde taks-voorspellingsboete in dit geval.

Probeer over te schakelen naar een struct -tupel. Dit zal de prestaties herstellen omdat er tijdens runtime geen pointer-dereferentie hoeft te gebeuren om toegang te krijgen tot tuple-leden.

Chris Sinclair merkt in de opmerkingen op dat "voor TotalCount rond 10.000 of minder, de gesorteerde versie sneller presteert ". Dit komt omdat een kleine lijst volledig in de CPU-cache past . De geheugentoegangen kunnen onvoorspelbaar zijn, maar het doel bevindt zich altijd in de cache. Ik geloof dat er nog steeds een kleine boete is, omdat zelfs het laden van de cache enkele cycli duurt. Maar dat lijkt geen probleem te zijn omdat de CPU met meerdere openstaande belastingen kan jongleren , waardoor de doorvoer toeneemt. Telkens wanneer de CPU wacht op geheugen, zal hij nog steeds versnellen in de instructiestroom om zoveel mogelijk geheugenbewerkingen in de wachtrij te plaatsen. Deze techniek wordt gebruikt om latentie te verbergen.

Dit soort gedrag laat zien hoe moeilijk het is om de prestaties van moderne CPU's te voorspellen. Het feit dat we slechts 2x langzamer zijn wanneer u van sequentiële naar willekeurige geheugentoegang gaat, vertel me hoeveel er onder de dekens gebeurt om de geheugenlatentie te verbergen. Een geheugentoegang kan de CPU 50-200 cycli laten stoppen. Gezien dat nummer zou je kunnen verwachten dat het programma>10x langzamer wordt bij het introduceren van willekeurige geheugentoegangen.


LINQ weet niet of je lijst is gesorteerd of niet.

Aangezien Count met predikaatparameter een extensiemethode is voor alle IEnumerables, denk ik dat het niet eens weet of het over de verzameling loopt met efficiënte willekeurige toegang. Het controleert dus eenvoudig elk element en Usr verklaarde waarom de prestaties lager werden.

Om de prestatievoordelen van gesorteerde arrays (zoals binair zoeken) te benutten, moet u iets meer coderen.