c# - इंट्रे इंडेक्स के साथ एरे टेबल लुकअप करने का सबसे तेज़ तरीका क्या है?




memory lookup (2)

मेरे पास एक वीडियो प्रोसेसिंग एप्लिकेशन है जो बहुत सारे डेटा को स्थानांतरित करता है।

चीजों को गति देने के लिए, मैंने एक लुकअप तालिका बनाई है, क्योंकि सार में कई गणनाओं को केवल एक बार गणना करने की आवश्यकता होती है और इसका पुन: उपयोग किया जा सकता है।

हालाँकि, मैं उस बिंदु पर हूँ जहाँ अब सभी लुकअप में 30% प्रसंस्करण समय लगता है। अगर यह धीमा हो सकता है मैं सोच रहा हूँ RAM .. हालाँकि, मैं अभी भी इसे और अधिक अनुकूलित करने का प्रयास करना चाहूंगा।

वर्तमान में मेरे पास निम्नलिखित हैं:

public readonly int[] largeArray = new int[3000*2000];
public readonly int[] lookUp = new int[width*height];

फिर मैं परिणाम प्राप्त करने के लिए पॉइंटर p (जो width * y + x बराबर है) के साथ एक लुकअप करता हूं।

int[] newResults = new int[width*height];
int p = 0;
for (int y = 0; y < height; y++) {
   for (int x = 0; x < width; x++, p++) {
      newResults[p] = largeArray[lookUp[p]];
   }
}

ध्यान दें कि मैं ऑप्टिमाइज़ करने के लिए पूरी सरणी कॉपी नहीं कर सकता। इसके अलावा, आवेदन भारी रूप से गुणा किया गया है।

कुछ प्रगति फ़ंक्शन स्टैक को छोटा करने में थी, इसलिए कोई प्राप्तकर्ता नहीं बल्कि एक आसानी से सरणी से सीधे पुनर्प्राप्ति।

मैं भी रूप में अच्छी तरह से परिवर्तित करने की कोशिश की है, लेकिन यह धीमी लग रहा था (जैसा कि मैं समझता हूँ कि यह शब्द आकार के कारण है)।

क्या कोई इंटप्रेट तेज होगा? मैं उसके बारे में कैसे जाऊंगा?

नीचे संलग्न समय वितरण का एक स्क्रीनशॉट है:


ऐसा लगता है कि आप यहां जो कर रहे हैं वह प्रभावी रूप से एक "इकट्ठा" है। आधुनिक सीपीयू ने इसके लिए विशेष रूप से VPGATHER** में निर्देश समर्पित VPGATHER** । यह .NET कोर 3 में सामने आया है, और नीचे की तरह कुछ काम करना चाहिए , जो कि सिंगल लूप परिदृश्य है (आप डबल-लूप संस्करण प्राप्त करने के लिए यहां से काम कर सकते हैं);

पहले परिणाम:

AVX enabled: False; slow loop from 0
e7ad04457529f201558c8a53f639fed30d3a880f75e613afe203e80a7317d0cb
for 524288 loops: 1524ms

AVX enabled: True; slow loop from 1024
e7ad04457529f201558c8a53f639fed30d3a880f75e613afe203e80a7317d0cb
for 524288 loops: 667ms

कोड:

using System;
using System.Diagnostics;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;

static class P
{
    static int Gather(int[] source, int[] index, int[] results, bool avx)
    {   // normally you wouldn't have avx as a parameter; that is just so
        // I can turn it off and on for the test; likewise the "int" return
        // here is so I can monitor (in the test) how much we did in the "old"
        // loop, vs AVX2; in real code this would be void return

        int y = 0;
        if (Avx2.IsSupported && avx)
        {
            var iv = MemoryMarshal.Cast<int, Vector256<int>>(index);
            var rv = MemoryMarshal.Cast<int, Vector256<int>>(results);

            unsafe
            {
                fixed (int* sPtr = source)
                {
                    // note: here I'm assuming we are trying to fill "results" in
                    // a single outer loop; for a double-loop, you'll probably need
                    // to slice the spans
                    for (int i = 0; i < rv.Length; i++)
                    {
                        rv[i] = Avx2.GatherVector256(sPtr, iv[i], 4);
                    }
                }
            }
            // move past everything we've processed via SIMD
            y += rv.Length * Vector256<int>.Count;
        }
        // now do anything left, which includes anything not aligned to 256 bits,
        // plus the "no AVX2" scenario
        int result = y;
        int end = results.Length; // hoist, since this is not the JIT recognized pattern
        for (; y < end; y++)
        {
            results[y] = source[index[y]];
        }
        return result;
    }

    static void Main()
    {
        // invent some random data
        var rand = new Random(12345);
        int size = 1024 * 512;
        int[] data = new int[size];
        for (int i = 0; i < data.Length; i++)
            data[i] = rand.Next(255);

        // build a fake index
        int[] index = new int[1024];
        for (int i = 0; i < index.Length; i++)
            index[i] = rand.Next(size);

        int[] results = new int[1024];

        void GatherLocal(bool avx)
        {
            // prove that we're getting the same data
            Array.Clear(results, 0, results.Length);
            int from = Gather(data, index, results, avx);
            Console.WriteLine($"AVX enabled: {avx}; slow loop from {from}");
            for (int i = 0; i < 32; i++)
            {
                Console.Write(results[i].ToString("x2"));
            }
            Console.WriteLine();

            const int TimeLoop = 1024 * 512;
            var watch = Stopwatch.StartNew();
            for (int i = 0; i < TimeLoop; i++)
                Gather(data, index, results, avx);
            watch.Stop();
            Console.WriteLine($"for {TimeLoop} loops: {watch.ElapsedMilliseconds}ms");
            Console.WriteLine();
        }
        GatherLocal(false);
        if (Avx2.IsSupported) GatherLocal(true);
    }
}

रैम पहले से ही संभव सबसे तेज चीजों में से एक है। केवल तेजी से मेमोरी सीपीयू कैश है। तो यह मेमोरी बाउंड होगा, लेकिन यह अभी भी बहुत तेज है।

निश्चित रूप से दिए गए आकारों में, यह सरणी आकार में 6 मिलियन प्रविष्टियाँ है। यह संभवतः किसी कैश में फिट नहीं होगा। और हमेशा के लिए खत्म करने के लिए ले जाएगा। यह गति क्या है यह मैटर नहीं करता है, यह बस बहुत अधिक डेटा है।

एक सामान्य नियम के रूप में, आजकल GPU पर वीडियो प्रसंस्करण किया जाता है। जीपीयू का शाब्दिक रूप से विशालकाय सरणियों पर काम करना है। क्योंकि वह छवि जो आप अभी देख रहे हैं वह है - एक विशाल सरणी।

अगर आपको इसे GPU की तरफ रखना है, तो शायद कैशिंग या लेजी इनटिलाइजेशन से मदद मिलेगी? संभावना है कि आपको वास्तव में हर मूल्य की आवश्यकता नहीं है। आपको केवल सामान्य मूल्यों की आवश्यकता है। डिसिरोलिंग से एक उदाहरण लें: यदि आप 2 6-पक्षीय पासा रोल करते हैं, तो 2-12 से हर परिणाम संभव है। लेकिन परिणाम 7 में से 6 में होता है। 2 और 12 केवल 36 मामलों में से 1 है। तो 7 संग्रहित होने से बहुत अधिक लाभकारी है 2 और 12।





lookup