c जल्दी से पता लगाएं कि एक सी सरणी में कोई मान मौजूद है या नहीं?




optimization assembly (12)

मेरे पास एक समय-महत्वपूर्ण आईएसआर के साथ एक एम्बेडेड एप्लिकेशन है जिसे आकार 256 (अधिमानतः 1024, लेकिन 256 न्यूनतम है) के माध्यम से पुनरावृत्त करने की आवश्यकता है और जांचें कि कोई मान सरणी सामग्री से मेल खाता है या नहीं। एक bool सत्य पर सेट किया जाएगा यह मामला है। एमसीयू एक एनएक्सपी एलपीसी 4357 है, एआरएम कॉर्टेक्स एम 4 कोर, कंपाइलर जीसीसी है। मेरे पास पहले से ही अनुकूलन स्तर 2 (3 धीमा है) और फ्लैश के बजाय फ़ंक्शन में रैम रख रहा है। मैं पॉइंटर अंकगणित और लूप के for भी उपयोग करता हूं, जो ऊपर की ओर गिनती करता है (जांच कर रहा है कि i!=0 जांच कर रहा i<256 कि i<256 ) जांच कर रहा i<256 । सब कुछ, मैं 12.5us की अवधि के साथ समाप्त होता हूं जिसे व्यवहार्य रूप से व्यवहार्य रूप से कम किया जाना चाहिए। यह अब (छद्म) कोड है जिसका उपयोग मैं करता हूं:

uint32_t i;
uint32_t *array_ptr = &theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
    if (compareVal == *array_ptr++)
    {
         validFlag = true;
         break;
     }
}

ऐसा करने का सबसे तेज़ तरीका क्या होगा? इनलाइन असेंबली का उपयोग करने की अनुमति है। अन्य 'कम सुरुचिपूर्ण' चाल भी अनुमति दी।


इस मामले में, यह ब्लूम फिल्टर की सार्थक जांच कर सकता है। वे जल्दी से स्थापित करने में सक्षम हैं कि एक मूल्य मौजूद नहीं है, जो एक अच्छी बात है क्योंकि अधिकांश 2 ^ 32 संभावित मान उस 1024 तत्व सरणी में नहीं हैं। हालांकि, कुछ झूठे सकारात्मक हैं जिन्हें अतिरिक्त जांच की आवश्यकता होगी।

चूंकि आपकी तालिका स्पष्ट रूप से स्थिर है, इसलिए आप यह निर्धारित कर सकते हैं कि आपके ब्लूम फ़िल्टर के लिए कौन से झूठे सकारात्मक मौजूद हैं और इन्हें एकदम सही हैश रखें।


अन्य लोगों ने आपके टेबल को पुनर्गठित करने का सुझाव दिया है, अंत में एक सेंटीनेल वैल्यू जोड़ना है, या बाइनरी सर्च प्रदान करने के लिए इसे सॉर्ट करना है।

आप कहते हैं "मैं पॉइंटर अंकगणित और लूप के लिए भी उपयोग करता हूं, जो ऊपर की गिनती करता है (जांच कर रहा है कि i != 0 जांच कर रहा i < 256 कि i < 256 ) जांच कर रहा i < 256 ।"

मेरी पहली सलाह है: पॉइंटर अंकगणित और डाउनकाउंटिंग से छुटकारा पाएं। सामान की तरह

for (i=0; i<256; i++)
{
    if (compareVal == the_array[i])
    {
       [...]
    }
}

संकलक के लिए मूर्खतापूर्ण हो जाता है। लूप idiomatic है, और एक लूप चर पर एक सरणी का अनुक्रमण idiomatic है। पॉइंटर अंकगणितीय और पॉइंटर्स के साथ जुगलिंग कंपाइलर को मुहावरों को खराब कर देगा और यह आपके द्वारा लिखे गए कोड से संबंधित कोड उत्पन्न करेगा, जो कि संकलक लेखक ने सामान्य कार्य के लिए सबसे अच्छा कोर्स होने का फैसला किया था।

उदाहरण के लिए, उपरोक्त कोड को -256 या -255 से शून्य तक चलने वाले लूप में संकलित किया जा सकता है, इंडेक्सिंग ऑफ &the_array[256] । संभावित रूप से सामान जो वैध सी में भी स्पष्ट नहीं है लेकिन आपके द्वारा उत्पन्न की जा रही मशीन के आर्किटेक्चर से मेल खाता है।

तो microoptimize मत करो । आप सिर्फ अपने अनुकूलक के कार्यों में स्पैनर्स फेंक रहे हैं। यदि आप चालाक होना चाहते हैं, तो डेटा संरचनाओं और एल्गोरिदम पर काम करें, लेकिन उनकी अभिव्यक्ति को सूक्ष्म रूप से लागू न करें। वर्तमान कंपाइलर / आर्किटेक्चर पर नहीं, तो अगले समय पर यह आपको काटने के लिए वापस आ जाएगा।

विशेष रूप से सरणी और इंडेक्स के बजाय पॉइंटर अंकगणित का उपयोग करना कंपाइलर को संरेखण, भंडारण स्थान, एलियासिंग विचारों और अन्य सामानों के बारे में पूरी तरह से अवगत होने के लिए जहर है, और मशीन आर्किटेक्चर के लिए सबसे उपयुक्त तरीके से ताकत कम करने जैसे अनुकूलन करने के लिए जहर है।


यदि आपकी तालिका में स्थिरांक का सेट अग्रिम में जाना जाता है, तो आप यह सुनिश्चित करने के लिए सही हैशिंग का उपयोग कर सकते हैं कि तालिका में केवल एक ही पहुंच हो। परफेक्ट हैशिंग एक हैश फ़ंक्शन निर्धारित करता है जो एक अद्वितीय स्लॉट के लिए हर रोचक कुंजी को मैप करता है (वह तालिका हमेशा घनी नहीं होती है, लेकिन आप यह तय कर सकते हैं कि आप कितनी गहन टेबल ले सकते हैं, कम घने तालिकाओं के साथ आमतौर पर सरल हैशिंग फ़ंक्शन का कारण बनता है)।

आमतौर पर, कुंजी के विशिष्ट सेट के लिए सही हैश फ़ंक्शन गणना करने के लिए अपेक्षाकृत आसान है; आप नहीं चाहते कि यह लंबा और जटिल हो क्योंकि वह समय के लिए प्रतिस्पर्धा करता है शायद कई जांच करने में बेहतर खर्च करता है।

परफेक्ट हैशिंग एक "1-जांच अधिकतम" योजना है। कोई इस विचार के साथ विचार को सामान्यीकृत कर सकता है कि किसी को हैश कोड की गणना करने की सादगी का व्यापार करना चाहिए, जिसमें के जांच करने के लिए समय लगता है। आखिरकार, लक्ष्य "देखने के लिए कम से कम कुल समय" है, कम से कम जांच या सरल हैश फ़ंक्शन नहीं है। हालांकि, मैंने कभी भी किसी के-प्रोब-मैक्स हैशिंग एल्गोरिदम का निर्माण नहीं देखा है। मुझे संदेह है कि कोई ऐसा कर सकता है, लेकिन यह संभवतः शोध है।

एक अन्य विचार: यदि आपका प्रोसेसर बेहद तेज़ है, तो एक परिपूर्ण हैश से स्मृति की जांच संभवतः निष्पादन समय पर हावी है। यदि प्रोसेसर बहुत तेज़ नहीं है, तो के> 1 जांच से व्यावहारिक हो सकता है।


तालिका क्रमबद्ध क्रम में रखें, और बेंटले की अनियंत्रित बाइनरी खोज का उपयोग करें:

i = 0;
if (key >= a[i+512]) i += 512;
if (key >= a[i+256]) i += 256;
if (key >= a[i+128]) i += 128;
if (key >= a[i+ 64]) i +=  64;
if (key >= a[i+ 32]) i +=  32;
if (key >= a[i+ 16]) i +=  16;
if (key >= a[i+  8]) i +=   8;
if (key >= a[i+  4]) i +=   4;
if (key >= a[i+  2]) i +=   2;
if (key >= a[i+  1]) i +=   1;
return (key == a[i]);

मुद्दा ये है,

  • यदि आप जानते हैं कि तालिका कितनी बड़ी है, तो आप जानते हैं कि कितने पुनरावृत्तियों होंगे, ताकि आप इसे पूरी तरह से अनलॉक कर सकें।
  • फिर, प्रत्येक पुनरावृत्ति पर == मामले के लिए कोई बिंदु परीक्षण नहीं है क्योंकि, अंतिम पुनरावृत्ति को छोड़कर, उस मामले की संभावना इसके लिए व्यय समय परीक्षण को उचित ठहराने के लिए बहुत कम है। **
  • अंत में, तालिका को 2 की शक्ति में विस्तार करके, आप सबसे अधिक तुलना में जोड़ते हैं, और अधिकतर दो स्टोरेज का एक कारक जोड़ते हैं।

** यदि आप संभावनाओं के संदर्भ में सोचने के लिए उपयोग नहीं किए जाते हैं, तो प्रत्येक निर्णय बिंदु में एक एन्ट्रॉपी होती है , जो कि इसे निष्पादित करके सीखने वाली औसत जानकारी होती है। >= परीक्षणों के लिए, प्रत्येक शाखा की संभावना लगभग 0.5 है, और -log2 (0.5) 1 है, इसका मतलब है कि यदि आप एक शाखा लेते हैं तो आप 1 बिट सीखते हैं, और यदि आप दूसरी शाखा लेते हैं तो आप एक बिट सीखते हैं, और औसतन उस शाखा की संभावना प्रत्येक शाखा समय पर आप जो भी सीखते हैं उसका योग है। तो 1*0.5 + 1*0.5 = 1 , इसलिए >= test की एन्ट्रॉपी 1*0.5 + 1*0.5 = 1 है। चूंकि आपके पास सीखने के लिए 10 बिट हैं, इसमें 10 शाखाएं होती हैं। यही कारण है कि यह तेज़ है!

दूसरी ओर, यदि आपका पहला परीक्षण है if (key == a[i+512) ? सत्य होने की संभावना 1/1024 है, जबकि झूठी संभावना 1023/1024 है। तो यदि यह सच है तो आप सभी 10 बिट्स सीखते हैं! लेकिन अगर यह गलत है तो आप सीखेंगे -log2 (1023/1024) = .00141 बिट्स, व्यावहारिक रूप से कुछ भी नहीं! इसलिए उस परीक्षा से आप जो औसत राशि सीखते हैं वह 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112 बिट्स है। थोड़ा सा सौवां। वह परीक्षण अपना वजन नहीं ले रहा है!


मान लें कि आपका प्रोसेसर 204 मेगाहट्र्ज पर चलता है जो एलपीसी 4357 के लिए अधिकतम लगता है, और यह भी मानते हुए कि आपका समय परिणाम औसत केस (सरणी के आधे भाग का आधा) दर्शाता है, हमें मिलता है:

  • सीपीयू आवृत्ति: 204 मेगाहट्र्ज
  • चक्र अवधि: 4.9 एनएस
  • चक्र में अवधि: 12.5 μs / 4.9 एनएस = 2551 चक्र
  • चक्र प्रति पुनरावृत्ति: 2551/128 = 1 9.9

तो, आपका खोज लूप प्रति पुनरावृत्ति के लगभग 20 चक्र खर्च करता है। यह भयानक नहीं लगता है, लेकिन मुझे लगता है कि इसे तेज़ी से बनाने के लिए आपको असेंबली को देखने की जरूरत है।

मैं इंडेक्स को छोड़ने और इसके बजाय पॉइंटर तुलना का उपयोग करने और सभी पॉइंटर्स const बनाने की सलाह const

bool arrayContains(const uint32_t *array, size_t length)
{
  const uint32_t * const end = array + length;
  while(array != end)
  {
    if(*array++ == 0x1234ABCD)
      return true;
  }
  return false;
}

यह कम से कम परीक्षण के लायक है।


यदि आप अपने मूल्यों के डोमेन को अपने आवेदन के लिए उपलब्ध स्मृति की मात्रा के साथ समायोजित कर सकते हैं, तो सबसे तेज़ समाधान आपके सरणी को बिट्स की सरणी के रूप में प्रस्तुत करना होगा:

bool theArray[MAX_VALUE]; // of which 1024 values are true, the rest false
uint32_t compareVal = 0x1234ABCD;
bool validFlag = theArray[compareVal];

संपादित करें

मैं आलोचकों की संख्या से आश्चर्यचकित हूं। इस धागे का शीर्षक है "मैं कैसे जल्दी से यह पता लगा सकता हूं कि एक सी सरणी में कोई मान मौजूद है या नहीं?" जिसके लिए मैं अपने जवाब से खड़ा रहूंगा क्योंकि यह ठीक से जवाब देता है। मैं तर्क दे सकता हूं कि इसमें सबसे तेज़ कुशल हैश फ़ंक्शन है (पता === मान के बाद)। मैंने टिप्पणियां पढ़ी हैं और मुझे स्पष्ट चेतावनी के बारे में पता है। निस्संदेह उन चेतावनियों को हल करने के लिए उपयोग की जा सकने वाली समस्याओं की सीमा को सीमित कर सकते हैं, लेकिन, उन समस्याओं के लिए जो यह हल करता है, यह बहुत कुशलतापूर्वक हल करता है।

इस जवाब को पूरी तरह से अस्वीकार करने के बजाय, इसे इष्टतम प्रारंभिक बिंदु के रूप में मानें जिसके लिए आप गति और प्रदर्शन के बीच बेहतर संतुलन प्राप्त करने के लिए हैश फ़ंक्शंस का उपयोग कर विकसित कर सकते हैं।


एक हैश सेट का प्रयोग करें। यह ओ (1) लुकअप समय देगा।

निम्नलिखित कोड मानते हैं कि आप मान 0 को 'खाली' मान के रूप में आरक्षित कर सकते हैं, यानी वास्तविक डेटा में नहीं हो रहा है। समाधान को ऐसी स्थिति के लिए विस्तारित किया जा सकता है जहां यह मामला नहीं है।

#define HASH(x) (((x >> 16) ^ x) & 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
    int i = HASH(value);
    while (my_hash[i] != 0 && my_hash[i] != value) i = (i + 1) % HASH_LEN;
    return i;
}

void store(uint32_t value)
{
    int i = lookup(value);
    if (my_hash[i] == 0)
       my_hash[i] = value;
}

bool contains(uint32_t value)
{
    return (my_hash[lookup(value)] == value);
}

इस उदाहरण कार्यान्वयन में, लुकअप समय आमतौर पर बहुत कम होगा, लेकिन सबसे खराब स्थिति में संग्रहीत प्रविष्टियों की संख्या तक हो सकता है। रीयलटाइम एप्लिकेशन के लिए, आप बाइनरी पेड़ का उपयोग करके एक कार्यान्वयन पर भी विचार कर सकते हैं, जिसमें अधिक अनुमानित लुकअप समय होगा।


मुझे खेद है कि अगर मेरा जवाब पहले से ही उत्तर दिया गया था - बस मैं आलसी पाठक हूं। तब आपको नीचे जाने के लिए स्वतंत्र महसूस होता है))

1) आप काउंटर 'मैं' को हटा सकते हैं - बस पॉइंटर्स की तुलना करें, यानी

for (ptr = &the_array[0]; ptr < the_array+1024; ptr++)
{
    if (compareVal == *ptr)
    {
       break;
    }
}
... compare ptr and the_array+1024 here - you do not need validFlag at all.

जो कुछ भी महत्वपूर्ण सुधार नहीं देंगे हालांकि, इस तरह के अनुकूलन शायद संकलक द्वारा हासिल किया जा सकता है।

2) जैसा कि पहले से ही अन्य उत्तरों द्वारा इसका उल्लेख किया गया था, लगभग सभी आधुनिक सीपीयू आरआईएससी आधारित हैं, उदाहरण के लिए एआरएम। यहां तक ​​कि आधुनिक इंटेल एक्स 86 सीपीयू भी आरआईएससी कोर का उपयोग करते हैं, जहां तक ​​मुझे पता है (फ्लाई पर एक्स 86 से संकलित)। Major optimization for RISC is pipeline optimization (and for Intel and other CPU as well), minimizing code jumps. One type of such optimization (probably a major one), is "cycle rollback" one. It's incredibly stupid, and efficient, even Intel compiler can do that AFAIK. It looks like:

if (compareVal == the_array[0]) { validFlag = true; goto end_of_compare; }
if (compareVal == the_array[1]) { validFlag = true; goto end_of_compare; }
...and so on...
end_of_compare:

This way the optimization is that the pipeline is not broken for the worst case (if compareVal is absent in the array), so it is as fast as possible (of course not counting algorithm optimizations such as hash tables, sorted arrays and so on, mentioned in other answers, which may give better results depending on array size. Cycles Rollback approach can be applied there as well by the way. I'm writing here about that I think I didn't see in others)

The second part of this optimization is that that array item is taken by direct address (calculated at compiling stage, make sure you use a static array), and do not need additional ADD op to calculate pointer from array's base address. This optimization may not have significant effect, since AFAIK ARM architecture has special features to speed up arrays addressing. But anyway it's always better to know that you did all the best just in C code directly, right?

Cycle Rollback may look awkward due to waste of ROM (yep, you did right placing it to fast part of RAM, if your board supports this feature), but actually it's a fair pay for speed, being based on RISC concept. This is just a general point of calculation optimization - you sacrifice space for sake of speed, and vice versa, depending on your requirements.

If you think that rollback for array of 1024 elements is too large sacrifice for your case, you can consider 'partial rollback', for example dividing the array into 2 parts of 512 items each, or 4x256, and so on.

3) modern CPU often support SIMD ops, for example ARM NEON instruction set - it allows to execute the same ops in parallel. Frankly speaking I do not remember if it is suitable for comparison ops, but I feel it may be, you should check that. Googling shows that there may be some tricks as well, to get max speed, see https://.com/a/5734019/1028256

I hope it can give you some new ideas.


आप अपने एल्गोरिदम को अनुकूलित करने में सहायता मांग रहे हैं, जो आपको असेंबलर पर धक्का दे सकता है। लेकिन आपका एल्गोरिदम (एक रैखिक खोज) इतना चालाक नहीं है, इसलिए आपको अपना एल्गोरिदम बदलने पर विचार करना चाहिए। उदाहरण के लिए:

बिल्कुल सही हैश समारोह

यदि आपके 256 "मान्य" मान स्थैतिक हैं और संकलन समय पर ज्ञात हैं, तो आप एक परिपूर्ण हैश फ़ंक्शन का उपयोग कर सकते हैं। आपको एक हैश फ़ंक्शन ढूंढना होगा जो आपके इनपुट मान को श्रेणी 0 .. n में किसी मान पर मैप करता है, जहां आपके सभी महत्वपूर्ण मानों के लिए कोई टकराव नहीं है। यही है, एक ही आउटपुट मान के लिए कोई भी "वैध" मान हैश नहीं है। एक अच्छा हैश फ़ंक्शन खोजते समय, आपका लक्ष्य है:

  • हैश फ़ंक्शन को तेज़ी से तेज़ रखें।
  • न्यूनतम करें। सबसे छोटा आप 256 (न्यूनतम परिपूर्ण हैश फ़ंक्शन) प्राप्त कर सकते हैं, लेकिन डेटा के आधार पर यह संभवतः हासिल करना मुश्किल है।

कुशल हैश फ़ंक्शन के लिए नोट, n अक्सर 2 की शक्ति होती है, जो कम बिट्स (और ऑपरेशन) के बिटवाई मास्क के बराबर होती है। उदाहरण हैश फ़ंक्शन:

  • इनपुट बाइट्स के सीआरसी, मॉड्यूल एन
  • ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n (जितना आवश्यक हो, i , j , k , ... को बाएं या दाएं बदलाव के साथ)

फिर आप एन प्रविष्टियों की एक निश्चित तालिका बनाते हैं, जहां हैश तालिका में इंडेक्स में इनपुट मानों को मैप करता है। मान्य मानों के लिए, तालिका प्रविष्टि में वैध मान होता है। अन्य सभी टेबल प्रविष्टियों के लिए, सुनिश्चित करें कि इंडेक्स की प्रत्येक प्रविष्टि में मेरे पास कुछ अन्य अमान्य मान है जो i के लिए हैश नहीं है।

फिर आपके इंटरप्ट रूटीन में, इनपुट एक्स के साथ:

  1. इंडेक्स I के लिए हैश एक्स (जो 0 0 एन में है)
  2. तालिका में प्रविष्टि को देखो और देखें कि इसमें मान x है या नहीं

यह 256 या 1024 मानों की रैखिक खोज से कहीं अधिक तेज़ होगा।

मैंने उचित हैश फ़ंक्शंस खोजने के लिए कुछ पायथन कोड लिखा है।

द्विआधारी खोज

यदि आप 256 "वैध" मानों की अपनी सरणी को सॉर्ट करते हैं, तो आप एक रैखिक खोज के बजाय बाइनरी खोज कर सकते हैं। इसका मतलब है कि आप केवल 8 चरणों ( log2(256) ) में log2(256) -प्रविष्टि तालिका, या 10 चरणों में 1024-प्रविष्टि तालिका में खोज करने में सक्षम होना चाहिए। फिर, यह 256 या 1024 मानों की रैखिक खोज से कहीं अधिक तेज़ होगा।


ऐसी परिस्थितियों में जहां प्रदर्शन अत्यंत महत्वपूर्ण है, सी कंपाइलर हाथ से ट्यूनेड असेंबली भाषा के साथ आप जो कर सकते हैं उसके मुकाबले सबसे तेज कोड का उत्पादन नहीं करेगा। मैं कम से कम प्रतिरोध का मार्ग लेता हूं - इस तरह के छोटे दिनचर्या के लिए, मैं बस एएसएम कोड लिखता हूं और एक अच्छा विचार करता हूं कि इसे निष्पादित करने के लिए कितने चक्र होंगे। आप सी कोड के साथ परेशान हो सकते हैं और अच्छे आउटपुट उत्पन्न करने के लिए कंपाइलर प्राप्त कर सकते हैं, लेकिन आप इस तरह आउटपुट को ट्यून करने में बहुत समय बर्बाद कर सकते हैं। पिछले कुछ सालों में कंपाइलर्स (विशेष रूप से माइक्रोसॉफ्ट से) काफी लंबा सफर तय कर चुके हैं, लेकिन वे अभी भी आपके कानों के बीच कंपाइलर जितना स्मार्ट नहीं हैं क्योंकि आप अपनी विशिष्ट स्थिति पर काम कर रहे हैं और न केवल एक सामान्य मामला। कंपाइलर कुछ निर्देशों (जैसे एलडीएम) का उपयोग नहीं कर सकता है जो इसे तेज कर सकता है, और लूप को अनलॉक करने के लिए पर्याप्त स्मार्ट होने की संभावना नहीं है। यहां ऐसा करने का एक तरीका है जिसमें मैंने अपनी टिप्पणी में वर्णित 3 विचारों को शामिल किया है: लूप अनोलिंग, कैश प्रीफेच और एकाधिक लोड (एलडीएम) निर्देश का उपयोग करना। निर्देश चक्र गणना प्रति सरणी तत्व के बारे में 3 घड़ियों तक आती है, लेकिन यह स्मृति स्मृति देरी को ध्यान में रखती नहीं है।

ऑपरेशन की सिद्धांत: एआरएम का सीपीयू डिज़ाइन एक घड़ी चक्र में अधिकांश निर्देश निष्पादित करता है, लेकिन निर्देश पाइपलाइन में निष्पादित होते हैं। सी कंपाइलर्स बीच में अन्य निर्देशों को अंतःस्थापित करके पाइपलाइन देरी को खत्म करने का प्रयास करेंगे। जब मूल सी कोड की तरह एक तंग लूप के साथ प्रस्तुत किया जाता है, तो कंपाइलर में देरी से छिपने में कठिनाई होगी क्योंकि स्मृति से पढ़ने वाले मान की तुरंत तुलना की जानी चाहिए। मेरा कोड नीचे 4 रजिस्टरों के 2 सेट के बीच वैकल्पिक रूप से स्मृति की देरी को कम करने और डेटा लाने वाली पाइपलाइन को कम करने के लिए वैकल्पिक है। आम तौर पर, बड़े डेटा सेट के साथ काम करते समय और आपका कोड अधिकांश या सभी उपलब्ध रजिस्टरों का उपयोग नहीं करता है, तो आपको अधिकतम प्रदर्शन नहीं मिल रहा है।

; r0 = count, r1 = source ptr, r2 = comparison value

   stmfd sp!,{r4-r11}   ; save non-volatile registers
   mov r3,r0,LSR #3     ; loop count = total count / 8
   pld [r1,#128]
   ldmia r1!,{r4-r7}    ; pre load first set
loop_top:
   pld [r1,#128]
   ldmia r1!,{r8-r11}   ; pre load second set
   cmp r4,r2            ; search for match
   cmpne r5,r2          ; use conditional execution to avoid extra branch instructions
   cmpne r6,r2
   cmpne r7,r2
   beq found_it
   ldmia r1!,{r4-r7}    ; use 2 sets of registers to hide load delays
   cmp r8,r2
   cmpne r9,r2
   cmpne r10,r2
   cmpne r11,r2
   beq found_it
   subs r3,r3,#1        ; decrement loop count
   bne loop_top
   mov r0,#0            ; return value = false (not found)
   ldmia sp!,{r4-r11}   ; restore non-volatile registers
   bx lr                ; return
found_it:
   mov r0,#1            ; return true
   ldmia sp!,{r4-r11}
   bx lr

अद्यतन: टिप्पणियों में बहुत से संदेह हैं जो सोचते हैं कि मेरा अनुभव अचूक / बेकार है और सबूत की आवश्यकता है। मैंने ऑप्टिमाइज़ेशन -ओ 2 के साथ निम्नलिखित आउटपुट उत्पन्न करने के लिए जीसीसी 4.8 (एंड्रॉइड एनडीके 9 सी से) का उपयोग किया (सभी अनुकूलन लूप अनोलिंग सहित चालू)। मैंने ऊपर दिए गए प्रश्न में प्रस्तुत मूल सी कोड संकलित किया। यहां जीसीसी का उत्पादन किया गया है:

.L9: cmp r3, r0
     beq .L8
.L3: ldr r2, [r3, #4]!
     cmp r2, r1
     bne .L9
     mov r0, #1
.L2: add sp, sp, #1024
     bx  lr
.L8: mov r0, #0
     b .L2

जीसीसी का आउटपुट न केवल लूप को अनलॉक करता है, बल्कि एलडीआर के बाद स्टॉल पर घड़ी को भी बर्बाद करता है। यह प्रति सरणी तत्व कम से कम 8 घड़ियों की आवश्यकता है। लूप से बाहर निकलने के लिए पता लगाने के लिए पते का उपयोग करने का यह अच्छा काम करता है, लेकिन सभी जादुई चीजें संकलक करने में सक्षम हैं, इस कोड में कहीं भी नहीं पाए जाते हैं। मैंने लक्ष्य प्लेटफ़ॉर्म पर कोड नहीं चलाया है (मेरे पास एक नहीं है), लेकिन एआरएम कोड प्रदर्शन में अनुभवी कोई भी देख सकता है कि मेरा कोड तेज़ है।

अपडेट 2: मैंने माइक्रोसॉफ्ट के विजुअल स्टूडियो 2013 एसपी 2 को कोड के साथ बेहतर करने का मौका दिया। यह मेरे सरणी प्रारंभिकरण को सदिश बनाने के लिए एनईओएन निर्देशों का उपयोग करने में सक्षम था, लेकिन ओपी द्वारा लिखी गई रैखिक मूल्य खोज जीसीसी द्वारा जेनरेट की गई थी (मैंने लेबल को और अधिक पठनीय बनाने के लिए नाम बदल दिया):

loop_top:
   ldr  r3,[r1],#4  
   cmp  r3,r2  
   beq  true_exit
   subs r0,r0,#1 
   bne  loop_top
false_exit: xxx
   bx   lr
true_exit: xxx
   bx   lr

जैसा कि मैंने कहा, मेरे पास ओपी के सटीक हार्डवेयर का स्वामित्व नहीं है, लेकिन मैं 3 अलग-अलग संस्करणों के एनवीडिया टेग्रा 3 और टेग्रा 4 पर प्रदर्शन का परीक्षण करूँगा और जल्द ही परिणाम यहां पोस्ट करूंगा।

अपडेट 3: मैंने अपना कोड और माइक्रोसॉफ्ट के संकलित एआरएम कोड को टेग्रा 3 और टेग्रा 4 (भूतल आरटी, सतह आरटी 2) पर चलाया। मैंने एक लूप के 1000000 पुनरावृत्तियों को चलाया जो एक मैच खोजने में विफल रहता है ताकि सब कुछ कैश में हो और इसे मापना आसान हो।

             My Code       MS Code
Surface RT    297ns         562ns
Surface RT 2  172ns         296ns  

दोनों मामलों में मेरा कोड लगभग दोगुनी तेजी से चलता है। अधिकांश आधुनिक एआरएम सीपीयू शायद इसी तरह के परिणाम देंगे।


I'm a great fan of hashing. The problem of course is to find an efficient algorithm that is both fast and uses a minimum amount of memory (especially on an embedded processor).

If you know beforehand the values that may occur you can create a program that runs through a multitude of algorithms to find the best one - or, rather, the best parameters for your data.

I created such a program that you can read about in this post and achieved some very fast results. 16000 entries translates roughly to 2^14 or an average of 14 comparisons to find the value using a binary search. I explicitly aimed for very fast lookups - on average finding the value in <=1.5 lookups - which resulted in greater RAM requirements. I believe that with a more conservative average value (say <=3) a lot of memory could be saved. By comparison the average case for a binary search on your 256 or 1024 entries would result in an average number of comparisons of 8 and 10, respectively.

My average lookup required around 60 cycles (on a laptop with an intel i5) with a generic algorithm (utilizing one division by a variable) and 40-45 cycles with a specialized (probably utilizing a multiplication). This should translate into sub-microsecond lookup times on your MCU, depending of course on the clock frequency it executes at.

It can be real-life-tweaked further if the entry array keeps track of how many times an entry was accessed. If the entry array is sorted from most to least accessed before the indeces are computed then it'll find the most commonly occuring values with a single comparison.


वेक्टरिज़ेशन का उपयोग यहां किया जा सकता है, क्योंकि यह अक्सर memchr के कार्यान्वयन में होता है। आप निम्नलिखित एल्गोरिदम का उपयोग करते हैं:

  1. अपनी क्वेरी दोहराने का एक मुखौटा बनाएं, जो आपके ओएस की बिट गिनती (64-बिट, 32-बिट इत्यादि) के बराबर है। 64-बिट सिस्टम पर आप दो बार 32-बिट क्वेरी दोहराएंगे।

  2. सूची को एक साथ डेटा के कई टुकड़ों की सूची के रूप में प्रक्रिया करें, केवल सूची को बड़े डेटा प्रकार की सूची में डालने और मूल्यों को खींचकर। प्रत्येक खंड के लिए, इसे मुखौटा के साथ एक्सओआर करें, फिर XOR 0b0111 के साथ ... 1, फिर 1 जोड़ें, फिर 0b1000 के मुखौटा के साथ ... 0 दोहराना। यदि परिणाम 0 है, निश्चित रूप से कोई मैच नहीं है। अन्यथा, (आमतौर पर बहुत अधिक संभावना के साथ) एक मैच हो सकता है, इसलिए आम तौर पर खंड को खोजें।

उदाहरण कार्यान्वयन: https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src





arm