በ Go ውስጥ የቢትማፕ ኢንዴክሶች፡ በዱር ፍጥነት ይፈልጉ

መግቢያ

ይህንን ዘገባ በእንግሊዝኛ በ GopherCon Russia 2019 በሞስኮ እና በሩሲያኛ በኒዝሂ ኖቭጎሮድ ስብሰባ ላይ ሰጥቻለሁ። እየተነጋገርን ያለነው ስለ ቢትማፕ መረጃ ጠቋሚ ነው - ከቢ-ዛፍ ያነሰ የተለመደ ፣ ግን ብዙም አስደሳች አይደለም። ማጋራት። መቅዳት በጉባኤው ላይ በእንግሊዝኛ እና በሩሲያኛ የጽሑፍ ግልባጭ ንግግሮች ።

የቢትማፕ ኢንዴክስ እንዴት እንደሚሰራ ፣ የተሻለ በሚሆንበት ጊዜ ፣ ​​ከሌሎች ኢንዴክሶች የከፋ በሚሆንበት ጊዜ እና በምን ጉዳዮች ላይ ከእነሱ የበለጠ ፈጣን እንደሆነ እንመለከታለን ። የትኞቹ ታዋቂ ዲቢኤምኤስ ቀድሞውኑ የቢትማፕ ኢንዴክሶች እንዳላቸው እንይ; በጎ ውስጥ የራሳችንን ለመጻፍ እንሞክር። እና "ለጣፋጭነት" የራሳችንን እጅግ በጣም ፈጣን የሆነ ልዩ የውሂብ ጎታ ለመፍጠር ዝግጁ የሆኑ ቤተ-መጻሕፍትን እንጠቀማለን።

ሥራዎቼ ለእርስዎ ጠቃሚ እና አስደሳች እንዲሆኑ በእውነት ተስፋ አደርጋለሁ። ሂድ!

መግቢያ

http://bit.ly/bitmapindexes
https://github.com/mkevac/gopherconrussia2019

ሰላም ሁላችሁም! ምሽት ስድስት ሰዓት ሲሆን ሁላችንም በጣም ደክሞናል። ስለ አሰልቺ የውሂብ ጎታ መረጃ ጠቋሚ ንድፈ ሐሳብ ለመነጋገር ጥሩ ጊዜ ነው, አይደል? አይጨነቁ፣ እዚህ እና እዚያ ሁለት የመነሻ ኮድ መስመር ይኖረኛል። 🙂

ሁሉም ቀልዶች ወደ ጎን ፣ ዘገባው በመረጃ የተሞላ ነው ፣ እና ብዙ ጊዜ የለንም። ስለዚህ እንጀምር።

ዛሬ ስለሚከተሉት ነገሮች እናገራለሁ.

• ኢንዴክሶች ምንድን ናቸው;
• የቢትማፕ መረጃ ጠቋሚ ምንድን ነው;
• የት ጥቅም ላይ እንደሚውል እና ጥቅም ላይ የማይውልበት እና ለምን;
• በ Go ውስጥ ቀላል አተገባበር እና ከአቀነባባሪው ጋር ትንሽ ትግል;
• በመጠኑ ያነሰ ቀላል፣ ነገር ግን በGo assembler ውስጥ በጣም ውጤታማ አተገባበር;
• የቢትማፕ ኢንዴክሶች "ችግሮች";
• ነባር አተገባበር.

ስለዚህ ኢንዴክሶች ምንድን ናቸው?

መረጃ ጠቋሚው ከዋናው መረጃ በተጨማሪ የምንጠብቀው እና የምናዘምነው የተለየ የውሂብ መዋቅር ነው። ፍለጋውን ለማፋጠን ጥቅም ላይ ይውላል. ኢንዴክሶች ከሌለ መፈለግ ውሂቡን ሙሉ በሙሉ ማለፍን ይጠይቃል (ሙሉ ስካን የሚባል ሂደት) እና ይህ ሂደት የመስመር አልጎሪዝም ውስብስብነት አለው። ነገር ግን የውሂብ ጎታዎች ብዙውን ጊዜ ከፍተኛ መጠን ያለው ውሂብ ይይዛሉ እና የመስመር ውስብስብነት በጣም ቀርፋፋ ነው። በሐሳብ ደረጃ፣ ሎጋሪዝም ወይም ቋሚ አንድ እናገኛለን።

ይህ እጅግ በጣም የተወሳሰበ ርዕስ ነው፣ በስውር እና በንግድ ልውውጥ የተሞላ፣ ግን ለአስርተ አመታት የፈጀ የውሂብ ጎታ ልማት እና ምርምር ከተመለከትኩ በኋላ፣ የውሂብ ጎታ ኢንዴክሶችን ለመፍጠር በሰፊው ጥቅም ላይ የዋሉ ጥቂት አቀራረቦች ብቻ እንዳሉ ለመናገር ፈቃደኛ ነኝ።

የመጀመሪያው አቀራረብ የፍለጋ ቦታን በተዋረድ መቀነስ, የፍለጋ ቦታውን ወደ ትናንሽ ክፍሎች መከፋፈል ነው.

ብዙውን ጊዜ ይህንን የተለያዩ ዛፎችን በመጠቀም እንሰራለን. አንድ ምሳሌ በተለያዩ ርዕሶች የተከፋፈሉ ትናንሽ ሳጥኖችን የያዘ በመደርደሪያዎ ውስጥ ያለ ትልቅ የቁሳቁስ ሳጥን ነው። ቁሳቁስ ከፈለጉ ምናልባት "ኩኪዎች" ከሚለው ይልቅ "ቁሳቁሶች" በሚለው ሳጥን ውስጥ ይፈልጉ ይሆናል አይደል?

ሁለተኛው አቀራረብ የሚፈለገውን አካል ወይም የቡድን አባላትን ወዲያውኑ መምረጥ ነው. ይህንን በሃሽ ካርታዎች ወይም በተገላቢጦሽ ኢንዴክሶች ውስጥ እናደርጋለን. ሃሽ ካርታዎችን መጠቀም ከቀዳሚው ምሳሌ ጋር በጣም ተመሳሳይ ነው፣ ነገር ግን በሳጥኖች ሳጥን ምትክ፣ በቁም ሳጥንዎ ውስጥ የመጨረሻ እቃዎች ያሉት ትናንሽ ሳጥኖች አሉዎት።

ሦስተኛው አቀራረብ የፍለጋ ፍላጎትን ማስወገድ ነው. ይህንን የምንሰራው Bloom filters ወይም cuckoo ማጣሪያዎችን በመጠቀም ነው። የመጀመሪያዎቹ ወዲያውኑ መልስ ይሰጣሉ, ከመፈለግ ያድኑዎታል.

የመጨረሻው አቀራረብ ዘመናዊ ሃርድዌር የሚሰጠንን ኃይል በሙሉ ሙሉ በሙሉ መጠቀም ነው. በቢትማፕ ኢንዴክሶች ውስጥ የምናደርገው ይህ ነው። አዎ፣ እነሱን ስንጠቀም አንዳንድ ጊዜ ሙሉውን መረጃ ጠቋሚ ውስጥ ማለፍ አለብን፣ ነገር ግን እጅግ በጣም በብቃት እናደርገዋለን።

እንዳልኩት የውሂብ ጎታ ኢንዴክሶች ርዕስ ሰፊ እና በስምምነት የተሞላ ነው። ይህ ማለት አንዳንድ ጊዜ ብዙ አቀራረቦችን በተመሳሳይ ጊዜ መጠቀም እንችላለን፡ ፍለጋውን የበለጠ ማፋጠን ከፈለግን ወይም ሁሉንም ሊሆኑ የሚችሉ የፍለጋ አይነቶችን መሸፈን ካለብን።

ዛሬ ስለ እነዚህ በጣም ታዋቂው አቀራረብ እናገራለሁ - የቢትማፕ ኢንዴክሶች።

በዚህ ርዕስ ላይ እኔ ማን ነኝ የምናገረው?

ባዱ ላይ በቡድን መሪ ሆኜ ነው የምሰራው (ምናልባት አንተ ባምብል የተባለውን ሌላ ምርታችንን በደንብ ታውቃለህ)። በአለም ዙሪያ ከ 400 ሚሊዮን በላይ ተጠቃሚዎች እና ለእነሱ ምርጥ ተዛማጅ የሚመርጡ ብዙ ባህሪያት አሉን. ይህንን የምናደርገው የቢትማፕ ኢንዴክሶችን ጨምሮ ብጁ አገልግሎቶችን በመጠቀም ነው።

ስለዚህ የቢትማፕ መረጃ ጠቋሚ ምንድን ነው?

የቢትማፕ ኢንዴክሶች፣ ስሙ እንደሚያመለክተው፣ የፍለጋ ኢንዴክስን ለመተግበር ቢትማፕ ወይም ቢትሴቶችን ይጠቀሙ። በወፍ በረር እይታ፣ ይህ ኢንዴክስ ማንኛቸውም አካላት (እንደ ሰዎች ያሉ) እና ንብረቶቻቸውን ወይም ግቤቶችን (ዕድሜ፣ የአይን ቀለም፣ ወዘተ) የሚወክሉ አንድ ወይም ከዚያ በላይ ቢትማፖች እና ቢት ኦፕሬሽኖችን (እና፣ ወይም፣ ኖት) በመጠቀም ስልተ-ቀመር ይዟል። ) የፍለጋ ጥያቄውን ለመመለስ.

በብዙ ዝቅተኛ ካርዲናሊቲ ዓምዶች ("የዓይን ቀለም" ወይም "የጋብቻ ሁኔታን" እና እንደ "ከከተማው መሀል ያለው ርቀት" ከሚመስል ነገር ጋር አስቡ) ፍለጋዎች በሚኖሩበት ጊዜ የቢትማፕ ኢንዴክሶች በጣም ተስማሚ እና በጣም ውጤታማ እንደሆኑ ተነግሮናል። ግን በኋላ አሳይሻለሁ ለከፍተኛ ካርዲናሊቲ አምዶች እንዲሁ በጥሩ ሁኔታ እንደሚሰሩ።

በጣም ቀላሉን የቢትማፕ መረጃ ጠቋሚን እንመልከት።

እንደዚህ ያሉ ሁለትዮሽ ንብረቶች ያላቸው የሞስኮ ምግብ ቤቶች ዝርዝር እንዳለን አስብ።

• በሜትሮ አቅራቢያ;
• የግል ማቆሚያ አለ;
• በረንዳ አለ (በረንዳ አለው);
• ጠረጴዛ መያዝ ይችላሉ (የተያዙ ቦታዎችን ይቀበላል);
• ለቬጀቴሪያኖች (ቪጋን ተስማሚ);
• ውድ (ውድ)።

ለእያንዳንዱ ምግብ ቤት ከ 0 ጀምሮ ተከታታይ ቁጥር እንስጥ እና ማህደረ ትውስታን ለ 6 ቢትማፕ (ለእያንዳንዱ ባህሪ አንድ) እንመድብ። ከዚያም ሬስቶራንቱ ይህ ንብረት አለው ወይም የለውም በሚለው ላይ በመመስረት እነዚህን ቢትማፕ እንሞላለን። ሬስቶራንት 4 በረንዳ ካለው፣ በ " has a veranda" ውስጥ ያለው ቢት 4 ቢትማፕ ወደ 1 ይቀናበራል (ቬራንዳ ከሌለ፣ ከዚያም ወደ 0)።

አሁን በጣም ቀላሉ የቢትማፕ መረጃ ጠቋሚ አለን እና እንደሚከተሉት ያሉ ጥያቄዎችን ለመመለስ ልንጠቀምበት እንችላለን፡-

• "ለቬጀቴሪያን ተስማሚ የሆኑ ምግብ ቤቶችን አሳየኝ";
• "ጠረጴዛ የምትይዝበት በረንዳ ያለው ርካሽ ምግብ ቤቶችን አሳየኝ"

እንዴት? እስቲ እንመልከት። የመጀመሪያው ጥያቄ በጣም ቀላል ነው. እኛ ማድረግ ያለብን የ"ቬጀቴሪያን ወዳጃዊ" ቢትማፕን ወስደን ቁሳቸው ወደተጋለጡ ሬስቶራንቶች ዝርዝር መቀየር ነው።


ሁለተኛው ጥያቄ ትንሽ ውስብስብ ነው. ውድ ያልሆኑ ሬስቶራንቶችን ዝርዝር ለማግኘት “NOT bitmap” በሚለው “ውድ” ቢትማፕ ላይ መጠቀም አለብን፣ በመቀጠል እና “ጠረጴዛ ማስያዝ እችላለሁ” በሚለው ቢትማፕ እና ውጤቱም “ቬራንዳ አለ” ከሚለው ቢትማፕ ጋር። የተገኘው ቢትማፕ ሁሉንም መስፈርቶቻችንን የሚያሟሉ ተቋማትን ዝርዝር ይይዛል። በዚህ ምሳሌ፣ ይህ የዩኖስት ምግብ ቤት ብቻ ነው።


ብዙ ንድፈ-ሀሳብ አለ ፣ ግን አይጨነቁ ፣ ኮዱን በቅርቡ እናያለን።

የቢትማፕ ኢንዴክሶች የት ጥቅም ላይ ይውላሉ?

ጎግል የቢትማፕ ኢንዴክሶች ከሆናችሁ፣ 90% የሚሆኑት መልሶች ከOracle DB ጋር በአንድም ሆነ በሌላ መንገድ ይዛመዳሉ። ግን ሌሎች ዲቢኤምኤስዎች ምናልባት እንዲህ ዓይነቱን ጥሩ ነገር ይደግፋሉ ፣ አይደል? እውነታ አይደለም.

ዋና ዋና ተጠርጣሪዎችን ዝርዝር እንመልከት።

MySQL ገና የቢትማፕ ኢንዴክሶችን አይደግፍም፣ ነገር ግን ይህንን አማራጭ ለመጨመር የሚጠቁም ፕሮፖዛል አለ (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL የቢትማፕ ኢንዴክሶችን አይደግፍም፣ ነገር ግን የፍለጋ ውጤቶችን በበርካታ ሌሎች ኢንዴክሶች ላይ ለማጣመር ቀላል ቢትማፕ እና ቢት ኦፕሬሽኖችን ይጠቀማል።

Tarantool የቢትሴት ኢንዴክሶች አሉት እና ቀላል ፍለጋዎችን በእነሱ ላይ ይደግፋል።

ሬዲስ ቀላል የቢት ሜዳዎች አሉት (https://redis.io/commands/bitfield) እነሱን የመፈለግ ችሎታ ሳይኖር.

MongoDB ገና የቢትማፕ ኢንዴክሶችን አይደግፍም፣ ነገር ግን ይህ አማራጭ እንዲታከል የሚጠቁም ፕሮፖዛልም አለ። https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch ቢትማፕስን በውስጥ በኩል ይጠቀማል (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps)).

• ግን አዲስ ጎረቤታችን በቤታችን ታየ፡- ፒሎሳ። ይህ በGo ውስጥ የተጻፈ አዲስ ግንኙነት የሌለው የውሂብ ጎታ ነው። በውስጡ የቢትማፕ ኢንዴክሶችን ብቻ ይይዛል እና ሁሉንም ነገር በእነሱ ላይ ይመሰረታል። ትንሽ ቆይተን እንነጋገራለን.

በ Go ውስጥ ትግበራ

ግን ለምን የቢትማፕ ኢንዴክሶች በጣም አልፎ አልፎ ጥቅም ላይ ይውላሉ? ለዚህ ጥያቄ መልስ ከመስጠቱ በፊት, በ Go ውስጥ በጣም ቀላል የሆነ የቢትማፕ ኢንዴክስ እንዴት እንደሚተገበሩ ላሳይዎት እፈልጋለሁ.

ቢትማፕስ በመሠረቱ የውሂብ ቁርጥራጮች ብቻ ናቸው። በ Go ውስጥ፣ ለዚህ ​​የባይት ቁርጥራጭን እንጠቀም።

ለአንድ ሬስቶራንት ባህሪ አንድ ቢትማፕ አለን። እና እያንዳንዱ በቢትማፕ ውስጥ ያለው ቢት አንድ የተወሰነ ምግብ ቤት ይህ ንብረት እንዳለው ወይም እንደሌለው ያሳያል።

ሁለት አጋዥ ተግባራት ያስፈልጉናል. አንዱ የእኛን ቢትማፕ በዘፈቀደ ውሂብ ለመሙላት ጥቅም ላይ ይውላል። በዘፈቀደ፣ ነገር ግን ሬስቶራንቱ እያንዳንዱ ንብረት እንዲኖረው በተወሰነ ዕድል። ለምሳሌ በሞስኮ ውስጥ ጠረጴዛ መያዝ የማይችሉባቸው በጣም ጥቂት ምግብ ቤቶች እንዳሉ አምናለሁ, እና 20% የሚሆኑት ተቋማት ለቬጀቴሪያኖች ተስማሚ ናቸው ብዬ አስባለሁ.

ሁለተኛው ተግባር ቢትማፕን ወደ ምግብ ቤቶች ዝርዝር ይለውጠዋል።


ጥያቄውን ለመመለስ “የበረንዳ ቤት ያላቸው እና ቦታ ማስያዝ የሚችሉ ርካሽ ያልሆኑ ምግብ ቤቶችን አሳዩኝ”፣ ሁለት ቢት ኦፕሬሽኖች ያስፈልጉናል፡ አይደለም እና እና።

ይበልጥ ውስብስብ የሆነውን እና ኦፕሬተርን በመጠቀም ኮዳችንን በጥቂቱ ማቃለል እንችላለን።

ለእያንዳንዳቸው እነዚህ ተግባራት ተግባራት አሉን. ሁለቱም በቆርቆሮዎች ውስጥ ያልፋሉ, ከእያንዳንዱ ተጓዳኝ ንጥረ ነገሮችን ይውሰዱ, ከትንሽ ቀዶ ጥገና ጋር ያዋህዷቸው እና ውጤቱን በተፈጠረው ቁራጭ ውስጥ ያስቀምጡት.

እና አሁን የፍለጋ ጥያቄውን ለመመለስ የእኛን ቢትማፕ እና ተግባራቶች መጠቀም እንችላለን።

አፈጻጸሙ ያን ያህል ከፍ ያለ አይደለም፣ ምንም እንኳን ተግባራቶቹ በጣም ቀላል ቢሆኑም እና ተግባሩ በተጠራ ቁጥር አዲስ የውጤት ቁራጭ ባለመመለስ ብዙ ገንዘብ ቆጥበናል።

ከppprof ጋር ትንሽ መገለጫ ካደረግኩ በኋላ፣ Go compiler አንድ በጣም ቀላል ነገር ግን በጣም አስፈላጊ የሆነ ማመቻቸት እንደጎደለ አስተዋልኩ፡ ተግባርን ወደ ውስጥ ማስገባት።

እውነታው ግን የ Go compiler በቆርቆሮዎች ውስጥ የሚያልፉ ቀለበቶችን በጣም ይፈራል እና እንደዚህ ያሉ ቀለበቶችን የያዙ የመስመር ውስጥ ተግባራትን በከፊል ፈቃደኛ አይሆንም።

ግን አልፈራም እና እንደ ድሮው ጥሩ ጊዜ በሉፕ ፈንታ ጎቶን በመጠቀም አቀናባሪውን ማታለል እችላለሁ።

እና, እንደምታየው, አሁን አቀናባሪው የእኛን ተግባር በደስታ ያሰላል! በዚህ ምክንያት 2 ማይክሮ ሰከንድ ያህል መቆጠብ ችለናል። መጥፎ አይደለም!

ሁለተኛው ማነቆ የመሰብሰቢያውን ውጤት በቅርበት ከተመለከቱ ለማየት ቀላል ነው. አቀናባሪው በጣም ሞቃታማው ሉፕ ውስጥ የድንበር ፍተሻ አክሏል። እውነታው ግን Go ደህንነቱ የተጠበቀ ቋንቋ ነው, አቀናባሪው የእኔ ሶስት ክርክሮች (ሶስት ቁርጥራጮች) የተለያየ መጠን ያላቸው ናቸው ብሎ ፈራ. ከሁሉም በኋላ, ከዚያም ቋት የሚበዛበት ተብሎ የሚጠራው ክስተት በንድፈ ዕድል ይሆናል.

ሁሉም ቁርጥራጮች ተመሳሳይ መጠን ያላቸው መሆናቸውን በማሳየት አጠናቃሪውን እናረጋጋው። በተግባራችን መጀመሪያ ላይ ቀላል ቼክ በመጨመር ይህንን ማድረግ እንችላለን.

ይህንን አይቶ አቀናባሪው ቼኩን በደስታ ዘለለ እና መጨረሻ ላይ ሌላ 500 ናኖሴኮንዶች እንቆጥባለን።

ትላልቅ ስጋጃዎች

እሺ፣ ከቀላል አተገባበራችን የተወሰኑ አፈፃፀሞችን ለመጭመቅ ችለናል፣ነገር ግን ይህ ውጤት አሁን ባለው ሃርድዌር ከሚቻለው በላይ የከፋ ነው።

እኛ የምናደርገው መሰረታዊ የቢት ኦፕሬሽኖች ብቻ ነው፣ እና የእኛ ፕሮሰሰር በጣም በብቃት ያከናውናቸዋል። ግን በሚያሳዝን ሁኔታ, የእኛን ፕሮሰሰር በጣም ትንሽ በሆኑ ስራዎች "እንመግባለን". የእኛ ተግባራቶች በባይት-ባይት መሰረት ስራዎችን ያከናውናሉ. UIint8 ን በመጠቀም ከ64-ባይት ቺንኮች ጋር ለመስራት ኮዳችንን በቀላሉ ማስተካከል እንችላለን።

እንደምታየው ይህ ትንሽ ለውጥ የቡድኑን መጠን በስምንት እጥፍ በመጨመር ፕሮግራማችንን ስምንት ጊዜ አፋጥኗል። ትርፉ መስመራዊ ነው ሊባል ይችላል።

በመሰብሰቢያ ውስጥ ትግበራ

ግን ይህ መጨረሻ አይደለም. የእኛ ፕሮሰሰሮች ከ16፣ 32 እና ከ64 ባይት ክፍሎች ጋር መስራት ይችላሉ። እንደነዚህ ያሉ "ሰፊ" ኦፕሬሽኖች ነጠላ መመሪያ ብዙ ዳታ (ሲኤምዲ; አንድ መመሪያ, ብዙ መረጃ) ይባላሉ, እና ኮድን የመቀየር ሂደት እንደዚህ አይነት ስራዎችን ይጠቀማል.

እንደ አለመታደል ሆኖ የ Go compiler በቬክተሪዜሽን ላይ እጅግ በጣም ጥሩ ነው። በአሁኑ ጊዜ የ Go codeን ቬክተር ለማውጣት የሚቻለው Go assemblerን በመጠቀም እነዚህን ኦፕሬሽኖች ወስዶ በእጅ ማስቀመጥ ነው።

Go assembler እንግዳ አውሬ ነው። የመሰብሰቢያ ቋንቋ ከምትጽፉለት ኮምፒዩተር አርክቴክቸር ጋር በእጅጉ የተቆራኘ መሆኑን ታውቁ ይሆናል ነገርግን በGo ውስጥ ግን ያ አይደለም። Go assembler እንደ IRL (መካከለኛ ውክልና ቋንቋ) ወይም መካከለኛ ቋንቋ ነው፡ በተግባር ከመድረክ ነጻ ነው። ሮብ ፓይክ ጥሩ አፈጻጸም አሳይቷል። ሪፖርት አድርግ በዚህ ርዕስ ላይ ከበርካታ አመታት በፊት በጎፈር ኮን በዴንቨር።

በተጨማሪም Go ያልተለመደ የፕላን 9 ቅርጸት ይጠቀማል ይህም በአጠቃላይ ተቀባይነት ካላቸው AT&T እና Intel ፎርማቶች ይለያል።

Go assembler በእጅ መፃፍ በጣም አስደሳች እንዳልሆነ በእርግጠኝነት መናገር ይቻላል።

ግን፣ እንደ እድል ሆኖ፣ Go assemblerን እንድንጽፍ የሚረዱን ሁለት ከፍተኛ ደረጃ መሣሪያዎች አሉ፡ PeachPy እና avo። ሁለቱም መገልገያዎች Go assemblerን እንደየቅደም ተከተላቸው በ Python እና Go ከተጻፈ ከፍተኛ ደረጃ ኮድ ያመነጫሉ።

እነዚህ መገልገያዎች እንደ መመዝገቢያ ድልድል፣ ዑደቶችን መጻፍ እና በአጠቃላይ በGo ውስጥ ወደሚገኝ የመሰብሰቢያ ፕሮግራም የመግባትን ሂደት ያቃልላሉ።

አቮን እንጠቀማለን፣ስለዚህ ፕሮግራሞቻችን መደበኛ የ Go ፕሮግራሞች ይሆናሉ።

የአቮ ፕሮግራም ቀላሉ ምሳሌ ይህን ይመስላል። ዋና() ተግባር አለን ፣ በራሱ ውስጥ የ Add() ተግባርን የሚገልፅ ሲሆን ትርጉሙም ሁለት ቁጥሮችን መጨመር ነው። መለኪያዎችን በስም ለማግኘት እና ከነጻ እና ተስማሚ የፕሮሰሰር መመዝገቢያዎች አንዱን ለማግኘት የረዳት ተግባራት እዚህ አሉ። በ ADDQ ውስጥ እንደሚታየው እያንዳንዱ ፕሮሰሰር ኦፕሬሽን በአቮ ላይ ተጓዳኝ ተግባር አለው። በመጨረሻ ፣ የተገኘውን እሴት ለማከማቸት የረዳት ተግባርን እናያለን።

go geneን በመደወል ፕሮግራሙን በአቮ ላይ እናስፈጽማለን እና በዚህ ምክንያት ሁለት ፋይሎች ይፈጠራሉ፡

• በ Go assembler ውስጥ ካለው የውጤት ኮድ ጋር add.s;
• stub.go ሁለቱን አለም ለማገናኘት ከተግባር ራስጌዎች ጋር፡ ሂድ እና መሰብሰብ።

አሁን አቮ ምን እንደሚሰራ እና እንዴት እንደሚሰራ ከተመለከትን ተግባሮቻችንን እንይ። ሁለቱንም scalar እና vector (SIMD) የተግባሮቹ ስሪቶችን ተግባራዊ አድርጌያለሁ።

በመጀመሪያ ደረጃ ስካላር ስሪቶችን እንይ።

ልክ እንደ ቀደመው ምሳሌ, ነፃ እና ትክክለኛ የሆነ የአጠቃላይ ዓላማ መዝገብ እንጠይቃለን, ለክርክሮቹ ማካካሻዎችን እና መጠኖችን ማስላት አያስፈልገንም. አቮ ይህን ሁሉ ያደርግልናል.

አፈፃፀሙን ለማሻሻል እና የ Go compilerን ለማታለል መለያዎችን እና ጎቶ (ወይም መዝለሎችን) እንጠቀም ነበር፣ አሁን ግን ከመጀመሪያው እየሰራን ነው። ነጥቡ ዑደቶች ከፍተኛ ደረጃ ያላቸው ጽንሰ-ሐሳቦች ናቸው. በመሰብሰቢያ ውስጥ፣ መለያዎች እና መዝለሎች ብቻ አሉን።

የተቀረው ኮድ ቀድሞውኑ የሚታወቅ እና ሊረዳ የሚችል መሆን አለበት። ሉፕን ከስያሜዎች እና መዝለሎች ጋር እንኮርጃለን ፣ ከሁለቱ ቁርጥራጮች ትንሽ ዳታ ወስደን ከትንሽ ኦፕሬሽን ጋር (እና በዚህ ጉዳይ ላይ አይደለም) እናጣምራቸዋለን እና ውጤቱን ወደሚገኘው ቁራጭ እናስገባለን። ሁሉም።

የመጨረሻው ሰብሳቢ ኮድ ይህን ይመስላል። ማካካሻዎችን እና መጠኖችን (በአረንጓዴ የደመቁ) ማስላት ወይም ጥቅም ላይ የዋሉትን መዝገቦች መከታተል አልነበረብንም (በቀይ የደመቁ)።

የጉባዔው ቋንቋ አተገባበር አፈጻጸሙን በጎ ከነበረው የተሻለ አፈጻጸም ጋር ብናነፃፅረው ተመሳሳይ መሆኑን እናያለን። ይህ ደግሞ ይጠበቃል። ለነገሩ ምንም የተለየ ነገር አላደረግንም - Go compiler የሚያደርገውን ብቻ ነው የሰራነው።

እንደ አለመታደል ሆኖ አቀናባሪው በስብሰባ ቋንቋ የተፃፉ ተግባሮቻችንን እንዲያስገባ ማስገደድ አንችልም። የ Go compiler በአሁኑ ጊዜ እንዲህ አይነት ባህሪ የለውም፣ ምንም እንኳን ለተወሰነ ጊዜ ለመጨመር ጥያቄ ቢኖርም።

ለዚህም ነው በመሰብሰቢያ ቋንቋ ውስጥ ከትንሽ ተግባራት ምንም ጥቅም ማግኘት የማይቻልበት. ትልቅ ተግባራትን መፃፍ ወይም አዲሱን የሂሳብ/ቢት ጥቅል መጠቀም ወይም የአሰባሳቢውን ቋንቋ ማለፍ አለብን።

አሁን የእኛን ተግባራት የቬክተር ስሪቶችን እንመልከት.

ለዚህ ምሳሌ, እኔ AVX2 ን ለመጠቀም ወሰንኩ, ስለዚህ በ 32-ባይት ቁርጥራጮች ላይ የሚሰሩ ስራዎችን እንጠቀማለን. የኮዱ አወቃቀሩ ከስካላር ስሪት ጋር በጣም ተመሳሳይ ነው: መለኪያዎችን መጫን, ነፃ የጋራ መዝገብ መጠየቅ, ወዘተ.

አንድ ፈጠራ ሰፊ የቬክተር ስራዎች ልዩ ሰፊ መዝገቦችን ይጠቀማሉ. ባለ 32 ባይት ቸንክች፣ እነዚህ ከ Y ጋር ቅድመ ቅጥያ ያላቸው መዝገቦች ናቸው። ለዚህም ነው በኮዱ ውስጥ የYMM() ተግባርን የምታዩት። AVX-512ን ከ64-ቢት ቁርጥራጮች ጋር እየተጠቀምኩ ከሆነ ቅድመ ቅጥያው Z ይሆናል።

ሁለተኛው ፈጠራ ደግሞ loop unrolling የሚባል ማመቻቸት ለመጠቀም ወሰንኩ፣ ይህ ማለት ወደ loop መጀመሪያ ከመዝለልዎ በፊት ስምንት loop ስራዎችን በእጅ ማድረግ ማለት ነው። ይህ ማመቻቸት በኮዱ ውስጥ ያሉትን የቅርንጫፎችን ቁጥር ይቀንሳል, እና በነጻ መመዝገቢያዎች ብዛት የተገደበ ነው.

ደህና፣ ስለ አፈጻጸምስ? ቆንጆ ነች! ከምርጥ የ Go መፍትሄ ጋር ሲነጻጸር ሰባት ጊዜ ያህል ፍጥነት አሳክተናል። አስደናቂ ፣ ትክክል?

ነገር ግን ይህ አተገባበር እንኳን AVX-512፣ prefetching ወይም JIT (ልክ-በጊዜ ማጠናቀር) በመጠቀም ሊፋጠን ይችላል። ግን ይህ በእርግጥ ለተለየ ሪፖርት ርዕስ ነው።

ከቢትማፕ ኢንዴክሶች ጋር ችግሮች

አሁን በGo ውስጥ ያለውን የቢትማፕ ኢንዴክስ ቀላል አተገባበር እና በስብሰባ ቋንቋ የበለጠ ውጤታማ የሆነውን ከተመለከትን፣ በመጨረሻ የቢትማፕ ኢንዴክሶች ለምን እምብዛም ጥቅም ላይ እንደሚውሉ እንነጋገር።

የቆዩ ወረቀቶች ከቢትማፕ ኢንዴክሶች ጋር ሶስት ችግሮችን ይጠቅሳሉ፣ ነገር ግን እኔ እና አዲስ ወረቀቶች ከአሁን በኋላ ተዛማጅነት የሌላቸው እንደሆኑ እንከራከራለን። በእያንዳንዳቸው ወደ እነዚህ ችግሮች ጠልቀን አንገባም ነገር ግን በአጉል እይታ እንመለከታቸዋለን።

የከፍተኛ ካርዲናዊነት ችግር

ስለዚህ ፣ የቢትማፕ ኢንዴክሶች ዝቅተኛ ካርዲናዊነት ላላቸው መስኮች ብቻ ተስማሚ እንደሆኑ ተነግሮናል ፣ ማለትም ፣ ጥቂት እሴቶች ላላቸው (ለምሳሌ ፣ የጾታ ወይም የዓይን ቀለም) ፣ እና ምክንያቱ እንደዚህ ያሉ መስኮች የተለመደው ውክልና (አንድ) ነው። ቢት በዋጋ) ከፍተኛ ካርዲናሊቲ ከሆነ፣ በጣም ብዙ ቦታ ይወስዳል እና በተጨማሪም፣ እነዚህ የቢትማፕ ኢንዴክሶች ደካማ (አልፎ አልፎ) ይሞላሉ።


አንዳንድ ጊዜ የተለየ ውክልና ልንጠቀም እንችላለን፣ ለምሳሌ ቁጥሮችን ለመወከል የምንጠቀመው መደበኛ። ነገር ግን ሁሉንም ነገር የለወጠው የጨመቁ ስልተ ቀመሮች መምጣት ነበር። ባለፉት አሥርተ ዓመታት ውስጥ ሳይንቲስቶች እና ተመራማሪዎች ለቢትማፕ ከፍተኛ ቁጥር ያላቸውን የመጭመቂያ ስልተ ቀመሮችን ፈጥረዋል። ዋና ጥቅማቸው ቢትማፕን መግፋት አያስፈልግም ቢት ኦፕሬሽኖችን ለማከናወን - በተጨመቀ ቢትማፕ ላይ በቀጥታ የቢት ኦፕሬሽንን ማከናወን እንችላለን።

በቅርቡ፣ እንደ ሮሮ ቢትማፕ ያሉ ድቅል አቀራረቦች መታየት ጀምረዋል። በተመሳሳይ ጊዜ ለbitmaps ሶስት የተለያዩ ውክልናዎችን ይጠቀማሉ - ቢትማፕ ራሳቸው ፣ ድርድሮች እና ቢት ሩጫዎች የሚባሉት - እና በመካከላቸው ያለውን ሚዛን ከፍ ለማድረግ እና የማስታወስ ፍጆታን ለመቀነስ።

በጣም ተወዳጅ በሆኑ መተግበሪያዎች ውስጥ የሚያገሣ ቢትማፕ ማግኘት ይችላሉ። ለጎ ከሶስት በላይ ትግበራዎችን ጨምሮ ለተለያዩ የፕሮግራሚንግ ቋንቋዎች እጅግ በጣም ብዙ ትግበራዎች አሉ።

ከፍተኛ ካርዲናዊነትን ለመቋቋም የሚረዳን ሌላው አቀራረብ ቢኒንግ ይባላል. የሰውን ቁመት የሚወክል መስክ እንዳለህ አስብ። ቁመት ተንሳፋፊ ነጥብ ቁጥር ነው, ነገር ግን እኛ ሰዎች እንደዚያ አናስበውም. ለእኛ በ 185,2 ሴ.ሜ እና በ 185,3 ሴ.ሜ ቁመት መካከል ምንም ልዩነት የለም.

ተመሳሳይ እሴቶችን በ 1 ሴ.ሜ ውስጥ በቡድን መመደብ እንችላለን ።

እና በጣም ጥቂት ሰዎች ከ 50 ሴ.ሜ በታች እና ከ 250 ሴ.ሜ ቁመት እንደሚበልጡ ካወቅን ፣ እንግዲያውስ ማለቂያ የለሽ ካርዲናሊቲ ያለውን መስክ ወደ 200 የሚጠጉ እሴቶችን ወደ ሜዳ መለወጥ እንችላለን።

እርግጥ ነው, አስፈላጊ ከሆነ በኋላ ተጨማሪ ማጣሪያ ማድረግ እንችላለን.

ከፍተኛ የመተላለፊያ ይዘት ችግር

የቢትማፕ ኢንዴክሶች ቀጣዩ ችግር እነሱን ማዘመን በጣም ውድ ሊሆን ይችላል።

በመቶዎች የሚቆጠሩ ሌሎች መጠይቆች ውሂቡን በሚፈልጉበት ጊዜ የውሂብ ጎታዎች ውሂብን ማዘመን መቻል አለባቸው። በአንድ ጊዜ የውሂብ መዳረሻ ወይም ሌሎች የማጋሪያ ችግሮች ላይ ችግሮችን ለማስወገድ ቁልፎች ያስፈልጉናል። እና አንድ ትልቅ መቆለፊያ ባለበት, ችግር አለ - የመቆለፊያ ክርክር, ይህ መቆለፊያ ማነቆ በሚሆንበት ጊዜ.

ይህ ችግር በሻርዲንግ በመጠቀም ወይም የተሻሻሉ ኢንዴክሶችን በመጠቀም ሊፈታ ወይም ሊታለፍ ይችላል።

ሻርዲንግ ቀላል እና የታወቀ ነገር ነው. እንደማንኛውም ሌላ ውሂብ የቢትማፕ መረጃ ጠቋሚን መከፋፈል ይችላሉ። ከአንድ ትልቅ መቆለፊያ ይልቅ, ትንሽ መቆለፊያዎችን ታገኛላችሁ እና ስለዚህ የመቆለፊያ ክርክርን ያስወግዳሉ.

ችግሩን ለመፍታት ሁለተኛው መንገድ የተሻሻሉ ኢንዴክሶችን መጠቀም ነው. ለመፈለግ ወይም ለማንበብ የምትጠቀመው ኢንዴክስ አንድ ቅጂ፣ እና ለመፃፍ ወይም ለማዘመን የምትጠቀመው አንድ ቅጂ ሊኖርህ ይችላል። እና በተወሰነ ጊዜ ውስጥ አንድ ጊዜ (ለምሳሌ በ100 ms ወይም 500 ms አንድ ጊዜ) በማባዛት ትቀይራቸዋለህ። በእርግጥ ይህ አካሄድ ተግባራዊ የሚሆነው ማመልከቻዎ ትንሽ የዘገየ የፍለጋ መረጃ ጠቋሚን በሚይዝበት ጊዜ ብቻ ነው።

እነዚህ ሁለት አቀራረቦች በአንድ ጊዜ ጥቅም ላይ ሊውሉ ይችላሉ-የተቆራረጠ ስሪት መረጃ ጠቋሚ ሊኖርዎት ይችላል.

ተጨማሪ ውስብስብ መጠይቆች

የቢትማፕ ኢንዴክሶች የመጨረሻው ችግር ለተጨማሪ ውስብስብ የጥያቄ ዓይነቶች፣ እንደ ስፓን መጠይቆች ተስማሚ እንዳልሆኑ መነገሩ ነው።

በእርግጥ፣ ቢያስቡት፣ እንደ AND፣ OR፣ ወዘተ ያሉ ቢት ኦፕሬሽኖች ለጥያቄዎች በጣም ተስማሚ አይደሉም a la “በአዳር ከ200 እስከ 300 ዶላር የቤት ውስጥ ዋጋ ያላቸው ሆቴሎችን አሳየኝ።”

የዋህ እና በጣም ጥበብ የጎደለው መፍትሄ ለእያንዳንዱ የዶላር ዋጋ ውጤቱን ወስዶ ከቢትዊ ወይም ኦፕሬሽን ጋር ማጣመር ነው።

ትንሽ የተሻለው መፍትሄ መቧደንን መጠቀም ነው። ለምሳሌ, በ 50 ዶላር ቡድኖች ውስጥ. ይህ የእኛን ሂደት በ 50 ጊዜ ያፋጥነዋል.

ነገር ግን ለዚህ ዓይነቱ ጥያቄ በተለየ ሁኔታ የተፈጠረውን እይታ በመጠቀም ችግሩ በቀላሉ ይፈታል. በሳይንሳዊ ወረቀቶች ክልል-ኢንኮድ ቢትማፕስ ይባላል።

በዚህ ውክልና ውስጥ፣ ለአንዳንድ እሴት አንድ ቢት ብቻ አናዘጋጅም (ለምሳሌ 200)፣ ነገር ግን ይህን እሴት እና ሁሉንም ነገር ከፍ አድርገን እናስቀምጣለን። 200 እና ከዚያ በላይ። ለ 300: 300 እና ከዚያ በላይ. እናም ይቀጥላል.

ይህንን ውክልና በመጠቀም፣ ኢንዴክስን ሁለት ጊዜ ብቻ በማለፍ የዚህ አይነት የፍለጋ ጥያቄን መመለስ እንችላለን። በመጀመሪያ ፣ ክፍሉ ያነሰ ወይም 300 ዶላር የሚያወጣባቸውን ሆቴሎች ዝርዝር እናገኛለን ፣ እና ከዚያ የክፍሉ ዋጋ ያነሰባቸውን ወይም 199 ዶላር እናስወግዳለን። ዝግጁ።

ትገረማለህ፣ ነገር ግን የጂኦ መጠይቆች እንኳን የቢትማፕ ኢንዴክሶችን መጠቀም ይቻላል። ዘዴው መጋጠሚያዎን በጂኦሜትሪክ ምስል የሚከበብ የጂኦሜትሪክ ውክልና መጠቀም ነው። ለምሳሌ፣ S2 ከGoogle። ስዕሉ በቁጥር ሊቆጠሩ በሚችሉ ሶስት ወይም ከዚያ በላይ የተጠላለፉ መስመሮችን ለመወከል መቻል አለበት. በዚህ መንገድ የኛን ጂኦኬይን ወደ ብዙ መጠይቆች "ከክፍተቱ ጋር" (በእነዚህ ቁጥሮች በተሰየሙ መስመሮች) መለወጥ እንችላለን።

የማዞሪያ መፍትሔዎች ፡፡

ትንሽ እንደምፈልግህ ተስፋ አደርጋለሁ እና አሁን ሌላ ጠቃሚ መሳሪያ በጦር መሣሪያዎ ውስጥ አለህ። እንደዚህ አይነት ነገር ማድረግ ካስፈለገዎት የትኛውን መንገድ እንደሚመለከቱ ያውቃሉ።

ሆኖም ግን፣ ሁሉም ሰው ከባዶ የቢትማፕ ኢንዴክሶችን ለመፍጠር ጊዜ፣ ትዕግስት ወይም ሃብት የለውም። በተለይም በጣም የላቁ፣ ለምሳሌ ሲምዲ በመጠቀም።

እንደ እድል ሆኖ, እርስዎን ለማገዝ ብዙ የተዘጋጁ መፍትሄዎች አሉ.

የሚያገሣ ቢትማፕ

በመጀመሪያ፣ አስቀድሜ የተናገርኩት ያው የሚያገሣ የቢትማፕ ቤተ-መጽሐፍት አለ። የተሟላ የቢትማፕ መረጃ ጠቋሚ ለመፍጠር የሚያስፈልግዎትን ሁሉንም አስፈላጊ መያዣዎች እና ቢት ኦፕሬሽኖች ይዟል።

እንደ አለመታደል ሆኖ በአሁኑ ወቅት ከGo ትግበራዎች ውስጥ አንዳቸውም SIMD አይጠቀሙም ፣ ይህ ማለት የጎ ትግበራዎች ለምሳሌ ከሲ አፈፃፀም ያነሱ ናቸው ማለት ነው።

ፒሎሳ

ሌላው ሊረዳዎ የሚችል ምርት የፒሎሳ ዲቢኤምኤስ ነው፣ እሱም፣ በእውነቱ፣ የቢትማፕ ኢንዴክሶች ብቻ ያለው። ይህ በአንጻራዊነት አዲስ መፍትሄ ነው, ነገር ግን በከፍተኛ ፍጥነት ልብን እያሸነፈ ነው.

ፒሎሳ የሚያገሳ ቢትማፕን በውስጥ በኩል ይጠቀማል እና እነሱን ለመጠቀም ችሎታ ይሰጥዎታል፣ ከላይ የተናገርኳቸውን ነገሮች ያቃልላል እና ያብራራቸዋል፡ መቧደን፣ ክልል-ኢኮድ የተደረገ ቢትማፕ፣ የመስክ ጽንሰ-ሀሳብ፣ ወዘተ።

ቀድሞውንም የሚያውቁትን ጥያቄ ለመመለስ ፒሎሳን የመጠቀም ምሳሌን በፍጥነት እንይ።

ምሳሌው ከዚህ በፊት ካዩት ጋር በጣም ተመሳሳይ ነው። ደንበኛን ወደ ፒሎሳ አገልጋይ እንፈጥራለን ፣ ኢንዴክስ እና አስፈላጊ መስኮችን እንፈጥራለን ፣ ከዚያም መስኮቻችንን በዘፈቀደ መረጃ ከፕሮባቢሊቲዎች ጋር እንሞላለን እና በመጨረሻም የተለመደውን ጥያቄ እንፈጽማለን።

ከዚያ በኋላ፣ በ"ውድ" መስክ ላይ አይደለም የምንጠቀመው፣ ከዚያም ውጤቱን (ወይም AND it) ከ"ጣሪያ" መስክ እና ከ"የተያዙ ቦታዎች" ጋር እናገናኛለን። እና በመጨረሻ, የመጨረሻውን ውጤት እናገኛለን.

በቅርብ ጊዜ ውስጥ ይህ አዲስ ዓይነት ኢንዴክስ በዲቢኤምኤስ እንደ MySQL እና PostgreSQL - bitmap indexes እንደሚታይ ተስፋ አደርጋለሁ።

መደምደሚያ

እስካሁን ካልተኙ አመሰግናለሁ። በጊዜ ገደብ ምክንያት ብዙ ርዕሰ ጉዳዮችን ባጭሩ መንካት ነበረብኝ ነገር ግን ንግግሩ ጠቃሚ እና ምናልባትም አበረታች እንደሚሆን ተስፋ አደርጋለሁ።

የ Bitmap ኢንዴክሶች ማወቅ ጥሩ ናቸው፣ ምንም እንኳን አሁን ባያስፈልጓቸውም። በመሳሪያ ሳጥንዎ ውስጥ ሌላ መሳሪያ ይሁኑ።

ለ Go የተለያዩ የአፈጻጸም ዘዴዎችን እና የ Go compiler እስካሁን በደንብ ያልያዙትን ነገሮች ተመልክተናል። ግን ይህ ለእያንዳንዱ የ Go ፕሮግራም አውጪ ማወቅ በጣም ጠቃሚ ነው።

ልንነግርህ የፈለኩት ይህንን ብቻ ነው። አመሰግናለሁ!

ምንጭ: hab.com